morgand 02/02/20 10:01:34
Modified: collections/src/java/org/apache/commons/collections
LRUMap.java
collections/src/test/org/apache/commons/collections
TestLRUMap.java
Log:
LRUMap reimplemented, based on SequencedHashMap
Revision Changes Path
1.9 +1 -400
jakarta-commons/collections/src/java/org/apache/commons/collections/LRUMap.java
Index: LRUMap.java
===================================================================
RCS file:
/home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/LRUMap.java,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -r1.8 -r1.9
--- LRUMap.java 14 Feb 2002 21:24:32 -0000 1.8
+++ LRUMap.java 20 Feb 2002 18:01:34 -0000 1.9
@@ -1,400 +1 @@
-/*
- * $Header:
/home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/LRUMap.java,v
1.8 2002/02/14 21:24:32 morgand Exp $
- * $Revision: 1.8 $
- * $Date: 2002/02/14 21:24:32 $
- *
- * ====================================================================
- *
- * The Apache Software License, Version 1.1
- *
- * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in
- * the documentation and/or other materials provided with the
- * distribution.
- *
- * 3. The end-user documentation included with the redistribution, if
- * any, must include the following acknowlegement:
- * "This product includes software developed by the
- * Apache Software Foundation (http://www.apache.org/)."
- * Alternately, this acknowlegement may appear in the software itself,
- * if and wherever such third-party acknowlegements normally appear.
- *
- * 4. The names "The Jakarta Project", "Commons", and "Apache Software
- * Foundation" must not be used to endorse or promote products derived
- * from this software without prior written permission. For written
- * permission, please contact [EMAIL PROTECTED]
- *
- * 5. Products derived from this software may not be called "Apache"
- * nor may "Apache" appear in their names without prior written
- * permission of the Apache Group.
- *
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
- * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
- * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
- * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
- * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- * ====================================================================
- *
- * This software consists of voluntary contributions made by many
- * individuals on behalf of the Apache Software Foundation. For more
- * information on the Apache Software Foundation, please see
- * <http://www.apache.org/>.
- *
- */
-package org.apache.commons.collections;
-
-import java.io.Externalizable;
-import java.io.IOException;
-import java.io.ObjectInput;
-import java.io.ObjectOutput;
-import java.io.Serializable;
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.Map;
-import java.util.Set;
-
-/** <p>
- * An implementation of a Map which has a maximum size and uses a Least Recently
Used
- * algorithm to remove items from the Map when the maximum size is reached and new
items are added.
- * </p>
- *
- * <p>
- * This implementation uses a simple bubbling
- * algorithm, whereby every random access get() method call bubbles the item
- * up the list, further away from the 'drop zone'.
- * </p>
- *
- * <p>
- * A synchronized version can be obtained with:
- * <code>Collections.synchronizedMap( theMapToSynchronize )</code>
- * If it will be accessed by multiple threads, you _must_ synchronize access
- * to this Map. Even concurrent get(Object) operations produce indeterminate
- * behaviour.
- * </p>
- *
- * <p>
- * <b>Warning</b>: This class is not a true "Least Recently Used" map. When
- * mappings are accessed, the mapping is moved one position away from the end
- * of the list, rather than all the way to the front of the list. This means
- * that the "most" recently used, is not at the front of the list, and the
- * "least" recently used is not necessarily at the end of the list. Here's a
- * simple example (Provided by Aaron Smuts on commons-dev@):
- *
- * <pre>
- * Say that items 0 - 9 are put in. The limit is 10.
- *
- * The list looks like:
- *
- * Index order (0-9)
- * 9,8,7,6,5,4,3,2,1,0
- *
- * Item 1 is accessed and the list now looks like:
- * Index order (0-9)
- * 9,8,7,6,5,4,3,1,2,0
- *
- * Item 0 is accessed and the list now looks like:
- * Index order (0-9)
- * 9,8,7,6,5,4,3,1,0,2
- *
- * Item 2 is accessed and the list now looks like:
- * Index order (0-9)
- * 9,8,7,6,5,4,3,1,2,0
- *
- * Item 10 is added and the list now looks like
- * Index order (0-9)
- * 10,9,8,7,6,5,4,3,1,2
- *
- * Item 0 was droped but it was not the least recently used element.
- * </pre>
- * </p>
- * <p>
- * Additionally, the results from entrySet() and values() are not properly
- * backed by the map in violation of the Map API contract. These methods
- * are also not implemented efficiently.</li>
- * </ul>
- * </p>
- *
- * <p>These issues hopefully will be corrected at a later date.</p>
- *
- * @author <a href="mailto:[EMAIL PROTECTED]";>James Strachan</a>
- * @author <a href="mailto:[EMAIL PROTECTED]";>Morgan Delagrange</a>
- */
-public class LRUMap extends HashMap implements Externalizable {
-
- /** Holds value of property maximumSize. */
- private int maximumSize;
- /** Used to hold the bubble list - bubbles keys up the list as they are
accessed */
- private ArrayList bubbleList;
-
- //static final long serialVersionUID = 0x9e1e06764b24cb05L;
-
- public LRUMap() {
- this( 100 );
- }
-
- public LRUMap(int i) {
- super( i );
- maximumSize = i;
- bubbleList = new ArrayList( i );
- }
-
/**
* <p>
* Removes the least recently used object from the
Map.
* </p>
*
* <p>
* This method will determine the object
to
* remove and call remove(Object). If you want a subclass
* to perform
some operation before removing an Object,
* you can override remove(Object) for
all remove
* operations, or removeLRU() if you only want to affect
*
automatic removes.
* </p>
*
* @return the key of the removed item
*/
- public Object removeLRU() {
- int lastItem = size() - 1;
- Object key = bubbleList.get( lastItem );
remove( key );
- return key;
- }
-
- // Map interface
- //-------------------------------------------------------------------------
- public Object get( Object key ) {
- ValuePositionPair pair = getPair( key );
- if ( pair == null ) {
- return null;
- }
- int position = pair.position;
- if ( position > 0 ) {
- // lets bubble up this entry up the list
- // avoiding expesive list removal / insertion
- int position2 = position - 1;
- Object key2 = bubbleList.get( position2 );
- ValuePositionPair pair2 = getPair( key2 );
- if ( pair2 != null ) {
- pair2.position = position;
- pair.position = position2;
- bubbleList.set( position, key2 );
- bubbleList.set( position2, key );
- }
- }
- return pair.value;
- }
-
/**
* <p>Removes the key and its Object from the Map.</p>
*
* <p>(Note: this may result in the "Least Recently Used"
* object being
removed from the Map. In that case,
* the removeLRU() method is called. See
javadoc for
* removeLRU() for more details.)</p>
*
* @param key
Key of the Object to add.
* @param value Object to add
* @return Former
value of the key
* @see removeLRU()
*/
- public Object put( Object key, Object value ) {
ValuePositionPair
pair = new ValuePositionPair( value );
int mapSize = size();
//
check to see if the object already exists in
// our LRUMap, if it does then
the position in the
// bubble sort is OK
- int keyIndex = bubbleList.indexOf(key);
if (keyIndex != -1) {
pair.position = keyIndex;
} else if ( mapSize >= maximumSize ) {
- // lets retire the least recently used item in the cache
- int lastIndex = maximumSize - 1;
- pair.position = lastIndex;
removeLRU();
bubbleList.add(lastIndex, key);
- } else {
- pair.position = mapSize;
- bubbleList.add( mapSize, key );
- }
- pair = (ValuePositionPair) putPair( key, pair );
- return ( pair != null ) ? pair.value : null;
- }
-
- public Object remove( Object key ) {
- ValuePositionPair pair = removePair( key );
- if ( pair != null ) {
- bubbleList.remove( pair.position );
- return pair.value;
- }
- return null;
- }
-
- public boolean containsKey( Object key ) {
- return super.containsKey( key );
- }
-
- public boolean containsValue( Object value ) {
- for ( Iterator iter = pairIterator(); iter.hasNext(); ) {
- ValuePositionPair pair = (ValuePositionPair) iter.next();
- Object otherValue = pair.value;
- if ( value == otherValue ) {
- return true;
- }
- if ( value != null && value.equals( otherValue ) ) {
- return true;
- }
- }
- return false;
- }
-
- public Set keySet() {
- return super.keySet();
- }
-
- public Set entrySet() {
- HashSet answer = new HashSet();
- for ( Iterator iter = super.entrySet().iterator(); iter.hasNext(); ) {
- Map.Entry otherEntry = (Map.Entry) iter.next();
- Object key = otherEntry.getKey();
- ValuePositionPair pair = (ValuePositionPair) otherEntry.getValue();
- Object value = pair.value;
- Entry newEntry = new Entry( key, value );
- answer.add( newEntry );
- }
- return answer;
- }
-
- public Collection values() {
- ArrayList answer = new ArrayList();
- for ( Iterator iter = super.entrySet().iterator(); iter.hasNext(); ) {
- Map.Entry otherEntry = (Map.Entry) iter.next();
- Entry newEntry = new Entry( otherEntry.getKey(), otherEntry.getValue()
);
- answer.add( newEntry );
- }
- return answer;
- }
-
-
-
- // Externalizable interface
- //-------------------------------------------------------------------------
- public void readExternal( ObjectInput in ) throws IOException,
ClassNotFoundException {
- maximumSize = in.readInt();
- int size = in.readInt();
-
- // create a populated list
- bubbleList = new ArrayList( maximumSize );
- for( int i = 0; i < size; i++ ) {
- bubbleList.add( "" );
- }
-
- for( int i = 0; i < size; i++ ) {
- Object key = in.readObject();
- Object value = in.readObject();
- ValuePositionPair pair = (ValuePositionPair) value;
- int position = pair.position;
- bubbleList.set( position, pair );
- putPair( key, pair );
- }
- }
-
- public void writeExternal( ObjectOutput out ) throws IOException {
- out.writeInt( maximumSize );
- out.writeInt( size() );
- for( Iterator iterator = keySet().iterator(); iterator.hasNext(); ) {
- Object key = iterator.next();
- out.writeObject( key );
- Object value = getPair( key );
- out.writeObject( value );
- }
- }
-
-
- // Properties
- //-------------------------------------------------------------------------
- /** Getter for property maximumSize.
- * @return Value of property maximumSize.
- */
- public int getMaximumSize() {
- return maximumSize;
- }
- /** Setter for property maximumSize.
- * @param maximumSize New value of property maximumSize.
- */
- public void setMaximumSize(int maximumSize) {
- this.maximumSize = maximumSize;
- }
-
-
- // Implementation methods
- //-------------------------------------------------------------------------
- protected ValuePositionPair getPair( Object key ) {
- return (ValuePositionPair) super.get( key );
- }
-
- protected ValuePositionPair putPair( Object key, ValuePositionPair pair ) {
- return (ValuePositionPair) super.put( key, pair );
- }
-
- protected ValuePositionPair removePair( Object key ) {
- return (ValuePositionPair) super.remove( key );
- }
-
- protected Iterator pairIterator() {
- return super.values().iterator();
- }
-
- // Implementation classes
- //-------------------------------------------------------------------------
- protected static class ValuePositionPair implements Serializable {
-
- public Object value;
- public int position;
-
- public ValuePositionPair() {
- }
-
- public ValuePositionPair( Object value ) {
- this.value = value;
- }
-
- public String toString() {
- return "[ " + position + ": " + value + " ]";
- }
- }
-
- /**
- * A map entry, which is backed by this RefHashMap
- */
- class Entry implements Map.Entry {
-
- /**
- * Constructor
- */
- public Entry( Object key, Object value ) {
- this.key = key;
- this.value = value;
- }
-
- // Map.Entry interface
- // -----------------------------------------------------------
-
- /**
- * Retrieves the key of this mapping
- */
- public Object getKey() {
- return key;
- }
-
- /**
- * Retrieves the value of this mapping
- */
- public Object getValue() {
- return value;
- }
-
- /**
- * Sets the value of this mapping
- */
- public Object setValue( Object value ) {
- this.value = value;
- put( key, value );
- return value;
- }
-
- /**
- * Return the hash code of this mapping.
- * This algorithm was taken from the JavaDoc for Map.Entry
- */
- public int hashCode() {
- return ( getKey() == null ? 0 : getKey().hashCode() ) ^
- ( getValue() == null ? 0 : getValue().hashCode() );
- }
-
- /** The domain of this mapping */
- private Object key;
- /** The range of this mapping */
- private Object value;
- }
-}
+/*
* $Header:
/home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/LRUMap.java,v
1.9 2002/02/20 18:01:34 morgand Exp $
* $Revision: 1.9 $
* $Date: 2002/02/20
18:01:34 $
*
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 1999-2002 The Apache
Software Foundation. All rights
* reserved.
*
* Redistribution and use in source
and binary forms, with or without
* modification, are permitted provided that the
following conditions
* are met:
*
* 1. Redistributions of source code must retain
the above copyright
* notice, this list of conditions and the following
disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the
documentation and/or other materials provided with the
* distribution.
*
* 3.
The end-user documentation included with the redistribution, if
* any, must
include the following acknowlegement:
* "This product includes software
developed by the
* Apache Software Foundation (http://www.apache.org/)."
*
Alternately, this acknowlegement may appear in the software itself,
* if and
wherever such third-party acknowlegements normally appear.
*
* 4. The names "The
Jakarta Project", "Commons", and "Apache Software
* Foundation" must not be used
to endorse or promote products derived
* from this software without prior written
permission. For written
* permission, please contact [EMAIL PROTECTED]
*
* 5.
Products derived from this software may not be called "Apache"
* nor may "Apache"
appear in their names without prior written
* permission of the Apache Group.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND
FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE
SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
*
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY,
WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF
* SUCH DAMAGE.
*
====================================================================
*
* This
software consists of voluntary contributions made by many
* individuals on behalf of
the Apache Software Foundation. For more
* information on the Apache Software
Foundation, please see
* <http://www.apache.org/>.
*
*/
package
org.apache.commons.collections;
import java.io.Externalizable;
import
java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectInputStream;
import java.io.ObjectOutput;
import java.io.ObjectOutputStream;
import
java.util.Iterator;
/** <p>
* An implementation of a Map which has a maximum size
and uses a Least Recently Used
* algorithm to remove items from the Map when the
maximum size is reached and new items are added.
* </p>
*
* <p>
* A
synchronized version can be obtained with:
* <code>Collections.synchronizedMap(
theMapToSynchronize )</code>
* If it will be accessed by multiple threads, you
_must_ synchronize access
* to this Map. Even concurrent get(Object) operations
produce indeterminate
* behaviour.
* </p>
*
* <p>
* Unlike that Collections
1.0 version, this version of LRUMap does use a true
* LRU algorithm. The keys for
all gets and puts are moved to the front of
* the list. LRUMap is now a subclass of
SequencedHashMap, and the "LRU"
* key is now equivalent to LRUMap.getFirst().
*
</p>
*
*
* @author <a href="mailto:[EMAIL PROTECTED]";>James Strachan</a>
* @author <a href="mailto:[EMAIL PROTECTED]";>Morgan Delagrange</a>
*/
public class
LRUMap extends SequencedHashMap implements Externalizable {
private int
maximumSize = 0;
/**
* Default constructor, primarily for the purpose of
* de-externalization. This constructors sets a default
* LRU limit of 100 keys,
but this value may be overridden
* internally as a result of de-externalization.
*/
public LRUMap() {
this( 100 );
}
/**
* Create a new
LRUMap with a maximum capacity of <i>i</i>.
* Once <i>i</i> capacity is achieved,
subsequent gets
* and puts will push keys out of the map. See .
*
*
@param i Maximum capacity of the LRUMap
*/
public LRUMap(int i) {
super( i );
maximumSize = i;
}
/**
* <p>Removes the key and
its Object from the Map.</p>
*
* <p>(Note: this may result in the "Least
Recently Used"
* object being removed from the Map. In that case,
* the
removeLRU() method is called. See javadoc for
* removeLRU() for more
details.)</p>
*
* @param key Key of the Object to add.
* @param
value Object to add
* @return Former value of the key
* @see removeLRU()
*/
public Object put( Object key, Object value ) {
int mapSize
= size();
Object retval = null;
if ( mapSize >= maximumSize ) {
// don't retire LRU if you are just
// updating an existing key
if (!containsKey(key)) {
// lets retire the least
recently used item in the cache
removeLRU();
}
retval = super.put(key,value);
} else {
retval =
super.put(key,value);
}
return retval;
}
/**
* This
method is used internally by the class for
* finding and removing the LRU
Object.
*/
protected void removeLRU() {
Object key = getFirstKey();
Object value = get(key);
remove(key);
processRemovedLRU(key,value);
}
/**
* Subclasses of LRUMap may hook into
this method to
* provide specialized actions whenever an Object is
*
automatically removed from the cache. By default,
* this method does nothing.
*
* @param key key that was removed
* @param value value of that key
(can be null)
*/
protected void processRemovedLRU(Object key, Object value) {
}
// Externalizable interface
//-------------------------------------------------------------------------
public void readExternal( ObjectInput in ) throws IOException,
ClassNotFoundException {
maximumSize = in.readInt();
int size =
in.readInt();
for( int i = 0; i < size; i++ ) {
Object
key = in.readObject();
Object value = in.readObject();
put(key,value);
}
}
public void writeExternal( ObjectOutput out )
throws IOException {
out.writeInt( maximumSize );
out.writeInt( size()
);
for( Iterator iterator = keySet().iterator(); iterator.hasNext(); ) {
Object key = iterator.next();
out.writeObject( key );
Object value = get( key );
out.writeObject( value );
}
}
// Properties
//-------------------------------------------------------------------------
/** Getter for property maximumSize.
* @return Value of property maximumSize.
*/
public int getMaximumSize() {
return maximumSize;
}
/**
Setter for property maximumSize.
* @param maximumSize New value of property
maximumSize.
*/
public void setMaximumSize(int maximumSize) {
this.maximumSize = maximumSize;
while (size() > maximumSize) {
removeLRU();
}
}
}
\ No newline at end of file
1.12 +35 -61
jakarta-commons/collections/src/test/org/apache/commons/collections/TestLRUMap.java
Index: TestLRUMap.java
===================================================================
RCS file:
/home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestLRUMap.java,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -r1.11 -r1.12
--- TestLRUMap.java 19 Feb 2002 21:28:53 -0000 1.11
+++ TestLRUMap.java 20 Feb 2002 18:01:34 -0000 1.12
@@ -1,7 +1,7 @@
/*
- * $Header:
/home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestLRUMap.java,v
1.11 2002/02/19 21:28:53 morgand Exp $
- * $Revision: 1.11 $
- * $Date: 2002/02/19 21:28:53 $
+ * $Header:
/home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestLRUMap.java,v
1.12 2002/02/20 18:01:34 morgand Exp $
+ * $Revision: 1.12 $
+ * $Date: 2002/02/20 18:01:34 $
*
* ====================================================================
*
@@ -69,6 +69,7 @@
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
+import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
@@ -76,7 +77,7 @@
*
* @author <a href="mailto:[EMAIL PROTECTED]";>James Strachan</a>
* @author <a href="mailto:[EMAIL PROTECTED]";>Morgan Delagrange</a>
- * @version $Id: TestLRUMap.java,v 1.11 2002/02/19 21:28:53 morgand Exp $
+ * @version $Id: TestLRUMap.java,v 1.12 2002/02/20 18:01:34 morgand Exp $
*/
public class TestLRUMap extends TestMap
{
@@ -99,15 +100,14 @@
}
public void testRemoveLRU() {
- LRUMap map2 = new LRUMap(4);
+ LRUMap map2 = new LRUMap(3);
map2.put(new Integer(1),"foo");
map2.put(new Integer(2),"foo");
map2.put(new Integer(3),"foo");
map2.put(new Integer(4),"foo");
- map2.removeLRU(); // should be Integer(4)
- assertTrue("Second to last value should exist",map2.get(new
Integer(3)).equals("foo"));
- assertTrue("Last value inserted should not exist", map2.get(new Integer(4))
== null);
+ assertTrue("last value should exist",map2.get(new
Integer(4)).equals("foo"));
+ assertTrue("LRU should not exist", map2.get(new Integer(1)) == null);
}
public void testMultiplePuts() {
@@ -165,14 +165,6 @@
}
/**
- * Test performs a complex series of puts, then makes sure
- * that they have ended up in the correct LRU order.
- */
- public void testTrueLRU() {
- // implement when subclass of SequencedHashMap
- }
-
- /**
* Test that the size of the map is reduced immediately
* when setMaximumSize(int) is called
*/
@@ -218,65 +210,47 @@
*/
public void testLRUSubclass() {
LRUCounter counter = new LRUCounter(3);
- counter.put(new Integer(1),"foo");
- counter.put(new Integer(2),"foo");
- counter.put(new Integer(3),"foo");
- counter.put(new Integer(1),"foo");
- counter.put(new Integer(4),"foo");
- counter.put(new Integer(5),"foo");
- counter.put(new Integer(2),"foo");
- counter.remove(new Integer(5));
-
- assertTrue("size should be 2, but was " + counter.size(), counter.size() ==
2);
- assertTrue("removedCount should be 2 but was " + counter.removedCount,
- counter.removedCount == 2);
- }
-
- /**
- * You should be able to subclass LRUMap and perform a
- * custom action when items are removed automatically
- * or when remove is called manually
- * by overriding the remove(Object) method.
- */
- public void testRemoveSubclass() {
- RemoveCounter counter = new RemoveCounter(3);
- counter.put(new Integer(1),"foo");
- counter.put(new Integer(2),"foo");
- counter.put(new Integer(3),"foo");
- counter.put(new Integer(1),"foo");
- counter.put(new Integer(4),"foo");
- counter.put(new Integer(5),"foo");
- counter.put(new Integer(2),"foo");
- counter.remove(new Integer(5));
+ // oldest <--> newest
+ // 1
+ counter.put("1","foo");
+ // 1 2
+ counter.put("2","foo");
+ // 1 2 3
+ counter.put("3","foo");
+ // 2 3 1
+ counter.put("1","foo");
+ // 3 1 4 (2 goes out)
+ counter.put("4","foo");
+ // 1 4 5 (3 goes out)
+ counter.put("5","foo");
+ // 4 5 2 (1 goes out)
+ counter.put("2","foo");
+ // 4 2
+ counter.remove("5");
assertTrue("size should be 2, but was " + counter.size(), counter.size() ==
2);
assertTrue("removedCount should be 3 but was " + counter.removedCount,
counter.removedCount == 3);
- }
-
- private class LRUCounter extends LRUMap {
- int removedCount = 0;
- LRUCounter(int i) {
- super(i);
- }
+ assertTrue("first removed was '2'",counter.list.get(0).equals("2"));
+ assertTrue("second removed was '3'",counter.list.get(1).equals("3"));
+ assertTrue("third removed was '1'",counter.list.get(2).equals("1"));
- public Object removeLRU() {
- ++removedCount;
- return super.removeLRU();
- }
+ assertTrue("oldest key is '4'",counter.get(0).equals("4"));
+ assertTrue("newest key is '2'",counter.get(1).equals("2"));
}
- private class RemoveCounter extends LRUMap {
+ private class LRUCounter extends LRUMap {
int removedCount = 0;
+ ArrayList list = new ArrayList(3);
- RemoveCounter(int i) {
+ LRUCounter(int i) {
super(i);
}
- public Object remove(Object o) {
+ protected void processRemovedLRU(Object key, Object value) {
++removedCount;
- return super.remove(o);
+ list.add(key);
}
}
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
