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 }