content: // 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 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;
  import junit.framework.TestCase;
  
  /** @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;
      }
  
      @Override
      public K getKey() {
        return key;
      }
  
      @Override
      public V getValue() {
        return value;
      }
  
      @Override
      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(Integer.valueOf(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(Integer.valueOf(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(Integer.valueOf(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(Integer.valueOf(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(Integer.valueOf(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(Integer.valueOf(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(Integer.valueOf(i), entry.getKey());
        assertEquals(Integer.valueOf(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(Integer.valueOf(i), entry.getKey());
        assertEquals(Integer.valueOf(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(Integer.valueOf(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.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(Integer.valueOf(i), entry.getKey());
        assertEquals(Integer.valueOf(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(Integer.valueOf(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(Integer.valueOf(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));
    }
  }
  