1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    * 
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   * 
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math.util;
18  
19  import java.util.ConcurrentModificationException;
20  import java.util.HashMap;
21  import java.util.HashSet;
22  import java.util.Map;
23  import java.util.NoSuchElementException;
24  import java.util.Random;
25  import java.util.Set;
26  
27  import junit.framework.TestCase;
28  
29  /**
30   * Test cases for the {@link OpenIntToDoubleHashMap}.
31   */
32  public class OpenIntToDoubleHashMapTest extends TestCase {
33  
34      private Map<Integer, Double> javaMap = new HashMap<Integer, Double>();
35  
36      @Override
37      protected void setUp() throws Exception {
38          javaMap.put(50, 100.0);
39          javaMap.put(75, 75.0);
40          javaMap.put(25, 500.0);
41          javaMap.put(Integer.MAX_VALUE, Double.MAX_VALUE);
42          javaMap.put(0, -1.0);
43          javaMap.put(1, 0.0);
44          javaMap.put(33, -0.1);
45          javaMap.put(23234234, -242343.0);
46          javaMap.put(23321, Double.MIN_VALUE);
47          javaMap.put(-4444, 332.0);
48          javaMap.put(-1, -2323.0);
49          javaMap.put(Integer.MIN_VALUE, 44.0);
50  
51          /* Add a few more to cause the table to rehash */
52          javaMap.putAll(generate());
53  
54      }
55  
56      private Map<Integer, Double> generate() {
57          Map<Integer, Double> map = new HashMap<Integer, Double>();
58          Random r = new Random();
59          for (int i = 0; i < 2000; ++i)
60              map.put(r.nextInt(), r.nextDouble());
61          return map;
62      }
63  
64      private OpenIntToDoubleHashMap createFromJavaMap() {
65          OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
66          for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
67              map.put(mapEntry.getKey(), mapEntry.getValue());
68          }
69          return map;
70      }
71      
72      public void testPutAndGetWith0ExpectedSize() {
73          OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap(0);
74          assertPutAndGet(map);
75      }
76      
77      public void testPutAndGetWithExpectedSize() {
78          OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap(500);
79          assertPutAndGet(map);
80      }
81  
82      public void testPutAndGet() {
83          OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
84          assertPutAndGet(map);
85      }
86  
87      private void assertPutAndGet(OpenIntToDoubleHashMap map) {
88          assertPutAndGet(map, 0, new HashSet<Integer>());
89      }
90  
91      private void assertPutAndGet(OpenIntToDoubleHashMap map, int mapSize,
92              Set<Integer> keysInMap) {
93          assertEquals(mapSize, map.size());
94          for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
95              map.put(mapEntry.getKey(), mapEntry.getValue());
96              if (!keysInMap.contains(mapEntry.getKey()))
97                  ++mapSize;
98              assertEquals(mapSize, map.size());
99              assertEquals(mapEntry.getValue(), map.get(mapEntry.getKey()));
100         }
101     }
102 
103     public void testPutAbsentOnExisting() {
104         OpenIntToDoubleHashMap map = createFromJavaMap();
105         int size = javaMap.size();
106         for (Map.Entry<Integer, Double> mapEntry : generateAbsent().entrySet()) {
107             map.put(mapEntry.getKey(), mapEntry.getValue());
108             assertEquals(++size, map.size());
109             assertEquals(mapEntry.getValue(), map.get(mapEntry.getKey()));
110         }
111     }
112 
113     public void testPutOnExisting() {
114         OpenIntToDoubleHashMap map = createFromJavaMap();
115         for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
116             map.put(mapEntry.getKey(), mapEntry.getValue());
117             assertEquals(javaMap.size(), map.size());
118             assertEquals(mapEntry.getValue(), map.get(mapEntry.getKey()));
119         }
120     }
121 
122     public void testGetAbsent() {
123         Map<Integer, Double> generated = generateAbsent();
124         OpenIntToDoubleHashMap map = createFromJavaMap();
125         
126         for (Map.Entry<Integer, Double> mapEntry : generated.entrySet())
127             assertTrue(Double.isNaN(map.get(mapEntry.getKey())));
128     }
129 
130     public void testGetFromEmpty() {
131         OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
132         assertTrue(Double.isNaN(map.get(5)));
133         assertTrue(Double.isNaN(map.get(0)));
134         assertTrue(Double.isNaN(map.get(50)));
135     }
136 
137     public void testRemove() {
138         OpenIntToDoubleHashMap map = createFromJavaMap();
139         int mapSize = javaMap.size();
140         assertEquals(mapSize, map.size());
141         for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
142             map.remove(mapEntry.getKey());
143             assertEquals(--mapSize, map.size());
144             assertTrue(Double.isNaN(map.get(mapEntry.getKey())));
145         }
146 
147         /* Ensure that put and get still work correctly after removals */
148         assertPutAndGet(map);
149     }
150 
151     /* This time only remove some entries */
152     public void testRemove2() {
153         OpenIntToDoubleHashMap map = createFromJavaMap();
154         int mapSize = javaMap.size();
155         int count = 0;
156         Set<Integer> keysInMap = new HashSet<Integer>(javaMap.keySet());
157         for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
158             keysInMap.remove(mapEntry.getKey());
159             map.remove(mapEntry.getKey());
160             assertEquals(--mapSize, map.size());
161             assertTrue(Double.isNaN(map.get(mapEntry.getKey())));
162             if (count++ > 5)
163                 break;
164         }
165 
166         /* Ensure that put and get still work correctly after removals */
167         assertPutAndGet(map, mapSize, keysInMap);
168     }
169 
170     public void testRemoveFromEmpty() {
171         OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
172         assertTrue(Double.isNaN(map.remove(50)));
173     }
174 
175     public void testRemoveAbsent() {
176         Map<Integer, Double> generated = generateAbsent();
177 
178         OpenIntToDoubleHashMap map = createFromJavaMap();
179         int mapSize = map.size();
180         
181         for (Map.Entry<Integer, Double> mapEntry : generated.entrySet()) {
182             map.remove(mapEntry.getKey());
183             assertEquals(mapSize, map.size());
184             assertTrue(Double.isNaN(map.get(mapEntry.getKey())));
185         }
186     }
187 
188     /**
189      * Returns a map with at least 100 elements where each element is absent from javaMap.
190      */
191     private Map<Integer, Double> generateAbsent() {
192         Map<Integer, Double> generated = new HashMap<Integer, Double>();
193         do {
194             generated.putAll(generate());
195             for (Integer key : javaMap.keySet())
196                 generated.remove(key);
197         } while (generated.size() < 100);
198         return generated;
199     }
200 
201     public void testCopy() {
202         OpenIntToDoubleHashMap copy =
203             new OpenIntToDoubleHashMap(createFromJavaMap());
204         assertEquals(javaMap.size(), copy.size());
205 
206         for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet())
207             assertEquals(mapEntry.getValue(), copy.get(mapEntry.getKey()));
208     }
209 
210     public void testContainsKey() {
211         OpenIntToDoubleHashMap map = createFromJavaMap();
212         for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
213             assertTrue(map.containsKey(mapEntry.getKey()));
214         }
215         for (Map.Entry<Integer, Double> mapEntry : generateAbsent().entrySet()) {
216             assertFalse(map.containsKey(mapEntry.getKey()));
217         }
218         for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
219             int key = mapEntry.getKey();
220             assertTrue(map.containsKey(key));
221             map.remove(key);
222             assertFalse(map.containsKey(key));
223         }
224     }
225 
226     public void testIterator() {
227         OpenIntToDoubleHashMap map = createFromJavaMap();
228         OpenIntToDoubleHashMap.Iterator iterator = map.iterator();
229         for (int i = 0; i < map.size(); ++i) {
230             assertTrue(iterator.hasNext());
231             iterator.advance();
232             int key = iterator.key();
233             assertTrue(map.containsKey(key));
234             assertEquals(javaMap.get(key), map.get(key), 0);
235             assertEquals(javaMap.get(key), iterator.value(), 0);
236             assertTrue(javaMap.containsKey(key));
237         }
238         assertFalse(iterator.hasNext());
239         try {
240             iterator.advance();
241             fail("an exception should have been thrown");
242         } catch (NoSuchElementException nsee) {
243             // expected
244         }
245     }
246 
247     public void testConcurrentModification() {
248         OpenIntToDoubleHashMap map = createFromJavaMap();
249         OpenIntToDoubleHashMap.Iterator iterator = map.iterator();
250         map.put(3, 3);
251         try {
252             iterator.advance();
253             fail("an exception should have been thrown");
254         } catch (ConcurrentModificationException cme) {
255             // expected
256         }
257     }
258 
259     /**
260      * Regression test for a bug in findInsertionIndex where the hashing in the second probing
261      * loop was inconsistent with the first causing duplicate keys after the right sequence
262      * of puts and removes.
263      */
264     public void testPutKeysWithCollisions() {
265         OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
266         int key1 = -1996012590;
267         double value1 = 1.0;
268         map.put(key1, value1);
269         int key2 = 835099822;
270         map.put(key2, value1);
271         int key3 = 1008859686;
272         map.put(key3, value1);
273         assertEquals(value1, map.get(key3));
274         assertEquals(3, map.size());
275         
276         map.remove(key2);
277         double value2 = 2.0;
278         map.put(key3, value2);
279         assertEquals(value2, map.get(key3));
280         assertEquals(2, map.size());
281     }
282     
283     /**
284      * Similar to testPutKeysWithCollisions() but exercises the codepaths in a slightly
285      * different manner.
286      */
287     public void testPutKeysWithCollision2() {
288         OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
289         int key1 = 837989881;
290         double value1 = 1.0;
291         map.put(key1, value1);
292         int key2 = 476463321;
293         map.put(key2, value1);
294         assertEquals(2, map.size());
295         assertEquals(value1, map.get(key2));
296         
297         map.remove(key1);
298         double value2 = 2.0;
299         map.put(key2, value2);
300         assertEquals(1, map.size());
301         assertEquals(value2, map.get(key2));
302     }
303 
304 }