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 }