LRUMap has interesting behavior, not quite LRU

[apache-commons <ap...@weygandt.com>]

Commons developers,

I noticed that when the list fills up, entries added are at the bottom of
the list, therefore new entries bump the latest entry off the list - not the
LRU algorithm I would expect.

I have the source from commons-collections-1.0, I have also attempted to
verify that it is the latest in cvs. LRUMap.java is from version 1.1.

Further I have noticed that if you remove an item, the "bubbling up" stops
at that removed item.

Simple test, put the following code fragment into LRUMap and run:

BTW - I found an old copy of: org/apache/tomcat/util/LRUCache.java, which
has less features, and uses Hashtable (not HashMap) if anyone is interested.

Jon
-------------------------------
    public void report()
    {
        System.out.println("LRUMap report");
        System.out.println("       maximumSize: " + maximumSize);
        System.out.println("              size: " + size());
        System.out.println("   bubbleList.size: " + bubbleList.size());
        for(int i=0; i<bubbleList.size(); i++)
        {
            System.out.println("     " + i + "\t=" + bubbleList.get(i));
        }
    }

    public static void main(String [] args)
    {
        LRUMap m = new LRUMap(5);
        m.put("k1", "v1");
        m.put("k2", "v2");
        m.put("k3", "v3");
        m.put("k4", "v4");
        m.put("k5", "v5");
        m.report();
        m.put("k6", "v6");
        m.put("k7", "v7");
        m.report();
        m.remove("k3");
        m.report();
        m.get("k7");
        m.report();
        m.get("k7");
        m.report();
        m.get("k7");
        m.report();
        m.get("k7");
        m.report();
    }
---------------------------------

/* The output with comments below */

/* List is full - OK for now */
LRUMap report
       maximumSize: 5
              size: 5
   bubbleList.size: 5
     0 =k1
     1 =k2
     2 =k3
     3 =k4
     4 =k5

/* after adding k6 and k7, only k7 remains - ?? */
LRUMap report
       maximumSize: 5
              size: 5
   bubbleList.size: 5
     0 =k1
     1 =k2
     2 =k3
     3 =k4
     4 =k7

/* k3 has been removed from the internal HasMap, remains in array */
LRUMap report
       maximumSize: 5
              size: 4
   bubbleList.size: 5
     0 =k1
     1 =k2
     2 =k3
     3 =k4
     4 =k7

/* one bubble up - OK */
LRUMap report
       maximumSize: 5
              size: 4
   bubbleList.size: 5
     0 =k1
     1 =k2
     2 =k3
     3 =k7
     4 =k4

/* it's stuck, no more bubbling for k7 */
LRUMap report
       maximumSize: 5
              size: 4
   bubbleList.size: 5
     0 =k1
     1 =k2
     2 =k3
     3 =k7
     4 =k4
LRUMap report
       maximumSize: 5
              size: 4
   bubbleList.size: 5
     0 =k1
     1 =k2
     2 =k3
     3 =k7
     4 =k4
LRUMap report
       maximumSize: 5
              size: 4
   bubbleList.size: 5
     0 =k1
     1 =k2
     2 =k3
     3 =k7
     4 =k4





--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>