001    /*
002     *  Licensed to the Apache Software Foundation (ASF) under one or more
003     *  contributor license agreements.  See the NOTICE file distributed with
004     *  this work for additional information regarding copyright ownership.
005     *  The ASF licenses this file to You under the Apache License, Version 2.0
006     *  (the "License"); you may not use this file except in compliance with
007     *  the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     *  Unless required by applicable law or agreed to in writing, software
012     *  distributed under the License is distributed on an "AS IS" BASIS,
013     *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     *  See the License for the specific language governing permissions and
015     *  limitations under the License.
016     */
017    package org.apache.commons.collections;
018    
019    import java.io.Externalizable;
020    import java.io.IOException;
021    import java.io.ObjectInput;
022    import java.io.ObjectOutput;
023    import java.util.Iterator;
024    
025    /**
026     * <p>
027     * An implementation of a Map which has a maximum size and uses a Least Recently Used
028     * algorithm to remove items from the Map when the maximum size is reached and new items are added.
029     * </p>
030     * 
031     * <p>
032     * A synchronized version can be obtained with:
033     * <code>Collections.synchronizedMap( theMapToSynchronize )</code>
034     * If it will be accessed by multiple threads, you _must_ synchronize access
035     * to this Map.  Even concurrent get(Object) operations produce indeterminate
036     * behaviour.
037     * </p>
038     * 
039     * <p>
040     * Unlike the Collections 1.0 version, this version of LRUMap does use a true
041     * LRU algorithm.  The keys for all gets and puts are moved to the front of
042     * the list.  LRUMap is now a subclass of SequencedHashMap, and the "LRU"
043     * key is now equivalent to LRUMap.getFirst().
044     * </p>
045     * 
046     * @deprecated Moved to map subpackage. Due to be removed in v4.0.
047     * @since Commons Collections 1.0
048     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
049     * 
050     * @author <a href="mailto:jstrachan@apache.org">James Strachan</a>
051     * @author <a href="mailto:morgand@apache.org">Morgan Delagrange</a>
052     */
053    public class LRUMap extends SequencedHashMap implements Externalizable {
054            
055        private int maximumSize = 0;
056    
057        /**
058         * Default constructor, primarily for the purpose of
059         * de-externalization.  This constructors sets a default
060         * LRU limit of 100 keys, but this value may be overridden
061         * internally as a result of de-externalization.
062         */
063        public LRUMap() {
064            this( 100 );
065        }
066    
067        /**
068         * Create a new LRUMap with a maximum capacity of <i>i</i>.
069         * Once <i>i</i> capacity is achieved, subsequent gets
070         * and puts will push keys out of the map.  See .
071         * 
072         * @param i      Maximum capacity of the LRUMap
073         */
074        public LRUMap(int i) {
075            super( i );
076            maximumSize = i;
077        }
078    
079        /**
080         * <p>Get the value for a key from the Map.  The key
081         * will be promoted to the Most Recently Used position.
082         * Note that get(Object) operations will modify
083         * the underlying Collection.  Calling get(Object)
084         * inside of an iteration over keys, values, etc. is
085         * currently unsupported.</p>
086         * 
087         * @param key    Key to retrieve
088         * @return Returns the value.  Returns null if the key has a
089         *         null value <i>or</i> if the key has no value.
090         */
091        public Object get(Object key) {
092            if(!containsKey(key)) return null;
093    
094            Object value = remove(key);
095            super.put(key,value);
096            return value;
097        }
098    
099         /**
100          * <p>Removes the key and its Object from the Map.</p>
101          * 
102          * <p>(Note: this may result in the "Least Recently Used"
103          * object being removed from the Map.  In that case,
104          * the removeLRU() method is called.  See javadoc for
105          * removeLRU() for more details.)</p>
106          * 
107          * @param key    Key of the Object to add.
108          * @param value  Object to add
109          * @return Former value of the key
110          */    
111        public Object put( Object key, Object value ) {
112    
113            int mapSize = size();
114            Object retval = null;
115    
116            if ( mapSize >= maximumSize ) {
117    
118                // don't retire LRU if you are just
119                // updating an existing key
120                if (!containsKey(key)) {
121                    // lets retire the least recently used item in the cache
122                    removeLRU();
123                }
124            }
125    
126            retval = super.put(key,value);
127    
128            return retval;
129        }
130    
131        /**
132         * This method is used internally by the class for 
133         * finding and removing the LRU Object.
134         */
135        protected void removeLRU() {
136            Object key = getFirstKey();
137            // be sure to call super.get(key), or you're likely to 
138            // get infinite promotion recursion
139            Object value = super.get(key);
140            
141            remove(key);
142    
143            processRemovedLRU(key,value);
144        }
145    
146        /**
147         * Subclasses of LRUMap may hook into this method to
148         * provide specialized actions whenever an Object is
149         * automatically removed from the cache.  By default,
150         * this method does nothing.
151         * 
152         * @param key    key that was removed
153         * @param value  value of that key (can be null)
154         */
155        protected void processRemovedLRU(Object key, Object value) {
156        }
157     
158        // Externalizable interface
159        //-------------------------------------------------------------------------        
160        public void readExternal( ObjectInput in )  throws IOException, ClassNotFoundException {
161            maximumSize = in.readInt();
162            int size = in.readInt();
163            
164            for( int i = 0; i < size; i++ )  {
165                Object key = in.readObject();
166                Object value = in.readObject();
167                put(key,value);
168            }
169        }
170    
171        public void writeExternal( ObjectOutput out ) throws IOException {
172            out.writeInt( maximumSize );
173            out.writeInt( size() );
174            for( Iterator iterator = keySet().iterator(); iterator.hasNext(); ) {
175                Object key = iterator.next();
176                out.writeObject( key );
177                // be sure to call super.get(key), or you're likely to 
178                // get infinite promotion recursion
179                Object value = super.get( key );
180                out.writeObject( value );
181            }
182        }
183        
184        
185        // Properties
186        //-------------------------------------------------------------------------        
187        /** Getter for property maximumSize.
188         * @return Value of property maximumSize.
189         */
190        public int getMaximumSize() {
191            return maximumSize;
192        }
193        /** Setter for property maximumSize.
194         * @param maximumSize New value of property maximumSize.
195         */
196        public void setMaximumSize(int maximumSize) {
197            this.maximumSize = maximumSize;
198            while (size() > maximumSize) {
199                removeLRU();
200            }
201        }
202    
203    
204        // add a serial version uid, so that if we change things in the future
205        // without changing the format, we can still deserialize properly.
206        private static final long serialVersionUID = 2197433140769957051L;
207    }