Fixes in this patch: - Changed license to proper long form. - Added warnings to class documenation about the problems the class has.
FYI: I plan on revisiting this class to address the following problems (I documentated these in the patch so users of the class are also aware the problem exists): - LRU algorithm is not actually "least recently used". The idea of moving an entry only slightly further from the "drop zone" rather than all the way to the beginning is interesting, but it is not "least recently used". See example case exhibiting a flaw in the implementation in this email from Aaron Smuts: http://www.mail-archive.com/commons-dev%40jakarta.apache.org/msg02555.ht ml The approach in LRUMap may have been at attempt at a "most used" where the most used element is at the front of the list, but it fails to do that as well. An alternative data structure that may be interesting to implement woud be a splay tree, which attempts to keep freqeuently accessed items at the top of the tree, while less frequent items are at the bottom of the tree. Another alternative would be to use a heap, with priorities based on the account count. Both the splay tree and heap would operate more slowly than a HashMap though (splay trees and heaps have inherant O(log n) runtime for some operations. - To fix the above problem, the "Bubble List" probably won't exist, but if for some reason it still does, it appears as though things will break if you remove an item. remove(Object) removes the item from the map, but not the bubble list. - The results from entrySet() and values() are not properly backed by the map in violation of the Map API contract. Removes from the returned structures are not reflected in he overall Map. I didn't do a full review on this though, so there may be other items I might want to address. Regards, michael Index: D:/home/michael/dev/jakarta/jakarta-commons/collections/src/java/org/apa che/commons/collections/LRUMap.java =================================================================== RCS file: /home/cvspublic/jakarta-commons/collections/src/java/org/apache/commons/ collections/LRUMap.java,v retrieving revision 1.1 diff -u -r1.1 LRUMap.java --- D:/home/michael/dev/jakarta/jakarta-commons/collections/src/java/org/apa che/commons/collections/LRUMap.java 6 May 2001 11:04:25 -0000 1.1 +++ D:/home/michael/dev/jakarta/jakarta-commons/collections/src/java/org/apa che/commons/collections/LRUMap.java 3 Feb 2002 16:19:31 -0000 @@ -1,9 +1,62 @@ /* - * Copyright (C) The Apache Software Foundation. All rights reserved. + * $Header: $ + * $Revision: $ + * $Date: $ + * + * ==================================================================== + * + * The Apache Software License, Version 1.1 + * + * Copyright (c) 2001-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/>. * - * This software is published under the terms of the Apache Software License - * version 1.1, a copy of which has been included with this distribution in - * the LICENSE file. */ package org.apache.commons.collections; @@ -27,12 +80,50 @@ * </p> * * <p> - * <b>WARNING</b> the values() and entrySet() methods require optimisation - * like the standard {@link HashMap} implementations so that iteration - * over this Map is efficient. + * <p>Warning</p>: 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]">James Strachan</a> */ public class LRUMap extends HashMap implements Externalizable {
LRUMap.patch
Description: Binary data
-- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>