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 transient volatile int modCount = 0;
092    private float loadFactor = 0.6f;
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     * constructor
132     * @param ha
133     * @param capacity
134     * @param safeIterator If set to false, you must not modify the Storage
135     *          while iterating over it. If set to true, you can safely
136     *          modify, but the read-only iteration will happen on a copy
137     *          of the unmodified Storage.
138     *          This is similar to CopyOnWriteArrayList.
139     */
140    public Storage(Hash<? super T, ? super T> ha, int capacity, boolean safeIterator) {
141        this.hash = ha;
142        int cap = 1 << (int)(Math.ceil(Math.log(capacity/loadFactor) / Math.log(2)));
143        @SuppressWarnings("unchecked") T[] newData = (T[]) new Object[cap];
144        data = newData;
145        mask = data.length - 1;
146        this.safeIterator = safeIterator;
147    }
148
149    private void copyArray() {
150        if (arrayCopyNecessary) {
151            data = Utils.copyArray(data);
152            arrayCopyNecessary = false;
153        }
154    }
155
156    // --------------- Collection implementation ------------------------
157    @Override
158    public synchronized int size() {
159        return size;
160    }
161
162    @Override
163    public synchronized Iterator<T> iterator() {
164        if (safeIterator) {
165            arrayCopyNecessary = true;
166            return new SafeReadonlyIter(data);
167        } else
168            return new Iter();
169
170    }
171
172    @Override
173    public synchronized boolean contains(Object o) {
174        @SuppressWarnings("unchecked") T t = (T) o;
175        int bucket = getBucket(hash, t);
176        return bucket >= 0;
177    }
178
179    @Override
180    public synchronized boolean add(T t) {
181        T orig = putUnique(t);
182        return orig == t;
183    }
184
185    @Override
186    public synchronized boolean remove(Object o) {
187        @SuppressWarnings("unchecked") T t = (T) o;
188        T tOrig = removeElem(t);
189        return tOrig != null;
190    }
191
192    @Override
193    public synchronized void clear() {
194        copyArray();
195        modCount++;
196        size = 0;
197        for (int i = 0; i<data.length; i++) {
198            data[i] = null;
199        }
200    }
201
202    @Override
203    public synchronized int hashCode() {
204        int h = 0;
205        for (T t : this) {
206            h += hash.getHashCode(t);
207        }
208        return h;
209    }
210
211    // ----------------- Extended API ----------------------------
212
213    public synchronized T put(T t) {
214        copyArray();
215        modCount++;
216        ensureSpace();
217
218        int bucket = getBucket(hash, t);
219        if (bucket < 0) {
220            size++;
221            bucket = ~bucket;
222            assert data[bucket] == null;
223        }
224
225        T old = data[bucket];
226        data[bucket] = t;
227
228        return old;
229    }
230
231    public synchronized T get(T t) {
232        int bucket = getBucket(hash, t);
233        return bucket < 0 ? null : data[bucket];
234    }
235
236    public synchronized T putUnique(T t) {
237        copyArray();
238        modCount++;
239        ensureSpace();
240
241        int bucket = getBucket(hash, t);
242        if (bucket < 0) { // unique
243            size++;
244            assert data[~bucket] == null;
245            data[~bucket] = t;
246            return t;
247        }
248
249        return data[bucket];
250    }
251
252    public synchronized T removeElem(T t) {
253        copyArray();
254        modCount++;
255        int bucket = getBucket(hash, t);
256        return bucket < 0 ? null : doRemove(bucket);
257    }
258
259    public <K> Map<K,T> foreignKey(Hash<K,? super T> h) {
260        return new FMap<>(h);
261    }
262
263    // ---------------- Implementation
264
265    /**
266     * Additional mixing of hash
267     */
268    private int rehash(int h) {
269        //return 54435761*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            @Override
357            public boolean equals(O t1, O t2) {
358                return t1.equals(t2);
359            }
360        };
361    }
362    /*
363    public static <O> Hash<O,O> identityHash() {
364        return new Hash<O,O>() {
365            public int getHashCode(O t) {
366                return System.identityHashCode(t);
367            }
368            public boolean equals(O t1, O t2) {
369                return t1 == t2;
370            }
371        };
372    }
373     */
374
375    private final class FMap<K> implements Map<K,T> {
376        Hash<K,? super T> fHash;
377
378        private FMap(Hash<K,? super T> h) {
379            fHash = h;
380        }
381
382        @Override
383        public int size() {
384            return Storage.this.size();
385        }
386
387        @Override
388        public boolean isEmpty() {
389            return Storage.this.isEmpty();
390        }
391
392        @Override
393        public boolean containsKey(Object o) {
394            @SuppressWarnings("unchecked") 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") K key = (K) o;
407            int bucket = getBucket(fHash, key);
408            return bucket < 0 ? null : data[bucket];
409        }
410
411        @Override
412        public T put(K key, T value) {
413            if (!fHash.equals(key, value)) throw new IllegalArgumentException("inconsistent key");
414            return Storage.this.put(value);
415        }
416
417        @Override
418        public T remove(Object o) {
419            modCount++;
420            @SuppressWarnings("unchecked") K key = (K) o;
421            int bucket = getBucket(fHash, key);
422
423            return bucket < 0 ? null : doRemove(bucket);
424        }
425
426        @Override
427        public void putAll(Map<? extends K, ? extends T> m) {
428            if (m instanceof Storage.FMap) {
429                Storage.this.addAll(m.values());
430            } else {
431                for (Map.Entry<? extends K, ? extends T> e : m.entrySet()) {
432                    put(e.getKey(), e.getValue());
433                }
434            }
435        }
436
437        @Override
438        public void clear() {
439            Storage.this.clear();
440        }
441
442        @Override
443        public Set<K> keySet() {
444            throw new UnsupportedOperationException();
445        }
446
447        @Override
448        public Collection<T> values() {
449            return Storage.this;
450        }
451
452        @Override
453        public Set<Entry<K, T>> entrySet() {
454            throw new UnsupportedOperationException();
455        }
456    }
457
458    private final class SafeReadonlyIter implements Iterator<T> {
459        final T[] data;
460        int slot = 0;
461
462        SafeReadonlyIter(T[] data) {
463            this.data = data;
464        }
465
466        @Override
467        public boolean hasNext() {
468            align();
469            return slot < data.length;
470        }
471
472        @Override
473        public T next() {
474            if (!hasNext()) throw new NoSuchElementException();
475            return data[slot++];
476        }
477
478        @Override
479        public void remove() {
480            throw new UnsupportedOperationException();
481        }
482
483        private void align() {
484            while (slot < data.length && data[slot] == null) {
485                slot++;
486            }
487        }
488    }
489
490
491    private final class Iter implements Iterator<T> {
492        private final int mods;
493        int slot = 0;
494        int removeSlot = -1;
495
496        Iter() {
497            mods = modCount;
498        }
499
500        @Override
501        public boolean hasNext() {
502            align();
503            return slot < data.length;
504        }
505
506        @Override
507        public T next() {
508            if (!hasNext()) throw new NoSuchElementException();
509            removeSlot = slot;
510            return data[slot++];
511        }
512
513        @Override
514        public void remove() {
515            if (removeSlot == -1) throw new IllegalStateException();
516
517            doRemove(removeSlot);
518            slot = removeSlot; // some entry might have been relocated here
519            removeSlot = -1;
520        }
521
522        private void align() {
523            if (mods != modCount)
524                throw new ConcurrentModificationException();
525            while (slot < data.length && data[slot] == null) {
526                slot++;
527            }
528        }
529    }
530
531}