1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 package org.onemind.commons.java.datastructure;
22
23 import java.util.*;
24 /***
25 * Most recently used list implementation. It support entries expiration
26 * by access time.
27 * @author TiongHiang Lee (thlee@onemindsoft.org)
28 * @version $Id: MruList.java,v 1.4 2005/04/26 17:41:59 thlee Exp $ $Name: $
29 */
30 public class MruList implements Set
31 {
32
33 /***
34 * Represent an entry in the MruList
35 * @author TiongHiang Lee
36 */
37 protected static class MruEntry implements Comparable
38 {
39
40 /*** the last access time * */
41 private long _lastAccessTime;
42
43 /*** the object * */
44 private Object _obj;
45
46 /***
47 * Constructor
48 * @param obj the object
49 * @param time the time
50 */
51 public MruEntry(Object obj, long time)
52 {
53 _obj = obj;
54 _lastAccessTime = time;
55 }
56
57 /***
58 * Compare by the access time
59 * @param e another entry
60 * @return a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the
61 * specified object.
62 */
63 public int compareTo(MruEntry e)
64 {
65 if (_lastAccessTime > e._lastAccessTime)
66 {
67 return -1;
68 } else if (_lastAccessTime < e._lastAccessTime)
69 {
70 return 1;
71 } else
72 {
73 if (_obj.equals(e._obj))
74 {
75 return 0;
76 } else if (_obj.hashCode() > e._obj.hashCode())
77 {
78 return 1;
79 } else
80 {
81 return -1;
82 }
83 }
84 }
85
86 /***
87 * {@inheritDoc}
88 */
89 public int compareTo(Object o)
90 {
91 return compareTo((MruEntry) o);
92 }
93
94 /***
95 * Return the lastAccessTime
96 * @return the lastAccessTime.
97 */
98 public final long getLastAccessTime()
99 {
100 return _lastAccessTime;
101 }
102
103 /***
104 * Set the lastAccessTime
105 * @param lastAccessTime The lastAccessTime to set.
106 */
107 public final void setLastAccessTime(long lastAccessTime)
108 {
109 _lastAccessTime = lastAccessTime;
110 }
111
112 /***
113 * Return the obj
114 * @return the obj.
115 */
116 public final Object getObj()
117 {
118 return _obj;
119 }
120
121 /***
122 * Set the obj
123 * @param obj The obj to set.
124 */
125 public final void setObj(Object obj)
126 {
127 _obj = obj;
128 }
129
130 /***
131 * {@inheritDoc}
132 */
133 public String toString()
134 {
135 return (_obj + ": " + _lastAccessTime);
136 }
137 }
138
139 /***
140 * An iterator to the entries
141 * @author TiongHiang Lee
142 */
143 protected static class MruIterator implements Iterator
144 {
145
146 /*** the iterator * */
147 private Iterator _entryIterator;
148
149 /***
150 * Constructor
151 * @param entryIterator the iterator
152 */
153 public MruIterator(Iterator entryIterator)
154 {
155 _entryIterator = entryIterator;
156 }
157
158 /***
159 * {@inheritDoc}
160 */
161 public boolean hasNext()
162 {
163 return _entryIterator.hasNext();
164 }
165
166 /***
167 * {@inheritDoc}
168 */
169 public Object next()
170 {
171 MruEntry entry = (MruEntry) _entryIterator.next();
172 return entry._obj;
173 }
174
175 /***
176 * {@inheritDoc}
177 */
178 public void remove()
179 {
180 _entryIterator.remove();
181 }
182 }
183
184 /*** the entries map * */
185 private HashMap _entryMap = new HashMap();
186
187 /*** the last cleanup time * */
188 private long _lastCleanupTime;
189
190 /*** the sorted mru list * */
191 private TreeSet _mruList = new TreeSet();
192
193 /*** the size * */
194 private long _sizeLimit;
195
196 /*** the timeout * */
197 private long _timeout;
198
199 /***
200 * {@inheritDoc}
201 */
202 public MruList()
203 {
204 this(0, 0);
205 }
206
207 /***
208 * {@inheritDoc}
209 * @param sizeLimit the size limit of the MruList (0 for no size limit)
210 * @param timeout the timeout (0 for never timeout)
211 */
212 public MruList(long sizeLimit, long timeout)
213 {
214 _sizeLimit = sizeLimit;
215 _timeout = timeout;
216 _lastCleanupTime = System.currentTimeMillis();
217 }
218
219 /***
220 * Record that object o is being accessed. This will put a timestamp to the object
221 * @param o the object
222 * @return true if the object was in the list before
223 */
224 public boolean access(Object o)
225 {
226 long now = System.currentTimeMillis();
227 if ((_timeout > 0) && ((now - _lastCleanupTime) > _timeout))
228 {
229 expireEntries(_timeout);
230 }
231 boolean flag = false;
232 MruEntry entry = (MruEntry) _entryMap.get(o);
233 if (entry != null)
234 {
235 _mruList.remove(entry);
236 entry._lastAccessTime = now;
237 flag = true;
238 } else
239 {
240 entry = new MruEntry(o, now);
241 _entryMap.put(o, entry);
242 }
243 _mruList.add(entry);
244 if ((_sizeLimit > 0) && (size() > _sizeLimit))
245 {
246 truncateEntries(_sizeLimit);
247 }
248 return flag;
249 }
250
251 /***
252 * @see access(Object o)
253 */
254 public boolean add(Object o)
255 {
256 return access(o);
257 }
258
259 /***
260 * {@inheritDoc}
261 */
262 public boolean addAll(Collection c)
263 {
264 Iterator it = c.iterator();
265 while (it.hasNext())
266 {
267 add(it.next());
268 }
269 return true;
270 }
271
272 /***
273 * {@inheritDoc}
274 */
275 public void clear()
276 {
277 _entryMap.clear();
278 _mruList.clear();
279 }
280
281 /***
282 * {@inheritDoc}
283 */
284 public boolean contains(Object o)
285 {
286 return _entryMap.containsKey(o);
287 }
288
289 /***
290 * {@inheritDoc}
291 */
292 public boolean containsAll(Collection c)
293 {
294 return _entryMap.keySet().containsAll(c);
295 }
296
297 /***
298 * Expire the entries that was last access longer that time t Document this method.
299 * @param t the elapse time
300 */
301 public void expireEntries(long t)
302 {
303 long now = System.currentTimeMillis();
304 _lastCleanupTime = now;
305 do
306 {
307 MruEntry entry = (MruEntry) _mruList.last();
308 if (entry == null)
309 {
310 break;
311 } else if ((now - entry._lastAccessTime) > t)
312 {
313 expireEntry(entry._obj);
314 } else
315 {
316 break;
317 }
318 } while (true);
319 }
320
321 /***
322 * Get the last access time object obj
323 * @param obj the object
324 * @return the access time, or -1 if the object is not in the cache
325 */
326 public long getLastAccessTime(Object obj)
327 {
328 MruEntry entry = (MruEntry) _entryMap.get(obj);
329 if (entry != null)
330 {
331 return entry._lastAccessTime;
332 } else
333 {
334 return -1;
335 }
336 }
337
338 /***
339 * {@inheritDoc}
340 */
341 public boolean isEmpty()
342 {
343 return _entryMap.size() == 0;
344 }
345
346 /***
347 * {@inheritDoc}
348 */
349 public Iterator iterator()
350 {
351 return new MruIterator(_mruList.iterator());
352 }
353
354 /***
355 * {@inheritDoc}
356 */
357 public boolean remove(Object o)
358 {
359 MruEntry entry = (MruEntry) _entryMap.remove(o);
360 boolean flag = false;
361 if (entry != null)
362 {
363 _mruList.remove(entry);
364 flag = true;
365 }
366 return flag;
367 }
368
369 /***
370 * {@inheritDoc}
371 */
372 public boolean removeAll(Collection c)
373 {
374 boolean flag = false;
375 Iterator it = c.iterator();
376 while (it.hasNext())
377 {
378 if (remove(it.next()))
379 {
380 flag = true;
381 }
382 }
383 return flag;
384 }
385
386 /***
387 * {@inheritDoc}
388 */
389 public boolean retainAll(Collection c)
390 {
391 Iterator it = _entryMap.keySet().iterator();
392 boolean flag = false;
393 while (it.hasNext())
394 {
395 Object obj = it.next();
396 if (!c.contains(obj))
397 {
398 remove(obj);
399 flag = true;
400 }
401 }
402 return flag;
403 }
404
405 /***
406 * {@inheritDoc}
407 */
408 public int size()
409 {
410 return _entryMap.size();
411 }
412
413 /***
414 * {@inheritDoc}
415 */
416 public Object[] toArray()
417 {
418 throw new UnsupportedOperationException("Not implemented");
419 }
420
421 /***
422 * {@inheritDoc}
423 */
424 public Object[] toArray(Object[] a)
425 {
426 throw new UnsupportedOperationException("Not implemented");
427 }
428
429 /***
430 * Truncate the entries to specific size
431 * @param size the size
432 */
433 public void truncateEntries(long size)
434 {
435 while (size() > size)
436 {
437 MruEntry entry = (MruEntry) _mruList.last();
438 truncateEntry(entry._obj);
439 }
440 }
441
442 /***
443 * Remove the object from the MruList
444 * @param obj the object
445 */
446 protected void truncateEntry(Object obj)
447 {
448 remove(obj);
449 }
450
451 /***
452 * Remove the entry from the MruList
453 * @param obj expire the entry
454 */
455 protected void expireEntry(Object obj)
456 {
457 remove(obj);
458 }
459 }