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

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