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.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  * Test cases for {@link TreeBasedTable}.
43  *
44  * @author Jared Levy
45  * @author Louis Wasserman
46  */
47 @GwtCompatible(emulated = true)
48 public class TreeBasedTableTest extends AbstractTableTest {
49   @GwtIncompatible("suite")
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> {
TreeRowTest()78     public TreeRowTest() {
79       super(false, false, true, true, true);
80     }
81 
makeEmptyMap()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 
makePopulatedMap()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 
getKeyNotInPopulatedMap()101     @Override protected String getKeyNotInPopulatedMap() {
102       return "q";
103     }
104 
getValueNotInPopulatedMap()105     @Override protected String getValueNotInPopulatedMap() {
106       return "p";
107     }
108 
testClearSubMapOfRowMap()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 
create( Comparator<? super String> rowComparator, Comparator<? super Integer> columnComparator, Object... data)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 
create( Object... data)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 
testCreateExplicitComparators()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 
testCreateCopy()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")
testSerialization()175   public void testSerialization() {
176     table = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c');
177     SerializableTester.reserializeAndAssert(table);
178   }
179 
testToString_ordered()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 
testCellSetToString_ordered()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 
testRowKeySetToString_ordered()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 
testValuesToString_ordered()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 
testRowComparator()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 
testColumnComparator()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 
testRowKeySetComparator()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 
testRowKeySetFirst()231   public void testRowKeySetFirst() {
232     sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c');
233     assertSame("bar", sortedTable.rowKeySet().first());
234   }
235 
testRowKeySetLast()236   public void testRowKeySetLast() {
237     sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c');
238     assertSame("foo", sortedTable.rowKeySet().last());
239   }
240 
testRowKeySetHeadSet()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 
testRowKeySetTailSet()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 
testRowKeySetSubSet()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 
testRowMapComparator()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 
testRowMapFirstKey()278   public void testRowMapFirstKey() {
279     sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c');
280     assertSame("bar", sortedTable.rowMap().firstKey());
281   }
282 
testRowMapLastKey()283   public void testRowMapLastKey() {
284     sortedTable = create("foo", 1, 'a', "bar", 1, 'b', "foo", 3, 'c');
285     assertSame("foo", sortedTable.rowMap().lastKey());
286   }
287 
testRowKeyMapHeadMap()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 
testRowKeyMapTailMap()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 
testRowKeyMapSubMap()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 
testRowMapValuesAreSorted()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 
testColumnKeySet_isSorted()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 
testColumnKeySet_isSortedWithRealComparator()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 
testColumnKeySet_empty()361   public void testColumnKeySet_empty() {
362     table = create();
363     assertEquals("[]", table.columnKeySet().toString());
364   }
365 
testColumnKeySet_oneRow()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 
testColumnKeySet_oneColumn()373   public void testColumnKeySet_oneColumn() {
374     table = create("a", 1,  'X',
375                    "b", 1,  'X'
376                   );
377     assertEquals("[1]", table.columnKeySet().toString());
378   }
379 
testColumnKeySet_oneEntry()380   public void testColumnKeySet_oneEntry() {
381     table = create("a", 1,  'X');
382     assertEquals("[1]", table.columnKeySet().toString());
383   }
384 
testRowEntrySetContains()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 
testRowEntrySetRemove()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 
testRowSize()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 
testSubRowClearAndPut()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