001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     * 
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     * 
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.apache.commons.math.util;
018    
019    import java.util.ConcurrentModificationException;
020    import java.util.HashMap;
021    import java.util.HashSet;
022    import java.util.Map;
023    import java.util.NoSuchElementException;
024    import java.util.Random;
025    import java.util.Set;
026    
027    import junit.framework.TestCase;
028    
029    /**
030     * Test cases for the {@link OpenIntToDoubleHashMap}.
031     */
032    public class OpenIntToDoubleHashMapTest extends TestCase {
033    
034        private Map<Integer, Double> javaMap = new HashMap<Integer, Double>();
035    
036        @Override
037        protected void setUp() throws Exception {
038            javaMap.put(50, 100.0);
039            javaMap.put(75, 75.0);
040            javaMap.put(25, 500.0);
041            javaMap.put(Integer.MAX_VALUE, Double.MAX_VALUE);
042            javaMap.put(0, -1.0);
043            javaMap.put(1, 0.0);
044            javaMap.put(33, -0.1);
045            javaMap.put(23234234, -242343.0);
046            javaMap.put(23321, Double.MIN_VALUE);
047            javaMap.put(-4444, 332.0);
048            javaMap.put(-1, -2323.0);
049            javaMap.put(Integer.MIN_VALUE, 44.0);
050    
051            /* Add a few more to cause the table to rehash */
052            javaMap.putAll(generate());
053    
054        }
055    
056        private Map<Integer, Double> generate() {
057            Map<Integer, Double> map = new HashMap<Integer, Double>();
058            Random r = new Random();
059            for (int i = 0; i < 2000; ++i)
060                map.put(r.nextInt(), r.nextDouble());
061            return map;
062        }
063    
064        private OpenIntToDoubleHashMap createFromJavaMap() {
065            OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
066            for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
067                map.put(mapEntry.getKey(), mapEntry.getValue());
068            }
069            return map;
070        }
071        
072        public void testPutAndGetWith0ExpectedSize() {
073            OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap(0);
074            assertPutAndGet(map);
075        }
076        
077        public void testPutAndGetWithExpectedSize() {
078            OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap(500);
079            assertPutAndGet(map);
080        }
081    
082        public void testPutAndGet() {
083            OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
084            assertPutAndGet(map);
085        }
086    
087        private void assertPutAndGet(OpenIntToDoubleHashMap map) {
088            assertPutAndGet(map, 0, new HashSet<Integer>());
089        }
090    
091        private void assertPutAndGet(OpenIntToDoubleHashMap map, int mapSize,
092                Set<Integer> keysInMap) {
093            assertEquals(mapSize, map.size());
094            for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
095                map.put(mapEntry.getKey(), mapEntry.getValue());
096                if (!keysInMap.contains(mapEntry.getKey()))
097                    ++mapSize;
098                assertEquals(mapSize, map.size());
099                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    }