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 }