diff options
Diffstat (limited to 'src/java/com/jogamp/common')
| -rw-r--r-- | src/java/com/jogamp/common/util/ArrayHashMap.java | 305 | ||||
| -rw-r--r-- | src/java/com/jogamp/common/util/ArrayHashSet.java | 206 |
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"); + } + } } |