From c156343fec33ceea7f238b9766a9f4985fb92687 Mon Sep 17 00:00:00 2001 From: Sven Gothel Date: Wed, 1 Apr 2015 15:17:10 +0200 Subject: Add ArrayHashMap; Use 'supportNullValue' optimizing ArrayHashSet and ArrayHashMap; Unify ctor for both impl. Add/Enhance unit tests for both. --- make/scripts/runtest.sh | 5 +- src/java/com/jogamp/common/util/ArrayHashMap.java | 305 +++++++++++++++++++++ src/java/com/jogamp/common/util/ArrayHashSet.java | 206 +++++++++++--- .../com/jogamp/common/util/TestArrayHashMap01.java | 186 +++++++++++++ .../com/jogamp/common/util/TestArrayHashSet01.java | 123 +++++++-- 5 files changed, 761 insertions(+), 64 deletions(-) create mode 100644 src/java/com/jogamp/common/util/ArrayHashMap.java create mode 100644 src/junit/com/jogamp/common/util/TestArrayHashMap01.java diff --git a/make/scripts/runtest.sh b/make/scripts/runtest.sh index b93eef1..158dae5 100755 --- a/make/scripts/runtest.sh +++ b/make/scripts/runtest.sh @@ -90,7 +90,7 @@ function onetest() { #onetest com.jogamp.common.util.TestSystemPropsAndEnvs 2>&1 | tee -a $LOG #onetest com.jogamp.common.util.TestVersionInfo 2>&1 | tee -a $LOG #onetest com.jogamp.common.util.TestVersionNumber 2>&1 | tee -a $LOG -onetest com.jogamp.common.util.TestVersionSemantics 2>&1 | tee -a $LOG +#onetest com.jogamp.common.util.TestVersionSemantics 2>&1 | tee -a $LOG #onetest com.jogamp.common.util.TestIteratorIndexCORE 2>&1 | tee -a $LOG #onetest com.jogamp.common.util.locks.TestRecursiveLock01 2>&1 | tee -a $LOG #onetest com.jogamp.common.util.locks.TestRecursiveThreadGroupLock01 2>&1 | tee -a $LOG @@ -100,6 +100,7 @@ onetest com.jogamp.common.util.TestVersionSemantics 2>&1 | tee -a $LOG #onetest com.jogamp.common.util.TestFloatStack01 2>&1 | tee -a $LOG #onetest com.jogamp.common.util.TestIntegerStack01 2>&1 | tee -a $LOG #onetest com.jogamp.common.util.TestArrayHashSet01 2>&1 | tee -a $LOG +#onetest com.jogamp.common.util.TestArrayHashMap01 2>&1 | tee -a $LOG #onetest com.jogamp.common.util.IntIntHashMapTest 2>&1 | tee -a $LOG #onetest com.jogamp.common.util.IntObjectHashMapTest 2>&1 | tee -a $LOG #onetest com.jogamp.common.util.LongIntHashMapTest 2>&1 | tee -a $LOG @@ -141,7 +142,7 @@ onetest com.jogamp.common.util.TestVersionSemantics 2>&1 | tee -a $LOG #onetest com.jogamp.gluegen.jcpp.PreprocessorTest 2>&1 | tee -a $LOG #onetest com.jogamp.gluegen.test.junit.generation.Test1p1JavaEmitter 2>&1 | tee -a $LOG -#onetest com.jogamp.gluegen.test.junit.generation.Test1p2ProcAddressEmitter 2>&1 | tee -a $LOG +onetest com.jogamp.gluegen.test.junit.generation.Test1p2ProcAddressEmitter 2>&1 | tee -a $LOG #onetest com.jogamp.gluegen.test.junit.generation.Test1p2LoadJNIAndImplLib 2>&1 | tee -a $LOG #onetest com.jogamp.gluegen.test.junit.structgen.TestStructGen01 2>&1 | tee -a $LOG #onetest com.jogamp.gluegen.test.junit.structgen.TestStructGen02 2>&1 | tee -a $LOG diff --git a/src/java/com/jogamp/common/util/ArrayHashMap.java b/src/java/com/jogamp/common/util/ArrayHashMap.java new file mode 100644 index 0000000..35a484b --- /dev/null +++ b/src/java/com/jogamp/common/util/ArrayHashMap.java @@ -0,0 +1,305 @@ +/** + * Copyright 2015 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. + */ + +package com.jogamp.common.util; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.Iterator; +import java.util.Map; +import java.util.Set; + +/** + * {@link HashMap} implementation backed by an {@link ArrayList} to preserve order of values. + * + * Implementation properties are: + * + * + * O(1) operations: + * + * + * O(n) operations: + * + * + * For thread safety, the application shall decorate access to instances via + * {@link com.jogamp.common.util.locks.RecursiveLock}. + * +*/ +public class ArrayHashMap + implements Cloneable, Map +{ + /** + * Default load factor: {@value} + */ + public static final float DEFAULT_LOAD_FACTOR = 0.75f; + /** + * The default initial capacity: {@value} + */ + public static final int DEFAULT_INITIAL_CAPACITY = 16; + + private final HashMap map; // key -> object + private final ArrayList data; // list of objects + private final boolean supportNullValue; + + /** + * + * @param supportNullValue Use {@code true} for default behavior, i.e. {@code null} can be a valid value. + * Use {@code false} if {@code null} is not a valid value, + * here {@link #put(Object, Object)} and {@link #remove(Object)} will be optimized. + * @param initialCapacity use {@link #DEFAULT_INITIAL_CAPACITY} for default + * @param loadFactor use {@link #DEFAULT_LOAD_FACTOR} for default + * @see #supportsNullValue() + */ + public ArrayHashMap(final boolean supportNullValue, final int initialCapacity, final float loadFactor) { + this.map = new HashMap(initialCapacity, loadFactor); + this.data = new ArrayList(initialCapacity); + this.supportNullValue = supportNullValue; + } + + /** + * @return a shallow copy of this ArrayHashMap, elements are not copied. + */ + public ArrayHashMap(final ArrayHashMap o) { + map = new HashMap(o.map); + data = new ArrayList(o.data); + supportNullValue = o.supportNullValue; + } + + /** + * Returns {@code true} for default behavior, i.e. {@code null} can be a valid value. + *

+ * Returns {@code false} if {@code null} is not a valid value, + * here {@link #put(Object, Object)} and {@link #remove(Object)} are optimized operations. + *

+ * @see #ArrayHashMap(boolean, int, float) + */ + public final boolean supportsNullValue() { return supportNullValue; } + + // + // Cloneable + // + + /** + * Implementation uses {@link #ArrayHashMap(ArrayHashMap)}. + * @return a shallow copy of this ArrayHashMap, elements are not copied. + */ + @Override + public final Object clone() { + return new ArrayHashMap(this); + } + + /** + * Returns this object ordered ArrayList. Use w/ care, it's not a copy. + * @see #toArrayList() + */ + public final ArrayList getData() { return data; } + + /** + * @return a shallow copy of this ArrayHashMap's ArrayList, elements are not copied. + * @see #getData() + */ + public final ArrayList toArrayList() { + return new ArrayList(data); + } + + /** Returns this object hash map. Use w/ care, it's not a copy. */ + public final HashMap getMap() { return map; } + + @Override + public final String toString() { return data.toString(); } + + // + // Map + // + + @Override + public final void clear() { + data.clear(); + map.clear(); + } + + @Override + public Set keySet() { + return map.keySet(); + } + + /** + * {@inheritDoc} + *

+ * See {@link #getData()} and {@link #toArrayList()}. + *

+ * @see #getData() + * @see #toArrayList() + */ + @Override + public Collection values() { + return map.values(); + } + + @Override + public Set> entrySet() { + return map.entrySet(); + } + + @Override + public final V get(final Object key) { + return map.get(key); + } + + /** + * {@inheritDoc} + *

+ * This is an O(1) operation, in case the key does not exist, + * otherwise O(n). + *

+ * @throws NullPointerException if {@code value} is {@code null} but {@link #supportsNullValue()} == {@code false} + */ + @Override + public final V put(final K key, final V value) throws NullPointerException { + final V oldValue; + if( supportNullValue ) { + // slow path + final boolean exists = map.containsKey(key); + if(!exists) { + // !exists + if( null != ( oldValue = map.put(key, value) ) ) { + // slips a valid null .. + throw new InternalError("Already existing, but checked before: "+key+" -> "+oldValue); + } + } else { + // exists + oldValue = map.put(key, value); + if( !data.remove(oldValue) ) { + throw new InternalError("Already existing, but not in list: "+oldValue); + } + } + } else { + checkNullValue(value); + // fast path + if( null != ( oldValue = map.put(key, value) ) ) { + // exists + if( !data.remove(oldValue) ) { + throw new InternalError("Already existing, but not in list: "+oldValue); + } + } + } + if(!data.add(value)) { + throw new InternalError("Couldn't add value to list: "+value); + } + return oldValue; + } + + @Override + public void putAll(final Map m) { + for (final Iterator> i = m.entrySet().iterator(); i.hasNext(); ) { + final Map.Entry e = i.next(); + put(e.getKey(), e.getValue()); + } + } + + /** + * {@inheritDoc} + *

+ * This is an O(1) operation, in case the key does not exist, + * otherwise O(n). + *

+ */ + @Override + public final V remove(final Object key) { + if( supportNullValue ) { + if( map.containsKey(key) ) { + // exists + final V oldValue = map.remove(key); + if ( !data.remove(oldValue) ) { + throw new InternalError("Couldn't remove prev mapped pair: "+key+" -> "+oldValue); + } + return oldValue; + } + } else { + final V oldValue; + if ( null != (oldValue = map.remove(key) ) ) { + // exists + if ( !data.remove(oldValue) ) { + throw new InternalError("Couldn't remove prev mapped pair: "+key+" -> "+oldValue); + } + } + return oldValue; + } + return null; + } + + @Override + public final boolean containsKey(final Object key) { + return map.containsKey(key); + } + + @Override + public boolean containsValue(final Object value) { + return map.containsValue(value); + } + + @Override + public final boolean equals(final Object arrayHashMap) { + if ( !(arrayHashMap instanceof ArrayHashMap) ) { + return false; + } + return map.equals(((ArrayHashMap)arrayHashMap).map); + } + + @Override + public final int hashCode() { + return map.hashCode(); + } + + @Override + public final boolean isEmpty() { + return data.isEmpty(); + } + + @Override + public final int size() { + return data.size(); + } + + private static final void checkNullValue(final Object value) throws NullPointerException { + if( null == value ) { + throw new NullPointerException("Null value not supported"); + } + } +} diff --git a/src/java/com/jogamp/common/util/ArrayHashSet.java b/src/java/com/jogamp/common/util/ArrayHashSet.java index 34e84c4..8f61a8a 100644 --- a/src/java/com/jogamp/common/util/ArrayHashSet.java +++ b/src/java/com/jogamp/common/util/ArrayHashSet.java @@ -68,24 +68,77 @@ import java.util.ListIterator; public class ArrayHashSet implements Cloneable, Collection, List { + /** + * Default load factor: {@value} + */ + public static final float DEFAULT_LOAD_FACTOR = 0.75f; + /** + * The default initial capacity: {@value} + */ + public static final int DEFAULT_INITIAL_CAPACITY = 16; + private final HashMap map; // object -> object private final ArrayList data; // list of objects + private final boolean supportNullValue; + /** + * @deprecated Use {@link #ArrayHashSet(boolean, int, float)} + */ public ArrayHashSet() { - map = new HashMap(); - data = new ArrayList(); + this(true, DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } + /** + * @param initialCapacity + * @deprecated Use {@link #ArrayHashSet(boolean, int, float)} + */ public ArrayHashSet(final int initialCapacity) { - map = new HashMap(initialCapacity); - data = new ArrayList(initialCapacity); + this(true, initialCapacity, DEFAULT_LOAD_FACTOR); } + /** + * @param initialCapacity + * @param loadFactor + * @deprecated Use {@link #ArrayHashSet(boolean, int, float)} + */ public ArrayHashSet(final int initialCapacity, final float loadFactor) { - map = new HashMap(initialCapacity, loadFactor); - data = new ArrayList(initialCapacity); + this(true, initialCapacity, loadFactor); } + /** + * + * @param supportNullValue Use {@code true} for default behavior, i.e. {@code null} can be a valid value. + * Use {@code false} if {@code null} is not a valid value, + * here {@link #remove(E)} and {@link #getOrAdd(Object)} will be optimized. + * @param initialCapacity use {@link #DEFAULT_INITIAL_CAPACITY} for default + * @param loadFactor use {@link #DEFAULT_LOAD_FACTOR} for default + * @see #supportsNullValue() + */ + public ArrayHashSet(final boolean supportNullValue, final int initialCapacity, final float loadFactor) { + this.map = new HashMap(initialCapacity, loadFactor); + this.data = new ArrayList(initialCapacity); + this.supportNullValue = supportNullValue; + } + + /** + * @return a shallow copy of this ArrayHashSet, elements are not copied. + */ + public ArrayHashSet(final ArrayHashSet o) { + map = new HashMap(o.map); + data = new ArrayList(o.data); + supportNullValue = o.supportNullValue; + } + + /** + * Returns {@code true} for default behavior, i.e. {@code null} can be a valid value. + *

+ * Returns {@code false} if {@code null} is not a valid value, + * here {@link #remove(E)} and {@link #getOrAdd(Object)} are optimized operations. + *

+ * @see #ArrayHashSet(boolean, int, float) + */ + public final boolean supportsNullValue() { return supportNullValue; } + // // Cloneable // @@ -95,12 +148,7 @@ public class ArrayHashSet */ @Override public final Object clone() { - final ArrayList clonedList = new ArrayList(data); - - final ArrayHashSet newObj = new ArrayHashSet(); - newObj.addAll(clonedList); - - return newObj; + return new ArrayHashSet(this); } /** Returns this object ordered ArrayList. Use w/ care, it's not a copy. */ @@ -125,40 +173,66 @@ public class ArrayHashSet * Add element at the end of this list, if it is not contained yet. *
* This is an O(1) operation + *

+ * {@inheritDoc} + *

* * @return true if the element was added to this list, * otherwise false (already contained). + * @throws NullPointerException if {@code element} is {@code null} but {@link #supportsNullValue()} == {@code false} */ @Override - public final boolean add(final E element) { - final boolean exists = map.containsKey(element); - if(!exists) { + public final boolean add(final E element) throws NullPointerException { + if( !supportNullValue ) { + checkNull(element); + } + if( !map.containsKey(element) ) { + // !exists if(null != map.put(element, element)) { + // slips a valid null .. throw new InternalError("Already existing, but checked before: "+element); } if(!data.add(element)) { throw new InternalError("Couldn't add element: "+element); } + return true; } - return !exists; + return false; } /** * Remove element from this list. *
- * This is an O(1) operation, in case it does not exist, + * This is an O(1) operation, in case the element does not exist, * otherwise O(n). + *

+ * {@inheritDoc} + *

* * @return true if the element was removed from this list, * otherwise false (not contained). + * @throws NullPointerException if {@code element} is {@code null} but {@link #supportsNullValue()} == {@code false} */ @Override - public final boolean remove(final Object element) { - if ( null != map.remove(element) ) { - if ( ! data.remove(element) ) { - throw new InternalError("Couldn't remove prev mapped element: "+element); + public final boolean remove(final Object element) throws NullPointerException { + if( supportNullValue ) { + if( map.containsKey(element) ) { + // exists + map.remove(element); + if ( !data.remove(element) ) { + throw new InternalError("Couldn't remove prev mapped element: "+element); + } + return true; + } + } else { + checkNull(element); + if ( null != map.remove(element) ) { + // exists + if ( !data.remove(element) ) { + throw new InternalError("Couldn't remove prev mapped element: "+element); + } + return true; } - return true; } return false; } @@ -167,6 +241,9 @@ public class ArrayHashSet * Add all elements of given {@link java.util.Collection} at the end of this list. *
* This is an O(n) operation, over the given Collection size. + *

+ * {@inheritDoc} + *

* * @return true if at least one element was added to this list, * otherwise false (completely container). @@ -184,6 +261,9 @@ public class ArrayHashSet * Test for containment *
* This is an O(1) operation. + *

+ * {@inheritDoc} + *

* * @return true if the given element is contained by this list using fast hash map, * otherwise false. @@ -197,6 +277,9 @@ public class ArrayHashSet * Test for containment of given {@link java.util.Collection} *
* This is an O(n) operation, over the given Collection size. + *

+ * {@inheritDoc} + *

* * @return true if the given Collection is completly contained by this list using hash map, * otherwise false. @@ -215,6 +298,9 @@ public class ArrayHashSet * Remove all elements of given {@link java.util.Collection} from this list. *
* This is an O(n) operation. + *

+ * {@inheritDoc} + *

* * @return true if at least one element of this list was removed, * otherwise false. @@ -233,6 +319,9 @@ public class ArrayHashSet * remove all elements not contained by the given {@link java.util.Collection} c. *
* This is an O(n) operation. + *

+ * {@inheritDoc} + *

* * @return true if at least one element of this list was removed, * otherwise false. @@ -250,6 +339,9 @@ public class ArrayHashSet /** * This is an O(n) operation. + *

+ * {@inheritDoc} + *

* * @return true if arrayHashSet is of type ArrayHashSet and all entries are equal * Performance: arrayHashSet(1) @@ -264,6 +356,9 @@ public class ArrayHashSet /** * This is an O(n) operation over the size of this list. + *

+ * {@inheritDoc} + *

* * @return the hash code of this list as define in {@link java.util.List#hashCode()}, * ie hashing all elements of this list. @@ -316,30 +411,44 @@ public class ArrayHashSet * Add element at the given index in this list, if it is not contained yet. *
* This is an O(1) operation + *

+ * {@inheritDoc} + *

* * @throws IllegalArgumentException if the given element was already contained + * @throws NullPointerException if {@code element} is {@code null} but {@link #supportsNullValue()} == {@code false} */ @Override - public final void add(final int index, final E element) { + public final void add(final int index, final E element) throws IllegalArgumentException, NullPointerException { + if( !supportNullValue ) { + checkNull(element); + } if ( map.containsKey(element) ) { throw new IllegalArgumentException("Element "+element+" is already contained"); } if(null != map.put(element, element)) { + // slips a valid null .. throw new InternalError("Already existing, but checked before: "+element); } + // !exists data.add(index, element); } /** + *

+ * {@inheritDoc} + *

* @throws UnsupportedOperationException */ @Override - public final boolean addAll(final int index, final Collection c) { + public final boolean addAll(final int index, final Collection c) throws UnsupportedOperationException { throw new UnsupportedOperationException("Not supported yet."); } /** - * @throws UnsupportedOperationException + *

+ * {@inheritDoc} + *

*/ @Override public final E set(final int index, final E element) { @@ -354,6 +463,9 @@ public class ArrayHashSet * Remove element at given index from this list. *
* This is an O(n) operation. + *

+ * {@inheritDoc} + *

* * @return the removed object */ @@ -370,6 +482,9 @@ public class ArrayHashSet * Since this list is unique, equivalent to {@link #indexOf(java.lang.Object)}. *
* This is an O(n) operation. + *

+ * {@inheritDoc} + *

* * @return index of element, or -1 if not found */ @@ -409,34 +524,44 @@ public class ArrayHashSet *
* This is an O(1) operation. * - * @param key hash source to find the identical Object within this list + * @param element hash source to find the identical Object within this list * @return object from this list, identical to the given key hash code, * or null if not contained */ - public final E get(final Object key) { - return map.get(key); + public final E get(final Object element) { + return map.get(element); } /** * Identity method allowing to get the identical object, using the internal hash map.
- * If the key is not yet contained, add it. + * If the element is not yet contained, add it. *
* This is an O(1) operation. * - * @param key hash source to find the identical Object within this list + * @param element hash source to find the identical Object within this list * @return object from this list, identical to the given key hash code, * or add the given key and return it. + * @throws NullPointerException if {@code element} is {@code null} but {@link #supportsNullValue()} == {@code false} */ - public final E getOrAdd(final E key) { - final E identity = get(key); - if(null == identity) { - // object not contained yet, add it - if(!this.add(key)) { - throw new InternalError("Key not mapped, but contained in list: "+key); + public final E getOrAdd(final E element) throws NullPointerException { + if( supportNullValue ) { + if( map.containsKey(element) ) { + // existent + return map.get(element); } - return key; + } else { + checkNull(element); + final E identity = map.get(element); + if(null != identity) { + // existent + return identity; + } + } + // !existent + if(!this.add(element)) { + throw new InternalError("Element not mapped, but contained in list: "+element); } - return identity; + return element; } /** @@ -455,4 +580,9 @@ public class ArrayHashSet return data.contains(element); } + private static final void checkNull(final Object element) throws NullPointerException { + if( null == element ) { + throw new NullPointerException("Null element not supported"); + } + } } diff --git a/src/junit/com/jogamp/common/util/TestArrayHashMap01.java b/src/junit/com/jogamp/common/util/TestArrayHashMap01.java new file mode 100644 index 0000000..529612c --- /dev/null +++ b/src/junit/com/jogamp/common/util/TestArrayHashMap01.java @@ -0,0 +1,186 @@ +/** + * Copyright 2015 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. + */ + +package com.jogamp.common.util; + +import java.util.*; +import java.io.IOException; + +import org.junit.Assert; +import org.junit.Test; + +import com.jogamp.junit.util.SingletonJunitCase; + +import org.junit.FixMethodOrder; +import org.junit.runners.MethodSorters; + +@FixMethodOrder(MethodSorters.NAME_ASCENDING) +public class TestArrayHashMap01 extends SingletonJunitCase { + + public static class Dummy { + int i1, i2, i3; + + public Dummy(final int i1, final int i2, final int i3) { + this.i1 = i1; + this.i2 = i2; + this.i3 = i3; + } + + public boolean equals(final Object o) { + if(o instanceof Dummy) { + final Dummy d = (Dummy)o; + return this.i1 == d.i1 && + this.i2 == d.i2 && + this.i3 == d.i3 ; + } + return false; + } + + public final int hashCode() { + // 31 * x == (x << 5) - x + int hash = 31 + i1; + hash = ((hash << 5) - hash) + i2; + hash = ((hash << 5) - hash) + i3; + return hash; + } + + public String toString() { + return "Dummy["+super.toString()+": "+i1+", "+i2+", "+i3+"]"; + } + } + + void populate(final Map l, final int start, final int len, + final int i2, final int i3, final int expectedPlusSize) { + final int oldSize = l.size(); + for(int pos = start+len-1; pos>=start; pos--) { + l.put(pos, new Dummy(pos, i2, i3)); + } + Assert.assertEquals(expectedPlusSize, l.size() - oldSize); + } + boolean checkOrder(final List l, final int startIdx, final int start, final int len) { + for(int i=0; i l = + new ArrayHashMap(supportNullValue, + ArrayHashSet.DEFAULT_INITIAL_CAPACITY, + ArrayHashSet.DEFAULT_LOAD_FACTOR); + Assert.assertEquals(supportNullValue, l.supportsNullValue()); + final int p7_22_34_key, p7_22_34_idx; + final Dummy p7_22_34_orig; + final int p6_22_34_key, p6_22_34_idx; + final Dummy p6_22_34_orig; + { + populate(l, 10, 100, 22, 34, 100); // [109 .. 10] + Assert.assertTrue(checkOrder(l.getData(), 0, 10, 100)); + populate(l, 10, 100, 22, 34, 0); // [109 .. 10] + Assert.assertTrue(checkOrder(l.getData(), 0, 10, 100)); + populate(l, 6, 5, 22, 34, 4); // [ 9 .. 6], 10 already exists + Assert.assertTrue(checkOrder(l.getData(), 100, 6, 4)); + p7_22_34_idx = l.size() - 2; + p7_22_34_key = 7; + p7_22_34_orig = l.get(p7_22_34_key); + p6_22_34_idx = l.size() - 1; + p6_22_34_key = 6; + p6_22_34_orig = l.get(p6_22_34_key); + } + Assert.assertNotNull(p7_22_34_orig); + Assert.assertEquals(7, p7_22_34_orig.i1); + Assert.assertEquals(l.getData().get(p7_22_34_idx), p7_22_34_orig); + Assert.assertNotNull(p6_22_34_orig); + Assert.assertEquals(6, p6_22_34_orig.i1); + Assert.assertEquals(l.getData().get(p6_22_34_idx), p6_22_34_orig); + + final Dummy p7_22_34_other = new Dummy(7, 22, 34); + Assert.assertEquals(p7_22_34_other, p7_22_34_orig); + Assert.assertTrue(p7_22_34_other.hashCode() == p7_22_34_orig.hashCode()); + Assert.assertTrue(p7_22_34_other != p7_22_34_orig); // diff reference + final Dummy p6_22_34_other = new Dummy(6, 22, 34); + Assert.assertEquals(p6_22_34_other, p6_22_34_orig); + Assert.assertTrue(p6_22_34_other.hashCode() == p6_22_34_orig.hashCode()); + Assert.assertTrue(p6_22_34_other != p6_22_34_orig); // diff reference + + // fast identity .. + Dummy q = l.get(p6_22_34_key); + Assert.assertNotNull(q); + Assert.assertEquals(p6_22_34_other, q); + Assert.assertTrue(p6_22_34_other.hashCode() == q.hashCode()); + Assert.assertTrue(p6_22_34_other != q); // diff reference + Assert.assertTrue(p6_22_34_orig == q); // same reference + + Assert.assertTrue(l.containsValue(q)); + Assert.assertTrue(l.containsValue(p6_22_34_other)); // add equivalent + + q = l.put(p6_22_34_key, p6_22_34_other); // override w/ diff hash-obj + Assert.assertNotNull(q); + Assert.assertEquals(p6_22_34_other, q); + Assert.assertTrue(p6_22_34_other.hashCode() == q.hashCode()); + Assert.assertTrue(p6_22_34_other != q); // diff reference new != old (q) + Assert.assertTrue(p6_22_34_orig == q); // same reference orig == old (q) + Assert.assertTrue(checkOrder(l.getData(), 0, 10, 100)); + Assert.assertTrue(checkOrder(l.getData(), 100, 6, 4)); + + final Dummy p1_2_3 = new Dummy(1, 2, 3); // a new one .. + q = l.put(1, p1_2_3); // added test + Assert.assertNull(q); + + final Dummy pNull = null; + NullPointerException npe = null; + try { + q = l.put(0, pNull); + Assert.assertNull(q); + } catch (final NullPointerException _npe) { npe = _npe; } + if( l.supportsNullValue() ) { + Assert.assertNull(npe); + } else { + Assert.assertNotNull(npe); + } + } + + public static void main(final String args[]) throws IOException { + final String tstname = TestArrayHashMap01.class.getName(); + org.junit.runner.JUnitCore.main(tstname); + } + +} diff --git a/src/junit/com/jogamp/common/util/TestArrayHashSet01.java b/src/junit/com/jogamp/common/util/TestArrayHashSet01.java index 51db2c7..3e8fbc0 100644 --- a/src/junit/com/jogamp/common/util/TestArrayHashSet01.java +++ b/src/junit/com/jogamp/common/util/TestArrayHashSet01.java @@ -74,47 +74,99 @@ public class TestArrayHashSet01 extends SingletonJunitCase { } } - public void populate(final List l, final int start, final int len, final int i2, final int i3, final int expectedPlusSize) { + void populate(final List l, final int start, final int len, + final int i2, final int i3, final int expectedPlusSize) { final int oldSize = l.size(); - int pos = start+len-1; - while(pos>=start) { - l.add(new Dummy(pos--, i2, i3)); + for(int pos = start+len-1; pos>=start; pos--) { + l.add(new Dummy(pos, i2, i3)); } Assert.assertEquals(expectedPlusSize, l.size() - oldSize); } + boolean checkOrder(final List l, final int startIdx, final int start, final int len) { + for(int i=0; i l = new ArrayHashSet(); - populate(l, 10, 100, 22, 34, 100); // [10 .. 109] - populate(l, 10, 100, 22, 34, 0); // [10 .. 109] - populate(l, 6, 5, 22, 34, 4); // [ 6 .. 9], 10 already exists - - final Dummy p6_22_34 = new Dummy(6, 22, 34); + public void test01ArrayHashSetWithNullValue() { + testArrayHashSetImpl(true); + } + @Test + public void test02ArrayHashSetWithoutNullValue() { + testArrayHashSetImpl(false); + } + void testArrayHashSetImpl(final boolean supportNullValue) { + final ArrayHashSet l = + new ArrayHashSet(supportNullValue, + ArrayHashSet.DEFAULT_INITIAL_CAPACITY, + ArrayHashSet.DEFAULT_LOAD_FACTOR); + Assert.assertEquals(supportNullValue, l.supportsNullValue()); + final int p7_22_34_idx; + final Dummy p7_22_34_orig; + final int p6_22_34_idx; + final Dummy p6_22_34_orig; + { + populate(l, 10, 100, 22, 34, 100); // [109 .. 10] + Assert.assertTrue(checkOrder(l, 0, 10, 100)); + populate(l, 10, 100, 22, 34, 0); // [109 .. 10] + Assert.assertTrue(checkOrder(l, 0, 10, 100)); + populate(l, 6, 5, 22, 34, 4); // [ 9 .. 6], 10 already exists + Assert.assertTrue(checkOrder(l, 100, 6, 4)); + p7_22_34_idx = l.size() - 2; + p7_22_34_orig = l.get(p7_22_34_idx); + p6_22_34_idx = l.size() - 1; + p6_22_34_orig = l.get(p6_22_34_idx); + } + Assert.assertNotNull(p7_22_34_orig); + Assert.assertEquals(7, p7_22_34_orig.i1); + Assert.assertEquals(l.getData().get(p7_22_34_idx), p7_22_34_orig); + Assert.assertNotNull(p6_22_34_orig); + Assert.assertEquals(6, p6_22_34_orig.i1); + Assert.assertEquals(l.getData().get(p6_22_34_idx), p6_22_34_orig); + + final Dummy p7_22_34_other = new Dummy(7, 22, 34); + Assert.assertEquals(p7_22_34_other, p7_22_34_orig); + Assert.assertTrue(p7_22_34_other.hashCode() == p7_22_34_orig.hashCode()); + Assert.assertTrue(p7_22_34_other != p7_22_34_orig); // diff reference + final Dummy p6_22_34_other = new Dummy(6, 22, 34); + Assert.assertEquals(p6_22_34_other, p6_22_34_orig); + Assert.assertTrue(p6_22_34_other.hashCode() == p6_22_34_orig.hashCode()); + Assert.assertTrue(p6_22_34_other != p6_22_34_orig); // diff reference // slow get on position .. - final int i = l.indexOf(p6_22_34); + final int i = l.indexOf(p6_22_34_other); Dummy q = l.get(i); Assert.assertNotNull(q); - Assert.assertEquals(p6_22_34, q); - Assert.assertTrue(p6_22_34.hashCode() == q.hashCode()); - Assert.assertTrue(p6_22_34 != q); // diff reference + Assert.assertEquals(p6_22_34_other, q); + Assert.assertTrue(p6_22_34_other.hashCode() == q.hashCode()); + Assert.assertTrue(p6_22_34_other != q); // diff reference + Assert.assertTrue(p6_22_34_orig == q); // same reference // fast identity .. - q = l.get(p6_22_34); + q = l.get(p6_22_34_other); Assert.assertNotNull(q); - Assert.assertEquals(p6_22_34, q); - Assert.assertTrue(p6_22_34.hashCode() == q.hashCode()); - Assert.assertTrue(p6_22_34 != q); // diff reference + Assert.assertEquals(p6_22_34_other, q); + Assert.assertTrue(p6_22_34_other.hashCode() == q.hashCode()); + Assert.assertTrue(p6_22_34_other != q); // diff reference + Assert.assertTrue(p6_22_34_orig == q); // same reference Assert.assertTrue(!l.add(q)); // add same - Assert.assertTrue(!l.add(p6_22_34)); // add equivalent + Assert.assertTrue(!l.add(p6_22_34_other)); // add equivalent - q = l.getOrAdd(p6_22_34); // not added test + q = l.getOrAdd(p6_22_34_other); // not added test w/ diff hash-obj Assert.assertNotNull(q); - Assert.assertEquals(p6_22_34, q); - Assert.assertTrue(p6_22_34.hashCode() == q.hashCode()); - Assert.assertTrue(p6_22_34 != q); // diff reference + Assert.assertEquals(p6_22_34_other, q); + Assert.assertTrue(p6_22_34_other.hashCode() == q.hashCode()); + Assert.assertTrue(p6_22_34_other != q); // diff reference + Assert.assertTrue(p6_22_34_orig == q); // same reference + Assert.assertTrue(checkOrder(l, 0, 10, 100)); + Assert.assertTrue(checkOrder(l, 100, 6, 4)); final Dummy p1_2_3 = new Dummy(1, 2, 3); // a new one .. q = l.getOrAdd(p1_2_3); // added test @@ -122,6 +174,29 @@ public class TestArrayHashSet01 extends SingletonJunitCase { Assert.assertEquals(p1_2_3, q); Assert.assertTrue(p1_2_3.hashCode() == q.hashCode()); Assert.assertTrue(p1_2_3 == q); // _same_ reference, since getOrAdd added it + Assert.assertTrue(checkOrder(l, 0, 10, 100)); + Assert.assertTrue(checkOrder(l, 100, 6, 4)); + + final Dummy pNull = null; + NullPointerException npe = null; + try { + q = l.getOrAdd(pNull); + Assert.assertNull(q); + } catch (final NullPointerException _npe) { npe = _npe; } + if( l.supportsNullValue() ) { + Assert.assertNull(npe); + } else { + Assert.assertNotNull(npe); + } + + try { + Assert.assertTrue(l.remove(pNull)); + } catch (final NullPointerException _npe) { npe = _npe; } + if( l.supportsNullValue() ) { + Assert.assertNull(npe); + } else { + Assert.assertNotNull(npe); + } } public static void main(final String args[]) throws IOException { -- cgit v1.2.3