/*
* Copyright (C) 2004 TiongHiang Lee
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
* Email: thlee@onemindsoft.org
*/
package org.onemind.commons.java.datastructure;
import java.util.*;
/**
* Most recently used list implementation. It support entries expiration
* by access time.
* @author TiongHiang Lee (thlee@onemindsoft.org)
* @version $Id: MruList.java,v 1.4 2005/04/26 17:41:59 thlee Exp $ $Name: $
*/
public class MruList implements Set
{
/**
* Represent an entry in the MruList
* @author TiongHiang Lee
*/
protected static class MruEntry implements Comparable
{
/** the last access time * */
private long _lastAccessTime;
/** the object * */
private Object _obj;
/**
* Constructor
* @param obj the object
* @param time the time
*/
public MruEntry(Object obj, long time)
{
_obj = obj;
_lastAccessTime = time;
}
/**
* Compare by the access time
* @param e another entry
* @return a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the
* specified object.
*/
public int compareTo(MruEntry e)
{
if (_lastAccessTime > e._lastAccessTime)
{
return -1;
} else if (_lastAccessTime < e._lastAccessTime)
{
return 1;
} else
{
if (_obj.equals(e._obj))
{
return 0;
} else if (_obj.hashCode() > e._obj.hashCode())
{
return 1;
} else
{
return -1;
}
}
}
/**
* {@inheritDoc}
*/
public int compareTo(Object o)
{
return compareTo((MruEntry) o);
}
/**
* Return the lastAccessTime
* @return the lastAccessTime.
*/
public final long getLastAccessTime()
{
return _lastAccessTime;
}
/**
* Set the lastAccessTime
* @param lastAccessTime The lastAccessTime to set.
*/
public final void setLastAccessTime(long lastAccessTime)
{
_lastAccessTime = lastAccessTime;
}
/**
* Return the obj
* @return the obj.
*/
public final Object getObj()
{
return _obj;
}
/**
* Set the obj
* @param obj The obj to set.
*/
public final void setObj(Object obj)
{
_obj = obj;
}
/**
* {@inheritDoc}
*/
public String toString()
{
return (_obj + ": " + _lastAccessTime);
}
}
/**
* An iterator to the entries
* @author TiongHiang Lee
*/
protected static class MruIterator implements Iterator
{
/** the iterator * */
private Iterator _entryIterator;
/**
* Constructor
* @param entryIterator the iterator
*/
public MruIterator(Iterator entryIterator)
{
_entryIterator = entryIterator;
}
/**
* {@inheritDoc}
*/
public boolean hasNext()
{
return _entryIterator.hasNext();
}
/**
* {@inheritDoc}
*/
public Object next()
{
MruEntry entry = (MruEntry) _entryIterator.next();
return entry._obj;
}
/**
* {@inheritDoc}
*/
public void remove()
{
_entryIterator.remove();
}
}
/** the entries map * */
private HashMap _entryMap = new HashMap();
/** the last cleanup time * */
private long _lastCleanupTime;
/** the sorted mru list * */
private TreeSet _mruList = new TreeSet();
/** the size * */
private long _sizeLimit;
/** the timeout * */
private long _timeout;
/**
* {@inheritDoc}
*/
public MruList()
{
this(0, 0);
}
/**
* {@inheritDoc}
* @param sizeLimit the size limit of the MruList (0 for no size limit)
* @param timeout the timeout (0 for never timeout)
*/
public MruList(long sizeLimit, long timeout)
{
_sizeLimit = sizeLimit;
_timeout = timeout;
_lastCleanupTime = System.currentTimeMillis();
}
/**
* Record that object o is being accessed. This will put a timestamp to the object
* @param o the object
* @return true if the object was in the list before
*/
public boolean access(Object o)
{
long now = System.currentTimeMillis();
if ((_timeout > 0) && ((now - _lastCleanupTime) > _timeout))
{
expireEntries(_timeout);
}
boolean flag = false;
MruEntry entry = (MruEntry) _entryMap.get(o);
if (entry != null)
{ //exist already
_mruList.remove(entry);//must remove to add again later
entry._lastAccessTime = now;
flag = true;
} else
{
entry = new MruEntry(o, now);
_entryMap.put(o, entry);
}
_mruList.add(entry);
if ((_sizeLimit > 0) && (size() > _sizeLimit))
{
truncateEntries(_sizeLimit);
}
return flag;
}
/**
* @see access(Object o)
*/
public boolean add(Object o)
{
return access(o);
}
/**
* {@inheritDoc}
*/
public boolean addAll(Collection c)
{
Iterator it = c.iterator();
while (it.hasNext())
{
add(it.next());
}
return true;
}
/**
* {@inheritDoc}
*/
public void clear()
{
_entryMap.clear();
_mruList.clear();
}
/**
* {@inheritDoc}
*/
public boolean contains(Object o)
{
return _entryMap.containsKey(o);
}
/**
* {@inheritDoc}
*/
public boolean containsAll(Collection c)
{
return _entryMap.keySet().containsAll(c);
}
/**
* Expire the entries that was last access longer that time t Document this method.
* @param t the elapse time
*/
public void expireEntries(long t)
{
long now = System.currentTimeMillis();
_lastCleanupTime = now;
do
{
MruEntry entry = (MruEntry) _mruList.last();
if (entry == null)
{
break;
} else if ((now - entry._lastAccessTime) > t)
{
expireEntry(entry._obj);
} else
{
break;
}
} while (true);
}
/**
* Get the last access time object obj
* @param obj the object
* @return the access time, or -1 if the object is not in the cache
*/
public long getLastAccessTime(Object obj)
{
MruEntry entry = (MruEntry) _entryMap.get(obj);
if (entry != null)
{
return entry._lastAccessTime;
} else
{
return -1;
}
}
/**
* {@inheritDoc}
*/
public boolean isEmpty()
{
return _entryMap.size() == 0;
}
/**
* {@inheritDoc}
*/
public Iterator iterator()
{
return new MruIterator(_mruList.iterator());
}
/**
* {@inheritDoc}
*/
public boolean remove(Object o)
{
MruEntry entry = (MruEntry) _entryMap.remove(o);
boolean flag = false;
if (entry != null)
{
_mruList.remove(entry);
flag = true;
}
return flag;
}
/**
* {@inheritDoc}
*/
public boolean removeAll(Collection c)
{
boolean flag = false;
Iterator it = c.iterator();
while (it.hasNext())
{
if (remove(it.next()))
{
flag = true;
}
}
return flag;
}
/**
* {@inheritDoc}
*/
public boolean retainAll(Collection c)
{
Iterator it = _entryMap.keySet().iterator();
boolean flag = false;
while (it.hasNext())
{
Object obj = it.next();
if (!c.contains(obj))
{
remove(obj);
flag = true;
}
}
return flag;
}
/**
* {@inheritDoc}
*/
public int size()
{
return _entryMap.size();
}
/**
* {@inheritDoc}
*/
public Object[] toArray()
{
throw new UnsupportedOperationException("Not implemented");
}
/**
* {@inheritDoc}
*/
public Object[] toArray(Object[] a)
{
throw new UnsupportedOperationException("Not implemented");
}
/**
* Truncate the entries to specific size
* @param size the size
*/
public void truncateEntries(long size)
{
while (size() > size)
{
MruEntry entry = (MruEntry) _mruList.last();
truncateEntry(entry._obj);
}
}
/**
* Remove the object from the MruList
* @param obj the object
*/
protected void truncateEntry(Object obj)
{
remove(obj);
}
/**
* Remove the entry from the MruList
* @param obj expire the entry
*/
protected void expireEntry(Object obj)
{
remove(obj);
}
}