View Javadoc
1   /*
2    * Copyright (C) 2011 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5    * in compliance with the License. You may obtain a copy of the License at
6    *
7    * http://www.apache.org/licenses/LICENSE-2.0
8    *
9    * Unless required by applicable law or agreed to in writing, software distributed under the
10   * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
11   * express or implied. See the License for the specific language governing permissions and
12   * limitations under the License.
13   */
14  
15  package com.google.common.collect.testing.google;
16  
17  import static com.google.common.collect.BoundType.CLOSED;
18  import static com.google.common.collect.BoundType.OPEN;
19  import static com.google.common.collect.testing.Helpers.copyToList;
20  import static com.google.common.collect.testing.features.CollectionFeature.SUPPORTS_ADD;
21  import static com.google.common.collect.testing.features.CollectionFeature.SUPPORTS_REMOVE;
22  import static com.google.common.collect.testing.features.CollectionSize.ONE;
23  import static com.google.common.collect.testing.features.CollectionSize.SEVERAL;
24  import static com.google.common.collect.testing.features.CollectionSize.ZERO;
25  
26  import com.google.common.annotations.GwtCompatible;
27  import com.google.common.collect.BoundType;
28  import com.google.common.collect.Iterators;
29  import com.google.common.collect.Multiset;
30  import com.google.common.collect.Multiset.Entry;
31  import com.google.common.collect.Multisets;
32  import com.google.common.collect.SortedMultiset;
33  import com.google.common.collect.testing.features.CollectionFeature;
34  import com.google.common.collect.testing.features.CollectionSize;
35  import java.util.ArrayList;
36  import java.util.Arrays;
37  import java.util.Collections;
38  import java.util.List;
39  import java.util.NoSuchElementException;
40  
41  /**
42   * Tester for navigation of SortedMultisets.
43   *
44   * @author Louis Wasserman
45   */
46  @GwtCompatible
47  public class MultisetNavigationTester<E> extends AbstractMultisetTester<E> {
48    private SortedMultiset<E> sortedMultiset;
49    private List<E> entries;
50    private Entry<E> a;
51    private Entry<E> b;
52    private Entry<E> c;
53  
54    /**
55     * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
56     */
57    static <T> SortedMultiset<T> cast(Multiset<T> iterable) {
58      return (SortedMultiset<T>) iterable;
59    }
60  
61    @Override
62    public void setUp() throws Exception {
63      super.setUp();
64      sortedMultiset = cast(getMultiset());
65      entries =
66          copyToList(
67              getSubjectGenerator()
68                  .getSampleElements(getSubjectGenerator().getCollectionSize().getNumElements()));
69      Collections.sort(entries, sortedMultiset.comparator());
70  
71      // some tests assume SEVERAL == 3
72      if (entries.size() >= 1) {
73        a = Multisets.immutableEntry(entries.get(0), sortedMultiset.count(entries.get(0)));
74        if (entries.size() >= 3) {
75          b = Multisets.immutableEntry(entries.get(1), sortedMultiset.count(entries.get(1)));
76          c = Multisets.immutableEntry(entries.get(2), sortedMultiset.count(entries.get(2)));
77        }
78      }
79    }
80  
81    /**
82     * Resets the contents of sortedMultiset to have entries a, c, for the navigation tests.
83     */
84    @SuppressWarnings("unchecked")
85    // Needed to stop Eclipse whining
86    private void resetWithHole() {
87      List<E> container = new ArrayList<E>();
88      container.addAll(Collections.nCopies(a.getCount(), a.getElement()));
89      container.addAll(Collections.nCopies(c.getCount(), c.getElement()));
90      super.resetContainer(getSubjectGenerator().create(container.toArray()));
91      sortedMultiset = (SortedMultiset<E>) getMultiset();
92    }
93  
94    @CollectionSize.Require(ZERO)
95    public void testEmptyMultisetFirst() {
96      assertNull(sortedMultiset.firstEntry());
97      try {
98        sortedMultiset.elementSet().first();
99        fail();
100     } catch (NoSuchElementException e) {
101     }
102   }
103 
104   @CollectionFeature.Require(SUPPORTS_REMOVE)
105   @CollectionSize.Require(ZERO)
106   public void testEmptyMultisetPollFirst() {
107     assertNull(sortedMultiset.pollFirstEntry());
108   }
109 
110   @CollectionSize.Require(ZERO)
111   public void testEmptyMultisetNearby() {
112     for (BoundType type : BoundType.values()) {
113       assertNull(sortedMultiset.headMultiset(e0(), type).lastEntry());
114       assertNull(sortedMultiset.tailMultiset(e0(), type).firstEntry());
115     }
116   }
117 
118   @CollectionSize.Require(ZERO)
119   public void testEmptyMultisetLast() {
120     assertNull(sortedMultiset.lastEntry());
121     try {
122       assertNull(sortedMultiset.elementSet().last());
123       fail();
124     } catch (NoSuchElementException e) {
125     }
126   }
127 
128   @CollectionFeature.Require(SUPPORTS_REMOVE)
129   @CollectionSize.Require(ZERO)
130   public void testEmptyMultisetPollLast() {
131     assertNull(sortedMultiset.pollLastEntry());
132   }
133 
134   @CollectionSize.Require(ONE)
135   public void testSingletonMultisetFirst() {
136     assertEquals(a, sortedMultiset.firstEntry());
137   }
138 
139   @CollectionFeature.Require(SUPPORTS_REMOVE)
140   @CollectionSize.Require(ONE)
141   public void testSingletonMultisetPollFirst() {
142     assertEquals(a, sortedMultiset.pollFirstEntry());
143     assertTrue(sortedMultiset.isEmpty());
144   }
145 
146   @CollectionSize.Require(ONE)
147   public void testSingletonMultisetNearby() {
148     assertNull(sortedMultiset.headMultiset(e0(), OPEN).lastEntry());
149     assertNull(sortedMultiset.tailMultiset(e0(), OPEN).lastEntry());
150 
151     assertEquals(a, sortedMultiset.headMultiset(e0(), CLOSED).lastEntry());
152     assertEquals(a, sortedMultiset.tailMultiset(e0(), CLOSED).firstEntry());
153   }
154 
155   @CollectionSize.Require(ONE)
156   public void testSingletonMultisetLast() {
157     assertEquals(a, sortedMultiset.lastEntry());
158   }
159 
160   @CollectionFeature.Require(SUPPORTS_REMOVE)
161   @CollectionSize.Require(ONE)
162   public void testSingletonMultisetPollLast() {
163     assertEquals(a, sortedMultiset.pollLastEntry());
164     assertTrue(sortedMultiset.isEmpty());
165   }
166 
167   @CollectionSize.Require(SEVERAL)
168   public void testFirst() {
169     assertEquals(a, sortedMultiset.firstEntry());
170   }
171 
172   @SuppressWarnings("unchecked")
173   @CollectionFeature.Require(SUPPORTS_REMOVE)
174   @CollectionSize.Require(SEVERAL)
175   public void testPollFirst() {
176     assertEquals(a, sortedMultiset.pollFirstEntry());
177     assertEquals(Arrays.asList(b, c), copyToList(sortedMultiset.entrySet()));
178   }
179 
180   @CollectionFeature.Require(absent = SUPPORTS_REMOVE)
181   public void testPollFirstUnsupported() {
182     try {
183       sortedMultiset.pollFirstEntry();
184       fail();
185     } catch (UnsupportedOperationException e) {
186     }
187   }
188 
189   @CollectionSize.Require(SEVERAL)
190   public void testLower() {
191     resetWithHole();
192     assertEquals(null, sortedMultiset.headMultiset(a.getElement(), OPEN).lastEntry());
193     assertEquals(a, sortedMultiset.headMultiset(b.getElement(), OPEN).lastEntry());
194     assertEquals(a, sortedMultiset.headMultiset(c.getElement(), OPEN).lastEntry());
195   }
196 
197   @CollectionSize.Require(SEVERAL)
198   public void testFloor() {
199     resetWithHole();
200     assertEquals(a, sortedMultiset.headMultiset(a.getElement(), CLOSED).lastEntry());
201     assertEquals(a, sortedMultiset.headMultiset(b.getElement(), CLOSED).lastEntry());
202     assertEquals(c, sortedMultiset.headMultiset(c.getElement(), CLOSED).lastEntry());
203   }
204 
205   @CollectionSize.Require(SEVERAL)
206   public void testCeiling() {
207     resetWithHole();
208 
209     assertEquals(a, sortedMultiset.tailMultiset(a.getElement(), CLOSED).firstEntry());
210     assertEquals(c, sortedMultiset.tailMultiset(b.getElement(), CLOSED).firstEntry());
211     assertEquals(c, sortedMultiset.tailMultiset(c.getElement(), CLOSED).firstEntry());
212   }
213 
214   @CollectionSize.Require(SEVERAL)
215   public void testHigher() {
216     resetWithHole();
217     assertEquals(c, sortedMultiset.tailMultiset(a.getElement(), OPEN).firstEntry());
218     assertEquals(c, sortedMultiset.tailMultiset(b.getElement(), OPEN).firstEntry());
219     assertEquals(null, sortedMultiset.tailMultiset(c.getElement(), OPEN).firstEntry());
220   }
221 
222   @CollectionSize.Require(SEVERAL)
223   public void testLast() {
224     assertEquals(c, sortedMultiset.lastEntry());
225   }
226 
227   @SuppressWarnings("unchecked")
228   @CollectionFeature.Require(SUPPORTS_REMOVE)
229   @CollectionSize.Require(SEVERAL)
230   public void testPollLast() {
231     assertEquals(c, sortedMultiset.pollLastEntry());
232     assertEquals(Arrays.asList(a, b), copyToList(sortedMultiset.entrySet()));
233   }
234 
235   @CollectionFeature.Require(absent = SUPPORTS_REMOVE)
236   @CollectionSize.Require(SEVERAL)
237   public void testPollLastUnsupported() {
238     try {
239       sortedMultiset.pollLastEntry();
240       fail();
241     } catch (UnsupportedOperationException e) {
242     }
243   }
244 
245   @CollectionSize.Require(SEVERAL)
246   public void testDescendingNavigation() {
247     List<Entry<E>> ascending = new ArrayList<>();
248     Iterators.addAll(ascending, sortedMultiset.entrySet().iterator());
249     List<Entry<E>> descending = new ArrayList<>();
250     Iterators.addAll(descending, sortedMultiset.descendingMultiset().entrySet().iterator());
251     Collections.reverse(descending);
252     assertEquals(ascending, descending);
253   }
254 
255   void expectAddFailure(SortedMultiset<E> multiset, Entry<E> entry) {
256     try {
257       multiset.add(entry.getElement(), entry.getCount());
258       fail("Expected IllegalArgumentException");
259     } catch (IllegalArgumentException expected) {
260     }
261 
262     try {
263       multiset.add(entry.getElement());
264       fail("Expected IllegalArgumentException");
265     } catch (IllegalArgumentException expected) {
266     }
267 
268     try {
269       multiset.addAll(Collections.singletonList(entry.getElement()));
270       fail("Expected IllegalArgumentException");
271     } catch (IllegalArgumentException expected) {
272     }
273   }
274 
275   void expectRemoveZero(SortedMultiset<E> multiset, Entry<E> entry) {
276     assertEquals(0, multiset.remove(entry.getElement(), entry.getCount()));
277     assertFalse(multiset.remove(entry.getElement()));
278     assertFalse(multiset.elementSet().remove(entry.getElement()));
279   }
280 
281   void expectSetCountFailure(SortedMultiset<E> multiset, Entry<E> entry) {
282     try {
283       multiset.setCount(entry.getElement(), multiset.count(entry.getElement()));
284     } catch (IllegalArgumentException acceptable) {
285     }
286     try {
287       multiset.setCount(entry.getElement(), multiset.count(entry.getElement()) + 1);
288       fail("Expected IllegalArgumentException");
289     } catch (IllegalArgumentException expected) {
290     }
291   }
292 
293   @CollectionSize.Require(ONE)
294   @CollectionFeature.Require(SUPPORTS_ADD)
295   public void testAddOutOfTailBoundsOne() {
296     expectAddFailure(sortedMultiset.tailMultiset(a.getElement(), OPEN), a);
297   }
298 
299   @CollectionSize.Require(SEVERAL)
300   @CollectionFeature.Require(SUPPORTS_ADD)
301   public void testAddOutOfTailBoundsSeveral() {
302     expectAddFailure(sortedMultiset.tailMultiset(a.getElement(), OPEN), a);
303     expectAddFailure(sortedMultiset.tailMultiset(b.getElement(), CLOSED), a);
304     expectAddFailure(sortedMultiset.tailMultiset(b.getElement(), OPEN), a);
305     expectAddFailure(sortedMultiset.tailMultiset(b.getElement(), OPEN), b);
306     expectAddFailure(sortedMultiset.tailMultiset(c.getElement(), CLOSED), a);
307     expectAddFailure(sortedMultiset.tailMultiset(c.getElement(), CLOSED), b);
308     expectAddFailure(sortedMultiset.tailMultiset(c.getElement(), OPEN), a);
309     expectAddFailure(sortedMultiset.tailMultiset(c.getElement(), OPEN), b);
310     expectAddFailure(sortedMultiset.tailMultiset(c.getElement(), OPEN), c);
311   }
312 
313   @CollectionSize.Require(ONE)
314   @CollectionFeature.Require(SUPPORTS_ADD)
315   public void testAddOutOfHeadBoundsOne() {
316     expectAddFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), a);
317   }
318 
319   @CollectionSize.Require(SEVERAL)
320   @CollectionFeature.Require(SUPPORTS_ADD)
321   public void testAddOutOfHeadBoundsSeveral() {
322     expectAddFailure(sortedMultiset.headMultiset(c.getElement(), OPEN), c);
323     expectAddFailure(sortedMultiset.headMultiset(b.getElement(), CLOSED), c);
324     expectAddFailure(sortedMultiset.headMultiset(b.getElement(), OPEN), c);
325     expectAddFailure(sortedMultiset.headMultiset(b.getElement(), OPEN), b);
326     expectAddFailure(sortedMultiset.headMultiset(a.getElement(), CLOSED), c);
327     expectAddFailure(sortedMultiset.headMultiset(a.getElement(), CLOSED), b);
328     expectAddFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), c);
329     expectAddFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), b);
330     expectAddFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), a);
331   }
332 
333   @CollectionSize.Require(ONE)
334   @CollectionFeature.Require(SUPPORTS_REMOVE)
335   public void testRemoveOutOfTailBoundsOne() {
336     expectRemoveZero(sortedMultiset.tailMultiset(a.getElement(), OPEN), a);
337   }
338 
339   @CollectionSize.Require(SEVERAL)
340   @CollectionFeature.Require(SUPPORTS_REMOVE)
341   public void testRemoveOutOfTailBoundsSeveral() {
342     expectRemoveZero(sortedMultiset.tailMultiset(a.getElement(), OPEN), a);
343     expectRemoveZero(sortedMultiset.tailMultiset(b.getElement(), CLOSED), a);
344     expectRemoveZero(sortedMultiset.tailMultiset(b.getElement(), OPEN), a);
345     expectRemoveZero(sortedMultiset.tailMultiset(b.getElement(), OPEN), b);
346     expectRemoveZero(sortedMultiset.tailMultiset(c.getElement(), CLOSED), a);
347     expectRemoveZero(sortedMultiset.tailMultiset(c.getElement(), CLOSED), b);
348     expectRemoveZero(sortedMultiset.tailMultiset(c.getElement(), OPEN), a);
349     expectRemoveZero(sortedMultiset.tailMultiset(c.getElement(), OPEN), b);
350     expectRemoveZero(sortedMultiset.tailMultiset(c.getElement(), OPEN), c);
351   }
352 
353   @CollectionSize.Require(ONE)
354   @CollectionFeature.Require(SUPPORTS_REMOVE)
355   public void testRemoveOutOfHeadBoundsOne() {
356     expectRemoveZero(sortedMultiset.headMultiset(a.getElement(), OPEN), a);
357   }
358 
359   @CollectionSize.Require(SEVERAL)
360   @CollectionFeature.Require(SUPPORTS_REMOVE)
361   public void testRemoveOutOfHeadBoundsSeveral() {
362     expectRemoveZero(sortedMultiset.headMultiset(c.getElement(), OPEN), c);
363     expectRemoveZero(sortedMultiset.headMultiset(b.getElement(), CLOSED), c);
364     expectRemoveZero(sortedMultiset.headMultiset(b.getElement(), OPEN), c);
365     expectRemoveZero(sortedMultiset.headMultiset(b.getElement(), OPEN), b);
366     expectRemoveZero(sortedMultiset.headMultiset(a.getElement(), CLOSED), c);
367     expectRemoveZero(sortedMultiset.headMultiset(a.getElement(), CLOSED), b);
368     expectRemoveZero(sortedMultiset.headMultiset(a.getElement(), OPEN), c);
369     expectRemoveZero(sortedMultiset.headMultiset(a.getElement(), OPEN), b);
370     expectRemoveZero(sortedMultiset.headMultiset(a.getElement(), OPEN), a);
371   }
372 
373   @CollectionSize.Require(ONE)
374   @CollectionFeature.Require({SUPPORTS_ADD, SUPPORTS_REMOVE})
375   public void testSetCountOutOfTailBoundsOne() {
376     expectSetCountFailure(sortedMultiset.tailMultiset(a.getElement(), OPEN), a);
377   }
378 
379   @CollectionSize.Require(SEVERAL)
380   @CollectionFeature.Require({SUPPORTS_ADD, SUPPORTS_REMOVE})
381   public void testSetCountOutOfTailBoundsSeveral() {
382     expectSetCountFailure(sortedMultiset.tailMultiset(a.getElement(), OPEN), a);
383     expectSetCountFailure(sortedMultiset.tailMultiset(b.getElement(), CLOSED), a);
384     expectSetCountFailure(sortedMultiset.tailMultiset(b.getElement(), OPEN), a);
385     expectSetCountFailure(sortedMultiset.tailMultiset(b.getElement(), OPEN), b);
386     expectSetCountFailure(sortedMultiset.tailMultiset(c.getElement(), CLOSED), a);
387     expectSetCountFailure(sortedMultiset.tailMultiset(c.getElement(), CLOSED), b);
388     expectSetCountFailure(sortedMultiset.tailMultiset(c.getElement(), OPEN), a);
389     expectSetCountFailure(sortedMultiset.tailMultiset(c.getElement(), OPEN), b);
390     expectSetCountFailure(sortedMultiset.tailMultiset(c.getElement(), OPEN), c);
391   }
392 
393   @CollectionSize.Require(ONE)
394   @CollectionFeature.Require({SUPPORTS_ADD, SUPPORTS_REMOVE})
395   public void testSetCountOutOfHeadBoundsOne() {
396     expectSetCountFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), a);
397   }
398 
399   @CollectionSize.Require(SEVERAL)
400   @CollectionFeature.Require({SUPPORTS_ADD, SUPPORTS_REMOVE})
401   public void testSetCountOutOfHeadBoundsSeveral() {
402     expectSetCountFailure(sortedMultiset.headMultiset(c.getElement(), OPEN), c);
403     expectSetCountFailure(sortedMultiset.headMultiset(b.getElement(), CLOSED), c);
404     expectSetCountFailure(sortedMultiset.headMultiset(b.getElement(), OPEN), c);
405     expectSetCountFailure(sortedMultiset.headMultiset(b.getElement(), OPEN), b);
406     expectSetCountFailure(sortedMultiset.headMultiset(a.getElement(), CLOSED), c);
407     expectSetCountFailure(sortedMultiset.headMultiset(a.getElement(), CLOSED), b);
408     expectSetCountFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), c);
409     expectSetCountFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), b);
410     expectSetCountFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), a);
411   }
412 
413   @CollectionSize.Require(SEVERAL)
414   @CollectionFeature.Require(SUPPORTS_ADD)
415   public void testAddWithConflictingBounds() {
416     testEmptyRangeSubMultisetSupportingAdd(
417         sortedMultiset.subMultiset(a.getElement(), CLOSED, a.getElement(), OPEN));
418     testEmptyRangeSubMultisetSupportingAdd(
419         sortedMultiset.subMultiset(a.getElement(), OPEN, a.getElement(), OPEN));
420     testEmptyRangeSubMultisetSupportingAdd(
421         sortedMultiset.subMultiset(a.getElement(), OPEN, a.getElement(), CLOSED));
422     testEmptyRangeSubMultisetSupportingAdd(
423         sortedMultiset.subMultiset(b.getElement(), CLOSED, a.getElement(), CLOSED));
424     testEmptyRangeSubMultisetSupportingAdd(
425         sortedMultiset.subMultiset(b.getElement(), CLOSED, a.getElement(), OPEN));
426     testEmptyRangeSubMultisetSupportingAdd(
427         sortedMultiset.subMultiset(b.getElement(), OPEN, a.getElement(), OPEN));
428   }
429 
430   @CollectionSize.Require(SEVERAL)
431   @CollectionFeature.Require(SUPPORTS_ADD)
432   public void testConflictingBounds() {
433     testEmptyRangeSubMultiset(
434         sortedMultiset.subMultiset(a.getElement(), CLOSED, a.getElement(), OPEN));
435     testEmptyRangeSubMultiset(
436         sortedMultiset.subMultiset(a.getElement(), OPEN, a.getElement(), OPEN));
437     testEmptyRangeSubMultiset(
438         sortedMultiset.subMultiset(a.getElement(), OPEN, a.getElement(), CLOSED));
439     testEmptyRangeSubMultiset(
440         sortedMultiset.subMultiset(b.getElement(), CLOSED, a.getElement(), CLOSED));
441     testEmptyRangeSubMultiset(
442         sortedMultiset.subMultiset(b.getElement(), CLOSED, a.getElement(), OPEN));
443     testEmptyRangeSubMultiset(
444         sortedMultiset.subMultiset(b.getElement(), OPEN, a.getElement(), OPEN));
445   }
446 
447   public void testEmptyRangeSubMultiset(SortedMultiset<E> multiset) {
448     assertTrue(multiset.isEmpty());
449     assertEquals(0, multiset.size());
450     assertEquals(0, multiset.toArray().length);
451     assertTrue(multiset.entrySet().isEmpty());
452     assertFalse(multiset.iterator().hasNext());
453     assertEquals(0, multiset.entrySet().size());
454     assertEquals(0, multiset.entrySet().toArray().length);
455     assertFalse(multiset.entrySet().iterator().hasNext());
456   }
457 
458   @SuppressWarnings("unchecked")
459   public void testEmptyRangeSubMultisetSupportingAdd(SortedMultiset<E> multiset) {
460     for (Entry<E> entry : Arrays.asList(a, b, c)) {
461       expectAddFailure(multiset, entry);
462     }
463   }
464 
465   private static int totalSize(Iterable<? extends Entry<?>> entries) {
466     int sum = 0;
467     for (Entry<?> entry : entries) {
468       sum += entry.getCount();
469     }
470     return sum;
471   }
472 
473   private enum SubMultisetSpec {
474     TAIL_CLOSED {
475       @Override
476       <E> List<Entry<E>> expectedEntries(int targetEntry, List<Entry<E>> entries) {
477         return entries.subList(targetEntry, entries.size());
478       }
479 
480       @Override
481       <E> SortedMultiset<E> subMultiset(
482           SortedMultiset<E> multiset, List<Entry<E>> entries, int targetEntry) {
483         return multiset.tailMultiset(entries.get(targetEntry).getElement(), CLOSED);
484       }
485     },
486     TAIL_OPEN {
487       @Override
488       <E> List<Entry<E>> expectedEntries(int targetEntry, List<Entry<E>> entries) {
489         return entries.subList(targetEntry + 1, entries.size());
490       }
491 
492       @Override
493       <E> SortedMultiset<E> subMultiset(
494           SortedMultiset<E> multiset, List<Entry<E>> entries, int targetEntry) {
495         return multiset.tailMultiset(entries.get(targetEntry).getElement(), OPEN);
496       }
497     },
498     HEAD_CLOSED {
499       @Override
500       <E> List<Entry<E>> expectedEntries(int targetEntry, List<Entry<E>> entries) {
501         return entries.subList(0, targetEntry + 1);
502       }
503 
504       @Override
505       <E> SortedMultiset<E> subMultiset(
506           SortedMultiset<E> multiset, List<Entry<E>> entries, int targetEntry) {
507         return multiset.headMultiset(entries.get(targetEntry).getElement(), CLOSED);
508       }
509     },
510     HEAD_OPEN {
511       @Override
512       <E> List<Entry<E>> expectedEntries(int targetEntry, List<Entry<E>> entries) {
513         return entries.subList(0, targetEntry);
514       }
515 
516       @Override
517       <E> SortedMultiset<E> subMultiset(
518           SortedMultiset<E> multiset, List<Entry<E>> entries, int targetEntry) {
519         return multiset.headMultiset(entries.get(targetEntry).getElement(), OPEN);
520       }
521     };
522 
523     abstract <E> List<Entry<E>> expectedEntries(int targetEntry, List<Entry<E>> entries);
524 
525     abstract <E> SortedMultiset<E> subMultiset(
526         SortedMultiset<E> multiset, List<Entry<E>> entries, int targetEntry);
527   }
528 
529   private void testSubMultisetEntrySet(SubMultisetSpec spec) {
530     List<Entry<E>> entries = copyToList(sortedMultiset.entrySet());
531     for (int i = 0; i < entries.size(); i++) {
532       List<Entry<E>> expected = spec.expectedEntries(i, entries);
533       SortedMultiset<E> subMultiset = spec.subMultiset(sortedMultiset, entries, i);
534       assertEquals(expected, copyToList(subMultiset.entrySet()));
535     }
536   }
537 
538   private void testSubMultisetSize(SubMultisetSpec spec) {
539     List<Entry<E>> entries = copyToList(sortedMultiset.entrySet());
540     for (int i = 0; i < entries.size(); i++) {
541       List<Entry<E>> expected = spec.expectedEntries(i, entries);
542       SortedMultiset<E> subMultiset = spec.subMultiset(sortedMultiset, entries, i);
543       assertEquals(totalSize(expected), subMultiset.size());
544     }
545   }
546 
547   private void testSubMultisetDistinctElements(SubMultisetSpec spec) {
548     List<Entry<E>> entries = copyToList(sortedMultiset.entrySet());
549     for (int i = 0; i < entries.size(); i++) {
550       List<Entry<E>> expected = spec.expectedEntries(i, entries);
551       SortedMultiset<E> subMultiset = spec.subMultiset(sortedMultiset, entries, i);
552       assertEquals(expected.size(), subMultiset.entrySet().size());
553       assertEquals(expected.size(), subMultiset.elementSet().size());
554     }
555   }
556 
557   public void testTailClosedEntrySet() {
558     testSubMultisetEntrySet(SubMultisetSpec.TAIL_CLOSED);
559   }
560 
561   public void testTailClosedSize() {
562     testSubMultisetSize(SubMultisetSpec.TAIL_CLOSED);
563   }
564 
565   public void testTailClosedDistinctElements() {
566     testSubMultisetDistinctElements(SubMultisetSpec.TAIL_CLOSED);
567   }
568 
569   public void testTailOpenEntrySet() {
570     testSubMultisetEntrySet(SubMultisetSpec.TAIL_OPEN);
571   }
572 
573   public void testTailOpenSize() {
574     testSubMultisetSize(SubMultisetSpec.TAIL_OPEN);
575   }
576 
577   public void testTailOpenDistinctElements() {
578     testSubMultisetDistinctElements(SubMultisetSpec.TAIL_OPEN);
579   }
580 
581   public void testHeadClosedEntrySet() {
582     testSubMultisetEntrySet(SubMultisetSpec.HEAD_CLOSED);
583   }
584 
585   public void testHeadClosedSize() {
586     testSubMultisetSize(SubMultisetSpec.HEAD_CLOSED);
587   }
588 
589   public void testHeadClosedDistinctElements() {
590     testSubMultisetDistinctElements(SubMultisetSpec.HEAD_CLOSED);
591   }
592 
593   public void testHeadOpenEntrySet() {
594     testSubMultisetEntrySet(SubMultisetSpec.HEAD_OPEN);
595   }
596 
597   public void testHeadOpenSize() {
598     testSubMultisetSize(SubMultisetSpec.HEAD_OPEN);
599   }
600 
601   public void testHeadOpenDistinctElements() {
602     testSubMultisetDistinctElements(SubMultisetSpec.HEAD_OPEN);
603   }
604 
605   @CollectionSize.Require(SEVERAL)
606   @CollectionFeature.Require(SUPPORTS_REMOVE)
607   public void testClearTailOpen() {
608     List<Entry<E>> expected =
609         copyToList(sortedMultiset.headMultiset(b.getElement(), CLOSED).entrySet());
610     sortedMultiset.tailMultiset(b.getElement(), OPEN).clear();
611     assertEquals(expected, copyToList(sortedMultiset.entrySet()));
612   }
613 
614   @CollectionSize.Require(SEVERAL)
615   @CollectionFeature.Require(SUPPORTS_REMOVE)
616   public void testClearTailOpenEntrySet() {
617     List<Entry<E>> expected =
618         copyToList(sortedMultiset.headMultiset(b.getElement(), CLOSED).entrySet());
619     sortedMultiset.tailMultiset(b.getElement(), OPEN).entrySet().clear();
620     assertEquals(expected, copyToList(sortedMultiset.entrySet()));
621   }
622 
623   @CollectionSize.Require(SEVERAL)
624   @CollectionFeature.Require(SUPPORTS_REMOVE)
625   public void testClearTailClosed() {
626     List<Entry<E>> expected =
627         copyToList(sortedMultiset.headMultiset(b.getElement(), OPEN).entrySet());
628     sortedMultiset.tailMultiset(b.getElement(), CLOSED).clear();
629     assertEquals(expected, copyToList(sortedMultiset.entrySet()));
630   }
631 
632   @CollectionSize.Require(SEVERAL)
633   @CollectionFeature.Require(SUPPORTS_REMOVE)
634   public void testClearTailClosedEntrySet() {
635     List<Entry<E>> expected =
636         copyToList(sortedMultiset.headMultiset(b.getElement(), OPEN).entrySet());
637     sortedMultiset.tailMultiset(b.getElement(), CLOSED).entrySet().clear();
638     assertEquals(expected, copyToList(sortedMultiset.entrySet()));
639   }
640 
641   @CollectionSize.Require(SEVERAL)
642   @CollectionFeature.Require(SUPPORTS_REMOVE)
643   public void testClearHeadOpen() {
644     List<Entry<E>> expected =
645         copyToList(sortedMultiset.tailMultiset(b.getElement(), CLOSED).entrySet());
646     sortedMultiset.headMultiset(b.getElement(), OPEN).clear();
647     assertEquals(expected, copyToList(sortedMultiset.entrySet()));
648   }
649 
650   @CollectionSize.Require(SEVERAL)
651   @CollectionFeature.Require(SUPPORTS_REMOVE)
652   public void testClearHeadOpenEntrySet() {
653     List<Entry<E>> expected =
654         copyToList(sortedMultiset.tailMultiset(b.getElement(), CLOSED).entrySet());
655     sortedMultiset.headMultiset(b.getElement(), OPEN).entrySet().clear();
656     assertEquals(expected, copyToList(sortedMultiset.entrySet()));
657   }
658 
659   @CollectionSize.Require(SEVERAL)
660   @CollectionFeature.Require(SUPPORTS_REMOVE)
661   public void testClearHeadClosed() {
662     List<Entry<E>> expected =
663         copyToList(sortedMultiset.tailMultiset(b.getElement(), OPEN).entrySet());
664     sortedMultiset.headMultiset(b.getElement(), CLOSED).clear();
665     assertEquals(expected, copyToList(sortedMultiset.entrySet()));
666   }
667 
668   @CollectionSize.Require(SEVERAL)
669   @CollectionFeature.Require(SUPPORTS_REMOVE)
670   public void testClearHeadClosedEntrySet() {
671     List<Entry<E>> expected =
672         copyToList(sortedMultiset.tailMultiset(b.getElement(), OPEN).entrySet());
673     sortedMultiset.headMultiset(b.getElement(), CLOSED).entrySet().clear();
674     assertEquals(expected, copyToList(sortedMultiset.entrySet()));
675   }
676 }