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 }