X-Git-Url: https://gerrit.simantics.org/r/gitweb?p=simantics%2Fplatform.git;a=blobdiff_plain;f=bundles%2Forg.simantics.utils.datastructures%2Fsrc%2Forg%2Fsimantics%2Futils%2Fdatastructures%2FInterlacedArrayMap.java;fp=bundles%2Forg.simantics.utils.datastructures%2Fsrc%2Forg%2Fsimantics%2Futils%2Fdatastructures%2FInterlacedArrayMap.java;h=6ea16dd52b0bece077758d1c4563e172b9b8fe44;hp=0000000000000000000000000000000000000000;hb=c125a1755cc7c4a6241c3c5bf841c3db0ff2d658;hpb=591f4572f18d20a08a797a8e5c4a8dfc1b3320c1

diff --git a/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/InterlacedArrayMap.java b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/InterlacedArrayMap.java
new file mode 100644
index 000000000..6ea16dd52
--- /dev/null
+++ b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/InterlacedArrayMap.java
@@ -0,0 +1,538 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Association for Decentralized Information Management
+ * in Industry THTH ry.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     Semantum Oy - initial API and implementation
+ *******************************************************************************/
+package org.simantics.utils.datastructures;
+
+import java.lang.reflect.Array;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * A space-optimized immutable Map implementation where keys and values are
+ * interlaced in one Object array.
+ * 
+ * <p>
+ * Both map keys and values are specified as separate typed arrays that must be
+ * equally sized. This provides for space-optimization by allowing reusable key
+ * array instances since the keys cannot be modified.
+ * 
+ * <p>
+ * The map should be considered immutable, but it does allow modification of a
+ * value for an existing key as this only changes the value, the key will remain
+ * untouched.
+ * 
+ * The nested class {@link InterlacedArrayMapBuilder} allows easy and
+ * minimal-allocation construction of an {@link InterlacedArrayMap}. Use
+ * {@link InterlacedArrayMap#builder()} or
+ * {@link InterlacedArrayMap#builder(int)} to create the builder. The idea is to
+ * minimize the space allocated for the {@link #data} field in the built map
+ * instance. If the builder is completely filled up, i.e. its capacity matches
+ * added key, value pair count, the array it contains is directly transferred to
+ * the built map instance without creating any extra copies. So if possible, set
+ * the correct initial capacity for the builder.
+ * 
+ * @author Tuukka Lehtonen
+ * 
+ * @param <K>
+ *            key class
+ * @param <V>
+ *            value class
+ */
+public class InterlacedArrayMap<K, V> implements Map<K, V> {
+
+    final Object[] data;
+    Set<Map.Entry<K, V>> entrySet;
+    Set<K> keySet;
+    Collection<V> valueSet;
+
+    public static class InterlacedArrayMapBuilder<K, V> {
+
+        private Object[] elementData;
+        private int count = 0;
+
+        private InterlacedArrayMapBuilder(int initialCapacity) {
+            this.elementData = new Object[initialCapacity*2];
+        }
+
+        public void add(K key, V v) {
+            ensureCapacityInternal(count + 2);
+            elementData[count] = key;
+            elementData[count+1] = v;
+            count += 2;
+        }
+
+        private void ensureCapacityInternal(int minCapacity) {
+            // overflow-conscious code
+            if (minCapacity - elementData.length > 0)
+                grow(minCapacity);
+        }
+
+        /**
+         * The maximum size of array to allocate.
+         * Some VMs reserve some header words in an array.
+         * Attempts to allocate larger arrays may result in
+         * OutOfMemoryError: Requested array size exceeds VM limit
+         */
+        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
+
+        /**
+         * Increases the capacity to ensure that it can hold at least the
+         * number of elements specified by the minimum capacity argument.
+         *
+         * @param minCapacity the desired minimum capacity
+         */
+        private void grow(int minCapacity) {
+            // overflow-conscious code
+            int oldCapacity = elementData.length;
+            int newCapacity = oldCapacity + (oldCapacity >> 1);
+            if (newCapacity - minCapacity < 0)
+                newCapacity = minCapacity;
+            if (newCapacity - MAX_ARRAY_SIZE > 0)
+                newCapacity = hugeCapacity(minCapacity);
+            // minCapacity is usually close to size, so this is a win:
+            elementData = Arrays.copyOf(elementData, newCapacity);
+        }
+
+        private static int hugeCapacity(int minCapacity) {
+            if (minCapacity < 0) // overflow
+                throw new OutOfMemoryError();
+            return (minCapacity > MAX_ARRAY_SIZE) ?
+                Integer.MAX_VALUE :
+                MAX_ARRAY_SIZE;
+        }
+
+        public InterlacedArrayMap<K, V> build() {
+            return count == elementData.length
+                    ? new InterlacedArrayMap<>(elementData)
+                    : new InterlacedArrayMap<>(Arrays.copyOf(elementData, count));
+        }
+
+    }
+
+    /**
+     * Default initial capacity.
+     */
+    private static final int DEFAULT_CAPACITY = 10;
+
+    /**
+     * @return a map builder with the default initial capacity of
+     *         {@value #DEFAULT_CAPACITY} key,value pairs.
+     */
+    public static <K, V> InterlacedArrayMapBuilder<K, V> builder() {
+        return new InterlacedArrayMapBuilder<K, V>(DEFAULT_CAPACITY);
+    }
+
+    /**
+     * @param initialCapacity
+     *            the amount of key,value pairs to fit into the builder
+     *            initially without having to reallocate anything
+     * @return a map builder with the specified initial key,value pair capacity
+     */
+    public static <K, V> InterlacedArrayMapBuilder<K, V> builder(int initialCapacity) {
+        return new InterlacedArrayMapBuilder<K, V>(initialCapacity);
+    }
+
+    /**
+     * Just like {@link #InterlacedArrayMap(Object[])} but takes the array of
+     * objects as a collection.
+     * 
+     * @param keysAndValues
+     *            an interlaced array where where (key, value) pairs are
+     *            repeated in consecutive indexes of the array
+     * @throws IllegalArgumentException
+     *             if the array size is not divisible by two
+     * @throws NullPointerException
+     *             if either parameter is <code>null</code>
+     */
+    public InterlacedArrayMap(List<?> keysAndValues) {
+        this(keysAndValues.toArray());
+    }
+
+    /**
+     * Constructs new ArrayMap based on an interlaced array of keys and values.
+     * The array size must be divisible by two.
+     * 
+     * @param keysAndValues
+     *            an interlaced array where where (key, value) pairs are
+     *            repeated in consecutive indexes of the array
+     * @throws IllegalArgumentException
+     *             if the array size is not divisible by two
+     * @throws NullPointerException
+     *             if either parameter is <code>null</code>
+     */
+    public InterlacedArrayMap(Object[] keysAndValues) {
+        // NPE is caught by this.
+        if ((keysAndValues.length & 1) != 0)
+            throw new IllegalArgumentException("key and value array size (" + keysAndValues.length + ") is not divisible by 2");
+        this.data = keysAndValues;
+    }
+
+    @Override
+    public Set<Map.Entry<K, V>> entrySet() {
+        return (entrySet != null) ? entrySet : (entrySet = new EntrySet());
+    }
+
+    @Override
+    public void clear() {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public boolean containsKey(Object key) {
+        return contains(0, key);
+    }
+
+    @Override
+    public boolean containsValue(Object value) {
+        return contains(1, value);
+    }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public V get(Object key) {
+        if (key == null) {
+            for (int i = 0; i < data.length; i += 2) {
+                if (data[i] == null) {
+                    return (V) data[i+1];
+                }
+            }
+            return null;
+        }
+        int hash = key.hashCode();
+        for (int i = 0; i < data.length; i += 2) {
+            Object k = data[i];
+            if (k == key || (hash == k.hashCode() && key.equals(k))) {
+                return (V) data[i+1];
+            }
+        }
+        return null;
+    }
+
+    @Override
+    public boolean isEmpty() {
+        return data.length == 0;
+    }
+
+    @Override
+    public Set<K> keySet() {
+        return (keySet != null) ? keySet : (keySet =  new OffsetSet<K>(0));
+    }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public V put(K key, V value) {
+        if (key == null) {
+            for (int i = 0; i < data.length; i += 2) {
+                if (data[i] == null) {
+                    V old = (V) data[i+1];
+                    data[i+1] = value;
+                    return old;
+                }
+            }
+            throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");
+        }
+        int hash = key.hashCode();
+        for (int i = 0; i < data.length; i += 2) {
+            K k = (K) data[i];
+            if (k == key || (hash == k.hashCode() && key.equals(k))) {
+                V old = (V) data[i+1];
+                data[i+1] = value;
+                return old;
+            }
+        }
+        throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");
+    }
+
+    @Override
+    public void putAll(Map<? extends K, ? extends V> m) {
+        for (K k : m.keySet()) {
+            if (!containsKey(k))
+                throw new UnsupportedOperationException("key " + k + " not present in ArrayMap");
+        }
+        for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
+            put(entry.getKey(), entry.getValue());
+        }
+    }
+
+    @Override
+    public V remove(Object key) {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public int size() {
+        return data.length >> 1;
+    }
+
+    @Override
+    public Collection<V> values() {
+        return valueSet != null ? valueSet : (valueSet = new OffsetSet<V>(1));
+    }
+
+    private boolean contains(int offset, Object o) {
+        int len = data.length;
+        if (o == null) {
+            for (int i = offset; i < len; i += 2)
+                if (data[i] == null)
+                    return true;
+            return false;
+        }
+        int hash = o.hashCode();
+        for (int i = offset; i < len; i += 2) {
+            Object k = data[i];
+            if (o == k || (hash == k.hashCode() && o.equals(k)))
+                return true;
+        }
+        return false;
+    }
+
+    class OffsetSet<T> extends ImmutableSet<T> implements Set<T> {
+
+        private final int offset;
+
+        public OffsetSet(int offset) {
+            this.offset = offset;
+        }
+
+        @Override
+        public boolean contains(Object o) {
+            return InterlacedArrayMap.this.contains(offset, o);
+        }
+
+        @Override
+        public boolean containsAll(Collection<?> c) {
+            for (Object o : c)
+                if (!contains(o))
+                    return false;
+            return true;
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return data.length == 0;
+        }
+
+        @Override
+        public Iterator<T> iterator() {
+            return new ImmutableIterator<T>() {
+                int i = offset;
+
+                @Override
+                public boolean hasNext() {
+                    return i < data.length;
+                }
+
+                @Override
+                public T next() {
+                    if (i >= data.length)
+                        throw new NoSuchElementException("no more elements (" + data.length + " walked)");
+                    @SuppressWarnings("unchecked")
+                    T t = (T) data[i];
+                    ++i;
+                    return t;
+                }
+            };
+        }
+
+        @Override
+        public int size() {
+            return data.length >> 1;
+        }
+
+        @Override
+        public Object[] toArray() {
+            int len = data.length >> 1;
+            Object[] a = new Object[len];
+            for (int i = 0; i < len; ++i)
+                a[i] = data[i*2+offset];
+            return a;
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        public <TT> TT[] toArray(TT[] a) {
+            int len = data.length >> 1;
+            if (a.length < len) {
+                Class<?> clazz = a.getClass();
+                // Make a new array of a's runtime type, but my contents:
+                a = ((Object)clazz == (Object)Object[].class)
+                ? (TT[]) new Object[len]
+                : (TT[]) Array.newInstance(clazz.getComponentType(), len);
+            }
+            for (int i = 0; i < len; ++i)
+                a[i] = (TT) data[i*2+offset];
+            if (a.length > len)
+                a[len] = null;
+            return a;
+        }
+    }
+
+    class EntrySet extends ImmutableSet<Map.Entry<K, V>> implements Set<Map.Entry<K, V>> {
+
+        @Override
+        public boolean contains(Object o) {
+            throw new UnsupportedOperationException("TODO");
+        }
+
+        @Override
+        public boolean containsAll(Collection<?> c) {
+            for (Object o : c)
+                if (!contains(o))
+                    return false;
+            return true;
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return data.length == 0;
+        }
+
+        @Override
+        public Iterator<Map.Entry<K, V>> iterator() {
+            return new ImmutableIterator<Map.Entry<K, V>>() {
+                int i = 0;
+
+                @Override
+                public boolean hasNext() {
+                    return i < data.length;
+                }
+
+                @Override
+                public Map.Entry<K, V> next() {
+                    if (i >= data.length)
+                        throw new NoSuchElementException("no more elements (" + (data.length >> 1) + " walked)");
+                    @SuppressWarnings("unchecked")
+                    Map.Entry<K, V> entry = new ArrayMapEntry<K, V>(i, (K) data[i], (V) data[i+1]);
+                    i += 2;
+                    return entry;
+                }
+            };
+        }
+
+        @Override
+        public int size() {
+            return data.length >> 1;
+        }
+
+    }
+
+    /**
+     * Returns the hash code value for this map.  The hash code of a map is
+     * defined to be the sum of the hash codes of each entry in the map's
+     * <tt>entrySet()</tt> view.  This ensures that <tt>m1.equals(m2)</tt>
+     * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two maps
+     * <tt>m1</tt> and <tt>m2</tt>, as required by the general contract of
+     * {@link Object#hashCode}.
+     *
+     * <p>This implementation iterates over <tt>entrySet()</tt>, calling
+     * {@link Map.Entry#hashCode hashCode()} on each element (entry) in the
+     * set, and adding up the results.
+     *
+     * @return the hash code value for this map
+     * @see Map.Entry#hashCode()
+     * @see Object#equals(Object)
+     * @see Set#equals(Object)
+     */
+    @Override
+    @SuppressWarnings("unchecked")
+    public int hashCode() {
+        int h = 0;
+        int l = data.length;
+        for (int i = 0; i < l; i += 2) {
+            K key = (K) data[i];
+            V value = (V) data[i+1];
+            int hash = (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());
+            h += hash;
+        }
+        return h;
+    }
+
+    /**
+     * Compares the specified object with this map for equality.  Returns
+     * <tt>true</tt> if the given object is also a map and the two maps
+     * represent the same mappings.  More formally, two maps <tt>m1</tt> and
+     * <tt>m2</tt> represent the same mappings if
+     * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This ensures that the
+     * <tt>equals</tt> method works properly across different implementations
+     * of the <tt>Map</tt> interface.
+     *
+     * <p>This implementation first checks if the specified object is this map;
+     * if so it returns <tt>true</tt>.  Then, it checks if the specified
+     * object is a map whose size is identical to the size of this map; if
+     * not, it returns <tt>false</tt>.  If so, it iterates over this map's
+     * <tt>entrySet</tt> collection, and checks that the specified map
+     * contains each mapping that this map contains.  If the specified map
+     * fails to contain such a mapping, <tt>false</tt> is returned.  If the
+     * iteration completes, <tt>true</tt> is returned.
+     *
+     * @param o object to be compared for equality with this map
+     * @return <tt>true</tt> if the specified object is equal to this map
+     */
+    @Override
+    @SuppressWarnings("unchecked")
+    public boolean equals(Object o) {
+        if (o == this)
+            return true;
+
+        if (!(o instanceof Map))
+            return false;
+        Map<K, V> m = (Map<K, V>) o;
+        if (m.size() != size())
+            return false;
+
+        try {
+            int l = data.length;
+            for (int i = 0; i < l; i += 2) {
+                K key = (K) data[i];
+                V value = (V) data[i+1];
+                if (value == null) {
+                    if (!(m.get(key)==null && m.containsKey(key)))
+                        return false;
+                } else {
+                    if (!value.equals(m.get(key)))
+                        return false;
+                }
+            }
+        } catch (ClassCastException unused) {
+            return false;
+        } catch (NullPointerException unused) {
+            return false;
+        }
+
+        return true;
+    }
+
+    @Override
+    public String toString() {
+        Iterator<Map.Entry<K,V>> i = entrySet().iterator();
+        if (! i.hasNext())
+            return "{}";
+
+        StringBuilder sb = new StringBuilder();
+        sb.append('{');
+        for (;;) {
+            Map.Entry<K,V> e = i.next();
+            K key = e.getKey();
+            V value = e.getValue();
+            sb.append(key   == this ? "(this Map)" : key);
+            sb.append('=');
+            sb.append(value == this ? "(this Map)" : value);
+            if (! i.hasNext())
+                return sb.append('}').toString();
+            sb.append(", ");
+        }
+    }
+}