KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > commons > collections > LRUMap


1 /*
2  * Copyright 2001-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections;
17
18 import java.io.Externalizable JavaDoc;
19 import java.io.IOException JavaDoc;
20 import java.io.ObjectInput JavaDoc;
21 import java.io.ObjectOutput JavaDoc;
22 import java.util.Iterator JavaDoc;
23
24 /**
25  * <p>
26  * An implementation of a Map which has a maximum size and uses a Least Recently Used
27  * algorithm to remove items from the Map when the maximum size is reached and new items are added.
28  * </p>
29  *
30  * <p>
31  * A synchronized version can be obtained with:
32  * <code>Collections.synchronizedMap( theMapToSynchronize )</code>
33  * If it will be accessed by multiple threads, you _must_ synchronize access
34  * to this Map. Even concurrent get(Object) operations produce indeterminate
35  * behaviour.
36  * </p>
37  *
38  * <p>
39  * Unlike the Collections 1.0 version, this version of LRUMap does use a true
40  * LRU algorithm. The keys for all gets and puts are moved to the front of
41  * the list. LRUMap is now a subclass of SequencedHashMap, and the "LRU"
42  * key is now equivalent to LRUMap.getFirst().
43  * </p>
44  *
45  * @deprecated Moved to map subpackage. Due to be removed in v4.0.
46  * @since Commons Collections 1.0
47  * @version $Revision: 1.23 $ $Date: 2004/02/18 01:15:42 $
48  *
49  * @author <a HREF="mailto:jstrachan@apache.org">James Strachan</a>
50  * @author <a HREF="mailto:morgand@apache.org">Morgan Delagrange</a>
51  */
52 public class LRUMap extends SequencedHashMap implements Externalizable JavaDoc {
53         
54     private int maximumSize = 0;
55
56     /**
57      * Default constructor, primarily for the purpose of
58      * de-externalization. This constructors sets a default
59      * LRU limit of 100 keys, but this value may be overridden
60      * internally as a result of de-externalization.
61      */
62     public LRUMap() {
63         this( 100 );
64     }
65
66     /**
67      * Create a new LRUMap with a maximum capacity of <i>i</i>.
68      * Once <i>i</i> capacity is achieved, subsequent gets
69      * and puts will push keys out of the map. See .
70      *
71      * @param i Maximum capacity of the LRUMap
72      */
73     public LRUMap(int i) {
74         super( i );
75         maximumSize = i;
76     }
77
78     /**
79      * <p>Get the value for a key from the Map. The key
80      * will be promoted to the Most Recently Used position.
81      * Note that get(Object) operations will modify
82      * the underlying Collection. Calling get(Object)
83      * inside of an iteration over keys, values, etc. is
84      * currently unsupported.</p>
85      *
86      * @param key Key to retrieve
87      * @return Returns the value. Returns null if the key has a
88      * null value <i>or</i> if the key has no value.
89      */
90     public Object JavaDoc get(Object JavaDoc key) {
91         if(!containsKey(key)) return null;
92
93         Object JavaDoc value = remove(key);
94         super.put(key,value);
95         return value;
96     }
97
98      /**
99       * <p>Removes the key and its Object from the Map.</p>
100       *
101       * <p>(Note: this may result in the "Least Recently Used"
102       * object being removed from the Map. In that case,
103       * the removeLRU() method is called. See javadoc for
104       * removeLRU() for more details.)</p>
105       *
106       * @param key Key of the Object to add.
107       * @param value Object to add
108       * @return Former value of the key
109       */
110     public Object JavaDoc put( Object JavaDoc key, Object JavaDoc value ) {
111
112         int mapSize = size();
113         Object JavaDoc retval = null;
114
115         if ( mapSize >= maximumSize ) {
116
117             // don't retire LRU if you are just
118 // updating an existing key
119 if (!containsKey(key)) {
120                 // lets retire the least recently used item in the cache
121 removeLRU();
122             }
123         }
124
125         retval = super.put(key,value);
126
127         return retval;
128     }
129
130     /**
131      * This method is used internally by the class for
132      * finding and removing the LRU Object.
133      */
134     protected void removeLRU() {
135         Object JavaDoc key = getFirstKey();
136         // be sure to call super.get(key), or you're likely to
137 // get infinite promotion recursion
138 Object JavaDoc value = super.get(key);
139         
140         remove(key);
141
142         processRemovedLRU(key,value);
143     }
144
145     /**
146      * Subclasses of LRUMap may hook into this method to
147      * provide specialized actions whenever an Object is
148      * automatically removed from the cache. By default,
149      * this method does nothing.
150      *
151      * @param key key that was removed
152      * @param value value of that key (can be null)
153      */
154     protected void processRemovedLRU(Object JavaDoc key, Object JavaDoc value) {
155     }
156  
157     // Externalizable interface
158 //-------------------------------------------------------------------------
159 public void readExternal( ObjectInput JavaDoc in ) throws IOException JavaDoc, ClassNotFoundException JavaDoc {
160         maximumSize = in.readInt();
161         int size = in.readInt();
162         
163         for( int i = 0; i < size; i++ ) {
164             Object JavaDoc key = in.readObject();
165             Object JavaDoc value = in.readObject();
166             put(key,value);
167         }
168     }
169
170     public void writeExternal( ObjectOutput JavaDoc out ) throws IOException JavaDoc {
171         out.writeInt( maximumSize );
172         out.writeInt( size() );
173         for( Iterator JavaDoc iterator = keySet().iterator(); iterator.hasNext(); ) {
174             Object JavaDoc key = iterator.next();
175             out.writeObject( key );
176             // be sure to call super.get(key), or you're likely to
177 // get infinite promotion recursion
178 Object JavaDoc value = super.get( key );
179             out.writeObject( value );
180         }
181     }
182     
183     
184     // Properties
185 //-------------------------------------------------------------------------
186 /** Getter for property maximumSize.
187      * @return Value of property maximumSize.
188      */
189     public int getMaximumSize() {
190         return maximumSize;
191     }
192     /** Setter for property maximumSize.
193      * @param maximumSize New value of property maximumSize.
194      */
195     public void setMaximumSize(int maximumSize) {
196         this.maximumSize = maximumSize;
197         while (size() > maximumSize) {
198             removeLRU();
199         }
200     }
201
202
203     // add a serial version uid, so that if we change things in the future
204 // without changing the format, we can still deserialize properly.
205 private static final long serialVersionUID = 2197433140769957051L;
206 }
207
Popular Tags