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