001 package org.rakeshv.utils;
002
003 import java.util.HashMap;
004
005 /**
006 * A <i><b>L</b>east <b>R</b>ecently <b>U</b>sed</i> implementation
007 * using an <code>array</code> and a <code>Map</code>.
008 *
009 * @see SharedObject
010 * @see ObjectCache
011 *
012 * <p>Copyright 2002-2006 Rakesh Vidyadharan</p>
013 * @author Rakesh Vidyadharan 2002 March 2
014 * @version $Id: SimpleLRU.java,v 1.5 2006/03/11 16:32:01 rakesh Exp $
015 */
016 public class SimpleLRU<T> extends Object implements DataStructure<T>
017 {
018 /**
019 * An array that is used to implement a <code>LRU</code>.
020 */
021 private T[] lru;
022
023 /**
024 * A <code>Map</code> that is used to map the {@link #index} (value)
025 * to the <code>Object</code> (key) that is being stored in the LRU.
026 * It also serves as a fast means for accessing objects that are
027 * stored in the LRU.
028 */
029 private HashMap<T, Integer> map;
030
031 /**
032 * A variable that holds the index into the {@link #lru} at which
033 * a new instance is to be added. The index <code>rolls around
034 * </code> from the end of the lru to the beginning when the lru
035 * is full.
036 */
037 private int index;
038
039 /**
040 * A flag to indicate that the lru has been filled. This will be
041 * set only once after the lru has been filled initially.
042 */
043 private boolean filled;
044
045 /**
046 * Construct a new <code>LRU</code> of the specified size.
047 */
048 @SuppressWarnings(value={"unchecked"})
049 public SimpleLRU( int size )
050 {
051 super();
052 filled = false;
053 lru = (T[]) new Object[ size ];
054 map = new HashMap<T, Integer>( size );
055 }
056
057 /**
058 * Return the current <code>Object</code> in the {@link #lru}. This
059 * is the object that will be replaced when the next call to
060 * {@link #add( Object )} is made.
061 *
062 * @return The Object that is at the {@link #index} within the lru.
063 * This will be <code>null</code> if the lru has not been
064 * {@link #filled} yet.
065 */
066 public T get()
067 {
068 return lru[ index ];
069 }
070
071 /**
072 * Add the specified object to {@link #lru}. Updates the {@link
073 * #index} after adding the specified object to the next location
074 * in the lru. Sets {@link #filled} to <code>true</code> when the
075 * {@link #index} rolls around to the beginning of the lru for the
076 * first time.
077 *
078 * <p><b>Note:</b> This method does not perform any <code>
079 * synchronisation</code>, and hence is not <code>thread-safe</code>.
080 * Client's must perform their own synchronisation if they so desire.
081 * </p>
082 *
083 * @param object The object to be added to the lru.
084 * @throws IllegalArgumentException If a <code>null</code> value was
085 * specified for the object.
086 */
087 public void add( T object )
088 {
089 if ( object == null )
090 {
091 throw new IllegalArgumentException(
092 "Null values are not allowed in the LRU" );
093 }
094
095 if ( map.containsKey( object ) )
096 {
097 if ( filled )
098 {
099 Integer position = (Integer) map.get( object );
100
101 if ( position.intValue() < ( lru.length - 1 ) )
102 {
103 T next = lru[ position.intValue() + 1 ];
104 Integer nextPosition = (Integer) map.get( next );
105
106 map.put( next, position );
107 map.put( object, nextPosition );
108
109 lru[ position.intValue() ] = next;
110 lru[ nextPosition.intValue() ] = object;
111 }
112 }
113 }
114 else if ( filled )
115 {
116 Integer position = (Integer) map.remove( lru[ 0 ] );
117 lru[ 0 ] = object;
118 map.put( object, position );
119 }
120 else
121 {
122 lru[ index ] = object;
123 map.put( object, new Integer( index ) );
124 index = ( ++index ) % lru.length;
125 }
126
127 if ( ! filled && index == 0 ) filled = true;
128 }
129
130 /**
131 * Removes the current <code>Object</code> designated for removal
132 * (located at index 0) from the {@link #lru} and the associated
133 * mapping from {@link #map}.
134 *
135 * @return The Object that was removed.
136 */
137 public T remove()
138 {
139 map.remove( lru[0 ] );
140 return lru[0];
141 }
142
143 /**
144 * Removes the specified object from the {@link #lru}. The time to
145 * remove the specified object will be directly proportional to the
146 * size of the lru.
147 *
148 * <p>This operation can be heavy, since it involves reordering
149 * the lru. The following conditions apply:</p>
150 *
151 * <ol>
152 * <li>Remove the matching object from the lru.
153 * <li>Move all succeeding objects in the lru up by one position.
154 * <li>Reset the {@link #index} to point to the end of the lru
155 * or to the previous position depending upon whether the lru was
156 * {@link #filled} or not.
157 * <li>Matching is performed using the equivalent matching rule
158 * (the {@link #equals( Object )}) operator as is implemented in the
159 * <code>Map</code> implementations.
160 * </ol>
161 *
162 * <p>If there are multiple instances of the same object in the lru,
163 * only the first matching object is removed.</p>
164 *
165 * <p><b>Note:</b> This method does not perform any <code>
166 * synchronisation</code>, and hence is not <code>thread-safe</code>.
167 * Client's must perform their own synchronisation if they so desire.
168 * </p>
169 *
170 * @param object The object that is to be removed from the lru.
171 * @return Returns <code>true</code> if the specified object was
172 * found and removed from the lru.
173 */
174 public boolean remove( T object )
175 {
176 boolean result = false;
177
178 int iterator = 0;
179 if ( map.containsKey( object ) )
180 {
181 iterator = ( (Integer) map.remove( object ) ).intValue();
182
183 if ( filled )
184 {
185 for ( ; iterator < lru.length - 1; ++iterator )
186 {
187 lru[ iterator ] = lru[ iterator + 1 ];
188 }
189
190 index = lru.length - 1;
191 }
192 else
193 {
194 for ( ; iterator < index - 1; ++iterator )
195 {
196 lru[ iterator ] = lru[ iterator + 1 ];
197 }
198
199 --index;
200 }
201 }
202
203 return result;
204 }
205
206 /**
207 * Removes all the objects from the {@link #lru} and the {@link #map}.
208 * The most efficient way to do it is to create a new instances of
209 * the lru array and the map, and consign the old instances to the
210 * garbage collector.
211 *
212 * <p><b>Note:</b> This method does not perform any <code>
213 * synchronisation</code>, and hence is not <code>thread-safe</code>.
214 * Client's must perform their own synchronisation if they so desire.
215 * </p>
216 */
217 @SuppressWarnings(value={"unchecked"})
218 public void clear()
219 {
220 int size = lru.length;
221 index = 0;
222 lru = (T[]) new Object[ size ];
223 map = new HashMap<T, Integer>( size );
224 }
225
226 /**
227 * Returns the size of the {@link #lru}. Returns the total size
228 * of the lru, if the lru has been {@link #filled}, else returns
229 * the {@link #index} value.
230 *
231 * @return The size of the lru.
232 */
233 public int size()
234 {
235 int size = 0;
236 if ( filled )
237 {
238 size = lru.length;
239 }
240 else
241 {
242 size = index;
243 }
244
245 return size;
246 }
247 }