1 /* 2 * Copyright (C) 2009 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; 18 19 import java.util.ArrayList; 20 import java.util.Collection; 21 import java.util.Collections; 22 import java.util.Comparator; 23 import java.util.Iterator; 24 import java.util.List; 25 import java.util.Map; 26 import java.util.Map.Entry; 27 import java.util.NoSuchElementException; 28 import java.util.Set; 29 import java.util.SortedMap; 30 31 /** 32 * Tests representing the contract of {@link SortedMap}. Concrete subclasses of 33 * this base class test conformance of concrete {@link SortedMap} subclasses to 34 * that contract. 35 * 36 * <p>This class is GWT compatible. 37 * 38 * @author Jared Levy 39 */ 40 // TODO: Use this class to test classes besides ImmutableSortedMap. 41 public abstract class SortedMapInterfaceTest<K, V> 42 extends MapInterfaceTest<K, V> { 43 44 /** A key type that is not assignable to any classes but Object. */ 45 private static final class IncompatibleComparableKeyType 46 implements Comparable<IncompatibleComparableKeyType> { 47 @Override public String toString() { 48 return "IncompatibleComparableKeyType"; 49 } 50 @Override 51 public int compareTo(IncompatibleComparableKeyType o) { 52 throw new ClassCastException(); 53 } 54 } 55 56 protected SortedMapInterfaceTest(boolean allowsNullKeys, 57 boolean allowsNullValues, boolean supportsPut, boolean supportsRemove, 58 boolean supportsClear) { 59 super(allowsNullKeys, allowsNullValues, supportsPut, supportsRemove, 60 supportsClear); 61 } 62 63 @Override protected abstract SortedMap<K, V> makeEmptyMap() 64 throws UnsupportedOperationException; 65 66 @Override protected abstract SortedMap<K, V> makePopulatedMap() 67 throws UnsupportedOperationException; 68 69 @Override protected SortedMap<K, V> makeEitherMap() { 70 try { 71 return makePopulatedMap(); 72 } catch (UnsupportedOperationException e) { 73 return makeEmptyMap(); 74 } 75 } 76 77 @SuppressWarnings("unchecked") // Needed for null comparator 78 public void testOrdering() { 79 final SortedMap<K, V> map; 80 try { 81 map = makePopulatedMap(); 82 } catch (UnsupportedOperationException e) { 83 return; 84 } 85 Iterator<K> iterator = map.keySet().iterator(); 86 K prior = iterator.next(); 87 Comparator<? super K> comparator = map.comparator(); 88 while (iterator.hasNext()) { 89 K current = iterator.next(); 90 if (comparator == null) { 91 Comparable comparable = (Comparable) prior; 92 assertTrue(comparable.compareTo(current) < 0); 93 } else { 94 assertTrue(map.comparator().compare(prior, current) < 0); 95 } 96 current = prior; 97 } 98 } 99 100 public void testEntrySetContainsEntryIncompatibleComparableKey() { 101 final Map<K, V> map; 102 final Set<Entry<K, V>> entrySet; 103 try { 104 map = makeEitherMap(); 105 } catch (UnsupportedOperationException e) { 106 return; 107 } 108 assertInvariants(map); 109 110 entrySet = map.entrySet(); 111 final V unmappedValue; 112 try { 113 unmappedValue = getValueNotInPopulatedMap(); 114 } catch (UnsupportedOperationException e) { 115 return; 116 } 117 Entry<IncompatibleComparableKeyType, V> entry 118 = mapEntry(new IncompatibleComparableKeyType(), unmappedValue); 119 assertFalse(entrySet.contains(entry)); 120 } 121 122 public void testFirstKeyEmpty() { 123 final SortedMap<K, V> map; 124 try { 125 map = makeEmptyMap(); 126 } catch (UnsupportedOperationException e) { 127 return; 128 } 129 try { 130 map.firstKey(); 131 fail("Expected NoSuchElementException"); 132 } catch (NoSuchElementException expected) {} 133 assertInvariants(map); 134 } 135 136 public void testFirstKeyNonEmpty() { 137 final SortedMap<K, V> map; 138 try { 139 map = makePopulatedMap(); 140 } catch (UnsupportedOperationException e) { 141 return; 142 } 143 K expected = map.keySet().iterator().next(); 144 assertEquals(expected, map.firstKey()); 145 assertInvariants(map); 146 } 147 148 public void testLastKeyEmpty() { 149 final SortedMap<K, V> map; 150 try { 151 map = makeEmptyMap(); 152 } catch (UnsupportedOperationException e) { 153 return; 154 } 155 try { 156 map.lastKey(); 157 fail("Expected NoSuchElementException"); 158 } catch (NoSuchElementException expected) {} 159 assertInvariants(map); 160 } 161 162 public void testLastKeyNonEmpty() { 163 final SortedMap<K, V> map; 164 try { 165 map = makePopulatedMap(); 166 } catch (UnsupportedOperationException e) { 167 return; 168 } 169 K expected = null; 170 for (K key : map.keySet()) { 171 expected = key; 172 } 173 assertEquals(expected, map.lastKey()); 174 assertInvariants(map); 175 } 176 177 private static <E> List<E> toList(Collection<E> collection) { 178 return new ArrayList<E>(collection); 179 } 180 181 private static <E> List<E> subListSnapshot( 182 List<E> list, int fromIndex, int toIndex) { 183 List<E> subList = new ArrayList<E>(); 184 for (int i = fromIndex; i < toIndex; i++) { 185 subList.add(list.get(i)); 186 } 187 return Collections.unmodifiableList(subList); 188 } 189 190 public void testHeadMap() { 191 final SortedMap<K, V> map; 192 try { 193 map = makeEitherMap(); 194 } catch (UnsupportedOperationException e) { 195 return; 196 } 197 List<Entry<K, V>> list = toList(map.entrySet()); 198 for (int i = 0; i < list.size(); i++) { 199 List<Entry<K, V>> expected = subListSnapshot(list, 0, i); 200 SortedMap<K, V> headMap = map.headMap(list.get(i).getKey()); 201 assertEquals(expected, toList(headMap.entrySet())); 202 } 203 } 204 205 public void testTailMap() { 206 final SortedMap<K, V> map; 207 try { 208 map = makeEitherMap(); 209 } catch (UnsupportedOperationException e) { 210 return; 211 } 212 List<Entry<K, V>> list = toList(map.entrySet()); 213 for (int i = 0; i < list.size(); i++) { 214 List<Entry<K, V>> expected = subListSnapshot(list, i, list.size()); 215 SortedMap<K, V> tailMap = map.tailMap(list.get(i).getKey()); 216 assertEquals(expected, toList(tailMap.entrySet())); 217 } 218 } 219 220 public void testSubMap() { 221 final SortedMap<K, V> map; 222 try { 223 map = makeEitherMap(); 224 } catch (UnsupportedOperationException e) { 225 return; 226 } 227 List<Entry<K, V>> list = toList(map.entrySet()); 228 for (int i = 0; i < list.size(); i++) { 229 for (int j = i; j < list.size(); j++) { 230 List<Entry<K, V>> expected = subListSnapshot(list, i, j); 231 SortedMap<K, V> subMap 232 = map.subMap(list.get(i).getKey(), list.get(j).getKey()); 233 assertEquals(expected, toList(subMap.entrySet())); 234 } 235 } 236 } 237 238 public void testSubMapIllegal() { 239 final SortedMap<K, V> map; 240 try { 241 map = makePopulatedMap(); 242 } catch (UnsupportedOperationException e) { 243 return; 244 } 245 if (map.size() < 2) { 246 return; 247 } 248 Iterator<K> iterator = map.keySet().iterator(); 249 K first = iterator.next(); 250 K second = iterator.next(); 251 try { 252 map.subMap(second, first); 253 fail("Expected IllegalArgumentException"); 254 } catch (IllegalArgumentException expected) {} 255 } 256 257 public void testTailMapEntrySet() { 258 final SortedMap<K, V> map; 259 try { 260 map = makePopulatedMap(); 261 } catch (UnsupportedOperationException e) { 262 return; 263 } 264 if (map.size() < 3) { 265 return; 266 } 267 Iterator<Entry<K, V>> iterator = map.entrySet().iterator(); 268 Entry<K, V> firstEntry = iterator.next(); 269 Entry<K, V> secondEntry = iterator.next(); 270 Entry<K, V> thirdEntry = iterator.next(); 271 SortedMap<K, V> tail = map.tailMap(secondEntry.getKey()); 272 Set<Entry<K, V>> tailEntrySet = tail.entrySet(); 273 assertTrue(tailEntrySet.contains(thirdEntry)); 274 assertTrue(tailEntrySet.contains(secondEntry)); 275 assertFalse(tailEntrySet.contains(firstEntry)); 276 assertEquals(tail.firstKey(), secondEntry.getKey()); 277 } 278 279 public void testHeadMapEntrySet() { 280 final SortedMap<K, V> map; 281 try { 282 map = makePopulatedMap(); 283 } catch (UnsupportedOperationException e) { 284 return; 285 } 286 if (map.size() < 3) { 287 return; 288 } 289 Iterator<Entry<K, V>> iterator = map.entrySet().iterator(); 290 Entry<K, V> firstEntry = iterator.next(); 291 Entry<K, V> secondEntry = iterator.next(); 292 Entry<K, V> thirdEntry = iterator.next(); 293 SortedMap<K, V> head = map.headMap(secondEntry.getKey()); 294 Set<Entry<K, V>> headEntrySet = head.entrySet(); 295 assertFalse(headEntrySet.contains(thirdEntry)); 296 assertFalse(headEntrySet.contains(secondEntry)); 297 assertTrue(headEntrySet.contains(firstEntry)); 298 assertEquals(head.firstKey(), firstEntry.getKey()); 299 assertEquals(head.lastKey(), firstEntry.getKey()); 300 } 301 302 public void testTailMapWriteThrough() { 303 final SortedMap<K, V> map; 304 try { 305 map = makePopulatedMap(); 306 } catch (UnsupportedOperationException e) { 307 return; 308 } 309 if (map.size() < 2 || !supportsPut) { 310 return; 311 } 312 Iterator<Entry<K, V>> iterator = map.entrySet().iterator(); 313 Entry<K, V> firstEntry = iterator.next(); 314 Entry<K, V> secondEntry = iterator.next(); 315 K key = secondEntry.getKey(); 316 SortedMap<K, V> subMap = map.tailMap(key); 317 V value = getValueNotInPopulatedMap(); 318 subMap.put(key, value); 319 assertEquals(secondEntry.getValue(), value); 320 assertEquals(map.get(key), value); 321 try { 322 subMap.put(firstEntry.getKey(), value); 323 fail("Expected IllegalArgumentException"); 324 } catch (IllegalArgumentException expected) { 325 } 326 } 327 328 public void testTailMapRemoveThrough() { 329 final SortedMap<K, V> map; 330 try { 331 map = makePopulatedMap(); 332 } catch (UnsupportedOperationException e) { 333 return; 334 } 335 int oldSize = map.size(); 336 if (map.size() < 2 || !supportsRemove) { 337 return; 338 } 339 Iterator<Entry<K, V>> iterator = map.entrySet().iterator(); 340 Entry<K, V> firstEntry = iterator.next(); 341 Entry<K, V> secondEntry = iterator.next(); 342 K key = secondEntry.getKey(); 343 SortedMap<K, V> subMap = map.tailMap(key); 344 subMap.remove(key); 345 assertNull(subMap.remove(firstEntry.getKey())); 346 assertEquals(map.size(), oldSize - 1); 347 assertFalse(map.containsKey(key)); 348 assertEquals(subMap.size(), oldSize - 2); 349 } 350 351 public void testTailMapClearThrough() { 352 final SortedMap<K, V> map; 353 try { 354 map = makePopulatedMap(); 355 } catch (UnsupportedOperationException e) { 356 return; 357 } 358 int oldSize = map.size(); 359 if (map.size() < 2 || !supportsClear) { 360 return; 361 } 362 Iterator<Entry<K, V>> iterator = map.entrySet().iterator(); 363 Entry<K, V> firstEntry = iterator.next(); 364 Entry<K, V> secondEntry = iterator.next(); 365 K key = secondEntry.getKey(); 366 SortedMap<K, V> subMap = map.tailMap(key); 367 int subMapSize = subMap.size(); 368 subMap.clear(); 369 assertEquals(map.size(), oldSize - subMapSize); 370 assertTrue(subMap.isEmpty()); 371 } 372 } 373