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