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 * @param <T> type of stored objects
071 */
072public class Storage<T> extends AbstractSet<T> {
073
074    public static class PrimitiveIdHash implements Hash<PrimitiveId, PrimitiveId> {
075
076        @Override
077        public int getHashCode(PrimitiveId k) {
078            return (int) k.getUniqueId() ^ k.getType().hashCode();
079        }
080
081        @Override
082        public boolean equals(PrimitiveId key, PrimitiveId value) {
083            if (key == null || value == null) return false;
084            return key.getUniqueId() == value.getUniqueId() && key.getType() == value.getType();
085        }
086    }
087
088    private final Hash<? super T, ? super T> hash;
089    private T[] data;
090    private int mask;
091    private int size;
092    private volatile int modCount;
093    private static final double LOAD_FACTOR = 0.6d;
094    private static final int DEFAULT_CAPACITY = 16;
095    private final boolean safeIterator;
096    private boolean arrayCopyNecessary;
097
098    /**
099     * Constructs a new {@code Storage} with default capacity (16).
100     */
101    public Storage() {
102        this(Storage.<T>defaultHash(), DEFAULT_CAPACITY, false);
103    }
104
105    /**
106     * Constructs a new {@code Storage} with given capacity.
107     * @param capacity capacity
108     */
109    public Storage(int capacity) {
110        this(Storage.<T>defaultHash(), capacity, false);
111    }
112
113    public Storage(Hash<? super T, ? super T> ha) {
114        this(ha, DEFAULT_CAPACITY, false);
115    }
116
117    public Storage(boolean safeIterator) {
118        this(Storage.<T>defaultHash(), DEFAULT_CAPACITY, safeIterator);
119    }
120
121    public Storage(int capacity, boolean safeIterator) {
122        this(Storage.<T>defaultHash(), capacity, safeIterator);
123    }
124
125    public Storage(Hash<? super T, ? super T> ha, boolean safeIterator) {
126        this(ha, DEFAULT_CAPACITY, safeIterator);
127    }
128
129    public Storage(Hash<? super T, ? super T> ha, int capacity) {
130        this(ha, capacity, false);
131    }
132
133    /**
134     * constructor
135     * @param ha hash
136     * @param capacity capacity
137     * @param safeIterator If set to false, you must not modify the Storage
138     *          while iterating over it. If set to true, you can safely
139     *          modify, but the read-only iteration will happen on a copy
140     *          of the unmodified Storage.
141     *          This is similar to CopyOnWriteArrayList.
142     */
143    public Storage(Hash<? super T, ? super T> ha, int capacity, boolean safeIterator) {
144        this.hash = ha;
145        int cap = 1 << (int) (Math.ceil(Math.log(capacity/LOAD_FACTOR) / Math.log(2)));
146        @SuppressWarnings("unchecked")
147        T[] newData = (T[]) new Object[cap];
148        data = newData;
149        mask = data.length - 1;
150        this.safeIterator = safeIterator;
151    }
152
153    private void copyArray() {
154        if (arrayCopyNecessary) {
155            data = Utils.copyArray(data);
156            arrayCopyNecessary = false;
157        }
158    }
159
160    // --------------- Collection implementation ------------------------
161    @Override
162    public synchronized int size() {
163        return size;
164    }
165
166    @Override
167    public synchronized Iterator<T> iterator() {
168        if (safeIterator) {
169            arrayCopyNecessary = true;
170            return new SafeReadonlyIter(data);
171        } else
172            return new Iter();
173
174    }
175
176    @Override
177    public synchronized boolean contains(Object o) {
178        @SuppressWarnings("unchecked")
179        T t = (T) o;
180        int bucket = getBucket(hash, t);
181        return bucket >= 0;
182    }
183
184    @Override
185    public synchronized boolean add(T t) {
186        T orig = putUnique(t);
187        return orig == t;
188    }
189
190    @Override
191    public synchronized boolean remove(Object o) {
192        @SuppressWarnings("unchecked")
193        T t = (T) o;
194        T tOrig = removeElem(t);
195        return tOrig != null;
196    }
197
198    @Override
199    public synchronized void clear() {
200        copyArray();
201        modCount++;
202        size = 0;
203        for (int i = 0; i < data.length; i++) {
204            data[i] = null;
205        }
206    }
207
208    @Override
209    public synchronized int hashCode() {
210        int h = 0;
211        for (T t : this) {
212            h += hash.getHashCode(t);
213        }
214        return h;
215    }
216
217    // ----------------- Extended API ----------------------------
218
219    public synchronized T put(T t) {
220        copyArray();
221        modCount++;
222        ensureSpace();
223
224        int bucket = getBucket(hash, t);
225        if (bucket < 0) {
226            size++;
227            bucket = ~bucket;
228            assert data[bucket] == null;
229        }
230
231        T old = data[bucket];
232        data[bucket] = t;
233
234        return old;
235    }
236
237    public synchronized T get(T t) {
238        int bucket = getBucket(hash, t);
239        return bucket < 0 ? null : data[bucket];
240    }
241
242    public synchronized T putUnique(T t) {
243        copyArray();
244        modCount++;
245        ensureSpace();
246
247        int bucket = getBucket(hash, t);
248        if (bucket < 0) { // unique
249            size++;
250            assert data[~bucket] == null;
251            data[~bucket] = t;
252            return t;
253        }
254
255        return data[bucket];
256    }
257
258    public synchronized T removeElem(T t) {
259        copyArray();
260        modCount++;
261        int bucket = getBucket(hash, t);
262        return bucket < 0 ? null : doRemove(bucket);
263    }
264
265    public <K> Map<K, T> foreignKey(Hash<K, ? super T> h) {
266        return new FMap<>(h);
267    }
268
269    // ---------------- Implementation
270
271    /**
272     * Additional mixing of hash
273     * @param h hash
274     * @return new hash
275     */
276    private static int rehash(int h) {
277        return 1103515245*h >> 2;
278    }
279
280    /**
281     * Finds a bucket for given key.
282     * @param <K> type for hashCode and first equals parameter
283     * @param ha hash function
284     *
285     * @param key The key to compare
286     * @return the bucket equivalent to the key or -(bucket) as an empty slot
287     * where such an entry can be stored.
288     */
289    private <K> int getBucket(Hash<K, ? super T> ha, K key) {
290        T entry;
291        int hcode = rehash(ha.getHashCode(key));
292        int bucket = hcode & mask;
293        while ((entry = data[bucket]) != null) {
294            if (ha.equals(key, entry))
295                return bucket;
296            bucket = (bucket+1) & mask;
297        }
298        return ~bucket;
299    }
300
301    private T doRemove(int slot) {
302        T t = data[slot];
303        assert t != null;
304
305        fillTheHole(slot); // fill the hole (or null it)
306        size--;
307        return t;
308    }
309
310    private void fillTheHole(int hole) {
311        int bucket = (hole+1) & mask;
312        T entry;
313
314        while ((entry = data[bucket]) != null) {
315            int right = rehash(hash.getHashCode(entry)) & mask;
316            // if the entry should be in <hole+1,bucket-1> (circular-wise)
317            // we can't move it. The move can be proved safe otherwise,
318            // because the entry safely belongs to <previous_null+1,hole>
319            if ((bucket < right && (right <= hole || hole <= bucket)) ||
320                    (right <= hole && hole <= bucket)) {
321
322                data[hole] = data[bucket];
323                hole = bucket;
324            }
325            bucket = (bucket+1) & mask;
326        }
327
328        // no entry belongs here, just null out the slot
329        data[hole] = null;
330    }
331
332    private void ensureSpace() {
333        if (size > data.length*LOAD_FACTOR) { // rehash
334            @SuppressWarnings("unchecked")
335            T[] big = (T[]) new Object[data.length * 2];
336            int nMask = big.length - 1;
337
338            for (T o : data) {
339                if (o == null) {
340                    continue;
341                }
342                int bucket = rehash(hash.getHashCode(o)) & nMask;
343                while (big[bucket] != null) {
344                    bucket = (bucket+1) & nMask;
345                }
346                big[bucket] = o;
347            }
348
349            data = big;
350            mask = nMask;
351        }
352    }
353
354    // -------------- factories --------------------
355    /**
356     * A factory for default hash implementation.
357     * @param <O> type for hash
358     * @return a hash implementation that just delegates to object's own hashCode and equals.
359     */
360    public static <O> Hash<O, O> defaultHash() {
361        return new Hash<O, O>() {
362            @Override
363            public int getHashCode(O t) {
364                return t.hashCode();
365            }
366
367            @Override
368            public boolean equals(O t1, O t2) {
369                return t1.equals(t2);
370            }
371        };
372    }
373
374    private final class FMap<K> implements Map<K, T> {
375        private final Hash<K, ? super T> fHash;
376
377        private FMap(Hash<K, ? super T> h) {
378            fHash = h;
379        }
380
381        @Override
382        public int size() {
383            return Storage.this.size();
384        }
385
386        @Override
387        public boolean isEmpty() {
388            return Storage.this.isEmpty();
389        }
390
391        @Override
392        public boolean containsKey(Object o) {
393            @SuppressWarnings("unchecked")
394            K key = (K) o;
395            int bucket = getBucket(fHash, key);
396            return bucket >= 0;
397        }
398
399        @Override
400        public boolean containsValue(Object value) {
401            return Storage.this.contains(value);
402        }
403
404        @Override
405        public T get(Object o) {
406            @SuppressWarnings("unchecked")
407            K key = (K) o;
408            int bucket = getBucket(fHash, key);
409            return bucket < 0 ? null : data[bucket];
410        }
411
412        @Override
413        public T put(K key, T value) {
414            if (!fHash.equals(key, value)) throw new IllegalArgumentException("inconsistent key");
415            return Storage.this.put(value);
416        }
417
418        @Override
419        public T remove(Object o) {
420            synchronized (Storage.this) {
421                modCount++;
422                @SuppressWarnings("unchecked")
423                K key = (K) o;
424                int bucket = getBucket(fHash, key);
425
426                return bucket < 0 ? null : doRemove(bucket);
427            }
428        }
429
430        @Override
431        public void putAll(Map<? extends K, ? extends T> m) {
432            if (m instanceof Storage.FMap) {
433                Storage.this.addAll(m.values());
434            } else {
435                for (Map.Entry<? extends K, ? extends T> e : m.entrySet()) {
436                    put(e.getKey(), e.getValue());
437                }
438            }
439        }
440
441        @Override
442        public void clear() {
443            Storage.this.clear();
444        }
445
446        @Override
447        public Set<K> keySet() {
448            throw new UnsupportedOperationException();
449        }
450
451        @Override
452        public Collection<T> values() {
453            return Storage.this;
454        }
455
456        @Override
457        public Set<Entry<K, T>> entrySet() {
458            throw new UnsupportedOperationException();
459        }
460    }
461
462    private final class SafeReadonlyIter implements Iterator<T> {
463        private final T[] data;
464        private int slot;
465
466        SafeReadonlyIter(T[] data) {
467            this.data = data;
468        }
469
470        @Override
471        public boolean hasNext() {
472            align();
473            return slot < data.length;
474        }
475
476        @Override
477        public T next() {
478            if (!hasNext()) throw new NoSuchElementException();
479            return data[slot++];
480        }
481
482        @Override
483        public void remove() {
484            throw new UnsupportedOperationException();
485        }
486
487        private void align() {
488            while (slot < data.length && data[slot] == null) {
489                slot++;
490            }
491        }
492    }
493
494    private final class Iter implements Iterator<T> {
495        private final int mods;
496        private int slot;
497        private int removeSlot = -1;
498
499        Iter() {
500            mods = modCount;
501        }
502
503        @Override
504        public boolean hasNext() {
505            align();
506            return slot < data.length;
507        }
508
509        @Override
510        public T next() {
511            if (!hasNext()) throw new NoSuchElementException();
512            removeSlot = slot;
513            return data[slot++];
514        }
515
516        @Override
517        public void remove() {
518            if (removeSlot == -1) throw new IllegalStateException();
519
520            doRemove(removeSlot);
521            slot = removeSlot; // some entry might have been relocated here
522            removeSlot = -1;
523        }
524
525        private void align() {
526            if (mods != modCount)
527                throw new ConcurrentModificationException();
528            while (slot < data.length && data[slot] == null) {
529                slot++;
530            }
531        }
532    }
533
534}