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