bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/ArrayMap.java

   1 /*******************************************************************************\r
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
   3  * in Industry THTH ry.\r
   4  * All rights reserved. This program and the accompanying materials\r
   5  * are made available under the terms of the Eclipse Public License v1.0\r
   6  * which accompanies this distribution, and is available at\r
   7  * http://www.eclipse.org/legal/epl-v10.html\r
   8  *\r
   9  * Contributors:\r
  10  *     VTT Technical Research Centre of Finland - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.utils.datastructures;\r
  13 \r
  14 import java.util.Arrays;\r
  15 import java.util.Collection;\r
  16 import java.util.Collections;\r
  17 import java.util.Iterator;\r
  18 import java.util.Map;\r
  19 import java.util.NoSuchElementException;\r
  20 import java.util.Set;\r
  21 \r
  22 /**\r
  23  * A space-optimized immutable Map implementation.\r
  24  * \r
  25  * <p>\r
  26  * Both map keys and values are specified as separate typed arrays that must be\r
  27  * equally sized. This provides for space-optimization by allowing reusable key\r
  28  * array instances since the keys cannot be modified.\r
  29  * \r
  30  * <p>\r
  31  * The map should be considered immutable, but it does allow modification of a\r
  32  * value for an existing key as this only changes the value, the key will remain\r
  33  * untouched.\r
  34  * \r
  35  * @author Tuukka Lehtonen\r
  36  * \r
  37  * @param <K> key class\r
  38  * @param <V> value class\r
  39  */\r
  40 public class ArrayMap<K, V> implements Map<K, V> {\r
  41 \r
  42     K[] keys;\r
  43     V[] values;\r
  44     Set<Map.Entry<K, V>> entrySet;\r
  45     Set<K> keySet;\r
  46     Collection<V> valueSet;\r
  47 \r
  48     public static class ArrayMapBuilder<K2, V2> {\r
  49 \r
  50         final private K2[] keys;\r
  51 \r
  52         ArrayMapBuilder(K2[] keys) {\r
  53             this.keys = keys;\r
  54         }\r
  55 \r
  56         public ArrayMap<K2, V2> values(@SuppressWarnings("unchecked") V2 ... values) {\r
  57             return new ArrayMap<K2, V2>(keys, values);\r
  58         }\r
  59 \r
  60     }\r
  61 \r
  62     public static <K2, V2>ArrayMapBuilder<K2, V2> keys(@SuppressWarnings("unchecked") K2 ... keys) {\r
  63         return new ArrayMapBuilder<K2, V2>(keys);\r
  64     }\r
  65 \r
  66     public static <K2, V2> ArrayMap<K2, V2> make(K2[] keys, @SuppressWarnings("unchecked") V2... values) {\r
  67         return new ArrayMap<K2, V2>(keys, values);\r
  68     }\r
  69 \r
  70     /**\r
  71      * Constructs new ArrayMap based on a key and value array. Both arrays must\r
  72      * be of the same size.\r
  73      * \r
  74      * @param keys key array\r
  75      * @param values value array\r
  76      * @throws IllegalArgumentException if the arrays are of different size\r
  77      * @throws NullPointerException if either parameter is <code>null</code>\r
  78      */\r
  79     public ArrayMap(K[] keys, V[] values) {\r
  80         // NPE is caught by this.\r
  81         if (keys.length != values.length)\r
  82             throw new IllegalArgumentException("key array size (" + keys.length + ") != value array size (" + values.length + ")");\r
  83         this.keys = keys;\r
  84         this.values = values;\r
  85     }\r
  86 \r
  87     @Override\r
  88     public Set<Map.Entry<K, V>> entrySet() {\r
  89         return (entrySet != null) ? entrySet : (entrySet = new EntrySet());\r
  90     }\r
  91 \r
  92     @Override\r
  93     public void clear() {\r
  94         throw new UnsupportedOperationException();\r
  95     }\r
  96 \r
  97     @Override\r
  98     public boolean containsKey(Object key) {\r
  99         return keySet().contains(key);\r
 100     }\r
 101 \r
 102     @Override\r
 103     public boolean containsValue(Object value) {\r
 104         return values().contains(value);\r
 105     }\r
 106 \r
 107     @Override\r
 108     public V get(Object key) {\r
 109         if (key == null) {\r
 110             for (int i = 0; i < keys.length; i++) {\r
 111                 if (keys[i] == null) {\r
 112                     return values[i];\r
 113                 }\r
 114             }\r
 115             return null;\r
 116         }\r
 117         int hash = key.hashCode();\r
 118         for (int i = 0; i < keys.length; i++) {\r
 119             K k = keys[i];\r
 120             if (k == key || (hash == k.hashCode() && key.equals(k))) {\r
 121                 return values[i];\r
 122             }\r
 123         }\r
 124         return null;\r
 125     }\r
 126 \r
 127     @Override\r
 128     public boolean isEmpty() {\r
 129         return keys.length == 0;\r
 130     }\r
 131 \r
 132     @Override\r
 133     public Set<K> keySet() {\r
 134         return (keySet != null) ? keySet : (keySet =  new KeySet());\r
 135     }\r
 136 \r
 137     @Override\r
 138     public V put(K key, V value) {\r
 139         if (key == null) {\r
 140             for (int i = 0; i < keys.length; i++) {\r
 141                 if (keys[i] == null) {\r
 142                     V old = values[i];\r
 143                     values[i] = value;\r
 144                     return old;\r
 145                 }\r
 146             }\r
 147             throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");\r
 148         }\r
 149         int hash = key.hashCode();\r
 150         for (int i = 0; i < keys.length; i++) {\r
 151             K k = keys[i];\r
 152             if (k == key || (hash == k.hashCode() && key.equals(k))) {\r
 153                 V old = values[i];\r
 154                 values[i] = value;\r
 155                 return old;\r
 156             }\r
 157         }\r
 158         throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");\r
 159     }\r
 160 \r
 161     @Override\r
 162     public void putAll(Map<? extends K, ? extends V> m) {\r
 163         for (K k : m.keySet()) {\r
 164             if (!containsKey(k))\r
 165                 throw new UnsupportedOperationException("key " + k + " not present in ArrayMap");\r
 166         }\r
 167         for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {\r
 168             put(entry.getKey(), entry.getValue());\r
 169         }\r
 170     }\r
 171 \r
 172     @Override\r
 173     public V remove(Object key) {\r
 174         throw new UnsupportedOperationException();\r
 175     }\r
 176 \r
 177     @Override\r
 178     public int size() {\r
 179         return keys.length;\r
 180     }\r
 181 \r
 182     @Override\r
 183     public Collection<V> values() {\r
 184         return valueSet != null ? valueSet : (valueSet = Collections.unmodifiableCollection(Arrays.asList(values)));\r
 185     }\r
 186 \r
 187     class KeySet extends ImmutableSet<K> implements Set<K> {\r
 188 \r
 189         @Override\r
 190         public boolean contains(Object o) {\r
 191             if (o == null) {\r
 192                 for (K k : keys)\r
 193                     if (k == null)\r
 194                         return true;\r
 195                 return false;\r
 196             }\r
 197             int hash = o.hashCode();\r
 198             for (K k : keys)\r
 199                 if (o == k || (hash == k.hashCode() && o.equals(k)))\r
 200                     return true;\r
 201             return false;\r
 202         }\r
 203 \r
 204         @Override\r
 205         public boolean containsAll(Collection<?> c) {\r
 206             for (Object o : c)\r
 207                 if (!contains(o))\r
 208                     return false;\r
 209             return true;\r
 210         }\r
 211 \r
 212         @Override\r
 213         public boolean isEmpty() {\r
 214             return keys.length == 0;\r
 215         }\r
 216 \r
 217         @Override\r
 218         public Iterator<K> iterator() {\r
 219             return new ImmutableIterator<K>() {\r
 220                 int i = 0;\r
 221 \r
 222                 @Override\r
 223                 public boolean hasNext() {\r
 224                     return i < keys.length;\r
 225                 }\r
 226 \r
 227                 @Override\r
 228                 public K next() {\r
 229                     if (i >= keys.length)\r
 230                         throw new NoSuchElementException("no more elements (" + keys.length + " walked)");\r
 231                     K k = keys[i];\r
 232                     ++i;\r
 233                     return k;\r
 234                 }\r
 235             };\r
 236         }\r
 237 \r
 238         @Override\r
 239         public int size() {\r
 240             return keys.length;\r
 241         }\r
 242 \r
 243         @Override\r
 244         public Object[] toArray() {\r
 245             return keys;\r
 246         }\r
 247 \r
 248         @SuppressWarnings("unchecked")\r
 249         @Override\r
 250         public <T> T[] toArray(T[] a) {\r
 251             if (a.length < keys.length)\r
 252                 // Make a new array of a's runtime type, but my contents:\r
 253                 return (T[]) Arrays.copyOf(keys, keys.length, a.getClass());\r
 254             System.arraycopy(keys, 0, a, 0, keys.length);\r
 255             if (a.length > keys.length)\r
 256                 a[keys.length] = null;\r
 257             return a;\r
 258         }\r
 259     }\r
 260 \r
 261     class EntrySet extends ImmutableSet<Map.Entry<K, V>> implements Set<Map.Entry<K, V>> {\r
 262 \r
 263         @Override\r
 264         public boolean contains(Object o) {\r
 265             throw new UnsupportedOperationException("TODO");\r
 266         }\r
 267 \r
 268         @Override\r
 269         public boolean containsAll(Collection<?> c) {\r
 270             for (Object o : c)\r
 271                 if (!contains(o))\r
 272                     return false;\r
 273             return true;\r
 274         }\r
 275 \r
 276         @Override\r
 277         public boolean isEmpty() {\r
 278             return keys.length == 0;\r
 279         }\r
 280 \r
 281         @Override\r
 282         public Iterator<Map.Entry<K, V>> iterator() {\r
 283             return new ImmutableIterator<Map.Entry<K, V>>() {\r
 284                 int i = 0;\r
 285 \r
 286                 @Override\r
 287                 public boolean hasNext() {\r
 288                     return i < keys.length;\r
 289                 }\r
 290 \r
 291                 @Override\r
 292                 public Map.Entry<K, V> next() {\r
 293                     if (i >= keys.length)\r
 294                         throw new NoSuchElementException("no more elements (" + keys.length + " walked)");\r
 295                     Map.Entry<K, V> entry = new Entry<K, V>(i, keys[i], values[i]);\r
 296                     ++i;\r
 297                     return entry;\r
 298                 }\r
 299             };\r
 300         }\r
 301 \r
 302         @Override\r
 303         public int size() {\r
 304             return keys.length;\r
 305         }\r
 306 \r
 307     }\r
 308 \r
 309     static class Entry<K, V> implements Map.Entry<K, V> {\r
 310         final K key;\r
 311         V value;\r
 312 \r
 313         /**\r
 314          * Creates new entry.\r
 315          */\r
 316         Entry(int h, K k, V v) {\r
 317             value = v;\r
 318             key = k;\r
 319         }\r
 320 \r
 321         @Override\r
 322         public final K getKey() {\r
 323             return key;\r
 324         }\r
 325 \r
 326         @Override\r
 327         public final V getValue() {\r
 328             return value;\r
 329         }\r
 330 \r
 331         @Override\r
 332         public final V setValue(V newValue) {\r
 333             V oldValue = value;\r
 334             value = newValue;\r
 335             return oldValue;\r
 336         }\r
 337 \r
 338         @Override\r
 339         public final boolean equals(Object o) {\r
 340             if (!(o instanceof Map.Entry<?, ?>))\r
 341                 return false;\r
 342             Map.Entry<?, ?> e = (Map.Entry<?, ?>)o;\r
 343             Object k1 = getKey();\r
 344             Object k2 = e.getKey();\r
 345             if (k1 == k2 || (k1 != null && k1.equals(k2))) {\r
 346                 Object v1 = getValue();\r
 347                 Object v2 = e.getValue();\r
 348                 if (v1 == v2 || (v1 != null && v1.equals(v2)))\r
 349                     return true;\r
 350             }\r
 351             return false;\r
 352         }\r
 353 \r
 354         @Override\r
 355         public final int hashCode() {\r
 356             return (key==null   ? 0 : key.hashCode()) ^\r
 357             (value==null ? 0 : value.hashCode());\r
 358         }\r
 359 \r
 360         @Override\r
 361         public final String toString() {\r
 362             return getKey() + "=" + getValue();\r
 363         }\r
 364     }\r
 365 \r
 366     /**\r
 367      * Returns the hash code value for this map.  The hash code of a map is\r
 368      * defined to be the sum of the hash codes of each entry in the map's\r
 369      * <tt>entrySet()</tt> view.  This ensures that <tt>m1.equals(m2)</tt>\r
 370      * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two maps\r
 371      * <tt>m1</tt> and <tt>m2</tt>, as required by the general contract of\r
 372      * {@link Object#hashCode}.\r
 373      *\r
 374      * <p>This implementation iterates over <tt>entrySet()</tt>, calling\r
 375      * {@link Map.Entry#hashCode hashCode()} on each element (entry) in the\r
 376      * set, and adding up the results.\r
 377      *\r
 378      * @return the hash code value for this map\r
 379      * @see Map.Entry#hashCode()\r
 380      * @see Object#equals(Object)\r
 381      * @see Set#equals(Object)\r
 382      */\r
 383     @Override\r
 384     public int hashCode() {\r
 385         int h = 0;\r
 386         int l = keys.length;\r
 387         for (int i = 0; i < l; i++) {\r
 388             K key = keys[i];\r
 389             V value = values[i];\r
 390             int hash = (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());\r
 391             h += hash;\r
 392         }\r
 393         return h;\r
 394     }\r
 395 \r
 396     /**\r
 397      * Compares the specified object with this map for equality.  Returns\r
 398      * <tt>true</tt> if the given object is also a map and the two maps\r
 399      * represent the same mappings.  More formally, two maps <tt>m1</tt> and\r
 400      * <tt>m2</tt> represent the same mappings if\r
 401      * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This ensures that the\r
 402      * <tt>equals</tt> method works properly across different implementations\r
 403      * of the <tt>Map</tt> interface.\r
 404      *\r
 405      * <p>This implementation first checks if the specified object is this map;\r
 406      * if so it returns <tt>true</tt>.  Then, it checks if the specified\r
 407      * object is a map whose size is identical to the size of this map; if\r
 408      * not, it returns <tt>false</tt>.  If so, it iterates over this map's\r
 409      * <tt>entrySet</tt> collection, and checks that the specified map\r
 410      * contains each mapping that this map contains.  If the specified map\r
 411      * fails to contain such a mapping, <tt>false</tt> is returned.  If the\r
 412      * iteration completes, <tt>true</tt> is returned.\r
 413      *\r
 414      * @param o object to be compared for equality with this map\r
 415      * @return <tt>true</tt> if the specified object is equal to this map\r
 416      */\r
 417     @Override\r
 418     @SuppressWarnings("unchecked")\r
 419     public boolean equals(Object o) {\r
 420         if (o == this)\r
 421             return true;\r
 422 \r
 423         if (!(o instanceof Map))\r
 424             return false;\r
 425         Map<K, V> m = (Map<K, V>) o;\r
 426         if (m.size() != size())\r
 427             return false;\r
 428 \r
 429         try {\r
 430             int l = keys.length;\r
 431             for (int i = 0; i < l; i++) {\r
 432                 K key = keys[i];\r
 433                 V value = values[i];\r
 434                 if (value == null) {\r
 435                     if (!(m.get(key)==null && m.containsKey(key)))\r
 436                         return false;\r
 437                 } else {\r
 438                     if (!value.equals(m.get(key)))\r
 439                         return false;\r
 440                 }\r
 441             }\r
 442         } catch (ClassCastException unused) {\r
 443             return false;\r
 444         } catch (NullPointerException unused) {\r
 445             return false;\r
 446         }\r
 447 \r
 448         return true;\r
 449     }\r
 450 \r
 451     @Override\r
 452     public String toString() {\r
 453         Iterator<Map.Entry<K,V>> i = entrySet().iterator();\r
 454         if (! i.hasNext())\r
 455             return "{}";\r
 456 \r
 457         StringBuilder sb = new StringBuilder();\r
 458         sb.append('{');\r
 459         for (;;) {\r
 460             Map.Entry<K,V> e = i.next();\r
 461             K key = e.getKey();\r
 462             V value = e.getValue();\r
 463             sb.append(key   == this ? "(this Map)" : key);\r
 464             sb.append('=');\r
 465             sb.append(value == this ? "(this Map)" : value);\r
 466             if (! i.hasNext())\r
 467                 return sb.append('}').toString();\r
 468             sb.append(", ");\r
 469         }\r
 470     }\r
 471 }\r