1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    * 
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   * 
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math.util;
18  
19  import java.util.ConcurrentModificationException;
20  import java.util.HashMap;
21  import java.util.HashSet;
22  import java.util.Map;
23  import java.util.NoSuchElementException;
24  import java.util.Random;
25  import java.util.Set;
26  import java.util.Map.Entry;
27  
28  import org.apache.commons.math.Field;
29  import org.apache.commons.math.fraction.Fraction;
30  import org.apache.commons.math.fraction.FractionConversionException;
31  import org.apache.commons.math.fraction.FractionField;
32  
33  import junit.framework.TestCase;
34  
35  public class OpenIntToFieldTest extends TestCase {
36  
37      private Map<Integer, Fraction> javaMap = new HashMap<Integer, Fraction>();
38      private FractionField field = FractionField.getInstance();
39  
40      @Override
41      protected void setUp() throws Exception {
42          javaMap.put(50, new Fraction(100.0));
43          javaMap.put(75, new Fraction(75.0));
44          javaMap.put(25, new Fraction(500.0));
45          javaMap.put(Integer.MAX_VALUE, new Fraction(Integer.MAX_VALUE));
46          javaMap.put(0, new Fraction(-1.0));
47          javaMap.put(1, new Fraction(0.0));
48          javaMap.put(33, new Fraction(-0.1));
49          javaMap.put(23234234, new Fraction(-242343.0));
50          javaMap.put(23321, new Fraction (Integer.MIN_VALUE));
51          javaMap.put(-4444, new Fraction(332.0));
52          javaMap.put(-1, new Fraction(-2323.0));
53          javaMap.put(Integer.MIN_VALUE, new Fraction(44.0));
54  
55          /* Add a few more to cause the table to rehash */
56          javaMap.putAll(generate());
57  
58      }
59  
60      private Map<Integer, Fraction> generate() {
61          Map<Integer, Fraction> map = new HashMap<Integer, Fraction>();
62          Random r = new Random();
63          double dd=0;
64          for (int i = 0; i < 2000; ++i)
65              dd = r.nextDouble(); 
66              try {
67                  map.put(r.nextInt(), new Fraction(dd));
68              } catch (FractionConversionException e) {
69                  throw new IllegalStateException("Invalid :"+dd, e);
70              }
71          return map;
72      }
73  
74      private OpenIntToFieldHashMap<Fraction> createFromJavaMap(Field<Fraction> field) {
75          OpenIntToFieldHashMap<Fraction> map = new OpenIntToFieldHashMap<Fraction>(field);
76          for (Map.Entry<Integer, Fraction> mapEntry : javaMap.entrySet()) {
77              map.put(mapEntry.getKey(), mapEntry.getValue());
78          }
79          return map;
80      }
81      
82      public void testPutAndGetWith0ExpectedSize() {
83          OpenIntToFieldHashMap<Fraction> map = new OpenIntToFieldHashMap<Fraction>(field,0);
84          assertPutAndGet(map);
85      }
86      
87      public void testPutAndGetWithExpectedSize() {
88          OpenIntToFieldHashMap<Fraction> map = new OpenIntToFieldHashMap<Fraction>(field,500);
89          assertPutAndGet(map);
90      }
91  
92      public void testPutAndGet() {
93          OpenIntToFieldHashMap<Fraction> map = new OpenIntToFieldHashMap<Fraction>(field);
94          assertPutAndGet(map);
95      }
96  
97      private void assertPutAndGet(OpenIntToFieldHashMap<Fraction> map) {
98          assertPutAndGet(map, 0, new HashSet<Integer>());
99      }
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 }