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