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 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 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 } 267
