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