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