001/*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the
010 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
011 * express or implied. See the License for the specific language governing permissions and
012 * limitations under the License.
013 */
014
015package com.google.common.collect.testing.google;
016
017import static com.google.common.collect.BoundType.CLOSED;
018import static com.google.common.collect.BoundType.OPEN;
019import static com.google.common.collect.testing.Helpers.copyToList;
020import static com.google.common.collect.testing.features.CollectionFeature.SUPPORTS_ADD;
021import static com.google.common.collect.testing.features.CollectionFeature.SUPPORTS_REMOVE;
022import static com.google.common.collect.testing.features.CollectionSize.ONE;
023import static com.google.common.collect.testing.features.CollectionSize.SEVERAL;
024import static com.google.common.collect.testing.features.CollectionSize.ZERO;
025import static com.google.common.collect.testing.google.ReflectionFreeAssertThrows.assertThrows;
026import static java.util.Arrays.asList;
027import static java.util.Collections.nCopies;
028import static java.util.Collections.singletonList;
029import static java.util.Collections.sort;
030
031import com.google.common.annotations.GwtCompatible;
032import com.google.common.collect.BoundType;
033import com.google.common.collect.Iterators;
034import com.google.common.collect.Multiset.Entry;
035import com.google.common.collect.Multisets;
036import com.google.common.collect.SortedMultiset;
037import com.google.common.collect.testing.features.CollectionFeature;
038import com.google.common.collect.testing.features.CollectionSize;
039import java.util.ArrayList;
040import java.util.Collections;
041import java.util.List;
042import java.util.NoSuchElementException;
043import org.junit.Ignore;
044
045/**
046 * Tester for navigation of SortedMultisets.
047 *
048 * @author Louis Wasserman
049 */
050@GwtCompatible
051@Ignore("test runners must not instantiate and run this directly, only via suites we build")
052// @Ignore affects the Android test runner, which respects JUnit 4 annotations on JUnit 3 tests.
053@SuppressWarnings("JUnit4ClassUsedInJUnit3")
054public class MultisetNavigationTester<E> extends AbstractMultisetTester<E> {
055  private SortedMultiset<E> sortedMultiset;
056  private List<E> entries;
057  private Entry<E> a;
058  private Entry<E> b;
059  private Entry<E> c;
060
061  @Override
062  public void setUp() throws Exception {
063    super.setUp();
064    sortedMultiset = (SortedMultiset<E>) getMultiset();
065    entries =
066        copyToList(
067            getSubjectGenerator()
068                .getSampleElements(getSubjectGenerator().getCollectionSize().getNumElements()));
069    sort(entries, sortedMultiset.comparator());
070
071    // some tests assume SEVERAL == 3
072    if (entries.size() >= 1) {
073      a = Multisets.immutableEntry(entries.get(0), sortedMultiset.count(entries.get(0)));
074      if (entries.size() >= 3) {
075        b = Multisets.immutableEntry(entries.get(1), sortedMultiset.count(entries.get(1)));
076        c = Multisets.immutableEntry(entries.get(2), sortedMultiset.count(entries.get(2)));
077      }
078    }
079  }
080
081  /** Resets the contents of sortedMultiset to have entries a, c, for the navigation tests. */
082  // Needed to stop Eclipse whining
083  private void resetWithHole() {
084    List<E> container = new ArrayList<>();
085    container.addAll(nCopies(a.getCount(), a.getElement()));
086    container.addAll(nCopies(c.getCount(), c.getElement()));
087    super.resetContainer(getSubjectGenerator().create(container.toArray()));
088    sortedMultiset = (SortedMultiset<E>) getMultiset();
089  }
090
091  @CollectionSize.Require(ZERO)
092  public void testEmptyMultisetFirst() {
093    assertNull(sortedMultiset.firstEntry());
094    assertThrows(NoSuchElementException.class, () -> sortedMultiset.elementSet().first());
095  }
096
097  @CollectionFeature.Require(SUPPORTS_REMOVE)
098  @CollectionSize.Require(ZERO)
099  public void testEmptyMultisetPollFirst() {
100    assertNull(sortedMultiset.pollFirstEntry());
101  }
102
103  @CollectionSize.Require(ZERO)
104  public void testEmptyMultisetNearby() {
105    for (BoundType type : BoundType.values()) {
106      assertNull(sortedMultiset.headMultiset(e0(), type).lastEntry());
107      assertNull(sortedMultiset.tailMultiset(e0(), type).firstEntry());
108    }
109  }
110
111  @CollectionSize.Require(ZERO)
112  public void testEmptyMultisetLast() {
113    assertNull(sortedMultiset.lastEntry());
114    assertThrows(
115        NoSuchElementException.class, () -> assertNull(sortedMultiset.elementSet().last()));
116  }
117
118  @CollectionFeature.Require(SUPPORTS_REMOVE)
119  @CollectionSize.Require(ZERO)
120  public void testEmptyMultisetPollLast() {
121    assertNull(sortedMultiset.pollLastEntry());
122  }
123
124  @CollectionSize.Require(ONE)
125  public void testSingletonMultisetFirst() {
126    assertEquals(a, sortedMultiset.firstEntry());
127  }
128
129  @CollectionFeature.Require(SUPPORTS_REMOVE)
130  @CollectionSize.Require(ONE)
131  public void testSingletonMultisetPollFirst() {
132    assertEquals(a, sortedMultiset.pollFirstEntry());
133    assertTrue(sortedMultiset.isEmpty());
134  }
135
136  @CollectionSize.Require(ONE)
137  public void testSingletonMultisetNearby() {
138    assertNull(sortedMultiset.headMultiset(e0(), OPEN).lastEntry());
139    assertNull(sortedMultiset.tailMultiset(e0(), OPEN).lastEntry());
140
141    assertEquals(a, sortedMultiset.headMultiset(e0(), CLOSED).lastEntry());
142    assertEquals(a, sortedMultiset.tailMultiset(e0(), CLOSED).firstEntry());
143  }
144
145  @CollectionSize.Require(ONE)
146  public void testSingletonMultisetLast() {
147    assertEquals(a, sortedMultiset.lastEntry());
148  }
149
150  @CollectionFeature.Require(SUPPORTS_REMOVE)
151  @CollectionSize.Require(ONE)
152  public void testSingletonMultisetPollLast() {
153    assertEquals(a, sortedMultiset.pollLastEntry());
154    assertTrue(sortedMultiset.isEmpty());
155  }
156
157  @CollectionSize.Require(SEVERAL)
158  public void testFirst() {
159    assertEquals(a, sortedMultiset.firstEntry());
160  }
161
162  @CollectionFeature.Require(SUPPORTS_REMOVE)
163  @CollectionSize.Require(SEVERAL)
164  public void testPollFirst() {
165    assertEquals(a, sortedMultiset.pollFirstEntry());
166    assertEquals(asList(b, c), copyToList(sortedMultiset.entrySet()));
167  }
168
169  @CollectionFeature.Require(absent = SUPPORTS_REMOVE)
170  public void testPollFirstUnsupported() {
171    assertThrows(UnsupportedOperationException.class, () -> sortedMultiset.pollFirstEntry());
172  }
173
174  @CollectionSize.Require(SEVERAL)
175  public void testLower() {
176    resetWithHole();
177    assertEquals(null, sortedMultiset.headMultiset(a.getElement(), OPEN).lastEntry());
178    assertEquals(a, sortedMultiset.headMultiset(b.getElement(), OPEN).lastEntry());
179    assertEquals(a, sortedMultiset.headMultiset(c.getElement(), OPEN).lastEntry());
180  }
181
182  @CollectionSize.Require(SEVERAL)
183  public void testFloor() {
184    resetWithHole();
185    assertEquals(a, sortedMultiset.headMultiset(a.getElement(), CLOSED).lastEntry());
186    assertEquals(a, sortedMultiset.headMultiset(b.getElement(), CLOSED).lastEntry());
187    assertEquals(c, sortedMultiset.headMultiset(c.getElement(), CLOSED).lastEntry());
188  }
189
190  @CollectionSize.Require(SEVERAL)
191  public void testCeiling() {
192    resetWithHole();
193
194    assertEquals(a, sortedMultiset.tailMultiset(a.getElement(), CLOSED).firstEntry());
195    assertEquals(c, sortedMultiset.tailMultiset(b.getElement(), CLOSED).firstEntry());
196    assertEquals(c, sortedMultiset.tailMultiset(c.getElement(), CLOSED).firstEntry());
197  }
198
199  @CollectionSize.Require(SEVERAL)
200  public void testHigher() {
201    resetWithHole();
202    assertEquals(c, sortedMultiset.tailMultiset(a.getElement(), OPEN).firstEntry());
203    assertEquals(c, sortedMultiset.tailMultiset(b.getElement(), OPEN).firstEntry());
204    assertEquals(null, sortedMultiset.tailMultiset(c.getElement(), OPEN).firstEntry());
205  }
206
207  @CollectionSize.Require(SEVERAL)
208  public void testLast() {
209    assertEquals(c, sortedMultiset.lastEntry());
210  }
211
212  @CollectionFeature.Require(SUPPORTS_REMOVE)
213  @CollectionSize.Require(SEVERAL)
214  public void testPollLast() {
215    assertEquals(c, sortedMultiset.pollLastEntry());
216    assertEquals(asList(a, b), copyToList(sortedMultiset.entrySet()));
217  }
218
219  @CollectionFeature.Require(absent = SUPPORTS_REMOVE)
220  @CollectionSize.Require(SEVERAL)
221  public void testPollLastUnsupported() {
222    assertThrows(UnsupportedOperationException.class, () -> sortedMultiset.pollLastEntry());
223  }
224
225  @CollectionSize.Require(SEVERAL)
226  public void testDescendingNavigation() {
227    List<Entry<E>> ascending = new ArrayList<>();
228    Iterators.addAll(ascending, sortedMultiset.entrySet().iterator());
229    List<Entry<E>> descending = new ArrayList<>();
230    Iterators.addAll(descending, sortedMultiset.descendingMultiset().entrySet().iterator());
231    Collections.reverse(descending);
232    assertEquals(ascending, descending);
233  }
234
235  void expectAddFailure(SortedMultiset<E> multiset, Entry<E> entry) {
236    try {
237      multiset.add(entry.getElement(), entry.getCount());
238      fail("Expected IllegalArgumentException");
239    } catch (IllegalArgumentException expected) {
240    }
241
242    try {
243      multiset.add(entry.getElement());
244      fail("Expected IllegalArgumentException");
245    } catch (IllegalArgumentException expected) {
246    }
247
248    try {
249      multiset.addAll(singletonList(entry.getElement()));
250      fail("Expected IllegalArgumentException");
251    } catch (IllegalArgumentException expected) {
252    }
253  }
254
255  void expectRemoveZero(SortedMultiset<E> multiset, Entry<E> entry) {
256    assertEquals(0, multiset.remove(entry.getElement(), entry.getCount()));
257    assertFalse(multiset.remove(entry.getElement()));
258    assertFalse(multiset.elementSet().remove(entry.getElement()));
259  }
260
261  void expectSetCountFailure(SortedMultiset<E> multiset, Entry<E> entry) {
262    try {
263      multiset.setCount(entry.getElement(), multiset.count(entry.getElement()));
264    } catch (IllegalArgumentException acceptable) {
265    }
266    try {
267      multiset.setCount(entry.getElement(), multiset.count(entry.getElement()) + 1);
268      fail("Expected IllegalArgumentException");
269    } catch (IllegalArgumentException expected) {
270    }
271  }
272
273  @CollectionSize.Require(ONE)
274  @CollectionFeature.Require(SUPPORTS_ADD)
275  public void testAddOutOfTailBoundsOne() {
276    expectAddFailure(sortedMultiset.tailMultiset(a.getElement(), OPEN), a);
277  }
278
279  @CollectionSize.Require(SEVERAL)
280  @CollectionFeature.Require(SUPPORTS_ADD)
281  public void testAddOutOfTailBoundsSeveral() {
282    expectAddFailure(sortedMultiset.tailMultiset(a.getElement(), OPEN), a);
283    expectAddFailure(sortedMultiset.tailMultiset(b.getElement(), CLOSED), a);
284    expectAddFailure(sortedMultiset.tailMultiset(b.getElement(), OPEN), a);
285    expectAddFailure(sortedMultiset.tailMultiset(b.getElement(), OPEN), b);
286    expectAddFailure(sortedMultiset.tailMultiset(c.getElement(), CLOSED), a);
287    expectAddFailure(sortedMultiset.tailMultiset(c.getElement(), CLOSED), b);
288    expectAddFailure(sortedMultiset.tailMultiset(c.getElement(), OPEN), a);
289    expectAddFailure(sortedMultiset.tailMultiset(c.getElement(), OPEN), b);
290    expectAddFailure(sortedMultiset.tailMultiset(c.getElement(), OPEN), c);
291  }
292
293  @CollectionSize.Require(ONE)
294  @CollectionFeature.Require(SUPPORTS_ADD)
295  public void testAddOutOfHeadBoundsOne() {
296    expectAddFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), a);
297  }
298
299  @CollectionSize.Require(SEVERAL)
300  @CollectionFeature.Require(SUPPORTS_ADD)
301  public void testAddOutOfHeadBoundsSeveral() {
302    expectAddFailure(sortedMultiset.headMultiset(c.getElement(), OPEN), c);
303    expectAddFailure(sortedMultiset.headMultiset(b.getElement(), CLOSED), c);
304    expectAddFailure(sortedMultiset.headMultiset(b.getElement(), OPEN), c);
305    expectAddFailure(sortedMultiset.headMultiset(b.getElement(), OPEN), b);
306    expectAddFailure(sortedMultiset.headMultiset(a.getElement(), CLOSED), c);
307    expectAddFailure(sortedMultiset.headMultiset(a.getElement(), CLOSED), b);
308    expectAddFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), c);
309    expectAddFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), b);
310    expectAddFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), a);
311  }
312
313  @CollectionSize.Require(ONE)
314  @CollectionFeature.Require(SUPPORTS_REMOVE)
315  public void testRemoveOutOfTailBoundsOne() {
316    expectRemoveZero(sortedMultiset.tailMultiset(a.getElement(), OPEN), a);
317  }
318
319  @CollectionSize.Require(SEVERAL)
320  @CollectionFeature.Require(SUPPORTS_REMOVE)
321  public void testRemoveOutOfTailBoundsSeveral() {
322    expectRemoveZero(sortedMultiset.tailMultiset(a.getElement(), OPEN), a);
323    expectRemoveZero(sortedMultiset.tailMultiset(b.getElement(), CLOSED), a);
324    expectRemoveZero(sortedMultiset.tailMultiset(b.getElement(), OPEN), a);
325    expectRemoveZero(sortedMultiset.tailMultiset(b.getElement(), OPEN), b);
326    expectRemoveZero(sortedMultiset.tailMultiset(c.getElement(), CLOSED), a);
327    expectRemoveZero(sortedMultiset.tailMultiset(c.getElement(), CLOSED), b);
328    expectRemoveZero(sortedMultiset.tailMultiset(c.getElement(), OPEN), a);
329    expectRemoveZero(sortedMultiset.tailMultiset(c.getElement(), OPEN), b);
330    expectRemoveZero(sortedMultiset.tailMultiset(c.getElement(), OPEN), c);
331  }
332
333  @CollectionSize.Require(ONE)
334  @CollectionFeature.Require(SUPPORTS_REMOVE)
335  public void testRemoveOutOfHeadBoundsOne() {
336    expectRemoveZero(sortedMultiset.headMultiset(a.getElement(), OPEN), a);
337  }
338
339  @CollectionSize.Require(SEVERAL)
340  @CollectionFeature.Require(SUPPORTS_REMOVE)
341  public void testRemoveOutOfHeadBoundsSeveral() {
342    expectRemoveZero(sortedMultiset.headMultiset(c.getElement(), OPEN), c);
343    expectRemoveZero(sortedMultiset.headMultiset(b.getElement(), CLOSED), c);
344    expectRemoveZero(sortedMultiset.headMultiset(b.getElement(), OPEN), c);
345    expectRemoveZero(sortedMultiset.headMultiset(b.getElement(), OPEN), b);
346    expectRemoveZero(sortedMultiset.headMultiset(a.getElement(), CLOSED), c);
347    expectRemoveZero(sortedMultiset.headMultiset(a.getElement(), CLOSED), b);
348    expectRemoveZero(sortedMultiset.headMultiset(a.getElement(), OPEN), c);
349    expectRemoveZero(sortedMultiset.headMultiset(a.getElement(), OPEN), b);
350    expectRemoveZero(sortedMultiset.headMultiset(a.getElement(), OPEN), a);
351  }
352
353  @CollectionSize.Require(ONE)
354  @CollectionFeature.Require({SUPPORTS_ADD, SUPPORTS_REMOVE})
355  public void testSetCountOutOfTailBoundsOne() {
356    expectSetCountFailure(sortedMultiset.tailMultiset(a.getElement(), OPEN), a);
357  }
358
359  @CollectionSize.Require(SEVERAL)
360  @CollectionFeature.Require({SUPPORTS_ADD, SUPPORTS_REMOVE})
361  public void testSetCountOutOfTailBoundsSeveral() {
362    expectSetCountFailure(sortedMultiset.tailMultiset(a.getElement(), OPEN), a);
363    expectSetCountFailure(sortedMultiset.tailMultiset(b.getElement(), CLOSED), a);
364    expectSetCountFailure(sortedMultiset.tailMultiset(b.getElement(), OPEN), a);
365    expectSetCountFailure(sortedMultiset.tailMultiset(b.getElement(), OPEN), b);
366    expectSetCountFailure(sortedMultiset.tailMultiset(c.getElement(), CLOSED), a);
367    expectSetCountFailure(sortedMultiset.tailMultiset(c.getElement(), CLOSED), b);
368    expectSetCountFailure(sortedMultiset.tailMultiset(c.getElement(), OPEN), a);
369    expectSetCountFailure(sortedMultiset.tailMultiset(c.getElement(), OPEN), b);
370    expectSetCountFailure(sortedMultiset.tailMultiset(c.getElement(), OPEN), c);
371  }
372
373  @CollectionSize.Require(ONE)
374  @CollectionFeature.Require({SUPPORTS_ADD, SUPPORTS_REMOVE})
375  public void testSetCountOutOfHeadBoundsOne() {
376    expectSetCountFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), a);
377  }
378
379  @CollectionSize.Require(SEVERAL)
380  @CollectionFeature.Require({SUPPORTS_ADD, SUPPORTS_REMOVE})
381  public void testSetCountOutOfHeadBoundsSeveral() {
382    expectSetCountFailure(sortedMultiset.headMultiset(c.getElement(), OPEN), c);
383    expectSetCountFailure(sortedMultiset.headMultiset(b.getElement(), CLOSED), c);
384    expectSetCountFailure(sortedMultiset.headMultiset(b.getElement(), OPEN), c);
385    expectSetCountFailure(sortedMultiset.headMultiset(b.getElement(), OPEN), b);
386    expectSetCountFailure(sortedMultiset.headMultiset(a.getElement(), CLOSED), c);
387    expectSetCountFailure(sortedMultiset.headMultiset(a.getElement(), CLOSED), b);
388    expectSetCountFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), c);
389    expectSetCountFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), b);
390    expectSetCountFailure(sortedMultiset.headMultiset(a.getElement(), OPEN), a);
391  }
392
393  @CollectionSize.Require(SEVERAL)
394  @CollectionFeature.Require(SUPPORTS_ADD)
395  public void testAddWithConflictingBounds() {
396    testEmptyRangeSubMultisetSupportingAdd(
397        sortedMultiset.subMultiset(a.getElement(), CLOSED, a.getElement(), OPEN));
398    testEmptyRangeSubMultisetSupportingAdd(
399        sortedMultiset.subMultiset(a.getElement(), OPEN, a.getElement(), OPEN));
400    testEmptyRangeSubMultisetSupportingAdd(
401        sortedMultiset.subMultiset(a.getElement(), OPEN, a.getElement(), CLOSED));
402    testEmptyRangeSubMultisetSupportingAdd(
403        sortedMultiset.subMultiset(b.getElement(), CLOSED, a.getElement(), CLOSED));
404    testEmptyRangeSubMultisetSupportingAdd(
405        sortedMultiset.subMultiset(b.getElement(), CLOSED, a.getElement(), OPEN));
406    testEmptyRangeSubMultisetSupportingAdd(
407        sortedMultiset.subMultiset(b.getElement(), OPEN, a.getElement(), OPEN));
408  }
409
410  @CollectionSize.Require(SEVERAL)
411  @CollectionFeature.Require(SUPPORTS_ADD)
412  public void testConflictingBounds() {
413    testEmptyRangeSubMultiset(
414        sortedMultiset.subMultiset(a.getElement(), CLOSED, a.getElement(), OPEN));
415    testEmptyRangeSubMultiset(
416        sortedMultiset.subMultiset(a.getElement(), OPEN, a.getElement(), OPEN));
417    testEmptyRangeSubMultiset(
418        sortedMultiset.subMultiset(a.getElement(), OPEN, a.getElement(), CLOSED));
419    testEmptyRangeSubMultiset(
420        sortedMultiset.subMultiset(b.getElement(), CLOSED, a.getElement(), CLOSED));
421    testEmptyRangeSubMultiset(
422        sortedMultiset.subMultiset(b.getElement(), CLOSED, a.getElement(), OPEN));
423    testEmptyRangeSubMultiset(
424        sortedMultiset.subMultiset(b.getElement(), OPEN, a.getElement(), OPEN));
425  }
426
427  public void testEmptyRangeSubMultiset(SortedMultiset<E> multiset) {
428    assertTrue(multiset.isEmpty());
429    assertEquals(0, multiset.size());
430    assertEquals(0, multiset.toArray().length);
431    assertTrue(multiset.entrySet().isEmpty());
432    assertFalse(multiset.iterator().hasNext());
433    assertEquals(0, multiset.entrySet().size());
434    assertEquals(0, multiset.entrySet().toArray().length);
435    assertFalse(multiset.entrySet().iterator().hasNext());
436  }
437
438  public void testEmptyRangeSubMultisetSupportingAdd(SortedMultiset<E> multiset) {
439    for (Entry<E> entry : asList(a, b, c)) {
440      expectAddFailure(multiset, entry);
441    }
442  }
443
444  private static int totalSize(Iterable<? extends Entry<?>> entries) {
445    int sum = 0;
446    for (Entry<?> entry : entries) {
447      sum += entry.getCount();
448    }
449    return sum;
450  }
451
452  private enum SubMultisetSpec {
453    TAIL_CLOSED {
454      @Override
455      <E> List<Entry<E>> expectedEntries(int targetEntry, List<Entry<E>> entries) {
456        return entries.subList(targetEntry, entries.size());
457      }
458
459      @Override
460      <E> SortedMultiset<E> subMultiset(
461          SortedMultiset<E> multiset, List<Entry<E>> entries, int targetEntry) {
462        return multiset.tailMultiset(entries.get(targetEntry).getElement(), CLOSED);
463      }
464    },
465    TAIL_OPEN {
466      @Override
467      <E> List<Entry<E>> expectedEntries(int targetEntry, List<Entry<E>> entries) {
468        return entries.subList(targetEntry + 1, entries.size());
469      }
470
471      @Override
472      <E> SortedMultiset<E> subMultiset(
473          SortedMultiset<E> multiset, List<Entry<E>> entries, int targetEntry) {
474        return multiset.tailMultiset(entries.get(targetEntry).getElement(), OPEN);
475      }
476    },
477    HEAD_CLOSED {
478      @Override
479      <E> List<Entry<E>> expectedEntries(int targetEntry, List<Entry<E>> entries) {
480        return entries.subList(0, targetEntry + 1);
481      }
482
483      @Override
484      <E> SortedMultiset<E> subMultiset(
485          SortedMultiset<E> multiset, List<Entry<E>> entries, int targetEntry) {
486        return multiset.headMultiset(entries.get(targetEntry).getElement(), CLOSED);
487      }
488    },
489    HEAD_OPEN {
490      @Override
491      <E> List<Entry<E>> expectedEntries(int targetEntry, List<Entry<E>> entries) {
492        return entries.subList(0, targetEntry);
493      }
494
495      @Override
496      <E> SortedMultiset<E> subMultiset(
497          SortedMultiset<E> multiset, List<Entry<E>> entries, int targetEntry) {
498        return multiset.headMultiset(entries.get(targetEntry).getElement(), OPEN);
499      }
500    };
501
502    abstract <E> List<Entry<E>> expectedEntries(int targetEntry, List<Entry<E>> entries);
503
504    abstract <E> SortedMultiset<E> subMultiset(
505        SortedMultiset<E> multiset, List<Entry<E>> entries, int targetEntry);
506  }
507
508  private void testSubMultisetEntrySet(SubMultisetSpec spec) {
509    List<Entry<E>> entries = copyToList(sortedMultiset.entrySet());
510    for (int i = 0; i < entries.size(); i++) {
511      List<Entry<E>> expected = spec.expectedEntries(i, entries);
512      SortedMultiset<E> subMultiset = spec.subMultiset(sortedMultiset, entries, i);
513      assertEquals(expected, copyToList(subMultiset.entrySet()));
514    }
515  }
516
517  private void testSubMultisetSize(SubMultisetSpec spec) {
518    List<Entry<E>> entries = copyToList(sortedMultiset.entrySet());
519    for (int i = 0; i < entries.size(); i++) {
520      List<Entry<E>> expected = spec.expectedEntries(i, entries);
521      SortedMultiset<E> subMultiset = spec.subMultiset(sortedMultiset, entries, i);
522      assertEquals(totalSize(expected), subMultiset.size());
523    }
524  }
525
526  private void testSubMultisetDistinctElements(SubMultisetSpec spec) {
527    List<Entry<E>> entries = copyToList(sortedMultiset.entrySet());
528    for (int i = 0; i < entries.size(); i++) {
529      List<Entry<E>> expected = spec.expectedEntries(i, entries);
530      SortedMultiset<E> subMultiset = spec.subMultiset(sortedMultiset, entries, i);
531      assertEquals(expected.size(), subMultiset.entrySet().size());
532      assertEquals(expected.size(), subMultiset.elementSet().size());
533    }
534  }
535
536  public void testTailClosedEntrySet() {
537    testSubMultisetEntrySet(SubMultisetSpec.TAIL_CLOSED);
538  }
539
540  public void testTailClosedSize() {
541    testSubMultisetSize(SubMultisetSpec.TAIL_CLOSED);
542  }
543
544  public void testTailClosedDistinctElements() {
545    testSubMultisetDistinctElements(SubMultisetSpec.TAIL_CLOSED);
546  }
547
548  public void testTailOpenEntrySet() {
549    testSubMultisetEntrySet(SubMultisetSpec.TAIL_OPEN);
550  }
551
552  public void testTailOpenSize() {
553    testSubMultisetSize(SubMultisetSpec.TAIL_OPEN);
554  }
555
556  public void testTailOpenDistinctElements() {
557    testSubMultisetDistinctElements(SubMultisetSpec.TAIL_OPEN);
558  }
559
560  public void testHeadClosedEntrySet() {
561    testSubMultisetEntrySet(SubMultisetSpec.HEAD_CLOSED);
562  }
563
564  public void testHeadClosedSize() {
565    testSubMultisetSize(SubMultisetSpec.HEAD_CLOSED);
566  }
567
568  public void testHeadClosedDistinctElements() {
569    testSubMultisetDistinctElements(SubMultisetSpec.HEAD_CLOSED);
570  }
571
572  public void testHeadOpenEntrySet() {
573    testSubMultisetEntrySet(SubMultisetSpec.HEAD_OPEN);
574  }
575
576  public void testHeadOpenSize() {
577    testSubMultisetSize(SubMultisetSpec.HEAD_OPEN);
578  }
579
580  public void testHeadOpenDistinctElements() {
581    testSubMultisetDistinctElements(SubMultisetSpec.HEAD_OPEN);
582  }
583
584  @CollectionSize.Require(SEVERAL)
585  @CollectionFeature.Require(SUPPORTS_REMOVE)
586  public void testClearTailOpen() {
587    List<Entry<E>> expected =
588        copyToList(sortedMultiset.headMultiset(b.getElement(), CLOSED).entrySet());
589    sortedMultiset.tailMultiset(b.getElement(), OPEN).clear();
590    assertEquals(expected, copyToList(sortedMultiset.entrySet()));
591  }
592
593  @CollectionSize.Require(SEVERAL)
594  @CollectionFeature.Require(SUPPORTS_REMOVE)
595  public void testClearTailOpenEntrySet() {
596    List<Entry<E>> expected =
597        copyToList(sortedMultiset.headMultiset(b.getElement(), CLOSED).entrySet());
598    sortedMultiset.tailMultiset(b.getElement(), OPEN).entrySet().clear();
599    assertEquals(expected, copyToList(sortedMultiset.entrySet()));
600  }
601
602  @CollectionSize.Require(SEVERAL)
603  @CollectionFeature.Require(SUPPORTS_REMOVE)
604  public void testClearTailClosed() {
605    List<Entry<E>> expected =
606        copyToList(sortedMultiset.headMultiset(b.getElement(), OPEN).entrySet());
607    sortedMultiset.tailMultiset(b.getElement(), CLOSED).clear();
608    assertEquals(expected, copyToList(sortedMultiset.entrySet()));
609  }
610
611  @CollectionSize.Require(SEVERAL)
612  @CollectionFeature.Require(SUPPORTS_REMOVE)
613  public void testClearTailClosedEntrySet() {
614    List<Entry<E>> expected =
615        copyToList(sortedMultiset.headMultiset(b.getElement(), OPEN).entrySet());
616    sortedMultiset.tailMultiset(b.getElement(), CLOSED).entrySet().clear();
617    assertEquals(expected, copyToList(sortedMultiset.entrySet()));
618  }
619
620  @CollectionSize.Require(SEVERAL)
621  @CollectionFeature.Require(SUPPORTS_REMOVE)
622  public void testClearHeadOpen() {
623    List<Entry<E>> expected =
624        copyToList(sortedMultiset.tailMultiset(b.getElement(), CLOSED).entrySet());
625    sortedMultiset.headMultiset(b.getElement(), OPEN).clear();
626    assertEquals(expected, copyToList(sortedMultiset.entrySet()));
627  }
628
629  @CollectionSize.Require(SEVERAL)
630  @CollectionFeature.Require(SUPPORTS_REMOVE)
631  public void testClearHeadOpenEntrySet() {
632    List<Entry<E>> expected =
633        copyToList(sortedMultiset.tailMultiset(b.getElement(), CLOSED).entrySet());
634    sortedMultiset.headMultiset(b.getElement(), OPEN).entrySet().clear();
635    assertEquals(expected, copyToList(sortedMultiset.entrySet()));
636  }
637
638  @CollectionSize.Require(SEVERAL)
639  @CollectionFeature.Require(SUPPORTS_REMOVE)
640  public void testClearHeadClosed() {
641    List<Entry<E>> expected =
642        copyToList(sortedMultiset.tailMultiset(b.getElement(), OPEN).entrySet());
643    sortedMultiset.headMultiset(b.getElement(), CLOSED).clear();
644    assertEquals(expected, copyToList(sortedMultiset.entrySet()));
645  }
646
647  @CollectionSize.Require(SEVERAL)
648  @CollectionFeature.Require(SUPPORTS_REMOVE)
649  public void testClearHeadClosedEntrySet() {
650    List<Entry<E>> expected =
651        copyToList(sortedMultiset.tailMultiset(b.getElement(), OPEN).entrySet());
652    sortedMultiset.headMultiset(b.getElement(), CLOSED).entrySet().clear();
653    assertEquals(expected, copyToList(sortedMultiset.entrySet()));
654  }
655}