aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/java/com/jogamp/common/util/IntIntHashMap.java124
-rw-r--r--src/junit/com/jogamp/common/util/IntIntHashMapTest.java117
-rw-r--r--src/junit/com/jogamp/common/util/IntObjectHashMapTest.java210
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());
+ }
+
+}