New jogamp.common.util.ArrayHashSet, providing O(1) queries/add and identity operations

5 files changed, 608 insertions, 20 deletions

diff --git a/make/scripts/runtest.sh b/make/scripts/runtest.sh
index 9484eb4..2939c2a 100644
--- a/make/scripts/runtest.sh
+++ b/make/scripts/runtest.sh
@@ -22,6 +22,8 @@ function onetest() {
     echo
 }
 
-onetest com.jogamp.common.util.TestRecursiveToolkitLock 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.TestArrayHashSet01 2>&1 | tee -a $LOG
 #onetest com.jogamp.gluegen.test.TestPointerBufferEndian 2>&1 | tee -a $LOG
 #onetest com.jogamp.gluegen.test.TestStructAccessorEndian 2>&1 | tee -a $LOG
diff --git a/src/java/com/jogamp/common/util/ArrayHashSet.java b/src/java/com/jogamp/common/util/ArrayHashSet.java
new file mode 100644
index 0000000..af1c0bd
--- /dev/null
+++ b/src/java/com/jogamp/common/util/ArrayHashSet.java
@@ -0,0 +1,372 @@
+/**
+ * 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.
+ */
+
+package com.jogamp.common.util;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
+
+/** 
+ * Hashed ArrayList implementation of the List and Collection interface.
+ *
+ * Implementation properties are:
+ *  <ul>
+ *  <li> Unique elements utilizing {@link java.lang.Object#hashCode()} for O(1) operations, see below.</li>
+ *  <li> Provides {@link java.util.List} functionality,
+ *       ie {@link java.util.List#indexOf(java.lang.Object)}
+ *       and {@link java.util.List#get(int)}, hence object identity can be implemented.</li>
+ *  <li> Object identity via {@link #get(java.lang.Object)}</li>
+ *  <li> Java 1.3 compatible</li>
+ *  </ul>
+ *
+ * O(1) operations:
+ * <ul>
+ * <li> adding new element(s) </li>
+ * <li> test for containment </li>
+ * <li> identity </li>
+ * <li> trying to remove non existent elements </li>
+ * </ul>
+ *
+ * O(n) operations:
+ * <ul>
+ * <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 ArrayHashSet
+    implements Cloneable, Collection, List
+{
+    HashMap   map  = new HashMap();   // object -> object
+    ArrayList data = new ArrayList(); // list of objects
+
+    public ArrayHashSet() {
+        clear();
+    }
+
+    //
+    // Cloneable
+    //
+
+    public final Object clone()
+                    throws CloneNotSupportedException
+    {
+        ArrayList clonedList = (ArrayList)data.clone();
+
+        ArrayHashSet newObj = new ArrayHashSet();
+        newObj.addAll(clonedList);
+
+        return newObj;
+    }
+
+    //
+    // Collection
+    //
+
+    public final void clear() {
+        data.clear();
+        map.clear();
+    }
+
+    /**
+     * Add element at the end of this list, if it is not contained yet.
+     * <br>
+     * This is an O(1) operation
+     *
+     * @return true if the element was added to this list,
+     *         otherwise false (already contained).
+     */
+    public final boolean add(Object element) {
+        boolean exists = map.containsKey(element);
+        if(!exists) {
+            if(null != map.put(element, element)) {
+                throw new InternalError("Already existing, but checked before: "+element);
+            }
+            if(!data.add(element)) {
+                throw new InternalError("Couldn't add element: "+element);
+            }
+        }
+        return !exists;
+    }
+
+    /**
+     * Remove element from this list.
+     * <br>
+     * This is an O(1) operation, in case it does not exist,
+     * otherwise O(n).
+     *
+     * @return true if the element was removed from this list,
+     *         otherwise false (not contained).
+     */
+    public final boolean remove(Object element) {
+        if ( null != map.remove(element) ) {
+            if ( ! data.remove(element) ) {
+                throw new InternalError("Couldn't remove prev mapped element: "+element);
+            }
+            return true;
+        }
+        return false;
+    }
+
+    /**
+     * 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.
+     *
+     * @return true if at least one element was added to this list,
+     *         otherwise false (completely container).
+     */
+    public final boolean addAll(Collection c) {
+        boolean mod = false;
+        for (Iterator iter = c.iterator(); iter.hasNext(); ) {
+            mod = mod || add(iter.next()) ;
+        }
+        return mod;
+    }
+
+    /**
+     * Test for containment
+     * <br>
+     * This is an O(1) operation.
+     *
+     * @return true if the given element is contained by this list,
+     *         otherwise false.
+     */
+    public final boolean contains(Object element) {
+        return map.containsKey(element);
+    }
+
+    /**
+     * Test for containment of given {@link java.util.Collection}
+     * <br>
+     * This is an O(n) operation, over the given Collection size.
+     *
+     * @return true if the given Collection is completly contained by this list,
+     *         otherwise false.
+     */
+    public final boolean containsAll(Collection c) {
+        for (Iterator iter = c.iterator(); iter.hasNext(); ) {
+            if (! this.contains(iter.next()) ) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * Remove all elements of given {@link java.util.Collection} from this list.
+     * <br>
+     * This is an O(n) operation.
+     *
+     * @return true if at least one element of this list was removed,
+     *         otherwise false.
+     */
+    public final boolean removeAll(Collection c) {
+        boolean mod = false;
+        for (Iterator iter = c.iterator(); iter.hasNext(); ) {
+            mod = this.remove(iter.next()) || mod;
+        }
+        return mod;
+    }
+
+    /**
+     * Retain all elements of the given {@link java.util.Collection} c, ie
+     * remove all elements not contained by the given {@link java.util.Collection} c.
+     * <br>
+     * This is an O(n) operation.
+     *
+     * @return true if at least one element of this list was removed,
+     *         otherwise false.
+     */
+    public final boolean retainAll(Collection c) {
+        boolean mod = false;
+        for (Iterator iter = this.iterator(); iter.hasNext(); ) {
+            Object o = iter.next();
+            if (! c.contains(o) ) {
+                mod = this.remove(o) || mod;
+            }
+        }
+        return mod;
+    }
+
+    /**
+     * This is an O(n) operation.
+     *
+     * @return true if arrayHashSet is of type ArrayHashSet and all entries are equal
+     * Performance: arrayHashSet(1)
+     */
+    public final boolean equals(Object arrayHashSet) {
+        if ( !(arrayHashSet instanceof ArrayHashSet) ) {
+            return false;
+        }
+        return data.equals(((ArrayHashSet)arrayHashSet).data);
+    }
+
+    /**
+     * This is an O(n) operation over the size of this list.
+     *
+     * @return the hash code of this list as define in {@link java.util.List#hashCode()},
+     * ie hashing all elements of this list.
+     */
+    public final int hashCode() {
+        return data.hashCode();
+    }
+
+    public final boolean isEmpty() {
+        return data.isEmpty();
+    }
+
+    public final Iterator iterator() {
+        return data.iterator();
+    }
+
+    public final int size() {
+        return data.size();
+    }
+
+    public final Object[] toArray() {
+        return data.toArray();
+    }
+
+    public final Object[] toArray(Object[] a) {
+        return data.toArray(a);
+    }
+
+    //
+    // List
+    //
+
+    public final Object get(int index) {
+        return data.get(index);
+    }
+
+    public final int indexOf(Object element) {
+        return data.indexOf(element);
+    }
+
+    public final List toList() {
+        return data;
+    }
+
+    /**
+     * Add element at the given index in this list, if it is not contained yet.
+     * <br>
+     * This is an O(1) operation
+     *
+     * @throws IllegalArgumentException if the given element was already contained
+     */
+    public final void add(int index, Object element) {
+        if ( map.containsKey(element) ) {
+            throw new IllegalArgumentException("Element "+element+" is already contained");
+        }
+        if(null != map.put(element, element)) {
+            throw new InternalError("Already existing, but checked before: "+element);
+        }
+        data.add(index, element);
+    }
+
+    /**
+     * @throws UnsupportedOperationException
+     */
+    public final boolean addAll(int index, Collection c) {
+        throw new UnsupportedOperationException("Not supported yet.");
+    }
+
+    /**
+     * @throws UnsupportedOperationException
+     */
+    public final Object set(int index, Object element) {
+        Object old = remove(index);
+        if(null!=old) {
+            add(index, element);
+        }
+        return old;
+    }
+
+    /**
+     * Remove element at given index from this list.
+     * <br>
+     * This is an O(n) operation.
+     *
+     * @return the removed object
+     */
+    public final Object remove(int index) {
+        Object o = get(index);
+        if( null!=o && remove(o) ) {
+            return o;
+        }
+        return null;
+    }
+
+    /**
+     * Since this list is unique, equivalent to {@link #indexOf(java.lang.Object)}.
+     * <br>
+     * This is an O(n) operation.
+     *
+     * @return index of element, or -1 if not found
+     */
+    public final int lastIndexOf(Object o) {
+        return indexOf(o);
+    }
+
+    public final ListIterator listIterator() {
+        return data.listIterator();
+    }
+
+    public final ListIterator listIterator(int index) {
+        return data.listIterator(index);
+    }
+
+    public final List subList(int fromIndex, int toIndex) {
+        return data.subList(fromIndex, toIndex);
+    }
+
+    //
+    // ArrayHashSet
+    //
+
+    /**
+     * Identity method allowing to fetch an equivalent object, using the internal hash map.
+     * <br>
+     * This is an O(1) operation.
+     * 
+     * @param ident argument to find an equivalent Object within this list
+     * @return the Object contained in this list equivalent to the given <code>ident</code> Object
+     */
+    public final Object get(Object ident) {
+        return map.get(ident);
+    }
+
+}
diff --git a/src/junit/com/jogamp/common/util/TestArrayHashSet01.java b/src/junit/com/jogamp/common/util/TestArrayHashSet01.java
new file mode 100644
index 0000000..5486671
--- /dev/null
+++ b/src/junit/com/jogamp/common/util/TestArrayHashSet01.java
@@ -0,0 +1,117 @@
+/**
+ * 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.
+ */
+ 
+package com.jogamp.common.util;
+
+import java.util.*;
+import java.io.IOException;
+
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.BeforeClass;
+import org.junit.AfterClass;
+import org.junit.Test;
+
+public class TestArrayHashSet01 {
+
+    public static class Dummy {
+        int i1, i2, i3;
+
+        public Dummy(int i1, int i2, int i3) {
+            this.i1 = i1;
+            this.i2 = i2;
+            this.i3 = i3;
+        }
+
+        public boolean equals(Object o) {
+            if(o instanceof Dummy) {
+                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+"]";
+        }
+    }
+
+    public void populate(List l, int start, int len, int i2, int i3, int expectedPlusSize) {
+        int oldSize = l.size();
+        int pos = start+len-1;
+        while(pos>=start) {
+            l.add(new Dummy(pos--, i2, i3));
+        }
+        Assert.assertEquals(expectedPlusSize, l.size() - oldSize);
+    }
+
+    @Test
+    public void test01ArrayHashSet() {
+        int sum=0;
+        ArrayHashSet 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
+
+        Dummy p6_22_34 = new Dummy(6, 22, 34);
+
+        // slow get on position ..
+        int i = l.indexOf(p6_22_34);
+        Dummy q = (Dummy) 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
+
+        // fast identity ..
+        q = (Dummy) l.get(p6_22_34);
+        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.assertTrue(!l.add(q)); // add same
+        Assert.assertTrue(!l.add(p6_22_34)); // add equivalent
+    }
+
+    public static void main(String args[]) throws IOException {
+        String tstname = TestArrayHashSet01.class.getName();
+        org.junit.runner.JUnitCore.main(tstname);
+    }
+
+}
diff --git a/src/junit/com/jogamp/common/util/TestIteratorIndexCORE.java b/src/junit/com/jogamp/common/util/TestIteratorIndexCORE.java
new file mode 100644
index 0000000..0a3bd31
--- /dev/null
+++ b/src/junit/com/jogamp/common/util/TestIteratorIndexCORE.java
@@ -0,0 +1,116 @@
+/**
+ * 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.
+ */
+ 
+package com.jogamp.common.util;
+
+import java.util.*;
+import java.io.IOException;
+
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.BeforeClass;
+import org.junit.AfterClass;
+import org.junit.Test;
+
+public class TestIteratorIndexCORE {
+
+    static int elems = 10;
+    static int loop = 9999999;
+
+    public void populate(List l, int len) {
+        while(len>0) {
+            l.add(new Integer(len--));
+        }
+    }
+
+    @Test
+    public void test01ArrayListIterator() {
+        int sum=0;
+        ArrayList l = new ArrayList();
+        populate(l, elems);
+
+        for(int j=loop; j>0; j--) {
+            for(Iterator iter = l.iterator(); iter.hasNext(); ) {
+                Integer i = (Integer)iter.next();
+                sum+=i.intValue();
+            }
+        }
+        System.err.println("test01-arraylist-iterator sum: "+sum);
+    }
+
+    @Test
+    public void test0ArrayListIndex() {
+        int sum=0;
+        ArrayList l = new ArrayList();
+        populate(l, elems);
+
+        for(int j=loop; j>0; j--) {
+            for(int k = 0; k < l.size(); k++) {
+                Integer i = (Integer)l.get(k);
+                sum+=i.intValue();
+            }
+        }
+        System.err.println("test01-arraylist-index sum: "+sum);
+    }
+
+    @Test
+    public void test01LinkedListListIterator() {
+        int sum=0;
+        LinkedList l = new LinkedList();
+        populate(l, elems);
+
+        for(int j=loop; j>0; j--) {
+            for(Iterator iter = l.iterator(); iter.hasNext(); ) {
+                Integer i = (Integer)iter.next();
+                sum+=i.intValue();
+            }
+        }
+        System.err.println("test01-linkedlist-iterator sum: "+sum);
+    }
+
+    @Test
+    public void test01LinkedListListIndex() {
+        int sum=0;
+        LinkedList l = new LinkedList();
+        populate(l, elems);
+
+        for(int j=loop; j>0; j--) {
+            for(int k = 0; k < l.size(); k++) {
+                Integer i = (Integer)l.get(k);
+                sum+=i.intValue();
+            }
+        }
+        System.err.println("test01-linkedlist-index sum: "+sum);
+    }
+
+    public static void main(String args[]) throws IOException {
+        String tstname = TestIteratorIndexCORE.class.getName();
+        org.junit.runner.JUnitCore.main(tstname);
+    }
+
+}
diff --git a/src/junit/com/jogamp/common/util/locks/TestRecursiveLock01.java b/src/junit/com/jogamp/common/util/locks/TestRecursiveLock01.java
index e7560d9..ff3c4e0 100644
--- a/src/junit/com/jogamp/common/util/locks/TestRecursiveLock01.java
+++ b/src/junit/com/jogamp/common/util/locks/TestRecursiveLock01.java
@@ -254,26 +254,7 @@ public class TestRecursiveLock01 {
     }
 
     public static void main(String args[]) throws IOException {
-        /*for(int i=0; i<args.length; i++) {
-            if(args[i].equals("-time")) {
-                durationPerTest = atoi(args[++i]);
-            }
-        }
-        System.out.println("durationPerTest: "+durationPerTest);
-        */
         String tstname = TestRecursiveLock01.class.getName();
-        /*
-        org.apache.tools.ant.taskdefs.optional.junit.JUnitTestRunner.main(new String[] {
-            tstname,
-            "filtertrace=true",
-            "haltOnError=false",
-            "haltOnFailure=false",
-            "showoutput=true",
-            "outputtoformatters=true",
-            "logfailedtests=true",
-            "logtestlistenerevents=true",
-            "formatter=org.apache.tools.ant.taskdefs.optional.junit.PlainJUnitResultFormatter",
-            "formatter=org.apache.tools.ant.taskdefs.optional.junit.XMLJUnitResultFormatter,TEST-"+tstname+".xml" } ); */
         org.junit.runner.JUnitCore.main(tstname);
     }