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