LRUMap


1   /* ====================================================================
2    *
3    * The Apache Software License, Version 1.1
4    *
5    * Copyright (c) 1999-2002 The Apache Software Foundation.  All rights
6    * reserved.
7    *
8    * Redistribution and use in source and binary forms, with or without
9    * modification, are permitted provided that the following conditions
10   * are met:
11   *
12   * 1. Redistributions of source code must retain the above copyright
13   *    notice, this list of conditions and the following disclaimer.
14   *
15   * 2. Redistributions in binary form must reproduce the above copyright
16   *    notice, this list of conditions and the following disclaimer in
17   *    the documentation and/or other materials provided with the
18   *    distribution.
19   *
20   * 3. The end-user documentation included with the redistribution, if
21   *    any, must include the following acknowlegement:
22   *       "This product includes software developed by the
23   *        Apache Software Foundation (http://www.apache.org/)."
24   *    Alternately, this acknowlegement may appear in the software itself,
25   *    if and wherever such third-party acknowlegements normally appear.
26   *
27   * 4. The names "The Jakarta Project", "Commons", and "Apache Software
28   *    Foundation" must not be used to endorse or promote products derived
29   *    from this software without prior written permission. For written
30   *    permission, please contact apache@apache.org.
31   *
32   * 5. Products derived from this software may not be called "Apache"
33   *    nor may "Apache" appear in their names without prior written
34   *    permission of the Apache Group.
35   *
36   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
40   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
43   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
44   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
45   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
46   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47   * SUCH DAMAGE.
48   * ====================================================================
49   *
50   * This software consists of voluntary contributions made by many
51   * individuals on behalf of the Apache Software Foundation.  For more
52   * information on the Apache Software Foundation, please see
53   * <http://www.apache.org/>.
54   *
55   */
56  package org.enhydra.shark.utilities;
57  
58  import java.io.Externalizable  ;
59  import java.io.IOException  ;
60  import java.io.ObjectInput  ;
61  import java.io.ObjectOutput  ;
62  import java.util.Iterator  ;
63  import java.util.Map  ;
64  
65  /**
66   * <p>
67   * An implementation of a Map which has a maximum size and uses a Least Recently Used
68   * algorithm to remove items from the Map when the maximum size is reached and new items are added.
69   * </p>
70   *
71   * <p>
72   * A synchronized version can be obtained with:
73   * <code>Collections.synchronizedMap( theMapToSynchronize )</code>
74   * If it will be accessed by multiple threads, you _must_ synchronize access
75   * to this Map.  Even concurrent get(Object) operations produce indeterminate
76   * behaviour.
77   * </p>
78   *
79   * <p>
80   * Unlike the Collections 1.0 version, this version of LRUCache does use a true
81   * LRU algorithm.  The keys for all gets and puts are moved to the front of
82   * the list.  LRUCache is now a subclass of SequencedHashMap, and the "LRU"
83   * key is now equivalent to LRUCache.getFirst().
84   * </p>
85   *
86   * @since 1.0
87   * @author <a HREF="mailto:jstrachan@apache.org">James Strachan</a>
88   * @author <a HREF="mailto:morgand@apache.org">Morgan Delagrange</a>
89   */
90  public class LRUMap extends SequencedHashMap implements Externalizable   {
91  
92     private int maximumSize = 0;
93  
94     /**
95      * Default constructor, primarily for the purpose of
96      * de-externalization.  This constructors sets a default
97      * cache with maximum size set to 0 (cache is not used at the moment) and
98      * with a default capacity (16) and load factor (0.75).
99      */
100    public LRUMap() {
101       super();
102    }
103 
104    /**
105     * Creates a new LRUMap with a maximum capacity of <i>maxSize</i> and
106     * with a default capacity (16) and load factor (0.75). Once <i>maxSize</i>
107     * capacity is achieved, subsequent gets and puts will push keys out of
108     * the map.
109     *
110     * @param maxSize      Maximum capacity of the LRUMap.
111     */
112    public LRUMap(int maxSize) {
113       this();
114       maximumSize = maxSize;
115    }
116 
117    /**
118     * Create a new LRUCache with a default maximum capacity (0) and
119     * with the capacity <i>initialCapacity</i> and load factor <i>loadFactor</i>.
120     *
121     * @param  initialCapacity The initial capacity.
122     * @param  loadFactor The load factor.
123     */
124    public LRUMap(int initialCapacity, float loadFactor) {
125       super(initialCapacity, loadFactor);
126    }
127 
128    /**
129     * Create a new LRUCache with a maximum capacity of <i>maxSize</i> and
130     * with the capacity <i>initialCapacity</i> and load factor <i>loadFactor</i>.
131     * Once <i>maxSize</i> capacity is achieved, subsequent gets and puts will
132     * push keys out of the map.
133     *
134     * @param  initialCapacity The initial capacity.
135     * @param  loadFactor The load factor.
136     * @param  maxSize Maximum capacity of the LRUMap.
137     */
138 
139    public LRUMap(int initialCapacity, float loadFactor, int maxSize) {
140       this(initialCapacity, loadFactor);
141       maximumSize = maxSize;
142    }
143 
144    /**
145     * Create a new LRUCache with the same mappings as the specified map <i>m</i>.
146     * The <tt>LRUCache</tt> instance is created with default load factor (0.75)
147     * and an initial capacity sufficient to hold the mappings in the specified
148     * map.
149     *
150     * @param  m The map whose mappings are to be placed in this LRUCache.
151     */
152 
153    public LRUMap(Map   m) {
154       maximumSize = m.size()+1;
155       //        super(m);
156       putAll(m);
157    }
158 
159    /**
160     * Create a new LRUCache with the same mappings as the specified map <i>m</i>.
161     * The <tt>LRUCache</tt> instance is created with default load factor (0.75)
162     * and an initial capacity sufficient to hold the mappings in the specified
163     * map. The attribute <i>maximumSize</i> is set to value <i>maxSize</i> if
164     * that value is greater than the size of the map <i>m</i>.
165     *
166     * @param  m The map whose mappings are to be placed in this LRUCache.
167     * @param  maxSize Maximum capacity of the LRUMap.
168     */
169    public LRUMap(Map   m, int maxSize) {
170       this(m);
171       if ((maxSize<0) || (maxSize>m.size()+1))
172          maximumSize = maxSize;
173    }
174 
175    /**
176     * Returns true if this LRUCache contains a mapping for the specified key.
177     *
178     * @param key The key whose presence in this LRUCache is to be tested.
179     *
180     * @return true if this LRUCache contains a mapping for the specified key.
181     */
182    public boolean containsKey(Object   key) {
183       if(maximumSize == 0)
184          return false;
185       return super.containsKey(key);
186    }
187 
188    /**
189     * Returns the value to which the specified key is mapped in this LRUCache,
190     * or null if the map contains no mapping for this key. If found, the key
191     * will be promoted to the Most Recently Used position.
192     * Note that get(Object) operations will modify the underlying Collection.
193     * Calling get(Object) inside of an iteration over keys, values, etc. is
194     * currently unsupported.</p>
195     *
196     * @param key    Key to retrieve.
197     * @return Returns the value. Returns null if the key has a null value <i>or</i>
198     * if the key has no value.
199     */
200    public Object   get(Object   key) {
201       if(maximumSize == 0)
202          return null;
203       if(!containsKey(key))
204          return null;
205       Object   value = remove(key);
206       super.put(key,value);
207       return value;
208    }
209 
210    /**
211     * Associates the specified value with the specified key in this LRUCache.
212     * If the map previously contained a mapping for this key, the old value
213     * is replaced.
214     * <p>(Note: this may result in the "Least Recently Used"
215     * object being removed from the Map.  In that case,
216     * the removeLRU() method is called.  See javadoc for
217     * removeLRU() for more details.)</p>
218     *
219     * @param key Key with which the specified value is to be associated.
220     * @param value Value to be associated with the specified key.
221     * @return Former value of the key.
222     */
223 
224 
225    public Object   put( Object   key, Object   value ) {
226       if(maximumSize == 0)
227          return null;
228       int mapSize = size();
229       Object   retval = null;
230 
231       if ((maximumSize > 0) && (mapSize >= maximumSize )) {
232 
233          // don't retire LRU if you are just
234          // updating an existing key
235          if (!containsKey(key)) {
236             // lets retire the least recently used item in the cache
237             removeLRU();
238          }
239       }
240       retval = super.put(key,value);
241       return retval;
242    }
243 
244    /**
245     *  Adds all the mappings in the specified map to this map, replacing any
246     *  mappings that already exist (as per {@link Map#putAll(Map)}).  The order
247     *  in which the entries are added is determined by the iterator returned
248     *  from {@link Map#entrySet()} for the specified map.
249     *
250     *  @param t the mappings that should be added to this map.
251     *
252     *  @exception NullPointerException if <code>t</code> is <code>null</code>.
253     **/
254    public void putAll(Map   t) {
255       Iterator   iter = t.entrySet().iterator();
256       while(iter.hasNext()) {
257          Map.Entry   entry = (Map.Entry  )iter.next();
258          this.put(entry.getKey(), entry.getValue());
259       }
260    }
261 
262    /**
263     * This method is used internally by the class for finding and removing
264     * the LRU Object.
265     */
266    protected void removeLRU() {
267       Object   key = getFirstKey();
268       // be sure to call super.get(key), or you're likely to
269       // get infinite promotion recursion
270       Object   value = super.get(key);
271       remove(key);
272       processRemovedLRU(key,value);
273    }
274 
275    /**
276     * Subclasses of LRUCache may hook into this method to
277     * provide specialized actions whenever an Object is
278     * automatically removed from the cache.  By default,
279     * this method does nothing.
280     *
281     * @param key    Key that was removed.
282     * @param value  Value of that key (can be null).
283     */
284    protected void processRemovedLRU(Object   key, Object   value) {
285    }
286 
287    // Externalizable interface
288    //-------------------------------------------------------------------------
289    public void readExternal( ObjectInput   in )  throws IOException  , ClassNotFoundException   {
290       maximumSize = in.readInt();
291       int size = in.readInt();
292 
293       for( int i = 0; i < size; i++ )  {
294          Object   key = in.readObject();
295          Object   value = in.readObject();
296          put(key,value);
297       }
298    }
299 
300    public void writeExternal( ObjectOutput   out ) throws IOException   {
301       out.writeInt( maximumSize );
302       out.writeInt( size() );
303       for( Iterator   iterator = keySet().iterator(); iterator.hasNext(); ) {
304          Object   key = iterator.next();
305          out.writeObject( key );
306          // be sure to call super.get(key), or you're likely to
307          // get infinite promotion recursion
308          Object   value = super.get( key );
309          out.writeObject( value );
310       }
311    }
312 
313 
314    // Properties
315    //-------------------------------------------------------------------------
316    /**
317     * Getter for property maximumSize.
318     *
319     * @return Value of property maximumSize.
320     */
321    public int getMaximumSize() {
322       return maximumSize;
323    }
324    /**
325     * Setter for property maximumSize.
326     *
327     * @param maxSize New value of property maximumSize.
328     */
329    public void setMaximumSize(int maxSize) {
330       this.maximumSize = maxSize;
331       if(maxSize >= 0) {
332          while (size() > maximumSize) {
333             removeLRU();
334          }
335       }
336    }
337 
338 
339    // add a serial version uid, so that if we change things in the future
340    // without changing the format, we can still deserialize properly.
341    //    private static final long serialVersionUID = 2197433140769957051L;
342 }
343
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags