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

   1 /*******************************************************************************\r
   2  * Copyright (c) 2016 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  *     Semantum Oy - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.utils.datastructures;\r
  13 \r
  14 import java.lang.reflect.Array;\r
  15 import java.util.Arrays;\r
  16 import java.util.Collection;\r
  17 import java.util.Iterator;\r
  18 import java.util.List;\r
  19 import java.util.Map;\r
  20 import java.util.NoSuchElementException;\r
  21 import java.util.Set;\r
  22 \r
  23 /**\r
  24  * A space-optimized immutable Map implementation where keys and values are\r
  25  * interlaced in one Object array.\r
  26  * \r
  27  * <p>\r
  28  * Both map keys and values are specified as separate typed arrays that must be\r
  29  * equally sized. This provides for space-optimization by allowing reusable key\r
  30  * array instances since the keys cannot be modified.\r
  31  * \r
  32  * <p>\r
  33  * The map should be considered immutable, but it does allow modification of a\r
  34  * value for an existing key as this only changes the value, the key will remain\r
  35  * untouched.\r
  36  * \r
  37  * The nested class {@link InterlacedArrayMapBuilder} allows easy and\r
  38  * minimal-allocation construction of an {@link InterlacedArrayMap}. Use\r
  39  * {@link InterlacedArrayMap#builder()} or\r
  40  * {@link InterlacedArrayMap#builder(int)} to create the builder. The idea is to\r
  41  * minimize the space allocated for the {@link #data} field in the built map\r
  42  * instance. If the builder is completely filled up, i.e. its capacity matches\r
  43  * added key, value pair count, the array it contains is directly transferred to\r
  44  * the built map instance without creating any extra copies. So if possible, set\r
  45  * the correct initial capacity for the builder.\r
  46  * \r
  47  * @author Tuukka Lehtonen\r
  48  * \r
  49  * @param <K>\r
  50  *            key class\r
  51  * @param <V>\r
  52  *            value class\r
  53  */\r
  54 public class InterlacedArrayMap<K, V> implements Map<K, V> {\r
  55 \r
  56     final Object[] data;\r
  57     Set<Map.Entry<K, V>> entrySet;\r
  58     Set<K> keySet;\r
  59     Collection<V> valueSet;\r
  60 \r
  61     public static class InterlacedArrayMapBuilder<K, V> {\r
  62 \r
  63         private Object[] elementData;\r
  64         private int count = 0;\r
  65 \r
  66         private InterlacedArrayMapBuilder(int initialCapacity) {\r
  67             this.elementData = new Object[initialCapacity*2];\r
  68         }\r
  69 \r
  70         public void add(K key, V v) {\r
  71             ensureCapacityInternal(count + 2);\r
  72             elementData[count] = key;\r
  73             elementData[count+1] = v;\r
  74             count += 2;\r
  75         }\r
  76 \r
  77         private void ensureCapacityInternal(int minCapacity) {\r
  78             // overflow-conscious code\r
  79             if (minCapacity - elementData.length > 0)\r
  80                 grow(minCapacity);\r
  81         }\r
  82 \r
  83         /**\r
  84          * The maximum size of array to allocate.\r
  85          * Some VMs reserve some header words in an array.\r
  86          * Attempts to allocate larger arrays may result in\r
  87          * OutOfMemoryError: Requested array size exceeds VM limit\r
  88          */\r
  89         private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;\r
  90 \r
  91         /**\r
  92          * Increases the capacity to ensure that it can hold at least the\r
  93          * number of elements specified by the minimum capacity argument.\r
  94          *\r
  95          * @param minCapacity the desired minimum capacity\r
  96          */\r
  97         private void grow(int minCapacity) {\r
  98             // overflow-conscious code\r
  99             int oldCapacity = elementData.length;\r
 100             int newCapacity = oldCapacity + (oldCapacity >> 1);\r
 101             if (newCapacity - minCapacity < 0)\r
 102                 newCapacity = minCapacity;\r
 103             if (newCapacity - MAX_ARRAY_SIZE > 0)\r
 104                 newCapacity = hugeCapacity(minCapacity);\r
 105             // minCapacity is usually close to size, so this is a win:\r
 106             elementData = Arrays.copyOf(elementData, newCapacity);\r
 107         }\r
 108 \r
 109         private static int hugeCapacity(int minCapacity) {\r
 110             if (minCapacity < 0) // overflow\r
 111                 throw new OutOfMemoryError();\r
 112             return (minCapacity > MAX_ARRAY_SIZE) ?\r
 113                 Integer.MAX_VALUE :\r
 114                 MAX_ARRAY_SIZE;\r
 115         }\r
 116 \r
 117         public InterlacedArrayMap<K, V> build() {\r
 118             return count == elementData.length\r
 119                     ? new InterlacedArrayMap<>(elementData)\r
 120                     : new InterlacedArrayMap<>(Arrays.copyOf(elementData, count));\r
 121         }\r
 122 \r
 123     }\r
 124 \r
 125     /**\r
 126      * Default initial capacity.\r
 127      */\r
 128     private static final int DEFAULT_CAPACITY = 10;\r
 129 \r
 130     /**\r
 131      * @return a map builder with the default initial capacity of\r
 132      *         {@value #DEFAULT_CAPACITY} key,value pairs.\r
 133      */\r
 134     public static <K, V> InterlacedArrayMapBuilder<K, V> builder() {\r
 135         return new InterlacedArrayMapBuilder<K, V>(DEFAULT_CAPACITY);\r
 136     }\r
 137 \r
 138     /**\r
 139      * @param initialCapacity\r
 140      *            the amount of key,value pairs to fit into the builder\r
 141      *            initially without having to reallocate anything\r
 142      * @return a map builder with the specified initial key,value pair capacity\r
 143      */\r
 144     public static <K, V> InterlacedArrayMapBuilder<K, V> builder(int initialCapacity) {\r
 145         return new InterlacedArrayMapBuilder<K, V>(initialCapacity);\r
 146     }\r
 147 \r
 148     /**\r
 149      * Just like {@link #InterlacedArrayMap(Object[])} but takes the array of\r
 150      * objects as a collection.\r
 151      * \r
 152      * @param keysAndValues\r
 153      *            an interlaced array where where (key, value) pairs are\r
 154      *            repeated in consecutive indexes of the array\r
 155      * @throws IllegalArgumentException\r
 156      *             if the array size is not divisible by two\r
 157      * @throws NullPointerException\r
 158      *             if either parameter is <code>null</code>\r
 159      */\r
 160     public InterlacedArrayMap(List<?> keysAndValues) {\r
 161         this(keysAndValues.toArray());\r
 162     }\r
 163 \r
 164     /**\r
 165      * Constructs new ArrayMap based on an interlaced array of keys and values.\r
 166      * The array size must be divisible by two.\r
 167      * \r
 168      * @param keysAndValues\r
 169      *            an interlaced array where where (key, value) pairs are\r
 170      *            repeated in consecutive indexes of the array\r
 171      * @throws IllegalArgumentException\r
 172      *             if the array size is not divisible by two\r
 173      * @throws NullPointerException\r
 174      *             if either parameter is <code>null</code>\r
 175      */\r
 176     public InterlacedArrayMap(Object[] keysAndValues) {\r
 177         // NPE is caught by this.\r
 178         if ((keysAndValues.length & 1) != 0)\r
 179             throw new IllegalArgumentException("key and value array size (" + keysAndValues.length + ") is not divisible by 2");\r
 180         this.data = keysAndValues;\r
 181     }\r
 182 \r
 183     @Override\r
 184     public Set<Map.Entry<K, V>> entrySet() {\r
 185         return (entrySet != null) ? entrySet : (entrySet = new EntrySet());\r
 186     }\r
 187 \r
 188     @Override\r
 189     public void clear() {\r
 190         throw new UnsupportedOperationException();\r
 191     }\r
 192 \r
 193     @Override\r
 194     public boolean containsKey(Object key) {\r
 195         return contains(0, key);\r
 196     }\r
 197 \r
 198     @Override\r
 199     public boolean containsValue(Object value) {\r
 200         return contains(1, value);\r
 201     }\r
 202 \r
 203     @SuppressWarnings("unchecked")\r
 204     @Override\r
 205     public V get(Object key) {\r
 206         if (key == null) {\r
 207             for (int i = 0; i < data.length; i += 2) {\r
 208                 if (data[i] == null) {\r
 209                     return (V) data[i+1];\r
 210                 }\r
 211             }\r
 212             return null;\r
 213         }\r
 214         int hash = key.hashCode();\r
 215         for (int i = 0; i < data.length; i += 2) {\r
 216             Object k = data[i];\r
 217             if (k == key || (hash == k.hashCode() && key.equals(k))) {\r
 218                 return (V) data[i+1];\r
 219             }\r
 220         }\r
 221         return null;\r
 222     }\r
 223 \r
 224     @Override\r
 225     public boolean isEmpty() {\r
 226         return data.length == 0;\r
 227     }\r
 228 \r
 229     @Override\r
 230     public Set<K> keySet() {\r
 231         return (keySet != null) ? keySet : (keySet =  new OffsetSet<K>(0));\r
 232     }\r
 233 \r
 234     @SuppressWarnings("unchecked")\r
 235     @Override\r
 236     public V put(K key, V value) {\r
 237         if (key == null) {\r
 238             for (int i = 0; i < data.length; i += 2) {\r
 239                 if (data[i] == null) {\r
 240                     V old = (V) data[i+1];\r
 241                     data[i+1] = value;\r
 242                     return old;\r
 243                 }\r
 244             }\r
 245             throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");\r
 246         }\r
 247         int hash = key.hashCode();\r
 248         for (int i = 0; i < data.length; i += 2) {\r
 249             K k = (K) data[i];\r
 250             if (k == key || (hash == k.hashCode() && key.equals(k))) {\r
 251                 V old = (V) data[i+1];\r
 252                 data[i+1] = value;\r
 253                 return old;\r
 254             }\r
 255         }\r
 256         throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");\r
 257     }\r
 258 \r
 259     @Override\r
 260     public void putAll(Map<? extends K, ? extends V> m) {\r
 261         for (K k : m.keySet()) {\r
 262             if (!containsKey(k))\r
 263                 throw new UnsupportedOperationException("key " + k + " not present in ArrayMap");\r
 264         }\r
 265         for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {\r
 266             put(entry.getKey(), entry.getValue());\r
 267         }\r
 268     }\r
 269 \r
 270     @Override\r
 271     public V remove(Object key) {\r
 272         throw new UnsupportedOperationException();\r
 273     }\r
 274 \r
 275     @Override\r
 276     public int size() {\r
 277         return data.length >> 1;\r
 278     }\r
 279 \r
 280     @Override\r
 281     public Collection<V> values() {\r
 282         return valueSet != null ? valueSet : (valueSet = new OffsetSet<V>(1));\r
 283     }\r
 284 \r
 285     private boolean contains(int offset, Object o) {\r
 286         int len = data.length;\r
 287         if (o == null) {\r
 288             for (int i = offset; i < len; i += 2)\r
 289                 if (data[i] == null)\r
 290                     return true;\r
 291             return false;\r
 292         }\r
 293         int hash = o.hashCode();\r
 294         for (int i = offset; i < len; i += 2) {\r
 295             Object k = data[i];\r
 296             if (o == k || (hash == k.hashCode() && o.equals(k)))\r
 297                 return true;\r
 298         }\r
 299         return false;\r
 300     }\r
 301 \r
 302     class OffsetSet<T> extends ImmutableSet<T> implements Set<T> {\r
 303 \r
 304         private final int offset;\r
 305 \r
 306         public OffsetSet(int offset) {\r
 307             this.offset = offset;\r
 308         }\r
 309 \r
 310         @Override\r
 311         public boolean contains(Object o) {\r
 312             return InterlacedArrayMap.this.contains(offset, o);\r
 313         }\r
 314 \r
 315         @Override\r
 316         public boolean containsAll(Collection<?> c) {\r
 317             for (Object o : c)\r
 318                 if (!contains(o))\r
 319                     return false;\r
 320             return true;\r
 321         }\r
 322 \r
 323         @Override\r
 324         public boolean isEmpty() {\r
 325             return data.length == 0;\r
 326         }\r
 327 \r
 328         @Override\r
 329         public Iterator<T> iterator() {\r
 330             return new ImmutableIterator<T>() {\r
 331                 int i = offset;\r
 332 \r
 333                 @Override\r
 334                 public boolean hasNext() {\r
 335                     return i < data.length;\r
 336                 }\r
 337 \r
 338                 @Override\r
 339                 public T next() {\r
 340                     if (i >= data.length)\r
 341                         throw new NoSuchElementException("no more elements (" + data.length + " walked)");\r
 342                     @SuppressWarnings("unchecked")\r
 343                     T t = (T) data[i];\r
 344                     ++i;\r
 345                     return t;\r
 346                 }\r
 347             };\r
 348         }\r
 349 \r
 350         @Override\r
 351         public int size() {\r
 352             return data.length >> 1;\r
 353         }\r
 354 \r
 355         @Override\r
 356         public Object[] toArray() {\r
 357             int len = data.length >> 1;\r
 358             Object[] a = new Object[len];\r
 359             for (int i = 0; i < len; ++i)\r
 360                 a[i] = data[i*2+offset];\r
 361             return a;\r
 362         }\r
 363 \r
 364         @SuppressWarnings("unchecked")\r
 365         @Override\r
 366         public <TT> TT[] toArray(TT[] a) {\r
 367             int len = data.length >> 1;\r
 368             if (a.length < len) {\r
 369                 Class<?> clazz = a.getClass();\r
 370                 // Make a new array of a's runtime type, but my contents:\r
 371                 a = ((Object)clazz == (Object)Object[].class)\r
 372                 ? (TT[]) new Object[len]\r
 373                 : (TT[]) Array.newInstance(clazz.getComponentType(), len);\r
 374             }\r
 375             for (int i = 0; i < len; ++i)\r
 376                 a[i] = (TT) data[i*2+offset];\r
 377             if (a.length > len)\r
 378                 a[len] = null;\r
 379             return a;\r
 380         }\r
 381     }\r
 382 \r
 383     class EntrySet extends ImmutableSet<Map.Entry<K, V>> implements Set<Map.Entry<K, V>> {\r
 384 \r
 385         @Override\r
 386         public boolean contains(Object o) {\r
 387             throw new UnsupportedOperationException("TODO");\r
 388         }\r
 389 \r
 390         @Override\r
 391         public boolean containsAll(Collection<?> c) {\r
 392             for (Object o : c)\r
 393                 if (!contains(o))\r
 394                     return false;\r
 395             return true;\r
 396         }\r
 397 \r
 398         @Override\r
 399         public boolean isEmpty() {\r
 400             return data.length == 0;\r
 401         }\r
 402 \r
 403         @Override\r
 404         public Iterator<Map.Entry<K, V>> iterator() {\r
 405             return new ImmutableIterator<Map.Entry<K, V>>() {\r
 406                 int i = 0;\r
 407 \r
 408                 @Override\r
 409                 public boolean hasNext() {\r
 410                     return i < data.length;\r
 411                 }\r
 412 \r
 413                 @Override\r
 414                 public Map.Entry<K, V> next() {\r
 415                     if (i >= data.length)\r
 416                         throw new NoSuchElementException("no more elements (" + (data.length >> 1) + " walked)");\r
 417                     @SuppressWarnings("unchecked")\r
 418                     Map.Entry<K, V> entry = new ArrayMapEntry<K, V>(i, (K) data[i], (V) data[i+1]);\r
 419                     i += 2;\r
 420                     return entry;\r
 421                 }\r
 422             };\r
 423         }\r
 424 \r
 425         @Override\r
 426         public int size() {\r
 427             return data.length >> 1;\r
 428         }\r
 429 \r
 430     }\r
 431 \r
 432     /**\r
 433      * Returns the hash code value for this map.  The hash code of a map is\r
 434      * defined to be the sum of the hash codes of each entry in the map's\r
 435      * <tt>entrySet()</tt> view.  This ensures that <tt>m1.equals(m2)</tt>\r
 436      * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two maps\r
 437      * <tt>m1</tt> and <tt>m2</tt>, as required by the general contract of\r
 438      * {@link Object#hashCode}.\r
 439      *\r
 440      * <p>This implementation iterates over <tt>entrySet()</tt>, calling\r
 441      * {@link Map.Entry#hashCode hashCode()} on each element (entry) in the\r
 442      * set, and adding up the results.\r
 443      *\r
 444      * @return the hash code value for this map\r
 445      * @see Map.Entry#hashCode()\r
 446      * @see Object#equals(Object)\r
 447      * @see Set#equals(Object)\r
 448      */\r
 449     @Override\r
 450     @SuppressWarnings("unchecked")\r
 451     public int hashCode() {\r
 452         int h = 0;\r
 453         int l = data.length;\r
 454         for (int i = 0; i < l; i += 2) {\r
 455             K key = (K) data[i];\r
 456             V value = (V) data[i+1];\r
 457             int hash = (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());\r
 458             h += hash;\r
 459         }\r
 460         return h;\r
 461     }\r
 462 \r
 463     /**\r
 464      * Compares the specified object with this map for equality.  Returns\r
 465      * <tt>true</tt> if the given object is also a map and the two maps\r
 466      * represent the same mappings.  More formally, two maps <tt>m1</tt> and\r
 467      * <tt>m2</tt> represent the same mappings if\r
 468      * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This ensures that the\r
 469      * <tt>equals</tt> method works properly across different implementations\r
 470      * of the <tt>Map</tt> interface.\r
 471      *\r
 472      * <p>This implementation first checks if the specified object is this map;\r
 473      * if so it returns <tt>true</tt>.  Then, it checks if the specified\r
 474      * object is a map whose size is identical to the size of this map; if\r
 475      * not, it returns <tt>false</tt>.  If so, it iterates over this map's\r
 476      * <tt>entrySet</tt> collection, and checks that the specified map\r
 477      * contains each mapping that this map contains.  If the specified map\r
 478      * fails to contain such a mapping, <tt>false</tt> is returned.  If the\r
 479      * iteration completes, <tt>true</tt> is returned.\r
 480      *\r
 481      * @param o object to be compared for equality with this map\r
 482      * @return <tt>true</tt> if the specified object is equal to this map\r
 483      */\r
 484     @Override\r
 485     @SuppressWarnings("unchecked")\r
 486     public boolean equals(Object o) {\r
 487         if (o == this)\r
 488             return true;\r
 489 \r
 490         if (!(o instanceof Map))\r
 491             return false;\r
 492         Map<K, V> m = (Map<K, V>) o;\r
 493         if (m.size() != size())\r
 494             return false;\r
 495 \r
 496         try {\r
 497             int l = data.length;\r
 498             for (int i = 0; i < l; i += 2) {\r
 499                 K key = (K) data[i];\r
 500                 V value = (V) data[i+1];\r
 501                 if (value == null) {\r
 502                     if (!(m.get(key)==null && m.containsKey(key)))\r
 503                         return false;\r
 504                 } else {\r
 505                     if (!value.equals(m.get(key)))\r
 506                         return false;\r
 507                 }\r
 508             }\r
 509         } catch (ClassCastException unused) {\r
 510             return false;\r
 511         } catch (NullPointerException unused) {\r
 512             return false;\r
 513         }\r
 514 \r
 515         return true;\r
 516     }\r
 517 \r
 518     @Override\r
 519     public String toString() {\r
 520         Iterator<Map.Entry<K,V>> i = entrySet().iterator();\r
 521         if (! i.hasNext())\r
 522             return "{}";\r
 523 \r
 524         StringBuilder sb = new StringBuilder();\r
 525         sb.append('{');\r
 526         for (;;) {\r
 527             Map.Entry<K,V> e = i.next();\r
 528             K key = e.getKey();\r
 529             V value = e.getValue();\r
 530             sb.append(key   == this ? "(this Map)" : key);\r
 531             sb.append('=');\r
 532             sb.append(value == this ? "(this Map)" : value);\r
 533             if (! i.hasNext())\r
 534                 return sb.append('}').toString();\r
 535             sb.append(", ");\r
 536         }\r
 537     }\r
 538 }\r