1 /***
2 * LUFOCache.java
3 *
4 * This file is part of the creme library.
5 * The creme library intends to ease the development effort of large
6 * applications by providing easy to use support classes.
7 *
8 * Copyright (C) 2002 Denis Bregeon
9 *
10 * This library is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU Lesser General Public
12 * License as published by the Free Software Foundation; either
13 * version 2.1 of the License, or (at your option) any later version.
14 *
15 * This library is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * Lesser General Public License for more details.
19 *
20 * You should have received a copy of the GNU Lesser General Public
21 * License along with this library; if not, write to the Free Software
22 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 *
24 * contact information: dbregeon@sourceforge.net
25 */
26 package org.jcreme.caches;
27
28 import java.util.HashMap;
29 import java.util.Iterator;
30 import java.util.Map;
31 import java.util.TreeMap;
32
33 /***
34 * A Cache object using a Least Used First Out policy. The LUFO cache is based
35 * on a Least Used First Out algorithm to select the objects that are removed
36 * from the cache to make room. This implementation uses a TreeMap. It also uses
37 * an encapsulation of the keys that counts the calls to the cache to retrieve
38 * an object.
39 *
40 * @author $Author: dbregeon $
41 * @version $Revision: 1.4 $
42 */
43 public class LUFOCache extends BaseCache {
44 /***
45 * Stores the values sorted according to the local key that is associated.
46 */
47 private final TreeMap values = new TreeMap();
48
49 /***
50 * This enables to recover the local key from the external key that was
51 * provided as a reference for a value.
52 */
53 private final HashMap keyToLocalKey = new HashMap();
54
55 /***
56 * This class enable to store the original key and the number of occurences
57 * when the associated value was recovered from the cache.
58 */
59 protected class LocalKey implements Comparable {
60 /***
61 * The original key from which this LocalKey was created.
62 */
63 private final Object key;
64
65 /***
66 * The number of access to the associated value.
67 */
68 private long numberOfUses = 0;
69
70 /***
71 * Builds a new local key.
72 *
73 * @param key
74 * the actual key in the Cache.
75 */
76 public LocalKey(Object key) {
77 this.key = key;
78 }
79
80 /***
81 * This method enables to increment the number of retrievals.
82 *
83 * @return the result of the incrementation.
84 */
85 public long incr() {
86 return ++this.numberOfUses;
87 }
88
89 /***
90 * Access to the current number of calls to retrieve the object
91 * associated to this key.
92 *
93 * @return the number of accesses to the associated value.
94 */
95 public long getNumberOfUses() {
96 return this.numberOfUses;
97 }
98
99 /***
100 * Gives access to the original key.
101 *
102 * @return the original key that was used to create this LocalKey.
103 */
104 public Object getKey() {
105 return this.key;
106 }
107
108 /***
109 * This method enables to compare the LocalKey objects to order them.
110 *
111 * @param o
112 * the LocalKey to compare.
113 * @return the comparison result. If the parameter is not a LocalKey and
114 * o is the underlying key the result is 0.
115 */
116 public int compareTo(final Object o) {
117 int result = -1;
118 if (o instanceof LocalKey) {
119 final long numberOfUses2 = ((LocalKey) o).getNumberOfUses();
120 final Object key2 = ((LocalKey) o).getKey();
121 result = ((this.numberOfUses == numberOfUses2) ? (this.key
122 .equals(key2) ? 0 : ((this.key.hashCode() > key2
123 .hashCode()) ? 1 : -1))
124 : ((this.numberOfUses > numberOfUses2) ? 1 : -1));
125 } else if (this.key.equals(o)) {
126 result = 0;
127 }
128 return result;
129 }
130
131 /***
132 * This method ensures that we can access in a Hashtable using either
133 * the original key or the LocalKey associated.
134 *
135 * @return the hashcode of the underlying key.
136 */
137 public int hashCode() {
138 return this.key.hashCode();
139 }
140
141 /***
142 * This method compares an object to this key.
143 *
144 * @param o
145 * the object to test for equality.
146 * @return true if o is a LocalKey with the same underlying key or o is
147 * equal to the underlying key. false otherwise.
148 */
149 public boolean equals(final Object o) {
150 boolean result = false;
151 if (o instanceof LocalKey) {
152 result = ((LocalKey) o).getKey().equals(this.key);
153 } else {
154 result = this.key.equals(o);
155 }
156 return result;
157 }
158 }
159
160 /***
161 * Creates new LUFOCache
162 */
163 public LUFOCache() {
164
165 super(CachePolicy.LUFO);
166 }
167
168 /***
169 * Creates new LUFOCache
170 *
171 * @param minSize
172 * the initial size of the Cache.
173 * @param maxSize
174 * the maximum number of objects contained by the cache.
175 */
176 public LUFOCache(int minSize, int maxSize) {
177
178 super(minSize, maxSize, CachePolicy.LUFO);
179 }
180
181 /***
182 * This method adds an object in the cache.
183 *
184 * @param key
185 * the key that will be used to retrieve the object.
186 * @param value
187 * the object to store in the cache.
188 */
189 public synchronized void registerObject(final Object key, final Object value) {
190 if ((key != null) && (value != null)) {
191 if (this.values.size() >= getMaxSize()) {
192 removeOneElement();
193 }
194 LocalKey localKey = (LocalKey) this.keyToLocalKey.get(key);
195 if (localKey == null) {
196 localKey = new LocalKey(key);
197 this.keyToLocalKey.put(key, localKey);
198 }
199 this.values.put(localKey, value);
200 fireElementAdded(buildEvent(value));
201 }
202 }
203
204 /***
205 * This method removes an object from the cache.
206 *
207 * @param key
208 * the key that was used to store the object in the cache.
209 */
210 public synchronized void unregisterObject(final Object key) {
211 final LocalKey localKey = (LocalKey) this.keyToLocalKey.get(key);
212 if (localKey != null) {
213 final Object value = this.values.remove(localKey);
214 if (value != null) {
215 this.keyToLocalKey.remove(key);
216 fireElementRemoved(buildEvent(value));
217 }
218 }
219 }
220
221 /***
222 * Gives access to an object registered in the cache.
223 *
224 * @param key
225 * the key used to register the searched object.
226 * @return the object stored in the cache. Null if no object was stored with
227 * this key.
228 */
229 public synchronized Object getObject(final Object key) {
230 Object result = null;
231 if (key != null) {
232 final LocalKey localKey = (LocalKey) this.keyToLocalKey.get(key);
233 if (localKey != null) {
234 result = this.values.remove(localKey);
235 localKey.incr();
236 this.values.put(localKey, result);
237 }
238 }
239 return result;
240 }
241
242 /***
243 * Removes all the objects from the Cache, leaving it empty.
244 */
245 public synchronized void clear() {
246 this.values.clear();
247 this.keyToLocalKey.clear();
248 fireElementRemoved(buildEvent(null));
249 }
250
251 /***
252 * This method is called when room is needed to add a new object in the
253 * cache.
254 */
255 protected synchronized void removeOneElement() {
256 final Object key = this.values.firstKey();
257 unregisterObject(key);
258 }
259
260 /***
261 * This method gives access to the full content of the cache.
262 *
263 * @return an array containing all the objects stored in the cache.
264 */
265 public synchronized Object[] getAllObjects() {
266 return this.values.values().toArray();
267 }
268
269 /***
270 * This method gives the same result as the getAllObjects method but the
271 * objects in the result array are types with the parameter type.
272 *
273 * @param type
274 * the type to give to the object in the result array.
275 * @return an array of objects of the type.
276 */
277 public synchronized Object[] getAllObjects(final Class type) {
278 return this.values.values().toArray(
279 (Object[]) java.lang.reflect.Array.newInstance(type,
280 this.values.size()));
281 }
282
283 /***
284 * This method enables to access to the cache contents.
285 *
286 * @return a map of the (key,value) contents of the cache.
287 */
288 public synchronized Map getMap() {
289 return (Map) this.values.clone();
290 }
291
292 /***
293 * This is a convenience method. It enables to add to the cache all the
294 * objects present in the map.
295 *
296 * @param m
297 * the map that contains the objects (and keys) to use.
298 */
299 public synchronized void registerAllObjects(final Map m) {
300 if (m != null) {
301 final Iterator iter = m.keySet().iterator();
302 Object currentKey = null;
303 while (iter.hasNext()) {
304 currentKey = iter.next();
305 registerObject(currentKey, m.get(currentKey));
306 }
307 }
308 }
309
310 /***
311 * This methods gives the current size of the cache.
312 *
313 * @return the number of objects currently stored in the cache.
314 */
315 public synchronized int getSize() {
316 return this.values.size();
317 }
318 }