1
2
3
4
5
6
7
8
9
10
11
12
13
14
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.SortedMapInterfaceTest;
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
31 import junit.framework.Test;
32 import junit.framework.TestSuite;
33
34 import java.util.Collections;
35 import java.util.Comparator;
36 import java.util.Map;
37 import java.util.Map.Entry;
38 import java.util.Set;
39 import java.util.SortedMap;
40
41
42
43
44
45
46
47 @GwtCompatible(emulated = true)
48 public 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 }