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