X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.utils.datastructures%2Fsrc%2Forg%2Fsimantics%2Futils%2Fdatastructures%2FArrayMap.java;h=0cc2cf337abd3922cb20c3bce47ef89a52c2e95a;hb=0ae2b770234dfc3cbb18bd38f324125cf0faca07;hp=b9b5415d85ba3b1a779189151ad9b51cf5470fae;hpb=53059ca1a958697cc6235d27628614fbaa944d59;p=simantics%2Fplatform.git diff --git a/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/ArrayMap.java b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/ArrayMap.java index b9b5415d8..0cc2cf337 100644 --- a/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/ArrayMap.java +++ b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/ArrayMap.java @@ -1,414 +1,414 @@ -/******************************************************************************* - * Copyright (c) 2007, 2010 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: - * VTT Technical Research Centre of Finland - initial API and implementation - *******************************************************************************/ -package org.simantics.utils.datastructures; - -import java.util.Arrays; -import java.util.Collection; -import java.util.Collections; -import java.util.Iterator; -import java.util.Map; -import java.util.NoSuchElementException; -import java.util.Set; - -/** - * A space-optimized immutable Map implementation. - * - *

- * 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. - * - * @author Tuukka Lehtonen - * - * @param key class - * @param value class - */ -public class ArrayMap implements Map { - - final K[] keys; - final V[] values; - Set> entrySet; - Set keySet; - Collection valueSet; - - public static class ArrayMapBuilder { - - final private K2[] keys; - - ArrayMapBuilder(K2[] keys) { - this.keys = keys; - } - - public ArrayMap values(@SuppressWarnings("unchecked") V2 ... values) { - return new ArrayMap(keys, values); - } - - } - - public static ArrayMapBuilder keys(@SuppressWarnings("unchecked") K2 ... keys) { - return new ArrayMapBuilder(keys); - } - - public static ArrayMap make(K2[] keys, @SuppressWarnings("unchecked") V2... values) { - return new ArrayMap(keys, values); - } - - /** - * Constructs new ArrayMap based on a key and value array. Both arrays must - * be of the same size. - * - * @param keys key array - * @param values value array - * @throws IllegalArgumentException if the arrays are of different size - * @throws NullPointerException if either parameter is null - */ - public ArrayMap(K[] keys, V[] values) { - // NPE is caught by this. - if (keys.length != values.length) - throw new IllegalArgumentException("key array size (" + keys.length + ") != value array size (" + values.length + ")"); - this.keys = keys; - this.values = values; - } - - @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 keySet().contains(key); - } - - @Override - public boolean containsValue(Object value) { - return values().contains(value); - } - - @Override - public V get(Object key) { - if (key == null) { - for (int i = 0; i < keys.length; i++) { - if (keys[i] == null) { - return values[i]; - } - } - return null; - } - int hash = key.hashCode(); - for (int i = 0; i < keys.length; i++) { - K k = keys[i]; - if (k == key || (hash == k.hashCode() && key.equals(k))) { - return values[i]; - } - } - return null; - } - - @Override - public boolean isEmpty() { - return keys.length == 0; - } - - @Override - public Set keySet() { - return (keySet != null) ? keySet : (keySet = new KeySet()); - } - - @Override - public V put(K key, V value) { - if (key == null) { - for (int i = 0; i < keys.length; i++) { - if (keys[i] == null) { - V old = values[i]; - values[i] = value; - return old; - } - } - throw new UnsupportedOperationException("key " + key + " not present in ArrayMap"); - } - int hash = key.hashCode(); - for (int i = 0; i < keys.length; i++) { - K k = keys[i]; - if (k == key || (hash == k.hashCode() && key.equals(k))) { - V old = values[i]; - values[i] = 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 keys.length; - } - - @Override - public Collection values() { - return valueSet != null ? valueSet : (valueSet = Collections.unmodifiableCollection(Arrays.asList(values))); - } - - class KeySet extends ImmutableSet implements Set { - - @Override - public boolean contains(Object o) { - if (o == null) { - for (K k : keys) - if (k == null) - return true; - return false; - } - int hash = o.hashCode(); - for (K k : keys) - if (o == k || (hash == k.hashCode() && o.equals(k))) - return true; - return false; - } - - @Override - public boolean containsAll(Collection c) { - for (Object o : c) - if (!contains(o)) - return false; - return true; - } - - @Override - public boolean isEmpty() { - return keys.length == 0; - } - - @Override - public Iterator iterator() { - return new ImmutableIterator() { - int i = 0; - - @Override - public boolean hasNext() { - return i < keys.length; - } - - @Override - public K next() { - if (i >= keys.length) - throw new NoSuchElementException("no more elements (" + keys.length + " walked)"); - K k = keys[i]; - ++i; - return k; - } - }; - } - - @Override - public int size() { - return keys.length; - } - - @Override - public Object[] toArray() { - return keys; - } - - @SuppressWarnings("unchecked") - @Override - public T[] toArray(T[] a) { - if (a.length < keys.length) - // Make a new array of a's runtime type, but my contents: - return (T[]) Arrays.copyOf(keys, keys.length, a.getClass()); - System.arraycopy(keys, 0, a, 0, keys.length); - if (a.length > keys.length) - a[keys.length] = 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 keys.length == 0; - } - - @Override - public Iterator> iterator() { - return new ImmutableIterator>() { - int i = 0; - - @Override - public boolean hasNext() { - return i < keys.length; - } - - @Override - public Map.Entry next() { - if (i >= keys.length) - throw new NoSuchElementException("no more elements (" + keys.length + " walked)"); - Map.Entry entry = new ArrayMapEntry(i, keys[i], values[i]); - ++i; - return entry; - } - }; - } - - @Override - public int size() { - return keys.length; - } - - } - - /** - * 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 - public int hashCode() { - int h = 0; - int l = keys.length; - for (int i = 0; i < l; i++) { - K key = keys[i]; - V value = values[i]; - 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 = keys.length; - for (int i = 0; i < l; i++) { - K key = keys[i]; - V value = values[i]; - 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) 2007, 2010 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: + * VTT Technical Research Centre of Finland - initial API and implementation + *******************************************************************************/ +package org.simantics.utils.datastructures; + +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.Iterator; +import java.util.Map; +import java.util.NoSuchElementException; +import java.util.Set; + +/** + * A space-optimized immutable Map implementation. + * + *

+ * 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. + * + * @author Tuukka Lehtonen + * + * @param key class + * @param value class + */ +public class ArrayMap implements Map { + + final K[] keys; + final V[] values; + Set> entrySet; + Set keySet; + Collection valueSet; + + public static class ArrayMapBuilder { + + final private K2[] keys; + + ArrayMapBuilder(K2[] keys) { + this.keys = keys; + } + + public ArrayMap values(@SuppressWarnings("unchecked") V2 ... values) { + return new ArrayMap(keys, values); + } + + } + + public static ArrayMapBuilder keys(@SuppressWarnings("unchecked") K2 ... keys) { + return new ArrayMapBuilder(keys); + } + + public static ArrayMap make(K2[] keys, @SuppressWarnings("unchecked") V2... values) { + return new ArrayMap(keys, values); + } + + /** + * Constructs new ArrayMap based on a key and value array. Both arrays must + * be of the same size. + * + * @param keys key array + * @param values value array + * @throws IllegalArgumentException if the arrays are of different size + * @throws NullPointerException if either parameter is null + */ + public ArrayMap(K[] keys, V[] values) { + // NPE is caught by this. + if (keys.length != values.length) + throw new IllegalArgumentException("key array size (" + keys.length + ") != value array size (" + values.length + ")"); + this.keys = keys; + this.values = values; + } + + @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 keySet().contains(key); + } + + @Override + public boolean containsValue(Object value) { + return values().contains(value); + } + + @Override + public V get(Object key) { + if (key == null) { + for (int i = 0; i < keys.length; i++) { + if (keys[i] == null) { + return values[i]; + } + } + return null; + } + int hash = key.hashCode(); + for (int i = 0; i < keys.length; i++) { + K k = keys[i]; + if (k == key || (hash == k.hashCode() && key.equals(k))) { + return values[i]; + } + } + return null; + } + + @Override + public boolean isEmpty() { + return keys.length == 0; + } + + @Override + public Set keySet() { + return (keySet != null) ? keySet : (keySet = new KeySet()); + } + + @Override + public V put(K key, V value) { + if (key == null) { + for (int i = 0; i < keys.length; i++) { + if (keys[i] == null) { + V old = values[i]; + values[i] = value; + return old; + } + } + throw new UnsupportedOperationException("key " + key + " not present in ArrayMap"); + } + int hash = key.hashCode(); + for (int i = 0; i < keys.length; i++) { + K k = keys[i]; + if (k == key || (hash == k.hashCode() && key.equals(k))) { + V old = values[i]; + values[i] = 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 keys.length; + } + + @Override + public Collection values() { + return valueSet != null ? valueSet : (valueSet = Collections.unmodifiableCollection(Arrays.asList(values))); + } + + class KeySet extends ImmutableSet implements Set { + + @Override + public boolean contains(Object o) { + if (o == null) { + for (K k : keys) + if (k == null) + return true; + return false; + } + int hash = o.hashCode(); + for (K k : keys) + if (o == k || (hash == k.hashCode() && o.equals(k))) + return true; + return false; + } + + @Override + public boolean containsAll(Collection c) { + for (Object o : c) + if (!contains(o)) + return false; + return true; + } + + @Override + public boolean isEmpty() { + return keys.length == 0; + } + + @Override + public Iterator iterator() { + return new ImmutableIterator() { + int i = 0; + + @Override + public boolean hasNext() { + return i < keys.length; + } + + @Override + public K next() { + if (i >= keys.length) + throw new NoSuchElementException("no more elements (" + keys.length + " walked)"); + K k = keys[i]; + ++i; + return k; + } + }; + } + + @Override + public int size() { + return keys.length; + } + + @Override + public Object[] toArray() { + return keys; + } + + @SuppressWarnings("unchecked") + @Override + public T[] toArray(T[] a) { + if (a.length < keys.length) + // Make a new array of a's runtime type, but my contents: + return (T[]) Arrays.copyOf(keys, keys.length, a.getClass()); + System.arraycopy(keys, 0, a, 0, keys.length); + if (a.length > keys.length) + a[keys.length] = 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 keys.length == 0; + } + + @Override + public Iterator> iterator() { + return new ImmutableIterator>() { + int i = 0; + + @Override + public boolean hasNext() { + return i < keys.length; + } + + @Override + public Map.Entry next() { + if (i >= keys.length) + throw new NoSuchElementException("no more elements (" + keys.length + " walked)"); + Map.Entry entry = new ArrayMapEntry(i, keys[i], values[i]); + ++i; + return entry; + } + }; + } + + @Override + public int size() { + return keys.length; + } + + } + + /** + * 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 + public int hashCode() { + int h = 0; + int l = keys.length; + for (int i = 0; i < l; i++) { + K key = keys[i]; + V value = values[i]; + 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 = keys.length; + for (int i = 0; i < l; i++) { + K key = keys[i]; + V value = values[i]; + 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(", "); + } + } +}