1 /* 2 * Copyright (C) 2008 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; 18 19 import static com.google.common.truth.Truth.assertThat; 20 21 import com.google.common.annotations.GwtCompatible; 22 import com.google.common.annotations.GwtIncompatible; 23 import com.google.common.collect.testing.SortedMapInterfaceTest; 24 import com.google.common.collect.testing.SortedMapTestSuiteBuilder; 25 import com.google.common.collect.testing.TestStringSortedMapGenerator; 26 import com.google.common.collect.testing.features.CollectionFeature; 27 import com.google.common.collect.testing.features.CollectionSize; 28 import com.google.common.collect.testing.features.MapFeature; 29 import com.google.common.testing.SerializableTester; 30 import java.util.Collections; 31 import java.util.Comparator; 32 import java.util.Map; 33 import java.util.Map.Entry; 34 import java.util.Set; 35 import java.util.SortedMap; 36 import junit.framework.Test; 37 import junit.framework.TestSuite; 38 39 /** 40 * Test cases for {@link TreeBasedTable}. 41 * 42 * @author Jared Levy 43 * @author Louis Wasserman 44 */ 45 @GwtCompatible(emulated = true) 46 public class TreeBasedTableTest extends AbstractTableTest { 47 @GwtIncompatible // suite suite()48 public static Test suite() { 49 TestSuite suite = new TestSuite(); 50 suite.addTestSuite(TreeBasedTableTest.class); 51 suite.addTestSuite(TreeRowTest.class); 52 suite.addTest( 53 SortedMapTestSuiteBuilder.using( 54 new TestStringSortedMapGenerator() { 55 @Override 56 protected SortedMap<String, String> create(Entry<String, String>[] entries) { 57 TreeBasedTable<String, String, String> table = TreeBasedTable.create(); 58 table.put("a", "b", "c"); 59 table.put("c", "b", "a"); 60 table.put("a", "a", "d"); 61 for (Entry<String, String> entry : entries) { 62 table.put("b", entry.getKey(), entry.getValue()); 63 } 64 return table.row("b"); 65 } 66 }) 67 .withFeatures( 68 MapFeature.GENERAL_PURPOSE, 69 CollectionFeature.SUPPORTS_ITERATOR_REMOVE, 70 CollectionSize.ANY) 71 .named("RowMapTestSuite") 72 .createTestSuite()); 73 return suite; 74 } 75 76 public static class TreeRowTest extends SortedMapInterfaceTest<String, String> { TreeRowTest()77 public TreeRowTest() { 78 super(false, false, true, true, true); 79 } 80 81 @Override makeEmptyMap()82 protected SortedMap<String, String> makeEmptyMap() { 83 TreeBasedTable<String, String, String> table = TreeBasedTable.create(); 84 table.put("a", "b", "c"); 85 table.put("c", "b", "a"); 86 table.put("a", "a", "d"); 87 return table.row("b"); 88 } 89 90 @Override makePopulatedMap()91 protected SortedMap<String, String> makePopulatedMap() { 92 TreeBasedTable<String, String, String> table = TreeBasedTable.create(); 93 table.put("a", "b", "c"); 94 table.put("c", "b", "a"); 95 table.put("b", "b", "x"); 96 table.put("b", "c", "y"); 97 table.put("b", "x", "n"); 98 table.put("a", "a", "d"); 99 return table.row("b"); 100 } 101 102 @Override getKeyNotInPopulatedMap()103 protected String getKeyNotInPopulatedMap() { 104 return "q"; 105 } 106 107 @Override getValueNotInPopulatedMap()108 protected String getValueNotInPopulatedMap() { 109 return "p"; 110 } 111 testClearSubMapOfRowMap()112 public void testClearSubMapOfRowMap() { 113 TreeBasedTable<String, String, String> table = TreeBasedTable.create(); 114 table.put("a", "b", "c"); 115 table.put("c", "b", "a"); 116 table.put("b", "b", "x"); 117 table.put("b", "c", "y"); 118 table.put("b", "x", "n"); 119 table.put("a", "a", "d"); 120 table.row("b").subMap("c", "x").clear(); 121 assertEquals(table.row("b"), ImmutableMap.of("b", "x", "x", "n")); 122 table.row("b").subMap("b", "y").clear(); 123 assertEquals(table.row("b"), ImmutableMap.of()); 124 assertFalse(table.backingMap.containsKey("b")); 125 } 126 } 127 128 private TreeBasedTable<String, Integer, Character> sortedTable; 129 create( Comparator<? super String> rowComparator, Comparator<? super Integer> columnComparator, Object... data)130 protected TreeBasedTable<String, Integer, Character> create( 131 Comparator<? super String> rowComparator, 132 Comparator<? super Integer> columnComparator, 133 Object... data) { 134 TreeBasedTable<String, Integer, Character> table = 135 TreeBasedTable.create(rowComparator, columnComparator); 136 table.put("foo", 4, 'a'); 137 table.put("cat", 1, 'b'); 138 table.clear(); 139 populate(table, data); 140 return table; 141 } 142 143 @Override create(Object... data)144 protected TreeBasedTable<String, Integer, Character> create(Object... data) { 145 TreeBasedTable<String, Integer, Character> table = TreeBasedTable.create(); 146 table.put("foo", 4, 'a'); 147 table.put("cat", 1, 'b'); 148 table.clear(); 149 populate(table, data); 150 return table; 151 } 152 testCreateExplicitComparators()153 public void testCreateExplicitComparators() { 154 table = TreeBasedTable.create(Collections.reverseOrder(), Ordering.usingToString()); 155 table.put("foo", 3, 'a'); 156 table.put("foo", 12, 'b'); 157 table.put("bar", 5, 'c'); 158 table.put("cat", 8, 'd'); 159 assertThat(table.rowKeySet()).containsExactly("foo", "cat", "bar").inOrder(); 160 assertThat(table.row("foo").keySet()).containsExactly(12, 3).inOrder(); 161 } 162 testCreateCopy()163 public void testCreateCopy() { 164 TreeBasedTable<String, Integer, Character> original = 165 TreeBasedTable.create(Collections.reverseOrder(), Ordering.usingToString()); 166 original.put("foo", 3, 'a'); 167 original.put("foo", 12, 'b'); 168 original.put("bar", 5, 'c'); 169 original.put("cat", 8, 'd'); 170 table = TreeBasedTable.create(original); 171 assertThat(table.rowKeySet()).containsExactly("foo", "cat", "bar").inOrder(); 172 assertThat(table.row("foo").keySet()).containsExactly(12, 3).inOrder(); 173 assertEquals(original, table); 174 } 175 176 @GwtIncompatible // SerializableTester testSerialization()177 public void testSerialization() { 178 table = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 179 SerializableTester.reserializeAndAssert(table); 180 } 181 testToString_ordered()182 public void testToString_ordered() { 183 table = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 184 assertEquals("{bar={1=b}, foo={1=a, 3=c}}", table.toString()); 185 assertEquals("{bar={1=b}, foo={1=a, 3=c}}", table.rowMap().toString()); 186 } 187 testCellSetToString_ordered()188 public void testCellSetToString_ordered() { 189 table = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 190 assertEquals("[(bar,1)=b, (foo,1)=a, (foo,3)=c]", table.cellSet().toString()); 191 } 192 testRowKeySetToString_ordered()193 public void testRowKeySetToString_ordered() { 194 table = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 195 assertEquals("[bar, foo]", table.rowKeySet().toString()); 196 } 197 testValuesToString_ordered()198 public void testValuesToString_ordered() { 199 table = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 200 assertEquals("[b, a, c]", table.values().toString()); 201 } 202 testRowComparator()203 public void testRowComparator() { 204 sortedTable = TreeBasedTable.create(); 205 assertSame(Ordering.natural(), sortedTable.rowComparator()); 206 207 sortedTable = TreeBasedTable.create(Collections.reverseOrder(), Ordering.usingToString()); 208 assertSame(Collections.reverseOrder(), sortedTable.rowComparator()); 209 } 210 testColumnComparator()211 public void testColumnComparator() { 212 sortedTable = TreeBasedTable.create(); 213 sortedTable.put("", 42, 'x'); 214 assertSame(Ordering.natural(), sortedTable.columnComparator()); 215 assertSame( 216 Ordering.natural(), 217 ((SortedMap<Integer, Character>) sortedTable.rowMap().values().iterator().next()) 218 .comparator()); 219 220 sortedTable = TreeBasedTable.create(Collections.reverseOrder(), Ordering.usingToString()); 221 sortedTable.put("", 42, 'x'); 222 assertSame(Ordering.usingToString(), sortedTable.columnComparator()); 223 assertSame( 224 Ordering.usingToString(), 225 ((SortedMap<Integer, Character>) sortedTable.rowMap().values().iterator().next()) 226 .comparator()); 227 } 228 testRowKeySetComparator()229 public void testRowKeySetComparator() { 230 sortedTable = TreeBasedTable.create(); 231 assertSame(Ordering.natural(), sortedTable.rowKeySet().comparator()); 232 233 sortedTable = TreeBasedTable.create(Collections.reverseOrder(), Ordering.usingToString()); 234 assertSame(Collections.reverseOrder(), sortedTable.rowKeySet().comparator()); 235 } 236 testRowKeySetFirst()237 public void testRowKeySetFirst() { 238 sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 239 assertSame("bar", sortedTable.rowKeySet().first()); 240 } 241 testRowKeySetLast()242 public void testRowKeySetLast() { 243 sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 244 assertSame("foo", sortedTable.rowKeySet().last()); 245 } 246 testRowKeySetHeadSet()247 public void testRowKeySetHeadSet() { 248 sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 249 Set<String> set = sortedTable.rowKeySet().headSet("cat"); 250 assertEquals(Collections.singleton("bar"), set); 251 set.clear(); 252 assertTrue(set.isEmpty()); 253 assertEquals(Collections.singleton("foo"), sortedTable.rowKeySet()); 254 } 255 testRowKeySetTailSet()256 public void testRowKeySetTailSet() { 257 sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 258 Set<String> set = sortedTable.rowKeySet().tailSet("cat"); 259 assertEquals(Collections.singleton("foo"), set); 260 set.clear(); 261 assertTrue(set.isEmpty()); 262 assertEquals(Collections.singleton("bar"), sortedTable.rowKeySet()); 263 } 264 testRowKeySetSubSet()265 public void testRowKeySetSubSet() { 266 sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c', "dog", 2, 'd'); 267 Set<String> set = sortedTable.rowKeySet().subSet("cat", "egg"); 268 assertEquals(Collections.singleton("dog"), set); 269 set.clear(); 270 assertTrue(set.isEmpty()); 271 assertEquals(ImmutableSet.of("bar", "foo"), sortedTable.rowKeySet()); 272 } 273 testRowMapComparator()274 public void testRowMapComparator() { 275 sortedTable = TreeBasedTable.create(); 276 assertSame(Ordering.natural(), sortedTable.rowMap().comparator()); 277 278 sortedTable = TreeBasedTable.create(Collections.reverseOrder(), Ordering.usingToString()); 279 assertSame(Collections.reverseOrder(), sortedTable.rowMap().comparator()); 280 } 281 testRowMapFirstKey()282 public void testRowMapFirstKey() { 283 sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 284 assertSame("bar", sortedTable.rowMap().firstKey()); 285 } 286 testRowMapLastKey()287 public void testRowMapLastKey() { 288 sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 289 assertSame("foo", sortedTable.rowMap().lastKey()); 290 } 291 testRowKeyMapHeadMap()292 public void testRowKeyMapHeadMap() { 293 sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 294 Map<String, Map<Integer, Character>> map = sortedTable.rowMap().headMap("cat"); 295 assertEquals(1, map.size()); 296 assertEquals(ImmutableMap.of(1, 'b'), map.get("bar")); 297 map.clear(); 298 assertTrue(map.isEmpty()); 299 assertEquals(Collections.singleton("foo"), sortedTable.rowKeySet()); 300 } 301 testRowKeyMapTailMap()302 public void testRowKeyMapTailMap() { 303 sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 304 Map<String, Map<Integer, Character>> map = sortedTable.rowMap().tailMap("cat"); 305 assertEquals(1, map.size()); 306 assertEquals(ImmutableMap.of(1, 'a', 3, 'c'), map.get("foo")); 307 map.clear(); 308 assertTrue(map.isEmpty()); 309 assertEquals(Collections.singleton("bar"), sortedTable.rowKeySet()); 310 } 311 testRowKeyMapSubMap()312 public void testRowKeyMapSubMap() { 313 sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c', "dog", 2, 'd'); 314 Map<String, Map<Integer, Character>> map = sortedTable.rowMap().subMap("cat", "egg"); 315 assertEquals(ImmutableMap.of(2, 'd'), map.get("dog")); 316 map.clear(); 317 assertTrue(map.isEmpty()); 318 assertEquals(ImmutableSet.of("bar", "foo"), sortedTable.rowKeySet()); 319 } 320 testRowMapValuesAreSorted()321 public void testRowMapValuesAreSorted() { 322 sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c', "dog", 2, 'd'); 323 assertTrue(sortedTable.rowMap().get("foo") instanceof SortedMap); 324 } 325 testColumnKeySet_isSorted()326 public void testColumnKeySet_isSorted() { 327 table = 328 create( 329 "a", 2, 'X', "a", 2, 'X', "b", 3, 'X', "b", 2, 'X', "c", 10, 'X', "c", 10, 'X', "c", 20, 330 'X', "d", 15, 'X', "d", 20, 'X', "d", 1, 'X', "e", 5, 'X'); 331 assertEquals("[1, 2, 3, 5, 10, 15, 20]", table.columnKeySet().toString()); 332 } 333 testColumnKeySet_isSortedWithRealComparator()334 public void testColumnKeySet_isSortedWithRealComparator() { 335 table = 336 create( 337 String.CASE_INSENSITIVE_ORDER, 338 Ordering.natural().reverse(), 339 "a", 340 2, 341 'X', 342 "a", 343 2, 344 'X', 345 "b", 346 3, 347 'X', 348 "b", 349 2, 350 'X', 351 "c", 352 10, 353 'X', 354 "c", 355 10, 356 'X', 357 "c", 358 20, 359 'X', 360 "d", 361 15, 362 'X', 363 "d", 364 20, 365 'X', 366 "d", 367 1, 368 'X', 369 "e", 370 5, 371 'X'); 372 assertEquals("[20, 15, 10, 5, 3, 2, 1]", table.columnKeySet().toString()); 373 } 374 testColumnKeySet_empty()375 public void testColumnKeySet_empty() { 376 table = create(); 377 assertEquals("[]", table.columnKeySet().toString()); 378 } 379 testColumnKeySet_oneRow()380 public void testColumnKeySet_oneRow() { 381 table = create("a", 2, 'X', "a", 1, 'X'); 382 assertEquals("[1, 2]", table.columnKeySet().toString()); 383 } 384 testColumnKeySet_oneColumn()385 public void testColumnKeySet_oneColumn() { 386 table = create("a", 1, 'X', "b", 1, 'X'); 387 assertEquals("[1]", table.columnKeySet().toString()); 388 } 389 testColumnKeySet_oneEntry()390 public void testColumnKeySet_oneEntry() { 391 table = create("a", 1, 'X'); 392 assertEquals("[1]", table.columnKeySet().toString()); 393 } 394 testRowEntrySetContains()395 public void testRowEntrySetContains() { 396 table = 397 sortedTable = 398 create( 399 "a", 2, 'X', "a", 2, 'X', "b", 3, 'X', "b", 2, 'X', "c", 10, 'X', "c", 10, 'X', "c", 400 20, 'X', "d", 15, 'X', "d", 20, 'X', "d", 1, 'X', "e", 5, 'X'); 401 SortedMap<Integer, Character> row = sortedTable.row("c"); 402 Set<Entry<Integer, Character>> entrySet = row.entrySet(); 403 assertTrue(entrySet.contains(Maps.immutableEntry(10, 'X'))); 404 assertTrue(entrySet.contains(Maps.immutableEntry(20, 'X'))); 405 assertFalse(entrySet.contains(Maps.immutableEntry(15, 'X'))); 406 entrySet = row.tailMap(15).entrySet(); 407 assertFalse(entrySet.contains(Maps.immutableEntry(10, 'X'))); 408 assertTrue(entrySet.contains(Maps.immutableEntry(20, 'X'))); 409 assertFalse(entrySet.contains(Maps.immutableEntry(15, 'X'))); 410 } 411 testRowEntrySetRemove()412 public void testRowEntrySetRemove() { 413 table = 414 sortedTable = 415 create( 416 "a", 2, 'X', "a", 2, 'X', "b", 3, 'X', "b", 2, 'X', "c", 10, 'X', "c", 10, 'X', "c", 417 20, 'X', "d", 15, 'X', "d", 20, 'X', "d", 1, 'X', "e", 5, 'X'); 418 SortedMap<Integer, Character> row = sortedTable.row("c"); 419 Set<Entry<Integer, Character>> entrySet = row.tailMap(15).entrySet(); 420 assertFalse(entrySet.remove(Maps.immutableEntry(10, 'X'))); 421 assertTrue(entrySet.remove(Maps.immutableEntry(20, 'X'))); 422 assertFalse(entrySet.remove(Maps.immutableEntry(15, 'X'))); 423 entrySet = row.entrySet(); 424 assertTrue(entrySet.remove(Maps.immutableEntry(10, 'X'))); 425 assertFalse(entrySet.remove(Maps.immutableEntry(20, 'X'))); 426 assertFalse(entrySet.remove(Maps.immutableEntry(15, 'X'))); 427 } 428 testRowSize()429 public void testRowSize() { 430 table = 431 sortedTable = 432 create( 433 "a", 2, 'X', "a", 2, 'X', "b", 3, 'X', "b", 2, 'X', "c", 10, 'X', "c", 10, 'X', "c", 434 20, 'X', "d", 15, 'X', "d", 20, 'X', "d", 1, 'X', "e", 5, 'X'); 435 SortedMap<Integer, Character> row = sortedTable.row("c"); 436 assertEquals(2, row.size()); 437 assertEquals(1, row.tailMap(15).size()); 438 } 439 testSubRowClearAndPut()440 public void testSubRowClearAndPut() { 441 table = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c'); 442 SortedMap<Integer, Character> row = (SortedMap<Integer, Character>) table.row("foo"); 443 SortedMap<Integer, Character> subRow = row.tailMap(2); 444 assertEquals(ImmutableMap.of(1, 'a', 3, 'c'), row); 445 assertEquals(ImmutableMap.of(3, 'c'), subRow); 446 table.remove("foo", 3); 447 assertEquals(ImmutableMap.of(1, 'a'), row); 448 assertEquals(ImmutableMap.of(), subRow); 449 table.remove("foo", 1); 450 assertEquals(ImmutableMap.of(), row); 451 assertEquals(ImmutableMap.of(), subRow); 452 table.put("foo", 2, 'b'); 453 assertEquals(ImmutableMap.of(2, 'b'), row); 454 assertEquals(ImmutableMap.of(2, 'b'), subRow); 455 row.clear(); 456 assertEquals(ImmutableMap.of(), row); 457 assertEquals(ImmutableMap.of(), subRow); 458 table.put("foo", 5, 'x'); 459 assertEquals(ImmutableMap.of(5, 'x'), row); 460 assertEquals(ImmutableMap.of(5, 'x'), subRow); 461 } 462 } 463