src/third_party/protobuf/java/src/test/java/com/google/protobuf/SmallSortedMapTest.java

   1 // Protocol Buffers - Google's data interchange format
   2 // Copyright 2008 Google Inc.  All rights reserved.
   3 // http://code.google.com/p/protobuf/
   4 //
   5 // Redistribution and use in source and binary forms, with or without
   6 // modification, are permitted provided that the following conditions are
   7 // met:
   8 //
   9 //     * Redistributions of source code must retain the above copyright
  10 // notice, this list of conditions and the following disclaimer.
  11 //     * Redistributions in binary form must reproduce the above
  12 // copyright notice, this list of conditions and the following disclaimer
  13 // in the documentation and/or other materials provided with the
  14 // distribution.
  15 //     * Neither the name of Google Inc. nor the names of its
  16 // contributors may be used to endorse or promote products derived from
  17 // this software without specific prior written permission.
  18 //
  19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30
  31 package com.google.protobuf;
  32
  33 import junit.framework.TestCase;
  34
  35 import java.util.ArrayList;
  36 import java.util.Arrays;
  37 import java.util.HashMap;
  38 import java.util.Iterator;
  39 import java.util.List;
  40 import java.util.Map;
  41 import java.util.Set;
  42 import java.util.TreeSet;
  43
  44 /**
  45  * @author darick@google.com Darick Tong
  46  */
  47 public class SmallSortedMapTest extends TestCase {
  48   // java.util.AbstractMap.SimpleEntry is private in JDK 1.5. We re-implement it
  49   // here for JDK 1.5 users.
  50   private static class SimpleEntry<K, V> implements Map.Entry<K, V> {
  51     private final K key;
  52     private V value;
  53
  54     SimpleEntry(K key, V value) {
  55       this.key = key;
  56       this.value = value;
  57     }
  58
  59     public K getKey() {
  60       return key;
  61     }
  62
  63     public V getValue() {
  64       return value;
  65     }
  66
  67     public V setValue(V value) {
  68       V oldValue = this.value;
  69       this.value = value;
  70       return oldValue;
  71     }
  72
  73     private static boolean eq(Object o1, Object o2) {
  74       return o1 == null ? o2 == null : o1.equals(o2);
  75     }
  76
  77     @Override
  78     public boolean equals(Object o) {
  79       if (!(o instanceof Map.Entry))
  80         return false;
  81       Map.Entry e = (Map.Entry) o;
  82       return eq(key, e.getKey()) && eq(value, e.getValue());
  83     }
  84
  85     @Override
  86     public int hashCode() {
  87       return ((key == null) ? 0 : key.hashCode()) ^
  88           ((value == null) ? 0 : value.hashCode());
  89     }
  90   }
  91
  92   public void testPutAndGetArrayEntriesOnly() {
  93     runPutAndGetTest(3);
  94   }
  95
  96   public void testPutAndGetOverflowEntries() {
  97     runPutAndGetTest(6);
  98   }
  99
 100   private void runPutAndGetTest(int numElements) {
 101     // Test with even and odd arraySize
 102     SmallSortedMap<Integer, Integer> map1 =
 103         SmallSortedMap.newInstanceForTest(3);
 104     SmallSortedMap<Integer, Integer> map2 =
 105         SmallSortedMap.newInstanceForTest(4);
 106     SmallSortedMap<Integer, Integer> map3 =
 107         SmallSortedMap.newInstanceForTest(3);
 108     SmallSortedMap<Integer, Integer> map4 =
 109         SmallSortedMap.newInstanceForTest(4);
 110
 111     // Test with puts in ascending order.
 112     for (int i = 0; i < numElements; i++) {
 113       assertNull(map1.put(i, i + 1));
 114       assertNull(map2.put(i, i + 1));
 115     }
 116     // Test with puts in descending order.
 117     for (int i = numElements - 1; i >= 0; i--) {
 118       assertNull(map3.put(i, i + 1));
 119       assertNull(map4.put(i, i + 1));
 120     }
 121
 122     assertEquals(Math.min(3, numElements), map1.getNumArrayEntries());
 123     assertEquals(Math.min(4, numElements), map2.getNumArrayEntries());
 124     assertEquals(Math.min(3, numElements), map3.getNumArrayEntries());
 125     assertEquals(Math.min(4, numElements), map4.getNumArrayEntries());
 126
 127     List<SmallSortedMap<Integer, Integer>> allMaps =
 128         new ArrayList<SmallSortedMap<Integer, Integer>>();
 129     allMaps.add(map1);
 130     allMaps.add(map2);
 131     allMaps.add(map3);
 132     allMaps.add(map4);
 133
 134     for (SmallSortedMap<Integer, Integer> map : allMaps) {
 135       assertEquals(numElements, map.size());
 136       for (int i = 0; i < numElements; i++) {
 137         assertEquals(new Integer(i + 1), map.get(i));
 138       }
 139     }
 140
 141     assertEquals(map1, map2);
 142     assertEquals(map2, map3);
 143     assertEquals(map3, map4);
 144   }
 145
 146   public void testReplacingPut() {
 147     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
 148     for (int i = 0; i < 6; i++) {
 149       assertNull(map.put(i, i + 1));
 150       assertNull(map.remove(i + 1));
 151     }
 152     for (int i = 0; i < 6; i++) {
 153       assertEquals(new Integer(i + 1), map.put(i, i + 2));
 154     }
 155   }
 156
 157   public void testRemove() {
 158     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
 159     for (int i = 0; i < 6; i++) {
 160       assertNull(map.put(i, i + 1));
 161       assertNull(map.remove(i + 1));
 162     }
 163
 164     assertEquals(3, map.getNumArrayEntries());
 165     assertEquals(3, map.getNumOverflowEntries());
 166     assertEquals(6,  map.size());
 167     assertEquals(makeSortedKeySet(0, 1, 2, 3, 4, 5), map.keySet());
 168
 169     assertEquals(new Integer(2), map.remove(1));
 170     assertEquals(3, map.getNumArrayEntries());
 171     assertEquals(2, map.getNumOverflowEntries());
 172     assertEquals(5,  map.size());
 173     assertEquals(makeSortedKeySet(0, 2, 3, 4, 5), map.keySet());
 174
 175     assertEquals(new Integer(5), map.remove(4));
 176     assertEquals(3, map.getNumArrayEntries());
 177     assertEquals(1, map.getNumOverflowEntries());
 178     assertEquals(4,  map.size());
 179     assertEquals(makeSortedKeySet(0, 2, 3, 5), map.keySet());
 180
 181     assertEquals(new Integer(4), map.remove(3));
 182     assertEquals(3, map.getNumArrayEntries());
 183     assertEquals(0, map.getNumOverflowEntries());
 184     assertEquals(3, map.size());
 185     assertEquals(makeSortedKeySet(0, 2, 5), map.keySet());
 186
 187     assertNull(map.remove(3));
 188     assertEquals(3, map.getNumArrayEntries());
 189     assertEquals(0, map.getNumOverflowEntries());
 190     assertEquals(3, map.size());
 191
 192     assertEquals(new Integer(1), map.remove(0));
 193     assertEquals(2, map.getNumArrayEntries());
 194     assertEquals(0, map.getNumOverflowEntries());
 195     assertEquals(2, map.size());
 196   }
 197
 198   public void testClear() {
 199     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
 200     for (int i = 0; i < 6; i++) {
 201       assertNull(map.put(i, i + 1));
 202     }
 203     map.clear();
 204     assertEquals(0, map.getNumArrayEntries());
 205     assertEquals(0, map.getNumOverflowEntries());
 206     assertEquals(0, map.size());
 207   }
 208
 209   public void testGetArrayEntryAndOverflowEntries() {
 210     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
 211     for (int i = 0; i < 6; i++) {
 212       assertNull(map.put(i, i + 1));
 213     }
 214     assertEquals(3, map.getNumArrayEntries());
 215     for (int i = 0; i < 3; i++) {
 216       Map.Entry<Integer, Integer> entry = map.getArrayEntryAt(i);
 217       assertEquals(new Integer(i), entry.getKey());
 218       assertEquals(new Integer(i + 1), entry.getValue());
 219     }
 220     Iterator<Map.Entry<Integer, Integer>> it =
 221         map.getOverflowEntries().iterator();
 222     for (int i = 3; i < 6; i++) {
 223       assertTrue(it.hasNext());
 224       Map.Entry<Integer, Integer> entry = it.next();
 225       assertEquals(new Integer(i), entry.getKey());
 226       assertEquals(new Integer(i + 1), entry.getValue());
 227     }
 228     assertFalse(it.hasNext());
 229   }
 230
 231   public void testEntrySetContains() {
 232     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
 233     for (int i = 0; i < 6; i++) {
 234       assertNull(map.put(i, i + 1));
 235     }
 236     Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
 237     for (int i = 0; i < 6; i++) {
 238       assertTrue(
 239           entrySet.contains(new SimpleEntry<Integer, Integer>(i, i + 1)));
 240       assertFalse(
 241           entrySet.contains(new SimpleEntry<Integer, Integer>(i, i)));
 242     }
 243   }
 244
 245   public void testEntrySetAdd() {
 246     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
 247     Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
 248     for (int i = 0; i < 6; i++) {
 249       Map.Entry<Integer, Integer> entry =
 250           new SimpleEntry<Integer, Integer>(i, i + 1);
 251       assertTrue(entrySet.add(entry));
 252       assertFalse(entrySet.add(entry));
 253     }
 254     for (int i = 0; i < 6; i++) {
 255       assertEquals(new Integer(i + 1), map.get(i));
 256     }
 257     assertEquals(3, map.getNumArrayEntries());
 258     assertEquals(3, map.getNumOverflowEntries());
 259     assertEquals(6, map.size());
 260   }
 261
 262   public void testEntrySetRemove() {
 263     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
 264     Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
 265     for (int i = 0; i < 6; i++) {
 266       assertNull(map.put(i, i + 1));
 267     }
 268     for (int i = 0; i < 6; i++) {
 269       Map.Entry<Integer, Integer> entry =
 270           new SimpleEntry<Integer, Integer>(i, i + 1);
 271       assertTrue(entrySet.remove(entry));
 272       assertFalse(entrySet.remove(entry));
 273     }
 274     assertTrue(map.isEmpty());
 275     assertEquals(0, map.getNumArrayEntries());
 276     assertEquals(0, map.getNumOverflowEntries());
 277     assertEquals(0, map.size());
 278   }
 279
 280   public void testEntrySetClear() {
 281     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
 282     for (int i = 0; i < 6; i++) {
 283       assertNull(map.put(i, i + 1));
 284     }
 285     map.entrySet().clear();
 286     assertTrue(map.isEmpty());
 287     assertEquals(0, map.getNumArrayEntries());
 288     assertEquals(0, map.getNumOverflowEntries());
 289     assertEquals(0, map.size());
 290   }
 291
 292   public void testEntrySetIteratorNext() {
 293     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
 294     for (int i = 0; i < 6; i++) {
 295       assertNull(map.put(i, i + 1));
 296     }
 297     Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
 298     for (int i = 0; i < 6; i++) {
 299       assertTrue(it.hasNext());
 300       Map.Entry<Integer, Integer> entry = it.next();
 301       assertEquals(new Integer(i), entry.getKey());
 302       assertEquals(new Integer(i + 1), entry.getValue());
 303     }
 304     assertFalse(it.hasNext());
 305   }
 306
 307   public void testEntrySetIteratorRemove() {
 308     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
 309     for (int i = 0; i < 6; i++) {
 310       assertNull(map.put(i, i + 1));
 311     }
 312     Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
 313     for (int i = 0; i < 6; i++) {
 314       assertTrue(map.containsKey(i));
 315       it.next();
 316       it.remove();
 317       assertFalse(map.containsKey(i));
 318       assertEquals(6 - i - 1, map.size());
 319     }
 320   }
 321
 322   public void testMapEntryModification() {
 323     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
 324     for (int i = 0; i < 6; i++) {
 325       assertNull(map.put(i, i + 1));
 326     }
 327     Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
 328     for (int i = 0; i < 6; i++) {
 329       Map.Entry<Integer, Integer> entry = it.next();
 330       entry.setValue(i + 23);
 331     }
 332     for (int i = 0; i < 6; i++) {
 333       assertEquals(new Integer(i + 23), map.get(i));
 334     }
 335   }
 336
 337   public void testMakeImmutable() {
 338     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
 339     for (int i = 0; i < 6; i++) {
 340       assertNull(map.put(i, i + 1));
 341     }
 342     map.makeImmutable();
 343     assertEquals(new Integer(1), map.get(0));
 344     assertEquals(6, map.size());
 345
 346     try {
 347       map.put(23, 23);
 348       fail("Expected UnsupportedOperationException");
 349     } catch (UnsupportedOperationException expected) {
 350     }
 351
 352     Map<Integer, Integer> other = new HashMap<Integer, Integer>();
 353     other.put(23, 23);
 354     try {
 355       map.putAll(other);
 356       fail("Expected UnsupportedOperationException");
 357     } catch (UnsupportedOperationException expected) {
 358     }
 359
 360     try {
 361       map.remove(0);
 362       fail("Expected UnsupportedOperationException");
 363     } catch (UnsupportedOperationException expected) {
 364     }
 365
 366     try {
 367       map.clear();
 368       fail("Expected UnsupportedOperationException");
 369     } catch (UnsupportedOperationException expected) {
 370     }
 371
 372     Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
 373     try {
 374       entrySet.clear();
 375       fail("Expected UnsupportedOperationException");
 376     } catch (UnsupportedOperationException expected) {
 377     }
 378
 379     Iterator<Map.Entry<Integer, Integer>> it = entrySet.iterator();
 380     while (it.hasNext()) {
 381       Map.Entry<Integer, Integer> entry = it.next();
 382       try {
 383         entry.setValue(0);
 384         fail("Expected UnsupportedOperationException");
 385       } catch (UnsupportedOperationException expected) {
 386       }
 387       try {
 388         it.remove();
 389         fail("Expected UnsupportedOperationException");
 390       } catch (UnsupportedOperationException expected) {
 391       }
 392     }
 393
 394     Set<Integer> keySet = map.keySet();
 395     try {
 396       keySet.clear();
 397       fail("Expected UnsupportedOperationException");
 398     } catch (UnsupportedOperationException expected) {
 399     }
 400
 401     Iterator<Integer> keys = keySet.iterator();
 402     while (keys.hasNext()) {
 403       Integer key = keys.next();
 404       try {
 405         keySet.remove(key);
 406         fail("Expected UnsupportedOperationException");
 407       } catch (UnsupportedOperationException expected) {
 408       }
 409       try {
 410         keys.remove();
 411         fail("Expected UnsupportedOperationException");
 412       } catch (UnsupportedOperationException expected) {
 413       }
 414     }
 415   }
 416
 417   private Set<Integer> makeSortedKeySet(Integer... keys) {
 418     return new TreeSet<Integer>(Arrays.<Integer>asList(keys));
 419   }
 420 }