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

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