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