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