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