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    }