X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.utils.datastructures%2Fsrc%2Forg%2Fsimantics%2Futils%2Fdatastructures%2FInterlacedArrayMap.java;h=07c427ba549b38cedd732cc4f94279947e38cedd;hb=refs%2Fchanges%2F38%2F238%2F2;hp=6ea16dd52b0bece077758d1c4563e172b9b8fe44;hpb=53059ca1a958697cc6235d27628614fbaa944d59;p=simantics%2Fplatform.git 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 index 6ea16dd52..07c427ba5 100644 --- 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 @@ -1,538 +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. - * - *

- * 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. - * - *

- * 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 - * key class - * @param - * value class - */ -public class InterlacedArrayMap implements Map { - - final Object[] data; - Set> entrySet; - Set keySet; - Collection valueSet; - - public static class InterlacedArrayMapBuilder { - - 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 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 InterlacedArrayMapBuilder builder() { - return new InterlacedArrayMapBuilder(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 InterlacedArrayMapBuilder builder(int initialCapacity) { - return new InterlacedArrayMapBuilder(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 null - */ - 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 null - */ - 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> 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 keySet() { - return (keySet != null) ? keySet : (keySet = new OffsetSet(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 m) { - for (K k : m.keySet()) { - if (!containsKey(k)) - throw new UnsupportedOperationException("key " + k + " not present in ArrayMap"); - } - for (Map.Entry 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 values() { - return valueSet != null ? valueSet : (valueSet = new OffsetSet(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 extends ImmutableSet implements Set { - - 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 iterator() { - return new ImmutableIterator() { - 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[] 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> implements Set> { - - @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> iterator() { - return new ImmutableIterator>() { - int i = 0; - - @Override - public boolean hasNext() { - return i < data.length; - } - - @Override - public Map.Entry next() { - if (i >= data.length) - throw new NoSuchElementException("no more elements (" + (data.length >> 1) + " walked)"); - @SuppressWarnings("unchecked") - Map.Entry entry = new ArrayMapEntry(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 - * entrySet() view. This ensures that m1.equals(m2) - * implies that m1.hashCode()==m2.hashCode() for any two maps - * m1 and m2, as required by the general contract of - * {@link Object#hashCode}. - * - *

This implementation iterates over entrySet(), 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 - * true if the given object is also a map and the two maps - * represent the same mappings. More formally, two maps m1 and - * m2 represent the same mappings if - * m1.entrySet().equals(m2.entrySet()). This ensures that the - * equals method works properly across different implementations - * of the Map interface. - * - *

This implementation first checks if the specified object is this map; - * if so it returns true. Then, it checks if the specified - * object is a map whose size is identical to the size of this map; if - * not, it returns false. If so, it iterates over this map's - * entrySet collection, and checks that the specified map - * contains each mapping that this map contains. If the specified map - * fails to contain such a mapping, false is returned. If the - * iteration completes, true is returned. - * - * @param o object to be compared for equality with this map - * @return true 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 m = (Map) 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> i = entrySet().iterator(); - if (! i.hasNext()) - return "{}"; - - StringBuilder sb = new StringBuilder(); - sb.append('{'); - for (;;) { - Map.Entry 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(", "); - } - } -} +/******************************************************************************* + * 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. + * + *

+ * 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. + * + *

+ * 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 + * key class + * @param + * value class + */ +public class InterlacedArrayMap implements Map { + + final Object[] data; + Set> entrySet; + Set keySet; + Collection valueSet; + + public static class InterlacedArrayMapBuilder { + + 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 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 InterlacedArrayMapBuilder builder() { + return new InterlacedArrayMapBuilder(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 InterlacedArrayMapBuilder builder(int initialCapacity) { + return new InterlacedArrayMapBuilder(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 null + */ + 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 null + */ + 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> 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 keySet() { + return (keySet != null) ? keySet : (keySet = new OffsetSet(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 m) { + for (K k : m.keySet()) { + if (!containsKey(k)) + throw new UnsupportedOperationException("key " + k + " not present in ArrayMap"); + } + for (Map.Entry 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 values() { + return valueSet != null ? valueSet : (valueSet = new OffsetSet(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 extends ImmutableSet implements Set { + + 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 iterator() { + return new ImmutableIterator() { + 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[] 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> implements Set> { + + @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> iterator() { + return new ImmutableIterator>() { + int i = 0; + + @Override + public boolean hasNext() { + return i < data.length; + } + + @Override + public Map.Entry next() { + if (i >= data.length) + throw new NoSuchElementException("no more elements (" + (data.length >> 1) + " walked)"); + @SuppressWarnings("unchecked") + Map.Entry entry = new ArrayMapEntry(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 + * entrySet() view. This ensures that m1.equals(m2) + * implies that m1.hashCode()==m2.hashCode() for any two maps + * m1 and m2, as required by the general contract of + * {@link Object#hashCode}. + * + *

This implementation iterates over entrySet(), 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 + * true if the given object is also a map and the two maps + * represent the same mappings. More formally, two maps m1 and + * m2 represent the same mappings if + * m1.entrySet().equals(m2.entrySet()). This ensures that the + * equals method works properly across different implementations + * of the Map interface. + * + *

This implementation first checks if the specified object is this map; + * if so it returns true. Then, it checks if the specified + * object is a map whose size is identical to the size of this map; if + * not, it returns false. If so, it iterates over this map's + * entrySet collection, and checks that the specified map + * contains each mapping that this map contains. If the specified map + * fails to contain such a mapping, false is returned. If the + * iteration completes, true is returned. + * + * @param o object to be compared for equality with this map + * @return true 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 m = (Map) 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> i = entrySet().iterator(); + if (! i.hasNext()) + return "{}"; + + StringBuilder sb = new StringBuilder(); + sb.append('{'); + for (;;) { + Map.Entry 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(", "); + } + } +}