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