commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From morg...@apache.org
Subject cvs commit: jakarta-commons/collections/src/test/org/apache/commons/collections TestLRUMap.java
Date Wed, 20 Feb 2002 18:01:34 GMT
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 apache@apache.org.
  - *
  - * 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:jstrachan@apache.org">James Strachan</a>
  -  * @author <a href="mailto:morgand@apache.org">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 apache@apache.org.
*
 * 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:jstrachan@apache.org">James Strachan</a>
 * @author <a href="mailto:morgand@apache.org">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:jstrachan@apache.org">James Strachan</a>
    * @author <a href="mailto:morgand@apache.org">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:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message