Primitive HashMap: Add deep clone(); Fix containsValue() in case of Object values (using equals(Object)); Adding junit tests for clone(), capacity and IntObjectHashMap

3 files changed, 440 insertions, 11 deletions

diff --git a/src/java/com/jogamp/common/util/IntIntHashMap.java b/src/java/com/jogamp/common/util/IntIntHashMap.java
index f449a95..487914b 100644
--- a/src/java/com/jogamp/common/util/IntIntHashMap.java
+++ b/src/java/com/jogamp/common/util/IntIntHashMap.java
@@ -31,6 +31,10 @@
  */
 package com.jogamp.common.util;
 
+import com.jogamp.common.JogampRuntimeException;
+import java.lang.reflect.Constructor;
+import java.lang.reflect.Method;
+import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Iterator;
 
@@ -45,6 +49,7 @@ import java.util.Iterator;
  *
  * @author Michael Bien
  * @author Simon Goller
+ * @author Sven Gothel
  * 
  * @see IntObjectHashMap
  * @see IntLongHashMap
@@ -52,7 +57,7 @@ import java.util.Iterator;
  * @see LongLongHashMap
  * @see LongIntHashMap
  */
-public class /*name*/IntIntHashMap/*name*/ implements Iterable {
+public class /*name*/IntIntHashMap/*name*/ implements Cloneable, Iterable {
 
     private final float loadFactor;
 
@@ -63,7 +68,33 @@ public class /*name*/IntIntHashMap/*name*/ implements Iterable {
     private int capacity;
     private int threshold;
     private /*value*/int/*value*/ keyNotFoundValue = /*null*/-1/*null*/;
-
+    
+    private static final boolean isPrimitive;
+    private static final Constructor entryConstructor;
+    private static final Method equalsMethod;
+    
+    static {
+        final Class valueClazz = /*value*/int/*value*/.class;
+        final Class keyClazz = /*key*/int/*key*/.class;
+        
+        isPrimitive = valueClazz.isPrimitive();
+        
+        Constructor c = null;
+        Method m = null;
+        if(!isPrimitive) {
+            c = ReflectionUtil.getConstructor(Entry.class, 
+                    new Class[] { keyClazz, valueClazz, Entry.class } );
+            
+            try {
+                m = valueClazz.getDeclaredMethod("equals", Object.class);
+            } catch (NoSuchMethodException ex) { 
+                throw new JogampRuntimeException("Class "+valueClazz+" doesn't support equals(Object)");
+            }
+        }
+        entryConstructor = c;
+        equalsMethod = m;
+    }
+    
     public /*name*/IntIntHashMap/*name*/() {
         this(16, 0.75f);
     }
@@ -92,12 +123,71 @@ public class /*name*/IntIntHashMap/*name*/ implements Iterable {
         this.mask = capacity - 1;
     }
 
+    private /*name*/IntIntHashMap/*name*/(float loadFactor, int table_size, int size,
+                                          int mask, int capacity, int threshold, 
+                                          /*value*/int/*value*/ keyNotFoundValue) {
+        this.loadFactor = loadFactor;
+        this.table = new Entry[table_size];
+        this.size = size;
+        
+        this.mask = mask;
+        this.capacity = capacity;
+        this.threshold = threshold;
+        
+        this.keyNotFoundValue = keyNotFoundValue;        
+    }
+    
+    /**
+     * Disclaimer: If the value type doesn't implement {@link Object#clone() clone()}, only the reference is copied.
+     * Note: Due to private fields we cannot implement a copy constructor, sorry.
+     * 
+     * @param source the primitive hash map to copy
+     */
+    @Override
+    public Object clone() {
+        /*name*/IntIntHashMap/*name*/ n = 
+                new /*name*/IntIntHashMap/*name*/(loadFactor, table.length, size, 
+                                                  mask, capacity, threshold, 
+                                                  keyNotFoundValue);
+        
+        for(int i=table.length-1; i>=0; i--) {
+            // single linked list -> ArrayList
+            final ArrayList<Entry> entries = new ArrayList();
+            Entry se = table[i];
+            while(null != se) {
+                entries.add(se);
+                se = se.next;
+            }
+            // clone ArrayList -> single linked list (bwd)
+            Entry de_next = null;
+            for(int j=entries.size()-1; j>=0; j--) {
+                se = entries.get(j);
+                if( isPrimitive ) {
+                    de_next = new Entry(se.key, se.value, de_next);
+                } else {
+                    final Object v = ReflectionUtil.callMethod(se.value, getCloneMethod(se.value));
+                    de_next = (Entry) ReflectionUtil.createInstance(entryConstructor, se.key, v, de_next);
+                }
+            }
+            // 1st elem of linked list is table entry
+            n.table[i] = de_next;
+        }          
+        return n;
+    }
+    
     public boolean containsValue(/*value*/int/*value*/ value) {
         Entry[] t = this.table;
         for (int i = t.length; i-- > 0;) {
             for (Entry e = t[i]; e != null; e = e.next) {
-                if (e.value == value) {
-                    return true;
+                if( isPrimitive ) {
+                    if (e.value == value) {
+                        return true;
+                    }
+                } else {
+                    final Boolean b = (Boolean) ReflectionUtil.callMethod(value, equalsMethod, e.value);
+                    if(b.booleanValue()) { 
+                        return true;
+                    }                    
                 }
             }
         }
@@ -138,7 +228,7 @@ public class /*name*/IntIntHashMap/*name*/ implements Iterable {
      */
 //    @SuppressWarnings(value="cast")
     public /*value*/int/*value*/ put(/*key*/int/*key*/ key, /*value*/int/*value*/ value) {
-        Entry[] t = this.table;
+        final Entry[] t = this.table;
         int index = (int) (key & mask);
         // Check if key already exists.
         for (Entry e = t[index]; e != null; e = e.next) {
@@ -154,7 +244,7 @@ public class /*name*/IntIntHashMap/*name*/ implements Iterable {
         if (size++ >= threshold) {
             // Rehash.
             int newCapacity = 2 * capacity;
-            Entry[] newTable = new Entry[newCapacity];
+            final Entry[] newTable = new Entry[newCapacity];
             /*key*/int/*key*/ bucketmask = newCapacity - 1;
             for (int j = 0; j < t.length; j++) {
                 Entry e = t[j];
@@ -224,6 +314,13 @@ public class /*name*/IntIntHashMap/*name*/ implements Iterable {
     }
 
     /**
+     * Returns the current capacity (buckets) in this map.
+     */
+    public int capacity() {
+        return capacity;
+    }
+
+    /**
      * Clears the entire map. The size is 0 after this operation.
      */
     public void clear() {
@@ -334,12 +431,12 @@ public class /*name*/IntIntHashMap/*name*/ implements Iterable {
         
         private Entry next;
 
-        private Entry(/*key*/int/*key*/ k, /*value*/int/*value*/ v, Entry n) {
+        Entry(/*key*/int/*key*/ k, /*value*/int/*value*/ v, Entry n) {
             key = k;
             value = v;
             next = n;
         }
-
+        
         /**
          * Returns the key of this entry.
          */
@@ -367,4 +464,15 @@ public class /*name*/IntIntHashMap/*name*/ implements Iterable {
         }
 
     }
+    
+    private static Method getCloneMethod(Object obj) {
+        final Class clazz = obj.getClass();
+        Method m = null;        
+        try {
+            m = clazz.getDeclaredMethod("clone");
+        } catch (NoSuchMethodException ex) { 
+            throw new JogampRuntimeException("Class "+clazz+" doesn't support clone()", ex);
+        }
+        return m;        
+    }
 }
diff --git a/src/junit/com/jogamp/common/util/IntIntHashMapTest.java b/src/junit/com/jogamp/common/util/IntIntHashMapTest.java
index 443d14f..bc03231 100644
--- a/src/junit/com/jogamp/common/util/IntIntHashMapTest.java
+++ b/src/junit/com/jogamp/common/util/IntIntHashMapTest.java
@@ -44,6 +44,7 @@ import static java.lang.System.*;
 /**
  *
  * @author Michael Bien
+ * @author Sven Gothel 
  */
 public class IntIntHashMapTest {
 
@@ -67,7 +68,6 @@ public class IntIntHashMapTest {
             rndValues[i] = valueRnd.nextInt();
             rndKeys[i] = keyRnd.nextInt();
         }
-
     }
 
     /**
@@ -116,18 +116,129 @@ public class IntIntHashMapTest {
             intmap.put(rndKeys[i], rndValues[i]);
         }
         
-        Iterator iterator = intmap.iterator();
+        Iterator<IntIntHashMap.Entry> iterator = intmap.iterator();
+        assertNotNull(iterator);
+        assertTrue(iterator.hasNext());
+
+        int n = 0;
+        while (iterator.hasNext()) {
+            IntIntHashMap.Entry entry = iterator.next();
+            assertNotNull(entry);
+            n++;
+        }
+        assertEquals(intmap.size(), n);
+
+//        out.println(intmap);
+
+    }
+
+    @Test
+    public void cloneTest() {
+
+        final int smallSize = iterations / 4 ;
+        
+        final IntIntHashMap intmap = new IntIntHashMap( smallSize + smallSize / 4,  0.75f);
+        intmap.setKeyNotFoundValue(-1);
+        
+        for (int i = 0; i < smallSize; i++) {
+            intmap.put(rndKeys[i], rndValues[i]);
+        }
+        assertEquals(intmap.size(), smallSize);
+        
+        final IntIntHashMap intmapCopy = (IntIntHashMap) intmap.clone();
+        
+        assertEquals(intmap.size(), intmapCopy.size());
+        assertEquals(intmap.getKeyNotFoundValue(), intmapCopy.getKeyNotFoundValue());
+        
+        Iterator<IntIntHashMap.Entry> iterator = intmap.iterator();
+        assertNotNull(iterator);
+        assertTrue(iterator.hasNext());
+
+        Iterator<IntIntHashMap.Entry> iteratorCopy = intmapCopy.iterator();
+        assertNotNull(iteratorCopy);
+        assertTrue(iteratorCopy.hasNext());
+        
+        int n = 0;
+        while (iterator.hasNext()) {
+            assertTrue(iteratorCopy.hasNext());
+            IntIntHashMap.Entry entry = iterator.next();
+            IntIntHashMap.Entry entryCopy = iteratorCopy.next();
+            assertNotNull(entry);
+            assertNotNull(entryCopy);
+            assertEquals(entry.key, entryCopy.key);
+            assertEquals(entry.value, entryCopy.value);
+            n++;
+        }
+        assertTrue(!iteratorCopy.hasNext());
+
+        assertEquals(intmap.size(), n);
+        assertEquals(intmapCopy.size(), n);
+
+        for (int i = 0; i < smallSize; i++) {
+            assertTrue(intmap.containsValue(rndValues[i]));
+            assertTrue(intmap.containsKey(rndKeys[i]));
+            assertTrue(intmapCopy.containsValue(rndValues[i]));
+            assertTrue(intmapCopy.containsKey(rndKeys[i]));
+        }
+        
+//        out.println(intmap);
+
+    }
+
+    @Test
+    public void capacityTest() {
+        final int fixedSize = 16; 
+        final int capacity = 32; 
+        
+        final IntIntHashMap intmap = new IntIntHashMap( capacity,  0.75f);
+        intmap.setKeyNotFoundValue(-1);
+        
+        assertEquals(intmap.capacity(), capacity);        
+        for (int i = 0; i < fixedSize; i++) {
+            intmap.put(rndKeys[i], rndValues[i]);
+        }
+        assertEquals(intmap.size(), fixedSize);
+        assertEquals(intmap.capacity(), capacity);
+        
+        final IntIntHashMap intmapCopy = (IntIntHashMap) intmap.clone();
+        
+        assertEquals(intmap.size(), intmapCopy.size());
+        assertEquals(intmap.capacity(), intmapCopy.capacity());
+        assertEquals(intmap.getKeyNotFoundValue(), intmapCopy.getKeyNotFoundValue());
+        
+        Iterator<IntIntHashMap.Entry> iterator = intmap.iterator();
         assertNotNull(iterator);
         assertTrue(iterator.hasNext());
 
+        Iterator<IntIntHashMap.Entry> iteratorCopy = intmapCopy.iterator();
+        assertNotNull(iteratorCopy);
+        assertTrue(iteratorCopy.hasNext());
+        
         int n = 0;
         while (iterator.hasNext()) {
-            IntIntHashMap.Entry entry = (IntIntHashMap.Entry)iterator.next();
+            assertTrue(iteratorCopy.hasNext());
+            IntIntHashMap.Entry entry = iterator.next();
+            IntIntHashMap.Entry entryCopy = iteratorCopy.next();
             assertNotNull(entry);
+            assertNotNull(entryCopy);
+            assertEquals(entry.key, entryCopy.key);
+            assertEquals(entry.value, entryCopy.value);
             n++;
         }
+        assertTrue(!iteratorCopy.hasNext());
+
         assertEquals(intmap.size(), n);
+        assertEquals(intmap.capacity(), capacity);
+        assertEquals(intmapCopy.size(), n);
+        assertEquals(intmapCopy.capacity(), capacity);
 
+        for (int i = 0; i < fixedSize; i++) {
+            assertTrue(intmap.containsValue(rndValues[i]));
+            assertTrue(intmap.containsKey(rndKeys[i]));
+            assertTrue(intmapCopy.containsValue(rndValues[i]));
+            assertTrue(intmapCopy.containsKey(rndKeys[i]));
+        }
+        
 //        out.println(intmap);
 
     }
diff --git a/src/junit/com/jogamp/common/util/IntObjectHashMapTest.java b/src/junit/com/jogamp/common/util/IntObjectHashMapTest.java
new file mode 100644
index 0000000..289ff7e
--- /dev/null
+++ b/src/junit/com/jogamp/common/util/IntObjectHashMapTest.java
@@ -0,0 +1,210 @@
+/**
+ * Copyright 2010 JogAmp Community. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification, are
+ * permitted provided that the following conditions are met:
+ * 
+ *    1. Redistributions of source code must retain the above copyright notice, this list of
+ *       conditions and the following disclaimer.
+ * 
+ *    2. Redistributions in binary form must reproduce the above copyright notice, this list
+ *       of conditions and the following disclaimer in the documentation and/or other materials
+ *       provided with the distribution.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY JogAmp Community ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
+ * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JogAmp Community OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ * 
+ * The views and conclusions contained in the software and documentation are those of the
+ * authors and should not be interpreted as representing official policies, either expressed
+ * or implied, of JogAmp Community.
+ */
+ 
+/**
+ * Created on Sunday, March 28 2010 21:01
+ */
+package com.jogamp.common.util;
+
+import java.io.IOException;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map.Entry;
+import java.util.Random;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+/**
+ *
+ * @author Michael Bien
+ * @author Sven Gothel 
+ */
+public class IntObjectHashMapTest {
+
+    public static class IntCloneable implements Cloneable {
+        private int i;         
+        
+        public IntCloneable(int i) { this.i = i; }    
+        
+        public int intValue() { return i; }
+        
+        @Override
+        public Object clone() {
+            return new IntCloneable(i);
+        }        
+        
+        @Override
+        public boolean equals(Object obj) {
+            if(this == obj)  { return true; }
+            if (obj instanceof IntCloneable) {
+                IntCloneable v = (IntCloneable)obj;
+                return i == v.i ;
+            }
+            return false;            
+        }
+    }
+    
+    private static int iterations;
+    private static int[] rndKeys;
+    private static IntCloneable[] rndValues;
+
+    @BeforeClass
+    public static void init() {
+
+        iterations = 20000;
+        final int keySeed = 42;
+        final int valueSeed = 23;
+
+        Random keyRnd = new Random(/*keySeed*/);
+        Random valueRnd = new Random(/*valueSeed*/);
+
+        rndKeys = new int[iterations];
+        rndValues = new IntCloneable[iterations];
+        for (int i = 0; i < iterations; i++) {
+            rndValues[i] = new IntCloneable(valueRnd.nextInt());
+            rndKeys[i] = keyRnd.nextInt();
+        }
+    }
+
+    /**
+     * Test of put method, of class IntObjectHashMap.
+     */
+    @Test
+    public void testPutRemove() {
+
+        final IntObjectHashMap intmap = new IntObjectHashMap();
+        final HashMap<Integer, IntCloneable> map = new HashMap<Integer, IntCloneable>();
+
+        // put
+        for (int i = 0; i < iterations; i++) {
+            intmap.put(rndKeys[i], rndValues[i]);
+
+            assertTrue(intmap.containsValue(rndValues[i]));
+            assertTrue(intmap.containsKey(rndKeys[i]));
+        }
+
+        for (int i = 0; i < iterations; i++) {
+            map.put(rndKeys[i], rndValues[i]);
+        }
+
+        assertEquals(map.size(), intmap.size());
+
+        for (Entry<Integer, IntCloneable> entry : map.entrySet()) {
+            assertTrue(intmap.containsKey(entry.getKey()));
+            assertTrue(intmap.containsValue(entry.getValue()));
+        }
+
+        int i = 0;
+        for (Entry<Integer, IntCloneable> entry : map.entrySet()) {
+            assertEquals(entry.getValue(), intmap.remove(entry.getKey()));
+            assertEquals(map.size() - i - 1, intmap.size());
+            i++;
+        }
+
+    }
+    
+    @Test
+    public void iteratorTest() {
+
+        final IntObjectHashMap intmap = new IntObjectHashMap(iterations);
+
+        for (int i = 0; i < iterations; i++) {
+            intmap.put(rndKeys[i], rndValues[i]);
+        }
+        
+        Iterator<IntObjectHashMap.Entry> iterator = intmap.iterator();
+        assertNotNull(iterator);
+        assertTrue(iterator.hasNext());
+
+        int n = 0;
+        while (iterator.hasNext()) {
+            IntObjectHashMap.Entry entry = iterator.next();
+            assertNotNull(entry);
+            n++;
+        }
+        assertEquals(intmap.size(), n);
+
+//        out.println(intmap);
+
+    }
+
+    @Test
+    public void cloneTest() {
+
+        final IntObjectHashMap intmap = new IntObjectHashMap(iterations);
+
+        for (int i = 0; i < iterations; i++) {
+            intmap.put(rndKeys[i], rndValues[i]);
+        }
+        
+        final IntObjectHashMap intmapCopy = (IntObjectHashMap) intmap.clone();
+        
+        assertEquals(intmap.size(), intmapCopy.size());
+        assertEquals(intmap.getKeyNotFoundValue(), intmapCopy.getKeyNotFoundValue());
+        
+        Iterator<IntObjectHashMap.Entry> iterator = intmap.iterator();
+        assertNotNull(iterator);
+        assertTrue(iterator.hasNext());
+
+        Iterator<IntObjectHashMap.Entry> iteratorCopy = intmapCopy.iterator();
+        assertNotNull(iteratorCopy);
+        assertTrue(iteratorCopy.hasNext());
+        
+        int n = 0;
+        while (iterator.hasNext()) {
+            assertTrue(iteratorCopy.hasNext());
+            IntObjectHashMap.Entry entry = iterator.next();
+            IntObjectHashMap.Entry entryCopy = iteratorCopy.next();
+            assertNotNull(entry);
+            assertNotNull(entryCopy);
+            assertEquals(entry.key, entryCopy.key);
+            assertEquals(entry.value, entryCopy.value);
+            n++;
+        }
+        assertTrue(!iteratorCopy.hasNext());
+
+        assertEquals(intmap.size(), n);
+        assertEquals(intmapCopy.size(), n);
+
+        for (int i = 0; i < iterations; i++) {
+            assertTrue(intmap.containsValue(rndValues[i]));
+            assertTrue(intmap.containsKey(rndKeys[i]));
+            assertTrue(intmapCopy.containsValue(rndValues[i]));
+            assertTrue(intmapCopy.containsKey(rndKeys[i]));
+        }
+        
+//        out.println(intmap);
+
+    }
+
+    public static void main(String args[]) throws IOException {
+        org.junit.runner.JUnitCore.main(IntObjectHashMapTest.class.getName());
+    }
+
+}