001: /*
002: * Copyright 2001-2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections;
017:
018: import java.io.Externalizable;
019: import java.io.IOException;
020: import java.io.ObjectInput;
021: import java.io.ObjectOutput;
022: import java.util.Iterator;
023:
024: /**
025: * <p>
026: * An implementation of a Map which has a maximum size and uses a Least Recently Used
027: * algorithm to remove items from the Map when the maximum size is reached and new items are added.
028: * </p>
029: *
030: * <p>
031: * A synchronized version can be obtained with:
032: * <code>Collections.synchronizedMap( theMapToSynchronize )</code>
033: * If it will be accessed by multiple threads, you _must_ synchronize access
034: * to this Map. Even concurrent get(Object) operations produce indeterminate
035: * behaviour.
036: * </p>
037: *
038: * <p>
039: * Unlike the Collections 1.0 version, this version of LRUMap does use a true
040: * LRU algorithm. The keys for all gets and puts are moved to the front of
041: * the list. LRUMap is now a subclass of SequencedHashMap, and the "LRU"
042: * key is now equivalent to LRUMap.getFirst().
043: * </p>
044: *
045: * @deprecated Moved to map subpackage. Due to be removed in v4.0.
046: * @since Commons Collections 1.0
047: * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
048: *
049: * @author <a href="mailto:jstrachan@apache.org">James Strachan</a>
050: * @author <a href="mailto:morgand@apache.org">Morgan Delagrange</a>
051: */
052: public class LRUMap extends SequencedHashMap implements Externalizable {
053:
054: private int maximumSize = 0;
055:
056: /**
057: * Default constructor, primarily for the purpose of
058: * de-externalization. This constructors sets a default
059: * LRU limit of 100 keys, but this value may be overridden
060: * internally as a result of de-externalization.
061: */
062: public LRUMap() {
063: this (100);
064: }
065:
066: /**
067: * Create a new LRUMap with a maximum capacity of <i>i</i>.
068: * Once <i>i</i> capacity is achieved, subsequent gets
069: * and puts will push keys out of the map. See .
070: *
071: * @param i Maximum capacity of the LRUMap
072: */
073: public LRUMap(int i) {
074: super (i);
075: maximumSize = i;
076: }
077:
078: /**
079: * <p>Get the value for a key from the Map. The key
080: * will be promoted to the Most Recently Used position.
081: * Note that get(Object) operations will modify
082: * the underlying Collection. Calling get(Object)
083: * inside of an iteration over keys, values, etc. is
084: * currently unsupported.</p>
085: *
086: * @param key Key to retrieve
087: * @return Returns the value. Returns null if the key has a
088: * null value <i>or</i> if the key has no value.
089: */
090: public Object get(Object key) {
091: if (!containsKey(key))
092: 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,
161: ClassNotFoundException {
162: maximumSize = in.readInt();
163: int size = in.readInt();
164:
165: for (int i = 0; i < size; i++) {
166: Object key = in.readObject();
167: Object value = in.readObject();
168: put(key, value);
169: }
170: }
171:
172: public void writeExternal(ObjectOutput out) throws IOException {
173: out.writeInt(maximumSize);
174: out.writeInt(size());
175: for (Iterator iterator = keySet().iterator(); iterator
176: .hasNext();) {
177: Object key = iterator.next();
178: out.writeObject(key);
179: // be sure to call super.get(key), or you're likely to
180: // get infinite promotion recursion
181: Object value = super .get(key);
182: out.writeObject(value);
183: }
184: }
185:
186: // Properties
187: //-------------------------------------------------------------------------
188: /** Getter for property maximumSize.
189: * @return Value of property maximumSize.
190: */
191: public int getMaximumSize() {
192: return maximumSize;
193: }
194:
195: /** Setter for property maximumSize.
196: * @param maximumSize New value of property maximumSize.
197: */
198: public void setMaximumSize(int maximumSize) {
199: this .maximumSize = maximumSize;
200: while (size() > maximumSize) {
201: removeLRU();
202: }
203: }
204:
205: // add a serial version uid, so that if we change things in the future
206: // without changing the format, we can still deserialize properly.
207: private static final long serialVersionUID = 2197433140769957051L;
208: }
|