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