1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
37
38
39
40
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
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
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
69
70
71 @SuppressWarnings("unchecked")
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)
79 public void testEmptyMapFirst() {
80 assertNull(navigableMap.firstEntry());
81 }
82
83 @MapFeature.Require(SUPPORTS_REMOVE)
84 @CollectionSize.Require(ZERO)
85 public void testEmptyMapPollFirst() {
86 assertNull(navigableMap.pollFirstEntry());
87 }
88
89 @CollectionSize.Require(ZERO)
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)
102 public void testEmptyMapLast() {
103 assertNull(navigableMap.lastEntry());
104 }
105
106 @MapFeature.Require(SUPPORTS_REMOVE)
107 @CollectionSize.Require(ZERO)
108 public void testEmptyMapPollLast() {
109 assertNull(navigableMap.pollLastEntry());
110 }
111
112 @CollectionSize.Require(ONE)
113 public void testSingletonMapFirst() {
114 assertEquals(a, navigableMap.firstEntry());
115 }
116
117 @MapFeature.Require(SUPPORTS_REMOVE)
118 @CollectionSize.Require(ONE)
119 public void testSingletonMapPollFirst() {
120 assertEquals(a, navigableMap.pollFirstEntry());
121 assertTrue(navigableMap.isEmpty());
122 }
123
124 @CollectionSize.Require(ONE)
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)
137 public void testSingletonMapLast() {
138 assertEquals(a, navigableMap.lastEntry());
139 }
140
141 @MapFeature.Require(SUPPORTS_REMOVE)
142 @CollectionSize.Require(ONE)
143 public void testSingletonMapPollLast() {
144 assertEquals(a, navigableMap.pollLastEntry());
145 assertTrue(navigableMap.isEmpty());
146 }
147
148 @CollectionSize.Require(SEVERAL)
149 public void testFirst() {
150 assertEquals(a, navigableMap.firstEntry());
151 }
152
153 @MapFeature.Require(SUPPORTS_REMOVE)
154 @CollectionSize.Require(SEVERAL)
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)
162 public void testPollFirstUnsupported() {
163 try {
164 navigableMap.pollFirstEntry();
165 fail();
166 } catch (UnsupportedOperationException e) {
167 }
168 }
169
170 @CollectionSize.Require(SEVERAL)
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)
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)
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)
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)
215 public void testLast() {
216 assertEquals(c, navigableMap.lastEntry());
217 }
218
219 @MapFeature.Require(SUPPORTS_REMOVE)
220 @CollectionSize.Require(SEVERAL)
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)
229 public void testPollLastUnsupported() {
230 try {
231 navigableMap.pollLastEntry();
232 fail();
233 } catch (UnsupportedOperationException e) {
234 }
235 }
236
237 @CollectionSize.Require(SEVERAL)
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)
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 }