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
17package com.google.common.collect;
18
19import static com.google.common.truth.Truth.assertThat;
20
21import com.google.common.annotations.GwtCompatible;
22import com.google.common.annotations.GwtIncompatible;
23import com.google.common.collect.testing.SortedMapInterfaceTest;
24import com.google.common.collect.testing.SortedMapTestSuiteBuilder;
25import com.google.common.collect.testing.TestStringSortedMapGenerator;
26import com.google.common.collect.testing.features.CollectionFeature;
27import com.google.common.collect.testing.features.CollectionSize;
28import com.google.common.collect.testing.features.MapFeature;
29import com.google.common.testing.SerializableTester;
30
31import junit.framework.Test;
32import junit.framework.TestSuite;
33
34import java.util.Collections;
35import java.util.Comparator;
36import java.util.Map;
37import java.util.Map.Entry;
38import java.util.Set;
39import 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)
48public 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}
453