001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.osm;
003
004import java.util.AbstractSet;
005import java.util.Collection;
006import java.util.ConcurrentModificationException;
007import java.util.Iterator;
008import java.util.Map;
009import java.util.NoSuchElementException;
010import java.util.Set;
011
012import org.openstreetmap.josm.tools.Utils;
013
014/**
015 * A Set-like class that allows looking up equivalent preexising instance.
016 * It is useful whereever one would use self-mapping construct like
017 * <code>Map&lt;T,T&gt;.put(t,t)</code>, that is, for caches, uniqueness filters or similar.
018 *
019 * The semantics of equivalency can be external to the object, using the
020 * {@link Hash} interface. The set also supports querying for entries using
021 * different key type, in case you can provide a Hash implementation
022 * that can resolve the equality.
023 *
024 * <h2>Examples</h2>
025 * <ul><li>A String cache:
026 * <pre>
027 * Storage&lt;String&gt; cache = new Storage(); // use default Hash
028 * for (String input : data) {
029 *     String onlyOne = cache.putIfUnique(input);
030 *     ....
031 * }
032 * </pre></li>
033 * <li>Identity-based set:
034 * <pre>
035 * Storage&lt;Object&gt; identity = new Storage(new Hash&lt;Object,Object&gt; {
036 *     public int getHashCode(Object o) {
037 *         return System.identityHashCode(o);
038 *     }
039 *     public boolean equals(Object o1, Object o2) {
040 *         return o1 == o2;
041 *     }
042 *  });
043 * </pre></li>
044 * <li>An object with int ID and id-based lookup:
045 * <pre>
046 * class Thing { int id; }
047 * Storage&lt;Thing&gt; things = new Storage(new Hash&lt;Thing,Thing&gt;() {
048 *     public int getHashCode(Thing t) {
049 *         return t.id;
050 *     }
051 *     public boolean equals(Thing t1, Thing t2) {
052 *         return t1 == t2;
053 *     }
054 *  });
055 * Map&lt;Integer,Thing&gt; fk = things.foreignKey(new Hash&lt;Integer,Thing&gt;() {
056 *     public int getHashCode(Integer i) {
057 *         return i.getIntValue();
058 *     }
059 *     public boolean equals(Integer k, Thing t) {
060 *         return t.id == k.getIntvalue();
061 *     }
062 * }
063 *
064 * things.put(new Thing(3));
065 * assert things.get(new Thing(3)) == fk.get(3);
066 * </pre></li>
067 * </ul>
068 *
069 * @author nenik
070 */
071public class Storage<T> extends AbstractSet<T> {
072
073    public static class PrimitiveIdHash implements Hash<PrimitiveId, PrimitiveId> {
074
075        @Override
076        public int getHashCode(PrimitiveId k) {
077            return (int) k.getUniqueId() ^ k.getType().hashCode();
078        }
079
080        @Override
081        public boolean equals(PrimitiveId key, PrimitiveId value) {
082            if (key == null || value == null) return false;
083            return key.getUniqueId() == value.getUniqueId() && key.getType() == value.getType();
084        }
085    }
086
087    private final Hash<? super T, ? super T> hash;
088    private T[] data;
089    private int mask;
090    private int size;
091    private volatile int modCount;
092    private double loadFactor = 0.6d;
093    private static final int DEFAULT_CAPACITY = 16;
094    private final boolean safeIterator;
095    private boolean arrayCopyNecessary;
096
097    /**
098     * Constructs a new {@code Storage} with default capacity (16).
099     */
100    public Storage() {
101        this(Storage.<T>defaultHash(), DEFAULT_CAPACITY, false);
102    }
103
104    /**
105     * Constructs a new {@code Storage} with given capacity.
106     */
107    public Storage(int capacity) {
108        this(Storage.<T>defaultHash(), capacity, false);
109    }
110
111    public Storage(Hash<? super T, ? super T> ha) {
112        this(ha, DEFAULT_CAPACITY, false);
113    }
114
115    public Storage(boolean safeIterator) {
116        this(Storage.<T>defaultHash(), DEFAULT_CAPACITY, safeIterator);
117    }
118
119    public Storage(int capacity, boolean safeIterator) {
120        this(Storage.<T>defaultHash(), capacity, safeIterator);
121    }
122
123    public Storage(Hash<? super T, ? super T> ha, boolean safeIterator) {
124        this(ha, DEFAULT_CAPACITY, safeIterator);
125    }
126
127    public Storage(Hash<? super T, ? super T> ha, int capacity) {
128        this(ha, capacity, false);
129    }
130
131    /**
132     * constructor
133     * @param ha hash
134     * @param capacity capacity
135     * @param safeIterator If set to false, you must not modify the Storage
136     *          while iterating over it. If set to true, you can safely
137     *          modify, but the read-only iteration will happen on a copy
138     *          of the unmodified Storage.
139     *          This is similar to CopyOnWriteArrayList.
140     */
141    public Storage(Hash<? super T, ? super T> ha, int capacity, boolean safeIterator) {
142        this.hash = ha;
143        int cap = 1 << (int) (Math.ceil(Math.log(capacity/loadFactor) / Math.log(2)));
144        @SuppressWarnings("unchecked") T[] newData = (T[]) new Object[cap];
145        data = newData;
146        mask = data.length - 1;
147        this.safeIterator = safeIterator;
148    }
149
150    private void copyArray() {
151        if (arrayCopyNecessary) {
152            data = Utils.copyArray(data);
153            arrayCopyNecessary = false;
154        }
155    }
156
157    // --------------- Collection implementation ------------------------
158    @Override
159    public synchronized int size() {
160        return size;
161    }
162
163    @Override
164    public synchronized Iterator<T> iterator() {
165        if (safeIterator) {
166            arrayCopyNecessary = true;
167            return new SafeReadonlyIter(data);
168        } else
169            return new Iter();
170
171    }
172
173    @Override
174    public synchronized boolean contains(Object o) {
175        @SuppressWarnings("unchecked") T t = (T) o;
176        int bucket = getBucket(hash, t);
177        return bucket >= 0;
178    }
179
180    @Override
181    public synchronized boolean add(T t) {
182        T orig = putUnique(t);
183        return orig == t;
184    }
185
186    @Override
187    public synchronized boolean remove(Object o) {
188        @SuppressWarnings("unchecked") T t = (T) o;
189        T tOrig = removeElem(t);
190        return tOrig != null;
191    }
192
193    @Override
194    public synchronized void clear() {
195        copyArray();
196        modCount++;
197        size = 0;
198        for (int i = 0; i < data.length; i++) {
199            data[i] = null;
200        }
201    }
202
203    @Override
204    public synchronized int hashCode() {
205        int h = 0;
206        for (T t : this) {
207            h += hash.getHashCode(t);
208        }
209        return h;
210    }
211
212    // ----------------- Extended API ----------------------------
213
214    public synchronized T put(T t) {
215        copyArray();
216        modCount++;
217        ensureSpace();
218
219        int bucket = getBucket(hash, t);
220        if (bucket < 0) {
221            size++;
222            bucket = ~bucket;
223            assert data[bucket] == null;
224        }
225
226        T old = data[bucket];
227        data[bucket] = t;
228
229        return old;
230    }
231
232    public synchronized T get(T t) {
233        int bucket = getBucket(hash, t);
234        return bucket < 0 ? null : data[bucket];
235    }
236
237    public synchronized T putUnique(T t) {
238        copyArray();
239        modCount++;
240        ensureSpace();
241
242        int bucket = getBucket(hash, t);
243        if (bucket < 0) { // unique
244            size++;
245            assert data[~bucket] == null;
246            data[~bucket] = t;
247            return t;
248        }
249
250        return data[bucket];
251    }
252
253    public synchronized T removeElem(T t) {
254        copyArray();
255        modCount++;
256        int bucket = getBucket(hash, t);
257        return bucket < 0 ? null : doRemove(bucket);
258    }
259
260    public <K> Map<K, T> foreignKey(Hash<K, ? super T> h) {
261        return new FMap<>(h);
262    }
263
264    // ---------------- Implementation
265
266    /**
267     * Additional mixing of hash
268     */
269    private static int rehash(int h) {
270        return 1103515245*h >> 2;
271    }
272
273    /**
274     * Finds a bucket for given key.
275     *
276     * @param key The key to compare
277     * @return the bucket equivalent to the key or -(bucket) as an empty slot
278     * where such an entry can be stored.
279     */
280    private <K> int getBucket(Hash<K, ? super T> ha, K key) {
281        T entry;
282        int hcode = rehash(ha.getHashCode(key));
283        int bucket = hcode & mask;
284        while ((entry = data[bucket]) != null) {
285            if (ha.equals(key, entry))
286                return bucket;
287            bucket = (bucket+1) & mask;
288        }
289        return ~bucket;
290    }
291
292    private T doRemove(int slot) {
293        T t = data[slot];
294        assert t != null;
295
296        fillTheHole(slot); // fill the hole (or null it)
297        size--;
298        return t;
299    }
300
301    private void fillTheHole(int hole) {
302        int bucket = (hole+1) & mask;
303        T entry;
304
305        while ((entry = data[bucket]) != null) {
306            int right = rehash(hash.getHashCode(entry)) & mask;
307            // if the entry should be in <hole+1,bucket-1> (circular-wise)
308            // we can't move it. The move can be proved safe otherwise,
309            // because the entry safely belongs to <previous_null+1,hole>
310            if ((bucket < right && (right <= hole || hole <= bucket)) ||
311                    (right <= hole && hole <= bucket)) {
312
313                data[hole] = data[bucket];
314                hole = bucket;
315            }
316            bucket = (bucket+1) & mask;
317        }
318
319        // no entry belongs here, just null out the slot
320        data[hole] = null;
321    }
322
323    private void ensureSpace() {
324        if (size > data.length*loadFactor) { // rehash
325            @SuppressWarnings("unchecked") T[] big = (T[]) new Object[data.length * 2];
326            int nMask = big.length - 1;
327
328            for (T o : data) {
329                if (o == null) {
330                    continue;
331                }
332                int bucket = rehash(hash.getHashCode(o)) & nMask;
333                while (big[bucket] != null) {
334                    bucket = (bucket+1) & nMask;
335                }
336                big[bucket] = o;
337            }
338
339            data = big;
340            mask = nMask;
341        }
342    }
343
344    // -------------- factories --------------------
345    /**
346     * A factory for default hash implementation.
347     * @return a hash implementation that just delegates to object's own
348     * hashCode and equals.
349     */
350    public static <O> Hash<O, O> defaultHash() {
351        return new Hash<O, O>() {
352            @Override
353            public int getHashCode(O t) {
354                return t.hashCode();
355            }
356
357            @Override
358            public boolean equals(O t1, O t2) {
359                return t1.equals(t2);
360            }
361        };
362    }
363
364    private final class FMap<K> implements Map<K, T> {
365        private Hash<K, ? super T> fHash;
366
367        private FMap(Hash<K, ? super T> h) {
368            fHash = h;
369        }
370
371        @Override
372        public int size() {
373            return Storage.this.size();
374        }
375
376        @Override
377        public boolean isEmpty() {
378            return Storage.this.isEmpty();
379        }
380
381        @Override
382        public boolean containsKey(Object o) {
383            @SuppressWarnings("unchecked") K key = (K) o;
384            int bucket = getBucket(fHash, key);
385            return bucket >= 0;
386        }
387
388        @Override
389        public boolean containsValue(Object value) {
390            return Storage.this.contains(value);
391        }
392
393        @Override
394        public T get(Object o) {
395            @SuppressWarnings("unchecked") K key = (K) o;
396            int bucket = getBucket(fHash, key);
397            return bucket < 0 ? null : data[bucket];
398        }
399
400        @Override
401        public T put(K key, T value) {
402            if (!fHash.equals(key, value)) throw new IllegalArgumentException("inconsistent key");
403            return Storage.this.put(value);
404        }
405
406        @Override
407        public T remove(Object o) {
408            modCount++;
409            @SuppressWarnings("unchecked") K key = (K) o;
410            int bucket = getBucket(fHash, key);
411
412            return bucket < 0 ? null : doRemove(bucket);
413        }
414
415        @Override
416        public void putAll(Map<? extends K, ? extends T> m) {
417            if (m instanceof Storage.FMap) {
418                Storage.this.addAll(m.values());
419            } else {
420                for (Map.Entry<? extends K, ? extends T> e : m.entrySet()) {
421                    put(e.getKey(), e.getValue());
422                }
423            }
424        }
425
426        @Override
427        public void clear() {
428            Storage.this.clear();
429        }
430
431        @Override
432        public Set<K> keySet() {
433            throw new UnsupportedOperationException();
434        }
435
436        @Override
437        public Collection<T> values() {
438            return Storage.this;
439        }
440
441        @Override
442        public Set<Entry<K, T>> entrySet() {
443            throw new UnsupportedOperationException();
444        }
445    }
446
447    private final class SafeReadonlyIter implements Iterator<T> {
448        private final T[] data;
449        private int slot;
450
451        SafeReadonlyIter(T[] data) {
452            this.data = data;
453        }
454
455        @Override
456        public boolean hasNext() {
457            align();
458            return slot < data.length;
459        }
460
461        @Override
462        public T next() {
463            if (!hasNext()) throw new NoSuchElementException();
464            return data[slot++];
465        }
466
467        @Override
468        public void remove() {
469            throw new UnsupportedOperationException();
470        }
471
472        private void align() {
473            while (slot < data.length && data[slot] == null) {
474                slot++;
475            }
476        }
477    }
478
479    private final class Iter implements Iterator<T> {
480        private final int mods;
481        private int slot;
482        private int removeSlot = -1;
483
484        Iter() {
485            mods = modCount;
486        }
487
488        @Override
489        public boolean hasNext() {
490            align();
491            return slot < data.length;
492        }
493
494        @Override
495        public T next() {
496            if (!hasNext()) throw new NoSuchElementException();
497            removeSlot = slot;
498            return data[slot++];
499        }
500
501        @Override
502        public void remove() {
503            if (removeSlot == -1) throw new IllegalStateException();
504
505            doRemove(removeSlot);
506            slot = removeSlot; // some entry might have been relocated here
507            removeSlot = -1;
508        }
509
510        private void align() {
511            if (mods != modCount)
512                throw new ConcurrentModificationException();
513            while (slot < data.length && data[slot] == null) {
514                slot++;
515            }
516        }
517    }
518
519}