third_party/protobuf/3.6.1/java/core/src/test/java/com/google/protobuf/SmallSortedMapTest.java - bazel - Git at Google

 // 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(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));
   }
 }
	// 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(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));
	}
	}