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