Add ArrayHashMap; Use 'supportNullValue' optimizing ArrayHashSet and ArrayHashMap; Unify ctor for both impl.

Add/Enhance unit tests for both.

2 files changed, 473 insertions, 38 deletions

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:
+ *  <ul>
+ *  <li> Unique elements utilizing {@link java.lang.Object#hashCode()} for O(1) operations, see below.</li>
+ *  <li> Java 1.5 compatible</li>
+ *  </ul>
+ *
+ * O(1) operations:
+ * <ul>
+ * <li> put new key-value-pair(s) </li>
+ * <li> test for containment </li>
+ * <li> trying to remove non existent elements </li>
+ * </ul>
+ *
+ * O(n) operations:
+ * <ul>
+ * <li> put existing key-value-pair(s) </li>
+ * <li> removing existing elements</li>
+ * </ul>
+ *
+ * For thread safety, the application shall decorate access to instances via
+ * {@link com.jogamp.common.util.locks.RecursiveLock}.
+ *
+*/
+public class ArrayHashMap<K, V>
+    implements Cloneable, Map<K, V>
+{
+    /**
+     * 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<K,V> map; // key -> object
+    private final ArrayList<V> 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<K,V>(initialCapacity, loadFactor);
+        this.data = new ArrayList<V>(initialCapacity);
+        this.supportNullValue = supportNullValue;
+    }
+
+    /**
+     * @return a shallow copy of this ArrayHashMap, elements are not copied.
+     */
+    public ArrayHashMap(final ArrayHashMap<K, V> o) {
+        map = new HashMap<K, V>(o.map);
+        data = new ArrayList<V>(o.data);
+        supportNullValue = o.supportNullValue;
+    }
+
+    /**
+     * Returns {@code true} for default behavior, i.e. {@code null} can be a valid value.
+     * <p>
+     * Returns {@code false} if {@code null} is not a valid value,
+     * here {@link #put(Object, Object)} and {@link #remove(Object)} are optimized operations.
+     * </p>
+     * @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<K, V>(this);
+    }
+
+    /**
+     * Returns this object ordered ArrayList. Use w/ care, it's not a copy.
+     * @see #toArrayList()
+     */
+    public final ArrayList<V> getData() { return data; }
+
+    /**
+     * @return a shallow copy of this ArrayHashMap's ArrayList, elements are not copied.
+     * @see #getData()
+     */
+    public final ArrayList<V> toArrayList() {
+        return new ArrayList<V>(data);
+    }
+
+    /** Returns this object hash map. Use w/ care, it's not a copy. */
+    public final HashMap<K,V> getMap() { return map; }
+
+    @Override
+    public final String toString() { return data.toString(); }
+
+    //
+    // Map
+    //
+
+    @Override
+    public final void clear() {
+        data.clear();
+        map.clear();
+    }
+
+    @Override
+    public Set<K> keySet() {
+        return map.keySet();
+    }
+
+    /**
+     * {@inheritDoc}
+     * <p>
+     * See {@link #getData()} and {@link #toArrayList()}.
+     * </p>
+     * @see #getData()
+     * @see #toArrayList()
+     */
+    @Override
+    public Collection<V> values() {
+        return map.values();
+    }
+
+    @Override
+    public Set<java.util.Map.Entry<K, V>> entrySet() {
+        return map.entrySet();
+    }
+
+    @Override
+    public final V get(final Object key) {
+        return map.get(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     * <p>
+     * This is an O(1) operation, in case the key does not exist,
+     * otherwise O(n).
+     * </p>
+     * @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<? extends K, ? extends V> m) {
+        for (final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
+            final Map.Entry<? extends K, ? extends V> e = i.next();
+            put(e.getKey(), e.getValue());
+        }
+    }
+
+    /**
+     * {@inheritDoc}
+     * <p>
+     * This is an O(1) operation, in case the key does not exist,
+     * otherwise O(n).
+     * </p>
+     */
+    @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<E>
     implements Cloneable, Collection<E>, List<E>
 {
+    /**
+     * 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<E,E> map; // object -> object
     private final ArrayList<E> data; // list of objects
+    private final boolean supportNullValue;
 
+    /**
+     * @deprecated Use {@link #ArrayHashSet(boolean, int, float)}
+     */
     public ArrayHashSet() {
-        map  = new HashMap<E,E>();
-        data = new ArrayList<E>();
+        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<E,E>(initialCapacity);
-        data = new ArrayList<E>(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<E,E>(initialCapacity, loadFactor);
-        data = new ArrayList<E>(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<E,E>(initialCapacity, loadFactor);
+        this.data = new ArrayList<E>(initialCapacity);
+        this.supportNullValue = supportNullValue;
+    }
+
+    /**
+     * @return a shallow copy of this ArrayHashSet, elements are not copied.
+     */
+    public ArrayHashSet(final ArrayHashSet<E> o) {
+        map = new HashMap<E, E>(o.map);
+        data = new ArrayList<E>(o.data);
+        supportNullValue = o.supportNullValue;
+    }
+
+    /**
+     * Returns {@code true} for default behavior, i.e. {@code null} can be a valid value.
+     * <p>
+     * Returns {@code false} if {@code null} is not a valid value,
+     * here {@link #remove(E)} and {@link #getOrAdd(Object)} are optimized operations.
+     * </p>
+     * @see #ArrayHashSet(boolean, int, float)
+     */
+    public final boolean supportsNullValue() { return supportNullValue; }
+
     //
     // Cloneable
     //
@@ -95,12 +148,7 @@ public class ArrayHashSet<E>
      */
     @Override
     public final Object clone() {
-        final ArrayList<E> clonedList = new ArrayList<E>(data);
-
-        final ArrayHashSet<E> newObj = new ArrayHashSet<E>();
-        newObj.addAll(clonedList);
-
-        return newObj;
+        return new ArrayHashSet<E>(this);
     }
 
     /** Returns this object ordered ArrayList. Use w/ care, it's not a copy. */
@@ -125,40 +173,66 @@ public class ArrayHashSet<E>
      * Add element at the end of this list, if it is not contained yet.
      * <br>
      * This is an O(1) operation
+     * <p>
+     * {@inheritDoc}
+     * </p>
      *
      * @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.
      * <br>
-     * 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).
+     * <p>
+     * {@inheritDoc}
+     * </p>
      *
      * @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<E>
      * Add all elements of given {@link java.util.Collection} at the end of this list.
      * <br>
      * This is an O(n) operation, over the given Collection size.
+     * <p>
+     * {@inheritDoc}
+     * </p>
      *
      * @return true if at least one element was added to this list,
      *         otherwise false (completely container).
@@ -184,6 +261,9 @@ public class ArrayHashSet<E>
      * Test for containment
      * <br>
      * This is an O(1) operation.
+     * <p>
+     * {@inheritDoc}
+     * </p>
      *
      * @return true if the given element is contained by this list using fast hash map,
      *         otherwise false.
@@ -197,6 +277,9 @@ public class ArrayHashSet<E>
      * Test for containment of given {@link java.util.Collection}
      * <br>
      * This is an O(n) operation, over the given Collection size.
+     * <p>
+     * {@inheritDoc}
+     * </p>
      *
      * @return true if the given Collection is completly contained by this list using hash map,
      *         otherwise false.
@@ -215,6 +298,9 @@ public class ArrayHashSet<E>
      * Remove all elements of given {@link java.util.Collection} from this list.
      * <br>
      * This is an O(n) operation.
+     * <p>
+     * {@inheritDoc}
+     * </p>
      *
      * @return true if at least one element of this list was removed,
      *         otherwise false.
@@ -233,6 +319,9 @@ public class ArrayHashSet<E>
      * remove all elements not contained by the given {@link java.util.Collection} c.
      * <br>
      * This is an O(n) operation.
+     * <p>
+     * {@inheritDoc}
+     * </p>
      *
      * @return true if at least one element of this list was removed,
      *         otherwise false.
@@ -250,6 +339,9 @@ public class ArrayHashSet<E>
 
     /**
      * This is an O(n) operation.
+     * <p>
+     * {@inheritDoc}
+     * </p>
      *
      * @return true if arrayHashSet is of type ArrayHashSet and all entries are equal
      * Performance: arrayHashSet(1)
@@ -264,6 +356,9 @@ public class ArrayHashSet<E>
 
     /**
      * This is an O(n) operation over the size of this list.
+     * <p>
+     * {@inheritDoc}
+     * </p>
      *
      * @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<E>
      * Add element at the given index in this list, if it is not contained yet.
      * <br>
      * This is an O(1) operation
+     * <p>
+     * {@inheritDoc}
+     * </p>
      *
      * @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);
     }
 
     /**
+     * <p>
+     * {@inheritDoc}
+     * </p>
      * @throws UnsupportedOperationException
      */
     @Override
-    public final boolean addAll(final int index, final Collection<? extends E> c) {
+    public final boolean addAll(final int index, final Collection<? extends E> c) throws UnsupportedOperationException {
         throw new UnsupportedOperationException("Not supported yet.");
     }
 
     /**
-     * @throws UnsupportedOperationException
+     * <p>
+     * {@inheritDoc}
+     * </p>
      */
     @Override
     public final E set(final int index, final E element) {
@@ -354,6 +463,9 @@ public class ArrayHashSet<E>
      * Remove element at given index from this list.
      * <br>
      * This is an O(n) operation.
+     * <p>
+     * {@inheritDoc}
+     * </p>
      *
      * @return the removed object
      */
@@ -370,6 +482,9 @@ public class ArrayHashSet<E>
      * Since this list is unique, equivalent to {@link #indexOf(java.lang.Object)}.
      * <br>
      * This is an O(n) operation.
+     * <p>
+     * {@inheritDoc}
+     * </p>
      *
      * @return index of element, or -1 if not found
      */
@@ -409,34 +524,44 @@ public class ArrayHashSet<E>
      * <br>
      * 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 <code>key</code> 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.<br>
-     * If the <code>key</code> is not yet contained, add it.
+     * If the <code>element</code> is not yet contained, add it.
      * <br>
      * 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 <code>key</code> hash code,
      * or add the given <code>key</code> 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<E>
         return data.contains(element);
     }
 
+    private static final void checkNull(final Object element) throws NullPointerException {
+        if( null == element ) {
+            throw new NullPointerException("Null element not supported");
+        }
+    }
 }