1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc.  All rights reserved.
3 // https://developers.google.com/protocol-buffers/
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 
SimpleEntry(K key, V value)54     SimpleEntry(K key, V value) {
55       this.key = key;
56       this.value = value;
57     }
58 
59     @Override
getKey()60     public K getKey() {
61       return key;
62     }
63 
64     @Override
getValue()65     public V getValue() {
66       return value;
67     }
68 
69     @Override
setValue(V value)70     public V setValue(V value) {
71       V oldValue = this.value;
72       this.value = value;
73       return oldValue;
74     }
75 
eq(Object o1, Object o2)76     private static boolean eq(Object o1, Object o2) {
77       return o1 == null ? o2 == null : o1.equals(o2);
78     }
79 
80     @Override
equals(Object o)81     public boolean equals(Object o) {
82       if (!(o instanceof Map.Entry))
83         return false;
84       Map.Entry e = (Map.Entry) o;
85       return eq(key, e.getKey()) && eq(value, e.getValue());
86     }
87 
88     @Override
hashCode()89     public int hashCode() {
90       return ((key == null) ? 0 : key.hashCode()) ^
91           ((value == null) ? 0 : value.hashCode());
92     }
93   }
94 
testPutAndGetArrayEntriesOnly()95   public void testPutAndGetArrayEntriesOnly() {
96     runPutAndGetTest(3);
97   }
98 
testPutAndGetOverflowEntries()99   public void testPutAndGetOverflowEntries() {
100     runPutAndGetTest(6);
101   }
102 
runPutAndGetTest(int numElements)103   private void runPutAndGetTest(int numElements) {
104     // Test with even and odd arraySize
105     SmallSortedMap<Integer, Integer> map1 =
106         SmallSortedMap.newInstanceForTest(3);
107     SmallSortedMap<Integer, Integer> map2 =
108         SmallSortedMap.newInstanceForTest(4);
109     SmallSortedMap<Integer, Integer> map3 =
110         SmallSortedMap.newInstanceForTest(3);
111     SmallSortedMap<Integer, Integer> map4 =
112         SmallSortedMap.newInstanceForTest(4);
113 
114     // Test with puts in ascending order.
115     for (int i = 0; i < numElements; i++) {
116       assertNull(map1.put(i, i + 1));
117       assertNull(map2.put(i, i + 1));
118     }
119     // Test with puts in descending order.
120     for (int i = numElements - 1; i >= 0; i--) {
121       assertNull(map3.put(i, i + 1));
122       assertNull(map4.put(i, i + 1));
123     }
124 
125     assertEquals(Math.min(3, numElements), map1.getNumArrayEntries());
126     assertEquals(Math.min(4, numElements), map2.getNumArrayEntries());
127     assertEquals(Math.min(3, numElements), map3.getNumArrayEntries());
128     assertEquals(Math.min(4, numElements), map4.getNumArrayEntries());
129 
130     List<SmallSortedMap<Integer, Integer>> allMaps =
131         new ArrayList<SmallSortedMap<Integer, Integer>>();
132     allMaps.add(map1);
133     allMaps.add(map2);
134     allMaps.add(map3);
135     allMaps.add(map4);
136 
137     for (SmallSortedMap<Integer, Integer> map : allMaps) {
138       assertEquals(numElements, map.size());
139       for (int i = 0; i < numElements; i++) {
140         assertEquals(new Integer(i + 1), map.get(i));
141       }
142     }
143 
144     assertEquals(map1, map2);
145     assertEquals(map2, map3);
146     assertEquals(map3, map4);
147   }
148 
testReplacingPut()149   public void testReplacingPut() {
150     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
151     for (int i = 0; i < 6; i++) {
152       assertNull(map.put(i, i + 1));
153       assertNull(map.remove(i + 1));
154     }
155     for (int i = 0; i < 6; i++) {
156       assertEquals(new Integer(i + 1), map.put(i, i + 2));
157     }
158   }
159 
testRemove()160   public void testRemove() {
161     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
162     for (int i = 0; i < 6; i++) {
163       assertNull(map.put(i, i + 1));
164       assertNull(map.remove(i + 1));
165     }
166 
167     assertEquals(3, map.getNumArrayEntries());
168     assertEquals(3, map.getNumOverflowEntries());
169     assertEquals(6,  map.size());
170     assertEquals(makeSortedKeySet(0, 1, 2, 3, 4, 5), map.keySet());
171 
172     assertEquals(new Integer(2), map.remove(1));
173     assertEquals(3, map.getNumArrayEntries());
174     assertEquals(2, map.getNumOverflowEntries());
175     assertEquals(5,  map.size());
176     assertEquals(makeSortedKeySet(0, 2, 3, 4, 5), map.keySet());
177 
178     assertEquals(new Integer(5), map.remove(4));
179     assertEquals(3, map.getNumArrayEntries());
180     assertEquals(1, map.getNumOverflowEntries());
181     assertEquals(4,  map.size());
182     assertEquals(makeSortedKeySet(0, 2, 3, 5), map.keySet());
183 
184     assertEquals(new Integer(4), map.remove(3));
185     assertEquals(3, map.getNumArrayEntries());
186     assertEquals(0, map.getNumOverflowEntries());
187     assertEquals(3, map.size());
188     assertEquals(makeSortedKeySet(0, 2, 5), map.keySet());
189 
190     assertNull(map.remove(3));
191     assertEquals(3, map.getNumArrayEntries());
192     assertEquals(0, map.getNumOverflowEntries());
193     assertEquals(3, map.size());
194 
195     assertEquals(new Integer(1), map.remove(0));
196     assertEquals(2, map.getNumArrayEntries());
197     assertEquals(0, map.getNumOverflowEntries());
198     assertEquals(2, map.size());
199   }
200 
testClear()201   public void testClear() {
202     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
203     for (int i = 0; i < 6; i++) {
204       assertNull(map.put(i, i + 1));
205     }
206     map.clear();
207     assertEquals(0, map.getNumArrayEntries());
208     assertEquals(0, map.getNumOverflowEntries());
209     assertEquals(0, map.size());
210   }
211 
testGetArrayEntryAndOverflowEntries()212   public void testGetArrayEntryAndOverflowEntries() {
213     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
214     for (int i = 0; i < 6; i++) {
215       assertNull(map.put(i, i + 1));
216     }
217     assertEquals(3, map.getNumArrayEntries());
218     for (int i = 0; i < 3; i++) {
219       Map.Entry<Integer, Integer> entry = map.getArrayEntryAt(i);
220       assertEquals(new Integer(i), entry.getKey());
221       assertEquals(new Integer(i + 1), entry.getValue());
222     }
223     Iterator<Map.Entry<Integer, Integer>> it =
224         map.getOverflowEntries().iterator();
225     for (int i = 3; i < 6; i++) {
226       assertTrue(it.hasNext());
227       Map.Entry<Integer, Integer> entry = it.next();
228       assertEquals(new Integer(i), entry.getKey());
229       assertEquals(new Integer(i + 1), entry.getValue());
230     }
231     assertFalse(it.hasNext());
232   }
233 
testEntrySetContains()234   public void testEntrySetContains() {
235     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
236     for (int i = 0; i < 6; i++) {
237       assertNull(map.put(i, i + 1));
238     }
239     Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
240     for (int i = 0; i < 6; i++) {
241       assertTrue(
242           entrySet.contains(new SimpleEntry<Integer, Integer>(i, i + 1)));
243       assertFalse(
244           entrySet.contains(new SimpleEntry<Integer, Integer>(i, i)));
245     }
246   }
247 
testEntrySetAdd()248   public void testEntrySetAdd() {
249     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
250     Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
251     for (int i = 0; i < 6; i++) {
252       Map.Entry<Integer, Integer> entry =
253           new SimpleEntry<Integer, Integer>(i, i + 1);
254       assertTrue(entrySet.add(entry));
255       assertFalse(entrySet.add(entry));
256     }
257     for (int i = 0; i < 6; i++) {
258       assertEquals(new Integer(i + 1), map.get(i));
259     }
260     assertEquals(3, map.getNumArrayEntries());
261     assertEquals(3, map.getNumOverflowEntries());
262     assertEquals(6, map.size());
263   }
264 
testEntrySetRemove()265   public void testEntrySetRemove() {
266     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
267     Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
268     for (int i = 0; i < 6; i++) {
269       assertNull(map.put(i, i + 1));
270     }
271     for (int i = 0; i < 6; i++) {
272       Map.Entry<Integer, Integer> entry =
273           new SimpleEntry<Integer, Integer>(i, i + 1);
274       assertTrue(entrySet.remove(entry));
275       assertFalse(entrySet.remove(entry));
276     }
277     assertTrue(map.isEmpty());
278     assertEquals(0, map.getNumArrayEntries());
279     assertEquals(0, map.getNumOverflowEntries());
280     assertEquals(0, map.size());
281   }
282 
testEntrySetClear()283   public void testEntrySetClear() {
284     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
285     for (int i = 0; i < 6; i++) {
286       assertNull(map.put(i, i + 1));
287     }
288     map.entrySet().clear();
289     assertTrue(map.isEmpty());
290     assertEquals(0, map.getNumArrayEntries());
291     assertEquals(0, map.getNumOverflowEntries());
292     assertEquals(0, map.size());
293   }
294 
testEntrySetIteratorNext()295   public void testEntrySetIteratorNext() {
296     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
297     for (int i = 0; i < 6; i++) {
298       assertNull(map.put(i, i + 1));
299     }
300     Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
301     for (int i = 0; i < 6; i++) {
302       assertTrue(it.hasNext());
303       Map.Entry<Integer, Integer> entry = it.next();
304       assertEquals(new Integer(i), entry.getKey());
305       assertEquals(new Integer(i + 1), entry.getValue());
306     }
307     assertFalse(it.hasNext());
308   }
309 
testEntrySetIteratorRemove()310   public void testEntrySetIteratorRemove() {
311     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
312     for (int i = 0; i < 6; i++) {
313       assertNull(map.put(i, i + 1));
314     }
315     Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
316     for (int i = 0; i < 6; i++) {
317       assertTrue(map.containsKey(i));
318       it.next();
319       it.remove();
320       assertFalse(map.containsKey(i));
321       assertEquals(6 - i - 1, map.size());
322     }
323   }
324 
testMapEntryModification()325   public void testMapEntryModification() {
326     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
327     for (int i = 0; i < 6; i++) {
328       assertNull(map.put(i, i + 1));
329     }
330     Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
331     for (int i = 0; i < 6; i++) {
332       Map.Entry<Integer, Integer> entry = it.next();
333       entry.setValue(i + 23);
334     }
335     for (int i = 0; i < 6; i++) {
336       assertEquals(new Integer(i + 23), map.get(i));
337     }
338   }
339 
testMakeImmutable()340   public void testMakeImmutable() {
341     SmallSortedMap<Integer, Integer> map = SmallSortedMap.newInstanceForTest(3);
342     for (int i = 0; i < 6; i++) {
343       assertNull(map.put(i, i + 1));
344     }
345     map.makeImmutable();
346     assertEquals(new Integer(1), map.get(0));
347     assertEquals(6, map.size());
348 
349     try {
350       map.put(23, 23);
351       fail("Expected UnsupportedOperationException");
352     } catch (UnsupportedOperationException expected) {
353     }
354 
355     Map<Integer, Integer> other = new HashMap<Integer, Integer>();
356     other.put(23, 23);
357     try {
358       map.putAll(other);
359       fail("Expected UnsupportedOperationException");
360     } catch (UnsupportedOperationException expected) {
361     }
362 
363     try {
364       map.remove(0);
365       fail("Expected UnsupportedOperationException");
366     } catch (UnsupportedOperationException expected) {
367     }
368 
369     try {
370       map.clear();
371       fail("Expected UnsupportedOperationException");
372     } catch (UnsupportedOperationException expected) {
373     }
374 
375     Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
376     try {
377       entrySet.clear();
378       fail("Expected UnsupportedOperationException");
379     } catch (UnsupportedOperationException expected) {
380     }
381 
382     Iterator<Map.Entry<Integer, Integer>> it = entrySet.iterator();
383     while (it.hasNext()) {
384       Map.Entry<Integer, Integer> entry = it.next();
385       try {
386         entry.setValue(0);
387         fail("Expected UnsupportedOperationException");
388       } catch (UnsupportedOperationException expected) {
389       }
390       try {
391         it.remove();
392         fail("Expected UnsupportedOperationException");
393       } catch (UnsupportedOperationException expected) {
394       }
395     }
396 
397     Set<Integer> keySet = map.keySet();
398     try {
399       keySet.clear();
400       fail("Expected UnsupportedOperationException");
401     } catch (UnsupportedOperationException expected) {
402     }
403 
404     Iterator<Integer> keys = keySet.iterator();
405     while (keys.hasNext()) {
406       Integer key = keys.next();
407       try {
408         keySet.remove(key);
409         fail("Expected UnsupportedOperationException");
410       } catch (UnsupportedOperationException expected) {
411       }
412       try {
413         keys.remove();
414         fail("Expected UnsupportedOperationException");
415       } catch (UnsupportedOperationException expected) {
416       }
417     }
418   }
419 
makeSortedKeySet(Integer... keys)420   private Set<Integer> makeSortedKeySet(Integer... keys) {
421     return new TreeSet<Integer>(Arrays.<Integer>asList(keys));
422   }
423 }
424