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 }