1/*
2 * Copyright (C) 2009 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.testing;
18
19import java.util.ArrayList;
20import java.util.Collection;
21import java.util.Collections;
22import java.util.Comparator;
23import java.util.Iterator;
24import java.util.List;
25import java.util.Map;
26import java.util.Map.Entry;
27import java.util.NoSuchElementException;
28import java.util.Set;
29import java.util.SortedMap;
30
31/**
32 * Tests representing the contract of {@link SortedMap}. Concrete subclasses of
33 * this base class test conformance of concrete {@link SortedMap} subclasses to
34 * that contract.
35 *
36 * <p>This class is GWT compatible.
37 *
38 * @author Jared Levy
39 */
40// TODO: Use this class to test classes besides ImmutableSortedMap.
41public abstract class SortedMapInterfaceTest<K, V>
42    extends MapInterfaceTest<K, V> {
43
44  /** A key type that is not assignable to any classes but Object. */
45  private static final class IncompatibleComparableKeyType
46      implements Comparable<IncompatibleComparableKeyType> {
47    @Override public String toString() {
48      return "IncompatibleComparableKeyType";
49    }
50    @Override
51    public int compareTo(IncompatibleComparableKeyType o) {
52      throw new ClassCastException();
53    }
54  }
55
56  protected SortedMapInterfaceTest(boolean allowsNullKeys,
57      boolean allowsNullValues, boolean supportsPut, boolean supportsRemove,
58      boolean supportsClear) {
59    super(allowsNullKeys, allowsNullValues, supportsPut, supportsRemove,
60        supportsClear);
61  }
62
63  @Override protected abstract SortedMap<K, V> makeEmptyMap()
64      throws UnsupportedOperationException;
65
66  @Override protected abstract SortedMap<K, V> makePopulatedMap()
67      throws UnsupportedOperationException;
68
69  @Override protected SortedMap<K, V> makeEitherMap() {
70    try {
71      return makePopulatedMap();
72    } catch (UnsupportedOperationException e) {
73      return makeEmptyMap();
74    }
75  }
76
77  @SuppressWarnings("unchecked") // Needed for null comparator
78  public void testOrdering() {
79    final SortedMap<K, V> map;
80    try {
81      map = makePopulatedMap();
82    } catch (UnsupportedOperationException e) {
83      return;
84    }
85    Iterator<K> iterator = map.keySet().iterator();
86    K prior = iterator.next();
87    Comparator<? super K> comparator = map.comparator();
88    while (iterator.hasNext()) {
89      K current = iterator.next();
90      if (comparator == null) {
91        Comparable comparable = (Comparable) prior;
92        assertTrue(comparable.compareTo(current) < 0);
93      } else {
94        assertTrue(map.comparator().compare(prior, current) < 0);
95      }
96      current = prior;
97    }
98  }
99
100  public void testEntrySetContainsEntryIncompatibleComparableKey() {
101    final Map<K, V> map;
102    final Set<Entry<K, V>> entrySet;
103    try {
104      map = makeEitherMap();
105    } catch (UnsupportedOperationException e) {
106      return;
107    }
108    assertInvariants(map);
109
110    entrySet = map.entrySet();
111    final V unmappedValue;
112    try {
113      unmappedValue = getValueNotInPopulatedMap();
114    } catch (UnsupportedOperationException e) {
115      return;
116    }
117    Entry<IncompatibleComparableKeyType, V> entry
118        = mapEntry(new IncompatibleComparableKeyType(), unmappedValue);
119    assertFalse(entrySet.contains(entry));
120  }
121
122  public void testFirstKeyEmpty() {
123    final SortedMap<K, V> map;
124    try {
125      map = makeEmptyMap();
126    } catch (UnsupportedOperationException e) {
127      return;
128    }
129    try {
130      map.firstKey();
131      fail("Expected NoSuchElementException");
132    } catch (NoSuchElementException expected) {}
133    assertInvariants(map);
134  }
135
136  public void testFirstKeyNonEmpty() {
137    final SortedMap<K, V> map;
138    try {
139      map = makePopulatedMap();
140    } catch (UnsupportedOperationException e) {
141      return;
142    }
143    K expected = map.keySet().iterator().next();
144    assertEquals(expected, map.firstKey());
145    assertInvariants(map);
146  }
147
148  public void testLastKeyEmpty() {
149    final SortedMap<K, V> map;
150    try {
151      map = makeEmptyMap();
152    } catch (UnsupportedOperationException e) {
153      return;
154    }
155    try {
156      map.lastKey();
157      fail("Expected NoSuchElementException");
158    } catch (NoSuchElementException expected) {}
159    assertInvariants(map);
160  }
161
162  public void testLastKeyNonEmpty() {
163    final SortedMap<K, V> map;
164    try {
165      map = makePopulatedMap();
166    } catch (UnsupportedOperationException e) {
167      return;
168    }
169    K expected = null;
170    for (K key : map.keySet()) {
171      expected = key;
172    }
173    assertEquals(expected, map.lastKey());
174    assertInvariants(map);
175  }
176
177  private static <E> List<E> toList(Collection<E> collection) {
178    return new ArrayList<E>(collection);
179  }
180
181  private static <E> List<E> subListSnapshot(
182      List<E> list, int fromIndex, int toIndex) {
183    List<E> subList = new ArrayList<E>();
184    for (int i = fromIndex; i < toIndex; i++) {
185      subList.add(list.get(i));
186    }
187    return Collections.unmodifiableList(subList);
188  }
189
190  public void testHeadMap() {
191    final SortedMap<K, V> map;
192    try {
193      map = makeEitherMap();
194    } catch (UnsupportedOperationException e) {
195      return;
196    }
197    List<Entry<K, V>> list = toList(map.entrySet());
198    for (int i = 0; i < list.size(); i++) {
199      List<Entry<K, V>> expected = subListSnapshot(list, 0, i);
200      SortedMap<K, V> headMap = map.headMap(list.get(i).getKey());
201      assertEquals(expected, toList(headMap.entrySet()));
202    }
203  }
204
205  public void testTailMap() {
206    final SortedMap<K, V> map;
207    try {
208      map = makeEitherMap();
209    } catch (UnsupportedOperationException e) {
210      return;
211    }
212    List<Entry<K, V>> list = toList(map.entrySet());
213    for (int i = 0; i < list.size(); i++) {
214      List<Entry<K, V>> expected = subListSnapshot(list, i, list.size());
215      SortedMap<K, V> tailMap = map.tailMap(list.get(i).getKey());
216      assertEquals(expected, toList(tailMap.entrySet()));
217    }
218  }
219
220  public void testSubMap() {
221    final SortedMap<K, V> map;
222    try {
223      map = makeEitherMap();
224    } catch (UnsupportedOperationException e) {
225      return;
226    }
227    List<Entry<K, V>> list = toList(map.entrySet());
228    for (int i = 0; i < list.size(); i++) {
229      for (int j = i; j < list.size(); j++) {
230        List<Entry<K, V>> expected = subListSnapshot(list, i, j);
231        SortedMap<K, V> subMap
232            = map.subMap(list.get(i).getKey(), list.get(j).getKey());
233        assertEquals(expected, toList(subMap.entrySet()));
234      }
235    }
236  }
237
238  public void testSubMapIllegal() {
239    final SortedMap<K, V> map;
240    try {
241      map = makePopulatedMap();
242    } catch (UnsupportedOperationException e) {
243      return;
244    }
245    if (map.size() < 2) {
246      return;
247    }
248    Iterator<K> iterator = map.keySet().iterator();
249    K first = iterator.next();
250    K second = iterator.next();
251    try {
252      map.subMap(second, first);
253      fail("Expected IllegalArgumentException");
254    } catch (IllegalArgumentException expected) {}
255  }
256
257  public void testTailMapEntrySet() {
258    final SortedMap<K, V> map;
259    try {
260      map = makePopulatedMap();
261    } catch (UnsupportedOperationException e) {
262      return;
263    }
264    if (map.size() < 3) {
265      return;
266    }
267    Iterator<Entry<K, V>> iterator = map.entrySet().iterator();
268    Entry<K, V> firstEntry = iterator.next();
269    Entry<K, V> secondEntry = iterator.next();
270    Entry<K, V> thirdEntry = iterator.next();
271    SortedMap<K, V> tail = map.tailMap(secondEntry.getKey());
272    Set<Entry<K, V>> tailEntrySet = tail.entrySet();
273    assertTrue(tailEntrySet.contains(thirdEntry));
274    assertTrue(tailEntrySet.contains(secondEntry));
275    assertFalse(tailEntrySet.contains(firstEntry));
276    assertEquals(tail.firstKey(), secondEntry.getKey());
277  }
278
279  public void testHeadMapEntrySet() {
280    final SortedMap<K, V> map;
281    try {
282      map = makePopulatedMap();
283    } catch (UnsupportedOperationException e) {
284      return;
285    }
286    if (map.size() < 3) {
287      return;
288    }
289    Iterator<Entry<K, V>> iterator = map.entrySet().iterator();
290    Entry<K, V> firstEntry = iterator.next();
291    Entry<K, V> secondEntry = iterator.next();
292    Entry<K, V> thirdEntry = iterator.next();
293    SortedMap<K, V> head = map.headMap(secondEntry.getKey());
294    Set<Entry<K, V>> headEntrySet = head.entrySet();
295    assertFalse(headEntrySet.contains(thirdEntry));
296    assertFalse(headEntrySet.contains(secondEntry));
297    assertTrue(headEntrySet.contains(firstEntry));
298    assertEquals(head.firstKey(), firstEntry.getKey());
299    assertEquals(head.lastKey(), firstEntry.getKey());
300  }
301
302  public void testTailMapWriteThrough() {
303    final SortedMap<K, V> map;
304    try {
305      map = makePopulatedMap();
306    } catch (UnsupportedOperationException e) {
307      return;
308    }
309    if (map.size() < 2 || !supportsPut) {
310      return;
311    }
312    Iterator<Entry<K, V>> iterator = map.entrySet().iterator();
313    Entry<K, V> firstEntry = iterator.next();
314    Entry<K, V> secondEntry = iterator.next();
315    K key = secondEntry.getKey();
316    SortedMap<K, V> subMap = map.tailMap(key);
317    V value = getValueNotInPopulatedMap();
318    subMap.put(key, value);
319    assertEquals(secondEntry.getValue(), value);
320    assertEquals(map.get(key), value);
321    try {
322      subMap.put(firstEntry.getKey(), value);
323      fail("Expected IllegalArgumentException");
324    } catch (IllegalArgumentException expected) {
325    }
326  }
327
328  public void testTailMapRemoveThrough() {
329    final SortedMap<K, V> map;
330    try {
331      map = makePopulatedMap();
332    } catch (UnsupportedOperationException e) {
333      return;
334    }
335    int oldSize = map.size();
336    if (map.size() < 2 || !supportsRemove) {
337      return;
338    }
339    Iterator<Entry<K, V>> iterator = map.entrySet().iterator();
340    Entry<K, V> firstEntry = iterator.next();
341    Entry<K, V> secondEntry = iterator.next();
342    K key = secondEntry.getKey();
343    SortedMap<K, V> subMap = map.tailMap(key);
344    subMap.remove(key);
345    assertNull(subMap.remove(firstEntry.getKey()));
346    assertEquals(map.size(), oldSize - 1);
347    assertFalse(map.containsKey(key));
348    assertEquals(subMap.size(), oldSize - 2);
349  }
350
351  public void testTailMapClearThrough() {
352    final SortedMap<K, V> map;
353    try {
354      map = makePopulatedMap();
355    } catch (UnsupportedOperationException e) {
356      return;
357    }
358    int oldSize = map.size();
359    if (map.size() < 2 || !supportsClear) {
360      return;
361    }
362    Iterator<Entry<K, V>> iterator = map.entrySet().iterator();
363    Entry<K, V> firstEntry = iterator.next();
364    Entry<K, V> secondEntry = iterator.next();
365    K key = secondEntry.getKey();
366    SortedMap<K, V> subMap = map.tailMap(key);
367    int subMapSize = subMap.size();
368    subMap.clear();
369    assertEquals(map.size(), oldSize - subMapSize);
370    assertTrue(subMap.isEmpty());
371  }
372}
373