View Javadoc
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  
17  package com.google.common.collect.testing.testers;
18  
19  import static com.google.common.collect.testing.features.CollectionSize.ONE;
20  import static com.google.common.collect.testing.features.CollectionSize.SEVERAL;
21  import static com.google.common.collect.testing.features.CollectionSize.ZERO;
22  import static com.google.common.collect.testing.features.MapFeature.SUPPORTS_REMOVE;
23  
24  import com.google.common.annotations.GwtIncompatible;
25  import com.google.common.collect.testing.AbstractMapTester;
26  import com.google.common.collect.testing.Helpers;
27  import com.google.common.collect.testing.features.CollectionSize;
28  import com.google.common.collect.testing.features.MapFeature;
29  import java.util.ArrayList;
30  import java.util.Collections;
31  import java.util.List;
32  import java.util.Map.Entry;
33  import java.util.NavigableMap;
34  
35  /**
36   * A generic JUnit test which tests operations on a NavigableMap. Can't be
37   * invoked directly; please see {@code NavigableMapTestSuiteBuilder}.
38   *
39   * @author Jesse Wilson
40   * @author Louis Wasserman
41   */
42  @GwtIncompatible
43  public class NavigableMapNavigationTester<K, V> extends AbstractMapTester<K, V> {
44  
45    private NavigableMap<K, V> navigableMap;
46    private List<Entry<K, V>> entries;
47    private Entry<K, V> a;
48    private Entry<K, V> b;
49    private Entry<K, V> c;
50  
51    @Override
52    public void setUp() throws Exception {
53      super.setUp();
54      navigableMap = (NavigableMap<K, V>) getMap();
55      entries =
56          Helpers.copyToList(
57              getSubjectGenerator()
58                  .getSampleElements(getSubjectGenerator().getCollectionSize().getNumElements()));
59      Collections.sort(entries, Helpers.<K, V>entryComparator(navigableMap.comparator()));
60  
61      // some tests assume SEVERAL == 3
62      if (entries.size() >= 1) {
63        a = entries.get(0);
64        if (entries.size() >= 3) {
65          b = entries.get(1);
66          c = entries.get(2);
67        }
68      }
69    }
70  
71    /**
72     * Resets the contents of navigableMap to have entries a, c, for the
73     * navigation tests.
74     */
75    @SuppressWarnings("unchecked") // Needed to stop Eclipse whining
76    private void resetWithHole() {
77      Entry<K, V>[] entries = new Entry[] {a, c};
78      super.resetMap(entries);
79      navigableMap = (NavigableMap<K, V>) getMap();
80    }
81  
82    @CollectionSize.Require(ZERO)
83    public void testEmptyMapFirst() {
84      assertNull(navigableMap.firstEntry());
85    }
86  
87    @MapFeature.Require(SUPPORTS_REMOVE)
88    @CollectionSize.Require(ZERO)
89    public void testEmptyMapPollFirst() {
90      assertNull(navigableMap.pollFirstEntry());
91    }
92  
93    @CollectionSize.Require(ZERO)
94    public void testEmptyMapNearby() {
95      assertNull(navigableMap.lowerEntry(k0()));
96      assertNull(navigableMap.lowerKey(k0()));
97      assertNull(navigableMap.floorEntry(k0()));
98      assertNull(navigableMap.floorKey(k0()));
99      assertNull(navigableMap.ceilingEntry(k0()));
100     assertNull(navigableMap.ceilingKey(k0()));
101     assertNull(navigableMap.higherEntry(k0()));
102     assertNull(navigableMap.higherKey(k0()));
103   }
104 
105   @CollectionSize.Require(ZERO)
106   public void testEmptyMapLast() {
107     assertNull(navigableMap.lastEntry());
108   }
109 
110   @MapFeature.Require(SUPPORTS_REMOVE)
111   @CollectionSize.Require(ZERO)
112   public void testEmptyMapPollLast() {
113     assertNull(navigableMap.pollLastEntry());
114   }
115 
116   @CollectionSize.Require(ONE)
117   public void testSingletonMapFirst() {
118     assertEquals(a, navigableMap.firstEntry());
119   }
120 
121   @MapFeature.Require(SUPPORTS_REMOVE)
122   @CollectionSize.Require(ONE)
123   public void testSingletonMapPollFirst() {
124     assertEquals(a, navigableMap.pollFirstEntry());
125     assertTrue(navigableMap.isEmpty());
126   }
127 
128   @CollectionSize.Require(ONE)
129   public void testSingletonMapNearby() {
130     assertNull(navigableMap.lowerEntry(k0()));
131     assertNull(navigableMap.lowerKey(k0()));
132     assertEquals(a, navigableMap.floorEntry(k0()));
133     assertEquals(a.getKey(), navigableMap.floorKey(k0()));
134     assertEquals(a, navigableMap.ceilingEntry(k0()));
135     assertEquals(a.getKey(), navigableMap.ceilingKey(k0()));
136     assertNull(navigableMap.higherEntry(k0()));
137     assertNull(navigableMap.higherKey(k0()));
138   }
139 
140   @CollectionSize.Require(ONE)
141   public void testSingletonMapLast() {
142     assertEquals(a, navigableMap.lastEntry());
143   }
144 
145   @MapFeature.Require(SUPPORTS_REMOVE)
146   @CollectionSize.Require(ONE)
147   public void testSingletonMapPollLast() {
148     assertEquals(a, navigableMap.pollLastEntry());
149     assertTrue(navigableMap.isEmpty());
150   }
151 
152   @CollectionSize.Require(SEVERAL)
153   public void testFirst() {
154     assertEquals(a, navigableMap.firstEntry());
155   }
156 
157   @MapFeature.Require(SUPPORTS_REMOVE)
158   @CollectionSize.Require(SEVERAL)
159   public void testPollFirst() {
160     assertEquals(a, navigableMap.pollFirstEntry());
161     assertEquals(entries.subList(1, entries.size()), Helpers.copyToList(navigableMap.entrySet()));
162   }
163 
164   @MapFeature.Require(absent = SUPPORTS_REMOVE)
165   public void testPollFirstUnsupported() {
166     try {
167       navigableMap.pollFirstEntry();
168       fail();
169     } catch (UnsupportedOperationException e) {
170     }
171   }
172 
173   @CollectionSize.Require(SEVERAL)
174   public void testLower() {
175     resetWithHole();
176     assertEquals(null, navigableMap.lowerEntry(a.getKey()));
177     assertEquals(null, navigableMap.lowerKey(a.getKey()));
178     assertEquals(a, navigableMap.lowerEntry(b.getKey()));
179     assertEquals(a.getKey(), navigableMap.lowerKey(b.getKey()));
180     assertEquals(a, navigableMap.lowerEntry(c.getKey()));
181     assertEquals(a.getKey(), navigableMap.lowerKey(c.getKey()));
182   }
183 
184   @CollectionSize.Require(SEVERAL)
185   public void testFloor() {
186     resetWithHole();
187     assertEquals(a, navigableMap.floorEntry(a.getKey()));
188     assertEquals(a.getKey(), navigableMap.floorKey(a.getKey()));
189     assertEquals(a, navigableMap.floorEntry(b.getKey()));
190     assertEquals(a.getKey(), navigableMap.floorKey(b.getKey()));
191     assertEquals(c, navigableMap.floorEntry(c.getKey()));
192     assertEquals(c.getKey(), navigableMap.floorKey(c.getKey()));
193   }
194 
195   @CollectionSize.Require(SEVERAL)
196   public void testCeiling() {
197     resetWithHole();
198     assertEquals(a, navigableMap.ceilingEntry(a.getKey()));
199     assertEquals(a.getKey(), navigableMap.ceilingKey(a.getKey()));
200     assertEquals(c, navigableMap.ceilingEntry(b.getKey()));
201     assertEquals(c.getKey(), navigableMap.ceilingKey(b.getKey()));
202     assertEquals(c, navigableMap.ceilingEntry(c.getKey()));
203     assertEquals(c.getKey(), navigableMap.ceilingKey(c.getKey()));
204   }
205 
206   @CollectionSize.Require(SEVERAL)
207   public void testHigher() {
208     resetWithHole();
209     assertEquals(c, navigableMap.higherEntry(a.getKey()));
210     assertEquals(c.getKey(), navigableMap.higherKey(a.getKey()));
211     assertEquals(c, navigableMap.higherEntry(b.getKey()));
212     assertEquals(c.getKey(), navigableMap.higherKey(b.getKey()));
213     assertEquals(null, navigableMap.higherEntry(c.getKey()));
214     assertEquals(null, navigableMap.higherKey(c.getKey()));
215   }
216 
217   @CollectionSize.Require(SEVERAL)
218   public void testLast() {
219     assertEquals(c, navigableMap.lastEntry());
220   }
221 
222   @MapFeature.Require(SUPPORTS_REMOVE)
223   @CollectionSize.Require(SEVERAL)
224   public void testPollLast() {
225     assertEquals(c, navigableMap.pollLastEntry());
226     assertEquals(
227         entries.subList(0, entries.size() - 1), Helpers.copyToList(navigableMap.entrySet()));
228   }
229 
230   @MapFeature.Require(absent = SUPPORTS_REMOVE)
231   @CollectionSize.Require(SEVERAL)
232   public void testPollLastUnsupported() {
233     try {
234       navigableMap.pollLastEntry();
235       fail();
236     } catch (UnsupportedOperationException e) {
237     }
238   }
239 
240   @CollectionSize.Require(SEVERAL)
241   public void testDescendingNavigation() {
242     List<Entry<K, V>> descending = new ArrayList<>(navigableMap.descendingMap().entrySet());
243     Collections.reverse(descending);
244     assertEquals(entries, descending);
245   }
246 
247   @CollectionSize.Require(absent = ZERO)
248   public void testHeadMapExclusive() {
249     assertFalse(navigableMap.headMap(a.getKey(), false).containsKey(a.getKey()));
250   }
251 
252   @CollectionSize.Require(absent = ZERO)
253   public void testHeadMapInclusive() {
254     assertTrue(navigableMap.headMap(a.getKey(), true).containsKey(a.getKey()));
255   }
256 
257   @CollectionSize.Require(absent = ZERO)
258   public void testTailMapExclusive() {
259     assertFalse(navigableMap.tailMap(a.getKey(), false).containsKey(a.getKey()));
260   }
261 
262   @CollectionSize.Require(absent = ZERO)
263   public void testTailMapInclusive() {
264     assertTrue(navigableMap.tailMap(a.getKey(), true).containsKey(a.getKey()));
265   }
266 }