Home | History | Annotate | Download | only in testing 
      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 
     17 package com.google.common.collect.testing;
     18 
     19 import java.util.ArrayList;
     20 import java.util.Collection;
     21 import java.util.Collections;
     22 import java.util.Comparator;
     23 import java.util.Iterator;
     24 import java.util.List;
     25 import java.util.Map;
     26 import java.util.Map.Entry;
     27 import java.util.NoSuchElementException;
     28 import java.util.Set;
     29 import 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.
     41 public 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