1 files changed, 420 insertions, 0 deletions
diff --git a/java/src/test/java/com/google/protobuf/SmallSortedMapTest.java b/java/src/test/java/com/google/protobuf/SmallSortedMapTest.java
new file mode 100644
index 0000000..366086d
--- /dev/null
+++ b/java/src/test/java/com/google/protobuf/SmallSortedMapTest.java
@@ -0,0 +1,420 @@
+// Protocol Buffers - Google's data interchange format
+// Copyright 2008 Google Inc.  All rights reserved.
+// https://developers.google.com/protocol-buffers/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+package com.google.protobuf;
+
+import junit.framework.TestCase;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeSet;
+
+/**
+ * @author darick@google.com Darick Tong
+ */
+public class SmallSortedMapTest extends TestCase {
+  // java.util.AbstractMap.SimpleEntry is private in JDK 1.5. We re-implement it
+  // here for JDK 1.5 users.
+  private static class SimpleEntry<K, V> implements Map.Entry<K, V> {
+    private final K key;
+    private V value;
+
+    SimpleEntry(K key, V value) {
+      this.key = key;
+      this.value = value;
+    }
+
+    public K getKey() {
+      return key;
+    }
+
+    public V getValue() {
+      return value;
+    }
+
+    public V setValue(V value) {
+      V oldValue = this.value;
+      this.value = value;
+      return oldValue;
+    }
+
+    private static boolean eq(Object o1, Object o2) {
+      return o1 == null ? o2 == null : o1.equals(o2);
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      if (!(o instanceof Map.Entry))
+        return false;
+      Map.Entry e = (Map.Entry) o;
+      return eq(key, e.getKey()) && eq(value, e.getValue());
+    }
+
+    @Override
+    public int hashCode() {
+      return ((key == null) ? 0 : key.hashCode()) ^
+          ((value == null) ? 0 : value.hashCode());
+    }
+  }
+
+  public void testPutAndGetArrayEntriesOnly() {
+    runPutAndGetTest(3);
+  }
+
+  public void testPutAndGetOverflowEntries() {
+    runPutAndGetTest(6);
+  }
+
+  private void runPutAndGetTest(int numElements) {
+    // Test with even and odd arraySize
+    SmallSortedMap<Integer, Integer> map1 =
+        SmallSortedMap.newInstanceForTest(3);
+    SmallSortedMap<Integer, Integer> map2 =
+        SmallSortedMap.newInstanceForTest(4);
+    SmallSortedMap<Integer, Integer> map3 =
+        SmallSortedMap.newInstanceForTest(3);
+    SmallSortedMap<Integer, Integer> map4 =
+        SmallSortedMap.newInstanceForTest(4);
+
+    // Test with puts in ascending order.
+    for (int i = 0; i < numElements; i++) {
+      assertNull(map1.put(i, i + 1));
+      assertNull(map2.put(i, i + 1));
+    }
+    // Test with puts in descending order.
+    for (int i = numElements - 1; i >= 0; i--) {
+      assertNull(map3.put(i, i + 1));
+      assertNull(map4.put(i, i + 1));
+    }
+
+    assertEquals(Math.min(3, numElements), map1.getNumArrayEntries());
+    assertEquals(Math.min(4, numElements), map2.getNumArrayEntries());
+    assertEquals(Math.min(3, numElements), map3.getNumArrayEntries());
+    assertEquals(Math.min(4, numElements), map4.getNumArrayEntries());
+
+    List<SmallSortedMap<Integer, Integer>> allMaps =
+        new ArrayList<SmallSortedMap<Integer, Integer>>();
+    allMaps.add(map1);
+    allMaps.add(map2);
+    allMaps.add(map3);
+    allMaps.add(map4);
+
+    for (SmallSortedMap<Integer, Integer> map : allMaps) {
+      assertEquals(numElements, map.size());
+      for (int i = 0; i < numElements; i++) {
+        assertEquals(new Integer(i + 1), map.get(i));
+      }
+    }
+
+    assertEquals(map1, map2);
+    assertEquals(map2, map3);
+    assertEquals(map3, map4);
+  }
+
+  public void testReplacingPut() {
+    SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
+    for (int i = 0; i < 6; i++) {
+      assertNull(map.put(i, i + 1));
+      assertNull(map.remove(i + 1));
+    }
+    for (int i = 0; i < 6; i++) {
+      assertEquals(new Integer(i + 1), map.put(i, i + 2));
+    }
+  }
+
+  public void testRemove() {
+    SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
+    for (int i = 0; i < 6; i++) {
+      assertNull(map.put(i, i + 1));
+      assertNull(map.remove(i + 1));
+    }
+
+    assertEquals(3, map.getNumArrayEntries());
+    assertEquals(3, map.getNumOverflowEntries());
+    assertEquals(6,  map.size());
+    assertEquals(makeSortedKeySet(0, 1, 2, 3, 4, 5), map.keySet());
+
+    assertEquals(new Integer(2), map.remove(1));
+    assertEquals(3, map.getNumArrayEntries());
+    assertEquals(2, map.getNumOverflowEntries());
+    assertEquals(5,  map.size());
+    assertEquals(makeSortedKeySet(0, 2, 3, 4, 5), map.keySet());
+
+    assertEquals(new Integer(5), map.remove(4));
+    assertEquals(3, map.getNumArrayEntries());
+    assertEquals(1, map.getNumOverflowEntries());
+    assertEquals(4,  map.size());
+    assertEquals(makeSortedKeySet(0, 2, 3, 5), map.keySet());
+
+    assertEquals(new Integer(4), map.remove(3));
+    assertEquals(3, map.getNumArrayEntries());
+    assertEquals(0, map.getNumOverflowEntries());
+    assertEquals(3, map.size());
+    assertEquals(makeSortedKeySet(0, 2, 5), map.keySet());
+
+    assertNull(map.remove(3));
+    assertEquals(3, map.getNumArrayEntries());
+    assertEquals(0, map.getNumOverflowEntries());
+    assertEquals(3, map.size());
+
+    assertEquals(new Integer(1), map.remove(0));
+    assertEquals(2, map.getNumArrayEntries());
+    assertEquals(0, map.getNumOverflowEntries());
+    assertEquals(2, map.size());
+  }
+
+  public void testClear() {
+    SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
+    for (int i = 0; i < 6; i++) {
+      assertNull(map.put(i, i + 1));
+    }
+    map.clear();
+    assertEquals(0, map.getNumArrayEntries());
+    assertEquals(0, map.getNumOverflowEntries());
+    assertEquals(0, map.size());
+  }
+
+  public void testGetArrayEntryAndOverflowEntries() {
+    SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
+    for (int i = 0; i < 6; i++) {
+      assertNull(map.put(i, i + 1));
+    }
+    assertEquals(3, map.getNumArrayEntries());
+    for (int i = 0; i < 3; i++) {
+      Map.Entry<Integer, Integer> entry = map.getArrayEntryAt(i);
+      assertEquals(new Integer(i), entry.getKey());
+      assertEquals(new Integer(i + 1), entry.getValue());
+    }
+    Iterator<Map.Entry<Integer, Integer>> it =
+        map.getOverflowEntries().iterator();
+    for (int i = 3; i < 6; i++) {
+      assertTrue(it.hasNext());
+      Map.Entry<Integer, Integer> entry = it.next();
+      assertEquals(new Integer(i), entry.getKey());
+      assertEquals(new Integer(i + 1), entry.getValue());
+    }
+    assertFalse(it.hasNext());
+  }
+
+  public void testEntrySetContains() {
+    SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
+    for (int i = 0; i < 6; i++) {
+      assertNull(map.put(i, i + 1));
+    }
+    Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
+    for (int i = 0; i < 6; i++) {
+      assertTrue(
+          entrySet.contains(new SimpleEntry<Integer, Integer>(i, i + 1)));
+      assertFalse(
+          entrySet.contains(new SimpleEntry<Integer, Integer>(i, i)));
+    }
+  }
+
+  public void testEntrySetAdd() {
+    SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
+    Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
+    for (int i = 0; i < 6; i++) {
+      Map.Entry<Integer, Integer> entry =
+          new SimpleEntry<Integer, Integer>(i, i + 1);
+      assertTrue(entrySet.add(entry));
+      assertFalse(entrySet.add(entry));
+    }
+    for (int i = 0; i < 6; i++) {
+      assertEquals(new Integer(i + 1), map.get(i));
+    }
+    assertEquals(3, map.getNumArrayEntries());
+    assertEquals(3, map.getNumOverflowEntries());
+    assertEquals(6, map.size());
+  }
+
+  public void testEntrySetRemove() {
+    SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
+    Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
+    for (int i = 0; i < 6; i++) {
+      assertNull(map.put(i, i + 1));
+    }
+    for (int i = 0; i < 6; i++) {
+      Map.Entry<Integer, Integer> entry =
+          new SimpleEntry<Integer, Integer>(i, i + 1);
+      assertTrue(entrySet.remove(entry));
+      assertFalse(entrySet.remove(entry));
+    }
+    assertTrue(map.isEmpty());
+    assertEquals(0, map.getNumArrayEntries());
+    assertEquals(0, map.getNumOverflowEntries());
+    assertEquals(0, map.size());
+  }
+
+  public void testEntrySetClear() {
+    SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
+    for (int i = 0; i < 6; i++) {
+      assertNull(map.put(i, i + 1));
+    }
+    map.entrySet().clear();
+    assertTrue(map.isEmpty());
+    assertEquals(0, map.getNumArrayEntries());
+    assertEquals(0, map.getNumOverflowEntries());
+    assertEquals(0, map.size());
+  }
+
+  public void testEntrySetIteratorNext() {
+    SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
+    for (int i = 0; i < 6; i++) {
+      assertNull(map.put(i, i + 1));
+    }
+    Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
+    for (int i = 0; i < 6; i++) {
+      assertTrue(it.hasNext());
+      Map.Entry<Integer, Integer> entry = it.next();
+      assertEquals(new Integer(i), entry.getKey());
+      assertEquals(new Integer(i + 1), entry.getValue());
+    }
+    assertFalse(it.hasNext());
+  }
+
+  public void testEntrySetIteratorRemove() {
+    SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
+    for (int i = 0; i < 6; i++) {
+      assertNull(map.put(i, i + 1));
+    }
+    Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
+    for (int i = 0; i < 6; i++) {
+      assertTrue(map.containsKey(i));
+      it.next();
+      it.remove();
+      assertFalse(map.containsKey(i));
+      assertEquals(6 - i - 1, map.size());
+    }
+  }
+
+  public void testMapEntryModification() {
+    SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
+    for (int i = 0; i < 6; i++) {
+      assertNull(map.put(i, i + 1));
+    }
+    Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
+    for (int i = 0; i < 6; i++) {
+      Map.Entry<Integer, Integer> entry = it.next();
+      entry.setValue(i + 23);
+    }
+    for (int i = 0; i < 6; i++) {
+      assertEquals(new Integer(i + 23), map.get(i));
+    }
+  }
+
+  public void testMakeImmutable() {
+    SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
+    for (int i = 0; i < 6; i++) {
+      assertNull(map.put(i, i + 1));
+    }
+    map.makeImmutable();
+    assertEquals(new Integer(1), map.get(0));
+    assertEquals(6, map.size());
+
+    try {
+      map.put(23, 23);
+      fail("Expected UnsupportedOperationException");
+    } catch (UnsupportedOperationException expected) {
+    }
+
+    Map<Integer, Integer> other = new HashMap<Integer, Integer>();
+    other.put(23, 23);
+    try {
+      map.putAll(other);
+      fail("Expected UnsupportedOperationException");
+    } catch (UnsupportedOperationException expected) {
+    }
+
+    try {
+      map.remove(0);
+      fail("Expected UnsupportedOperationException");
+    } catch (UnsupportedOperationException expected) {
+    }
+
+    try {
+      map.clear();
+      fail("Expected UnsupportedOperationException");
+    } catch (UnsupportedOperationException expected) {
+    }
+
+    Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
+    try {
+      entrySet.clear();
+      fail("Expected UnsupportedOperationException");
+    } catch (UnsupportedOperationException expected) {
+    }
+
+    Iterator<Map.Entry<Integer, Integer>> it = entrySet.iterator();
+    while (it.hasNext()) {
+      Map.Entry<Integer, Integer> entry = it.next();
+      try {
+        entry.setValue(0);
+        fail("Expected UnsupportedOperationException");
+      } catch (UnsupportedOperationException expected) {
+      }
+      try {
+        it.remove();
+        fail("Expected UnsupportedOperationException");
+      } catch (UnsupportedOperationException expected) {
+      }
+    }
+
+    Set<Integer> keySet = map.keySet();
+    try {
+      keySet.clear();
+      fail("Expected UnsupportedOperationException");
+    } catch (UnsupportedOperationException expected) {
+    }
+
+    Iterator<Integer> keys = keySet.iterator();
+    while (keys.hasNext()) {
+      Integer key = keys.next();
+      try {
+        keySet.remove(key);
+        fail("Expected UnsupportedOperationException");
+      } catch (UnsupportedOperationException expected) {
+      }
+      try {
+        keys.remove();
+        fail("Expected UnsupportedOperationException");
+      } catch (UnsupportedOperationException expected) {
+      }
+    }
+  }
+
+  private Set<Integer> makeSortedKeySet(Integer... keys) {
+    return new TreeSet<Integer>(Arrays.<Integer>asList(keys));
+  }
+}