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