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