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