001/**
002 *
003 * Copyright (c) 2014, the Railo Company Ltd. All rights reserved.
004 *
005 * This library is free software; you can redistribute it and/or
006 * modify it under the terms of the GNU Lesser General Public
007 * License as published by the Free Software Foundation; either 
008 * version 2.1 of the License, or (at your option) any later version.
009 * 
010 * This library is distributed in the hope that it will be useful,
011 * but WITHOUT ANY WARRANTY; without even the implied warranty of
012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
013 * Lesser General Public License for more details.
014 * 
015 * You should have received a copy of the GNU Lesser General Public 
016 * License along with this library.  If not, see <http://www.gnu.org/licenses/>.
017 * 
018 **/
019package lucee.commons.collection;
020import java.util.ConcurrentModificationException;
021import java.util.Iterator;
022import java.util.LinkedHashMap;
023import java.util.Map;
024import java.util.NoSuchElementException;
025
026import lucee.runtime.exp.PageException;
027
028public class LinkedHashMapPro<K,V>
029    extends HashMapPro<K,V>
030    implements MapPro<K,V>
031{
032
033    private static final long serialVersionUID = 3801124242820219131L;
034
035    /**
036     * The head of the doubly linked list.
037     */
038    private transient Entry<K,V> header;
039
040    /**
041     * The iteration ordering method for this linked hash map: <tt>true</tt>
042     * for access-order, <tt>false</tt> for insertion-order.
043     *
044     * @serial
045     */
046    private final boolean accessOrder;
047
048    /**
049     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
050     * with the specified initial capacity and load factor.
051     *
052     * @param  initialCapacity the initial capacity
053     * @param  loadFactor      the load factor
054     * @throws IllegalArgumentException if the initial capacity is negative
055     *         or the load factor is nonpositive
056     */
057    public LinkedHashMapPro(int initialCapacity, float loadFactor) {
058        super(initialCapacity, loadFactor);
059        accessOrder = false;
060    }
061
062    /**
063     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
064     * with the specified initial capacity and a default load factor (0.75).
065     *
066     * @param  initialCapacity the initial capacity
067     * @throws IllegalArgumentException if the initial capacity is negative
068     */
069    public LinkedHashMapPro(int initialCapacity) {
070        super(initialCapacity);
071        accessOrder = false;
072    }
073
074    /**
075     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
076     * with the default initial capacity (16) and load factor (0.75).
077     */
078    public LinkedHashMapPro() {
079        super();
080        accessOrder = false;
081    }
082    
083    // TODO better implementation
084    @Override
085    public void writeExternal(java.io.ObjectOutput out) throws java.io.IOException {
086        out.writeObject(new LinkedHashMap(this));
087    }
088    @Override
089    public void readExternal(java.io.ObjectInput in) throws java.io.IOException, ClassNotFoundException {
090        this.putAll((Map)in.readObject());
091    }
092
093    /**
094     * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
095     * the same mappings as the specified map.  The <tt>LinkedHashMap</tt>
096     * instance is created with a default load factor (0.75) and an initial
097     * capacity sufficient to hold the mappings in the specified map.
098     *
099     * @param  m the map whose mappings are to be placed in this map
100     * @throws NullPointerException if the specified map is null
101     */
102    public LinkedHashMapPro(Map<? extends K, ? extends V> m) {
103        super(m);
104        accessOrder = false;
105    }
106
107    /**
108     * Constructs an empty <tt>LinkedHashMap</tt> instance with the
109     * specified initial capacity, load factor and ordering mode.
110     *
111     * @param  initialCapacity the initial capacity
112     * @param  loadFactor      the load factor
113     * @param  accessOrder     the ordering mode - <tt>true</tt> for
114     *         access-order, <tt>false</tt> for insertion-order
115     * @throws IllegalArgumentException if the initial capacity is negative
116     *         or the load factor is nonpositive
117     */
118    public LinkedHashMapPro(int initialCapacity,
119                         float loadFactor,
120                         boolean accessOrder) {
121        super(initialCapacity, loadFactor);
122        this.accessOrder = accessOrder;
123    }
124
125    /**
126     * Called by superclass constructors and pseudoconstructors (clone,
127     * readObject) before any entries are inserted into the map.  Initializes
128     * the chain.
129     */
130    @Override
131    void init() {
132        header = new Entry<K,V>(-1, null, null, null);
133        header.before = header.after = header;
134    }
135
136    /**
137     * Transfers all entries to new table array.  This method is called
138     * by superclass resize.  It is overridden for performance, as it is
139     * faster to iterate using our linked list.
140     */
141    void transfer(HashMapPro.Entry[] newTable) {
142        int newCapacity = newTable.length;
143        for (Entry<K,V> e = header.after; e != header; e = e.after) {
144            //if (rehash)
145            //    e.hash = (e.key == null) ? 0 : hash(e.key);
146            int index = indexFor(e.hash, newCapacity);
147            e.next = newTable[index];
148            newTable[index] = e;
149        }
150    }
151
152
153    /**
154     * Returns <tt>true</tt> if this map maps one or more keys to the
155     * specified value.
156     *
157     * @param value value whose presence in this map is to be tested
158     * @return <tt>true</tt> if this map maps one or more keys to the
159     *         specified value
160     */
161    public boolean containsValue(Object value) {
162        // Overridden to take advantage of faster iterator
163        if (value==null) {
164            for (Entry e = header.after; e != header; e = e.after)
165                if (e.value==null)
166                    return true;
167        } else {
168            for (Entry e = header.after; e != header; e = e.after)
169                if (value.equals(e.value))
170                    return true;
171        }
172        return false;
173    }
174
175    /**
176     * Returns the value to which the specified key is mapped,
177     * or {@code null} if this map contains no mapping for the key.
178     *
179     * <p>More formally, if this map contains a mapping from a key
180     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
181     * key.equals(k))}, then this method returns {@code v}; otherwise
182     * it returns {@code null}.  (There can be at most one such mapping.)
183     *
184     * <p>A return value of {@code null} does not <i>necessarily</i>
185     * indicate that the map contains no mapping for the key; it's also
186     * possible that the map explicitly maps the key to {@code null}.
187     * The {@link #containsKey containsKey} operation may be used to
188     * distinguish these two cases.
189     */
190    public V get(Object key) {
191        HashMapPro.Entry<K,V> e = getEntry(key);
192        if (e == null)
193            return null;
194        e.recordAccess(this);
195        return e.value;
196    }
197    
198    public V g(K key) throws PageException { 
199        
200        int hash = (key == null) ? 0 : hash(key);
201        for (HashMapPro.Entry<K,V> e = table[indexFor(hash, table.length)];
202             e != null;
203             e = e.next) {
204            Object k;
205            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
206                e.recordAccess(this);
207                return e.getValue();
208            }
209        }
210        throw invalidKey(this, key,false);
211    }
212    
213    public V g(K key, V defaultValue) { 
214        
215        int hash = (key == null) ? 0 : hash(key);
216        for (HashMapPro.Entry<K,V> e = table[indexFor(hash, table.length)];
217             e != null;
218             e = e.next) {
219            Object k;
220            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
221                e.recordAccess(this);
222                return e.getValue();
223            }
224        }
225        return defaultValue;
226    }
227    
228    
229    
230    
231
232    /**
233     * Removes all of the mappings from this map.
234     * The map will be empty after this call returns.
235     */
236    public void clear() {
237        super.clear();
238        header.before = header.after = header;
239    }
240
241    /**
242     * LinkedHashMap entry.
243     */
244    private static class Entry<K,V> extends HashMapPro.Entry<K,V> {
245        // These fields comprise the doubly linked list used for iteration.
246        Entry<K,V> before, after;
247
248        Entry(int hash, K key, V value, HashMapPro.Entry<K,V> next) {
249            super(hash, key, value, next);
250        }
251
252        /**
253         * Removes this entry from the linked list.
254         */
255        private void remove() {
256            before.after = after;
257            after.before = before;
258        }
259
260        /**
261         * Inserts this entry before the specified existing entry in the list.
262         */
263        private void addBefore(Entry<K,V> existingEntry) {
264            after  = existingEntry;
265            before = existingEntry.before;
266            before.after = this;
267            after.before = this;
268        }
269
270        /**
271         * This method is invoked by the superclass whenever the value
272         * of a pre-existing entry is read by Map.get or modified by Map.set.
273         * If the enclosing Map is access-ordered, it moves the entry
274         * to the end of the list; otherwise, it does nothing.
275         */
276        void recordAccess(HashMapPro<K,V> m) {
277            LinkedHashMapPro<K,V> lm = (LinkedHashMapPro<K,V>)m;
278            if (lm.accessOrder) {
279                lm.modCount++;
280                remove();
281                addBefore(lm.header);
282            }
283        }
284
285        void recordRemoval(HashMapPro<K,V> m) {
286            remove();
287        }
288    }
289
290    private abstract class LinkedHashIterator<T> implements Iterator<T> {
291        Entry<K,V> nextEntry    = header.after;
292        Entry<K,V> lastReturned = null;
293
294        /**
295         * The modCount value that the iterator believes that the backing
296         * List should have.  If this expectation is violated, the iterator
297         * has detected concurrent modification.
298         */
299        int expectedModCount = modCount;
300
301        public boolean hasNext() {
302            return nextEntry != header;
303        }
304
305        public void remove() {
306            if (lastReturned == null)
307                throw new IllegalStateException();
308            if (modCount != expectedModCount)
309                throw new ConcurrentModificationException();
310
311            LinkedHashMapPro.this.remove(lastReturned.key);
312            lastReturned = null;
313            expectedModCount = modCount;
314        }
315
316        Entry<K,V> nextEntry() {
317            if (modCount != expectedModCount)
318                throw new ConcurrentModificationException();
319            if (nextEntry == header)
320                throw new NoSuchElementException();
321
322            Entry<K,V> e = lastReturned = nextEntry;
323            nextEntry = e.after;
324            return e;
325        }
326    }
327
328    private class KeyIterator extends LinkedHashIterator<K> {
329        public K next() { return nextEntry().getKey(); }
330    }
331
332    private class ValueIterator extends LinkedHashIterator<V> {
333        public V next() { return nextEntry().value; }
334    }
335
336    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
337        public Map.Entry<K,V> next() { return nextEntry(); }
338    }
339
340    // These Overrides alter the behavior of superclass view iterator() methods
341    Iterator<K> newKeyIterator()   { return new KeyIterator();   }
342    Iterator<V> newValueIterator() { return new ValueIterator(); }
343    Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
344
345    /**
346     * This override alters behavior of superclass put method. It causes newly
347     * allocated entry to get inserted at the end of the linked list and
348     * removes the eldest entry if appropriate.
349     */
350    void addEntry(int hash, K key, V value, int bucketIndex) {
351        super.addEntry(hash, key, value, bucketIndex);
352
353        // Remove eldest entry if instructed
354        Entry<K,V> eldest = header.after;
355        if (removeEldestEntry(eldest)) {
356            removeEntryForKey(eldest.key);
357        }
358    }
359
360    /**
361     * This override differs from addEntry in that it doesn't resize the
362     * table or remove the eldest entry.
363     */
364    void createEntry(int hash, K key, V value, int bucketIndex) {
365        HashMapPro.Entry<K,V> old = table[bucketIndex];
366        Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
367        table[bucketIndex] = e;
368        e.addBefore(header);
369        size++;
370    }
371
372    /**
373     * Returns <tt>true</tt> if this map should remove its eldest entry.
374     * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
375     * inserting a new entry into the map.  It provides the implementor
376     * with the opportunity to remove the eldest entry each time a new one
377     * is added.  This is useful if the map represents a cache: it allows
378     * the map to reduce memory consumption by deleting stale entries.
379     *
380     * <p>Sample use: this override will allow the map to grow up to 100
381     * entries and then delete the eldest entry each time a new entry is
382     * added, maintaining a steady state of 100 entries.
383     * <pre>
384     *     private static final int MAX_ENTRIES = 100;
385     *
386     *     protected boolean removeEldestEntry(Map.Entry eldest) {
387     *        return size() > MAX_ENTRIES;
388     *     }
389     * </pre>
390     *
391     * <p>This method typically does not modify the map in any way,
392     * instead allowing the map to modify itself as directed by its
393     * return value.  It <i>is</i> permitted for this method to modify
394     * the map directly, but if it does so, it <i>must</i> return
395     * <tt>false</tt> (indicating that the map should not attempt any
396     * further modification).  The effects of returning <tt>true</tt>
397     * after modifying the map from within this method are unspecified.
398     *
399     * <p>This implementation merely returns <tt>false</tt> (so that this
400     * map acts like a normal map - the eldest element is never removed).
401     *
402     * @param    eldest The least recently inserted entry in the map, or if
403     *           this is an access-ordered map, the least recently accessed
404     *           entry.  This is the entry that will be removed it this
405     *           method returns <tt>true</tt>.  If the map was empty prior
406     *           to the <tt>put</tt> or <tt>putAll</tt> invocation resulting
407     *           in this invocation, this will be the entry that was just
408     *           inserted; in other words, if the map contains a single
409     *           entry, the eldest entry is also the newest.
410     * @return   <tt>true</tt> if the eldest entry should be removed
411     *           from the map; <tt>false</tt> if it should be retained.
412     */
413    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
414        return false;
415    }
416}