NavigableSetNavigationTester.java revision 3c77433663281544363151bf284b0240dfd22a42
1/*
2 * Copyright (C) 2010 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect.testing.testers;
18
19import static com.google.common.collect.testing.features.CollectionFeature.SUPPORTS_REMOVE;
20import static com.google.common.collect.testing.features.CollectionSize.ONE;
21import static com.google.common.collect.testing.features.CollectionSize.SEVERAL;
22import static com.google.common.collect.testing.features.CollectionSize.ZERO;
23
24import com.google.common.collect.testing.Helpers;
25import com.google.common.collect.testing.features.CollectionFeature;
26import com.google.common.collect.testing.features.CollectionSize;
27
28import java.lang.reflect.Method;
29import java.util.ArrayList;
30import java.util.Collections;
31import java.util.Iterator;
32import java.util.List;
33import java.util.NavigableSet;
34import java.util.TreeSet;
35
36/**
37 * A generic JUnit test which tests operations on a NavigableSet. Can't be
38 * invoked directly; please see {@code NavigableSetTestSuiteBuilder}.
39 *
40 * @author Jesse Wilson
41 * @author Louis Wasserman
42 */
43public class NavigableSetNavigationTester<E> extends AbstractSetTester<E> {
44
45  private NavigableSet<E> navigableSet;
46  private List<E> values;
47  private E a;
48  private E b;
49  private E c;
50
51  @Override public void setUp() throws Exception {
52    super.setUp();
53    navigableSet = (NavigableSet<E>) getSet();
54    values = Helpers.copyToList(getSubjectGenerator().getSampleElements(
55        getSubjectGenerator().getCollectionSize().getNumElements()));
56    Collections.sort(values, navigableSet.comparator());
57
58    // some tests assume SEVERAL == 3
59    if (values.size() >= 1) {
60      a = values.get(0);
61      if (values.size() >= 3) {
62        b = values.get(1);
63        c = values.get(2);
64      }
65    }
66  }
67
68  /**
69   * Resets the contents of navigableSet to have elements a, c, for the
70   * navigation tests.
71   */
72  protected void resetWithHole() {
73    super.resetContainer(getSubjectGenerator().create(a, c));
74    navigableSet = (NavigableSet<E>) getSet();
75  }
76
77  @CollectionFeature.Require(SUPPORTS_REMOVE)
78  @CollectionSize.Require(ZERO)
79  public void testEmptySetPollFirst() {
80    assertNull(navigableSet.pollFirst());
81  }
82
83  @CollectionSize.Require(ZERO)
84  public void testEmptySetNearby() {
85    assertNull(navigableSet.lower(samples.e0));
86    assertNull(navigableSet.floor(samples.e0));
87    assertNull(navigableSet.ceiling(samples.e0));
88    assertNull(navigableSet.higher(samples.e0));
89  }
90
91  @CollectionFeature.Require(SUPPORTS_REMOVE)
92  @CollectionSize.Require(ZERO)
93  public void testEmptySetPollLast() {
94    assertNull(navigableSet.pollLast());
95  }
96
97  @CollectionFeature.Require(SUPPORTS_REMOVE)
98  @CollectionSize.Require(ONE)
99  public void testSingletonSetPollFirst() {
100    assertEquals(a, navigableSet.pollFirst());
101    assertTrue(navigableSet.isEmpty());
102  }
103
104  @CollectionSize.Require(ONE)
105  public void testSingletonSetNearby() {
106    assertNull(navigableSet.lower(samples.e0));
107    assertEquals(a, navigableSet.floor(samples.e0));
108    assertEquals(a, navigableSet.ceiling(samples.e0));
109    assertNull(navigableSet.higher(samples.e0));
110  }
111
112  @CollectionFeature.Require(SUPPORTS_REMOVE)
113  @CollectionSize.Require(ONE)
114  public void testSingletonSetPollLast() {
115    assertEquals(a, navigableSet.pollLast());
116    assertTrue(navigableSet.isEmpty());
117  }
118
119  @CollectionFeature.Require(SUPPORTS_REMOVE)
120  @CollectionSize.Require(SEVERAL)
121  public void testPollFirst() {
122    assertEquals(a, navigableSet.pollFirst());
123    assertEquals(
124        values.subList(1, values.size()), Helpers.copyToList(navigableSet));
125  }
126
127  @CollectionFeature.Require(absent = SUPPORTS_REMOVE)
128  public void testPollFirstUnsupported() {
129    try {
130      navigableSet.pollFirst();
131      fail();
132    } catch (UnsupportedOperationException e) {
133    }
134  }
135
136  @CollectionSize.Require(SEVERAL)
137  public void testLowerHole() {
138    resetWithHole();
139    assertEquals(null, navigableSet.lower(a));
140    assertEquals(a, navigableSet.lower(b));
141    assertEquals(a, navigableSet.lower(c));
142  }
143
144  @CollectionSize.Require(SEVERAL)
145  public void testFloorHole() {
146    resetWithHole();
147    assertEquals(a, navigableSet.floor(a));
148    assertEquals(a, navigableSet.floor(b));
149    assertEquals(c, navigableSet.floor(c));
150  }
151
152  @CollectionSize.Require(SEVERAL)
153  public void testCeilingHole() {
154    resetWithHole();
155    assertEquals(a, navigableSet.ceiling(a));
156    assertEquals(c, navigableSet.ceiling(b));
157    assertEquals(c, navigableSet.ceiling(c));
158  }
159
160  @CollectionSize.Require(SEVERAL)
161  public void testHigherHole() {
162    resetWithHole();
163    assertEquals(c, navigableSet.higher(a));
164    assertEquals(c, navigableSet.higher(b));
165    assertEquals(null, navigableSet.higher(c));
166  }
167
168  /*
169   * TODO(cpovirk): make "too small" and "too large" elements available for better navigation
170   * testing. At that point, we may be able to eliminate the "hole" tests, which would mean that
171   * ContiguousSet's tests would no longer need to suppress them.
172   */
173  @CollectionSize.Require(SEVERAL)
174  public void testLower() {
175    assertEquals(null, navigableSet.lower(a));
176    assertEquals(a, navigableSet.lower(b));
177    assertEquals(b, navigableSet.lower(c));
178  }
179
180  @CollectionSize.Require(SEVERAL)
181  public void testFloor() {
182    assertEquals(a, navigableSet.floor(a));
183    assertEquals(b, navigableSet.floor(b));
184    assertEquals(c, navigableSet.floor(c));
185  }
186
187  @CollectionSize.Require(SEVERAL)
188  public void testCeiling() {
189    assertEquals(a, navigableSet.ceiling(a));
190    assertEquals(b, navigableSet.ceiling(b));
191    assertEquals(c, navigableSet.ceiling(c));
192  }
193
194  @CollectionSize.Require(SEVERAL)
195  public void testHigher() {
196    assertEquals(b, navigableSet.higher(a));
197    assertEquals(c, navigableSet.higher(b));
198    assertEquals(null, navigableSet.higher(c));
199  }
200
201  @CollectionFeature.Require(SUPPORTS_REMOVE)
202  @CollectionSize.Require(SEVERAL)
203  public void testPollLast() {
204    assertEquals(c, navigableSet.pollLast());
205    assertEquals(
206        values.subList(0, values.size() - 1), Helpers.copyToList(navigableSet));
207  }
208
209  @CollectionFeature.Require(absent = SUPPORTS_REMOVE)
210  public void testPollLastUnsupported() {
211    try {
212      navigableSet.pollLast();
213      fail();
214    } catch (UnsupportedOperationException e) {
215    }
216  }
217
218  @CollectionSize.Require(SEVERAL)
219  public void testDescendingNavigation() {
220    List<E> descending = new ArrayList<E>();
221    for (Iterator<E> i = navigableSet.descendingIterator(); i.hasNext();) {
222      descending.add(i.next());
223    }
224    Collections.reverse(descending);
225    assertEquals(values, descending);
226  }
227
228  public void testEmptySubSet() {
229    NavigableSet<E> empty = navigableSet.subSet(samples.e0, false, samples.e0, false);
230    assertEquals(new TreeSet<E>(), empty);
231  }
232
233  /*
234   * TODO(cpovirk): more testing of subSet/headSet/tailSet/descendingSet? and/or generate derived
235   * suites?
236   */
237
238  /**
239   * Returns the {@link Method} instances for the test methods in this class that create a set with
240   * a "hole" in it so that set tests of {@code ContiguousSet} can suppress them with {@code
241   * FeatureSpecificTestSuiteBuilder.suppressing()}.
242   */
243  /*
244   * TODO(cpovirk): or we could make HOLES_FORBIDDEN a feature. Or we could declare that
245   * implementations are permitted to throw IAE if a hole is requested, and we could update
246   * test*Hole to permit IAE. (But might this ignore genuine bugs?) But see the TODO above
247   * testLower, which could make this all unnecessary
248   */
249  public static Method[] getHoleMethods() {
250    return new Method[] {
251        Helpers.getMethod(NavigableSetNavigationTester.class, "testLowerHole"),
252        Helpers.getMethod(NavigableSetNavigationTester.class, "testFloorHole"),
253        Helpers.getMethod(NavigableSetNavigationTester.class, "testCeilingHole"),
254        Helpers.getMethod(NavigableSetNavigationTester.class, "testHigherHole"),
255    };
256  }
257}
258