diff options
Diffstat (limited to 'src')
4 files changed, 605 insertions, 19 deletions
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); } |