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
10 * VTT Technical Research Centre of Finland - initial API and implementation
\r
11 *******************************************************************************/
\r
12 package org.simantics.utils.datastructures;
\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
23 * A space-optimized immutable Map implementation.
\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
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
35 * @author Tuukka Lehtonen
\r
37 * @param <K> key class
\r
38 * @param <V> value class
\r
40 public class ArrayMap<K, V> implements Map<K, V> {
\r
44 Set<Map.Entry<K, V>> entrySet;
\r
46 Collection<V> valueSet;
\r
48 public static class ArrayMapBuilder<K2, V2> {
\r
50 final private K2[] keys;
\r
52 ArrayMapBuilder(K2[] keys) {
\r
56 public ArrayMap<K2, V2> values(@SuppressWarnings("unchecked") V2 ... values) {
\r
57 return new ArrayMap<K2, V2>(keys, values);
\r
62 public static <K2, V2>ArrayMapBuilder<K2, V2> keys(@SuppressWarnings("unchecked") K2 ... keys) {
\r
63 return new ArrayMapBuilder<K2, V2>(keys);
\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
71 * Constructs new ArrayMap based on a key and value array. Both arrays must
\r
72 * be of the same size.
\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
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
84 this.values = values;
\r
88 public Set<Map.Entry<K, V>> entrySet() {
\r
89 return (entrySet != null) ? entrySet : (entrySet = new EntrySet());
\r
93 public void clear() {
\r
94 throw new UnsupportedOperationException();
\r
98 public boolean containsKey(Object key) {
\r
99 return keySet().contains(key);
\r
103 public boolean containsValue(Object value) {
\r
104 return values().contains(value);
\r
108 public V get(Object key) {
\r
110 for (int i = 0; i < keys.length; i++) {
\r
111 if (keys[i] == null) {
\r
117 int hash = key.hashCode();
\r
118 for (int i = 0; i < keys.length; i++) {
\r
120 if (k == key || (hash == k.hashCode() && key.equals(k))) {
\r
128 public boolean isEmpty() {
\r
129 return keys.length == 0;
\r
133 public Set<K> keySet() {
\r
134 return (keySet != null) ? keySet : (keySet = new KeySet());
\r
138 public V put(K key, V value) {
\r
140 for (int i = 0; i < keys.length; i++) {
\r
141 if (keys[i] == null) {
\r
147 throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");
\r
149 int hash = key.hashCode();
\r
150 for (int i = 0; i < keys.length; i++) {
\r
152 if (k == key || (hash == k.hashCode() && key.equals(k))) {
\r
158 throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");
\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
167 for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
\r
168 put(entry.getKey(), entry.getValue());
\r
173 public V remove(Object key) {
\r
174 throw new UnsupportedOperationException();
\r
178 public int size() {
\r
179 return keys.length;
\r
183 public Collection<V> values() {
\r
184 return valueSet != null ? valueSet : (valueSet = Collections.unmodifiableCollection(Arrays.asList(values)));
\r
187 class KeySet extends ImmutableSet<K> implements Set<K> {
\r
190 public boolean contains(Object o) {
\r
197 int hash = o.hashCode();
\r
199 if (o == k || (hash == k.hashCode() && o.equals(k)))
\r
205 public boolean containsAll(Collection<?> c) {
\r
213 public boolean isEmpty() {
\r
214 return keys.length == 0;
\r
218 public Iterator<K> iterator() {
\r
219 return new ImmutableIterator<K>() {
\r
223 public boolean hasNext() {
\r
224 return i < keys.length;
\r
229 if (i >= keys.length)
\r
230 throw new NoSuchElementException("no more elements (" + keys.length + " walked)");
\r
239 public int size() {
\r
240 return keys.length;
\r
244 public Object[] toArray() {
\r
248 @SuppressWarnings("unchecked")
\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
261 class EntrySet extends ImmutableSet<Map.Entry<K, V>> implements Set<Map.Entry<K, V>> {
\r
264 public boolean contains(Object o) {
\r
265 throw new UnsupportedOperationException("TODO");
\r
269 public boolean containsAll(Collection<?> c) {
\r
277 public boolean isEmpty() {
\r
278 return keys.length == 0;
\r
282 public Iterator<Map.Entry<K, V>> iterator() {
\r
283 return new ImmutableIterator<Map.Entry<K, V>>() {
\r
287 public boolean hasNext() {
\r
288 return i < keys.length;
\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
303 public int size() {
\r
304 return keys.length;
\r
309 static class Entry<K, V> implements Map.Entry<K, V> {
\r
314 * Creates new entry.
\r
316 Entry(int h, K k, V v) {
\r
322 public final K getKey() {
\r
327 public final V getValue() {
\r
332 public final V setValue(V newValue) {
\r
333 V oldValue = value;
\r
339 public final boolean equals(Object o) {
\r
340 if (!(o instanceof Map.Entry<?, ?>))
\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
355 public final int hashCode() {
\r
356 return (key==null ? 0 : key.hashCode()) ^
\r
357 (value==null ? 0 : value.hashCode());
\r
361 public final String toString() {
\r
362 return getKey() + "=" + getValue();
\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
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
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
384 public int hashCode() {
\r
386 int l = keys.length;
\r
387 for (int i = 0; i < l; i++) {
\r
389 V value = values[i];
\r
390 int hash = (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());
\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
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
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
418 @SuppressWarnings("unchecked")
\r
419 public boolean equals(Object o) {
\r
423 if (!(o instanceof Map))
\r
425 Map<K, V> m = (Map<K, V>) o;
\r
426 if (m.size() != size())
\r
430 int l = keys.length;
\r
431 for (int i = 0; i < l; i++) {
\r
433 V value = values[i];
\r
434 if (value == null) {
\r
435 if (!(m.get(key)==null && m.containsKey(key)))
\r
438 if (!value.equals(m.get(key)))
\r
442 } catch (ClassCastException unused) {
\r
444 } catch (NullPointerException unused) {
\r
452 public String toString() {
\r
453 Iterator<Map.Entry<K,V>> i = entrySet().iterator();
\r
457 StringBuilder sb = new StringBuilder();
\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
465 sb.append(value == this ? "(this Map)" : value);
\r
467 return sb.append('}').toString();
\r