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 import java.util.Map.Entry; 027 028 import org.apache.commons.math.Field; 029 import org.apache.commons.math.fraction.Fraction; 030 import org.apache.commons.math.fraction.FractionConversionException; 031 import org.apache.commons.math.fraction.FractionField; 032 033 import junit.framework.TestCase; 034 035 public class OpenIntToFieldTest extends TestCase { 036 037 private Map<Integer, Fraction> javaMap = new HashMap<Integer, Fraction>(); 038 private FractionField field = FractionField.getInstance(); 039 040 @Override 041 protected void setUp() throws Exception { 042 javaMap.put(50, new Fraction(100.0)); 043 javaMap.put(75, new Fraction(75.0)); 044 javaMap.put(25, new Fraction(500.0)); 045 javaMap.put(Integer.MAX_VALUE, new Fraction(Integer.MAX_VALUE)); 046 javaMap.put(0, new Fraction(-1.0)); 047 javaMap.put(1, new Fraction(0.0)); 048 javaMap.put(33, new Fraction(-0.1)); 049 javaMap.put(23234234, new Fraction(-242343.0)); 050 javaMap.put(23321, new Fraction (Integer.MIN_VALUE)); 051 javaMap.put(-4444, new Fraction(332.0)); 052 javaMap.put(-1, new Fraction(-2323.0)); 053 javaMap.put(Integer.MIN_VALUE, new Fraction(44.0)); 054 055 /* Add a few more to cause the table to rehash */ 056 javaMap.putAll(generate()); 057 058 } 059 060 private Map<Integer, Fraction> generate() { 061 Map<Integer, Fraction> map = new HashMap<Integer, Fraction>(); 062 Random r = new Random(); 063 double dd=0; 064 for (int i = 0; i < 2000; ++i) 065 dd = r.nextDouble(); 066 try { 067 map.put(r.nextInt(), new Fraction(dd)); 068 } catch (FractionConversionException e) { 069 throw new IllegalStateException("Invalid :"+dd, e); 070 } 071 return map; 072 } 073 074 private OpenIntToFieldHashMap<Fraction> createFromJavaMap(Field<Fraction> field) { 075 OpenIntToFieldHashMap<Fraction> map = new OpenIntToFieldHashMap<Fraction>(field); 076 for (Map.Entry<Integer, Fraction> mapEntry : javaMap.entrySet()) { 077 map.put(mapEntry.getKey(), mapEntry.getValue()); 078 } 079 return map; 080 } 081 082 public void testPutAndGetWith0ExpectedSize() { 083 OpenIntToFieldHashMap<Fraction> map = new OpenIntToFieldHashMap<Fraction>(field,0); 084 assertPutAndGet(map); 085 } 086 087 public void testPutAndGetWithExpectedSize() { 088 OpenIntToFieldHashMap<Fraction> map = new OpenIntToFieldHashMap<Fraction>(field,500); 089 assertPutAndGet(map); 090 } 091 092 public void testPutAndGet() { 093 OpenIntToFieldHashMap<Fraction> map = new OpenIntToFieldHashMap<Fraction>(field); 094 assertPutAndGet(map); 095 } 096 097 private void assertPutAndGet(OpenIntToFieldHashMap<Fraction> map) { 098 assertPutAndGet(map, 0, new HashSet<Integer>()); 099 } 100 101 private void assertPutAndGet(OpenIntToFieldHashMap<Fraction> map, int mapSize, 102 Set<Integer> keysInMap) { 103 assertEquals(mapSize, map.size()); 104 for (Map.Entry<Integer, Fraction> mapEntry : javaMap.entrySet()) { 105 map.put(mapEntry.getKey(), mapEntry.getValue()); 106 if (!keysInMap.contains(mapEntry.getKey())) 107 ++mapSize; 108 assertEquals(mapSize, map.size()); 109 assertEquals(mapEntry.getValue(), map.get(mapEntry.getKey())); 110 } 111 } 112 113 public void testPutAbsentOnExisting() { 114 OpenIntToFieldHashMap<Fraction> map = createFromJavaMap(field); 115 int size = javaMap.size(); 116 for (Map.Entry<Integer, Fraction> mapEntry : generateAbsent().entrySet()) { 117 map.put(mapEntry.getKey(), mapEntry.getValue()); 118 assertEquals(++size, map.size()); 119 assertEquals(mapEntry.getValue(), map.get(mapEntry.getKey())); 120 } 121 } 122 123 public void testPutOnExisting() { 124 OpenIntToFieldHashMap<Fraction> map = createFromJavaMap(field); 125 for (Map.Entry<Integer, Fraction> mapEntry : javaMap.entrySet()) { 126 map.put(mapEntry.getKey(), mapEntry.getValue()); 127 assertEquals(javaMap.size(), map.size()); 128 assertEquals(mapEntry.getValue(), map.get(mapEntry.getKey())); 129 } 130 } 131 132 public void testGetAbsent() { 133 Map<Integer, Fraction> generated = generateAbsent(); 134 OpenIntToFieldHashMap<Fraction> map = createFromJavaMap(field); 135 136 for (Map.Entry<Integer, Fraction> mapEntry : generated.entrySet()) 137 assertTrue(field.getZero().equals(map.get(mapEntry.getKey()))); 138 } 139 140 public void testGetFromEmpty() { 141 OpenIntToFieldHashMap<Fraction> map = new OpenIntToFieldHashMap<Fraction>(field); 142 assertTrue(field.getZero().equals(map.get(5))); 143 assertTrue(field.getZero().equals(map.get(0))); 144 assertTrue(field.getZero().equals(map.get(50))); 145 } 146 147 public void testRemove() { 148 OpenIntToFieldHashMap<Fraction> map = createFromJavaMap(field); 149 int mapSize = javaMap.size(); 150 assertEquals(mapSize, map.size()); 151 for (Map.Entry<Integer, Fraction> mapEntry : javaMap.entrySet()) { 152 map.remove(mapEntry.getKey()); 153 assertEquals(--mapSize, map.size()); 154 assertTrue(field.getZero().equals(map.get(mapEntry.getKey()))); 155 } 156 157 /* Ensure that put and get still work correctly after removals */ 158 assertPutAndGet(map); 159 } 160 161 /* This time only remove some entries */ 162 public void testRemove2() { 163 OpenIntToFieldHashMap<Fraction> map = createFromJavaMap(field); 164 int mapSize = javaMap.size(); 165 int count = 0; 166 Set<Integer> keysInMap = new HashSet<Integer>(javaMap.keySet()); 167 for (Map.Entry<Integer, Fraction> mapEntry : javaMap.entrySet()) { 168 keysInMap.remove(mapEntry.getKey()); 169 map.remove(mapEntry.getKey()); 170 assertEquals(--mapSize, map.size()); 171 assertTrue(field.getZero().equals(map.get(mapEntry.getKey()))); 172 if (count++ > 5) 173 break; 174 } 175 176 /* Ensure that put and get still work correctly after removals */ 177 assertPutAndGet(map, mapSize, keysInMap); 178 } 179 180 public void testRemoveFromEmpty() { 181 OpenIntToFieldHashMap<Fraction> map = new OpenIntToFieldHashMap<Fraction>(field); 182 assertTrue(field.getZero().equals(map.remove(50))); 183 } 184 185 public void testRemoveAbsent() { 186 Map<Integer, Fraction> generated = generateAbsent(); 187 188 OpenIntToFieldHashMap<Fraction> map = createFromJavaMap(field); 189 int mapSize = map.size(); 190 191 for (Map.Entry<Integer, Fraction> mapEntry : generated.entrySet()) { 192 map.remove(mapEntry.getKey()); 193 assertEquals(mapSize, map.size()); 194 assertTrue(field.getZero().equals(map.get(mapEntry.getKey()))); 195 } 196 } 197 198 /** 199 * Returns a map with at least 100 elements where each element is absent from javaMap. 200 */ 201 private Map<Integer, Fraction> generateAbsent() { 202 Map<Integer, Fraction> generated = new HashMap<Integer, Fraction>(); 203 do { 204 generated.putAll(generate()); 205 for (Integer key : javaMap.keySet()) 206 generated.remove(key); 207 } while (generated.size() < 100); 208 return generated; 209 } 210 211 public void testCopy() { 212 OpenIntToFieldHashMap<Fraction> copy = 213 new OpenIntToFieldHashMap<Fraction>(createFromJavaMap(field)); 214 assertEquals(javaMap.size(), copy.size()); 215 216 for (Map.Entry<Integer, Fraction> mapEntry : javaMap.entrySet()) 217 assertEquals(mapEntry.getValue(), copy.get(mapEntry.getKey())); 218 } 219 220 public void testContainsKey() { 221 OpenIntToFieldHashMap<Fraction> map = createFromJavaMap(field); 222 for (Entry<Integer, Fraction> mapEntry : javaMap.entrySet()) { 223 assertTrue(map.containsKey(mapEntry.getKey())); 224 } 225 for (Map.Entry<Integer, Fraction> mapEntry : generateAbsent().entrySet()) { 226 assertFalse(map.containsKey(mapEntry.getKey())); 227 } 228 for (Entry<Integer, Fraction> mapEntry : javaMap.entrySet()) { 229 int key = mapEntry.getKey(); 230 assertTrue(map.containsKey(key)); 231 map.remove(key); 232 assertFalse(map.containsKey(key)); 233 } 234 } 235 236 public void testIterator() { 237 OpenIntToFieldHashMap<Fraction> map = createFromJavaMap(field); 238 OpenIntToFieldHashMap<Fraction>.Iterator iterator = map.iterator(); 239 for (int i = 0; i < map.size(); ++i) { 240 assertTrue(iterator.hasNext()); 241 iterator.advance(); 242 int key = iterator.key(); 243 assertTrue(map.containsKey(key)); 244 assertEquals(javaMap.get(key), map.get(key)); 245 assertEquals(javaMap.get(key), iterator.value()); 246 assertTrue(javaMap.containsKey(key)); 247 } 248 assertFalse(iterator.hasNext()); 249 try { 250 iterator.advance(); 251 fail("an exception should have been thrown"); 252 } catch (NoSuchElementException nsee) { 253 // expected 254 } 255 } 256 257 public void testConcurrentModification() { 258 OpenIntToFieldHashMap<Fraction> map = createFromJavaMap(field); 259 OpenIntToFieldHashMap<Fraction>.Iterator iterator = map.iterator(); 260 map.put(3, new Fraction(3)); 261 try { 262 iterator.advance(); 263 fail("an exception should have been thrown"); 264 } catch (ConcurrentModificationException cme) { 265 // expected 266 } 267 } 268 269 /** 270 * Regression test for a bug in findInsertionIndex where the hashing in the second probing 271 * loop was inconsistent with the first causing duplicate keys after the right sequence 272 * of puts and removes. 273 */ 274 public void testPutKeysWithCollisions() { 275 OpenIntToFieldHashMap<Fraction> map = new OpenIntToFieldHashMap<Fraction>(field); 276 int key1 = -1996012590; 277 Fraction value1 = new Fraction(1); 278 map.put(key1, value1); 279 int key2 = 835099822; 280 map.put(key2, value1); 281 int key3 = 1008859686; 282 map.put(key3, value1); 283 assertEquals(value1, map.get(key3)); 284 assertEquals(3, map.size()); 285 286 map.remove(key2); 287 Fraction value2 = new Fraction(2); 288 map.put(key3, value2); 289 assertEquals(value2, map.get(key3)); 290 assertEquals(2, map.size()); 291 } 292 293 /** 294 * Similar to testPutKeysWithCollisions() but exercises the codepaths in a slightly 295 * different manner. 296 */ 297 public void testPutKeysWithCollision2() { 298 OpenIntToFieldHashMap<Fraction>map = new OpenIntToFieldHashMap<Fraction>(field); 299 int key1 = 837989881; 300 Fraction value1 = new Fraction(1); 301 map.put(key1, value1); 302 int key2 = 476463321; 303 map.put(key2, value1); 304 assertEquals(2, map.size()); 305 assertEquals(value1, map.get(key2)); 306 307 map.remove(key1); 308 Fraction value2 = new Fraction(2); 309 map.put(key2, value2); 310 assertEquals(1, map.size()); 311 assertEquals(value2, map.get(key2)); 312 } 313 314 315 }