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