--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/com/go/trove/util/UsageMap.java	Sat Mar 21 11:00:06 2009 +0000
@@ -0,0 +1,372 @@
+/* ====================================================================
+ * Trove - Copyright (c) 1997-2000 Walt Disney Internet Group
+ * ====================================================================
+ * The Tea Software License, Version 1.1
+ *
+ * Copyright (c) 2000 Walt Disney Internet Group. 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 acknowledgment:
+ *       "This product includes software developed by the
+ *        Walt Disney Internet Group (http://opensource.go.com/)."
+ *    Alternately, this acknowledgment may appear in the software itself,
+ *    if and wherever such third-party acknowledgments normally appear.
+ *
+ * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must
+ *    not be used to endorse or promote products derived from this
+ *    software without prior written permission. For written
+ *    permission, please contact opensource@dig.com.
+ *
+ * 5. Products derived from this software may not be called "Tea",
+ *    "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet",
+ *    "Kettle", "Trove" or "BeanDoc" appear in their name, without prior
+ *    written permission of the Walt Disney Internet 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 WALT DISNEY INTERNET GROUP 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.
+ * ====================================================================
+ *
+ * For more information about Tea, please see http://opensource.go.com/.
+ */
+
+package com.go.trove.util;
+
+import java.util.*;
+
+/******************************************************************************
+ * A Map that orders its keys based on how recently they have been used.
+ * Most recently used keys appear first in the Map. Keys are marked as being
+ * used whenever they are put into to the Map. To re-position a key, put it
+ * back in.
+ * 
+ * @author Brian S O'Neill
+ * @version
+ * <!--$$Revision:--> 15 <!-- $-->, <!--$$JustDate:-->  9/07/00 <!-- $-->
+ */
+public class UsageMap extends AbstractMap implements java.io.Serializable {
+    private Map mRecentMap;
+    private boolean mReverse;
+
+    private Entry mMostRecent;
+    private Entry mLeastRecent;
+
+    private transient Set mEntrySet;
+
+    /**
+     * Creates a UsageMap in forward order, MRU first.
+     */
+    public UsageMap() {
+        this(new HashMap());
+    }
+
+    /**
+     * @param backingMap map to use for storage
+     */
+    public UsageMap(Map backingMap) {
+        mRecentMap = backingMap;
+    }
+
+    /**
+     * With reverse order, keys are ordered least recently used first. The
+     * ordering of the map entries will be consistent with the order they were
+     * put into it. Switching to and from reverse order is performed quickly
+     * and is not affected by the current size of the map.
+     */
+    public void setReverseOrder(boolean reverse) {
+        mReverse = reverse;
+    }
+
+    /**
+     * Returns the first key in the map, the most recently used. If reverse
+     * order, then the least recently used is returned.
+     */
+    public Object firstKey() throws NoSuchElementException {
+        Entry first = (mReverse) ? mLeastRecent : mMostRecent;
+        if (first != null) {
+            return first.mKey;
+        }
+        else if (mRecentMap.size() == 0) {
+            throw new NoSuchElementException();
+        }
+        else {
+            return null;
+        }
+    }
+
+    /**
+     * Returns the last key in the map, the least recently used. If reverse
+     * order, then the most recently used is returned.
+     */
+    public Object lastKey() throws NoSuchElementException {
+        Entry last = (mReverse) ? mMostRecent : mLeastRecent;
+        if (last != null) {
+            return last.mKey;
+        }
+        else if (mRecentMap.size() == 0) {
+            throw new NoSuchElementException();
+        }
+        else {
+            return null;
+        }
+    }
+
+    public int size() {
+        return mRecentMap.size();
+    }
+
+    public boolean isEmpty() {
+        return mRecentMap.isEmpty();
+    }
+
+    public boolean containsKey(Object key) {
+        return mRecentMap.containsKey(key);
+    }
+
+    public Object get(Object key) {
+        Entry e = (Entry)mRecentMap.get(key);
+        return (e == null) ? null : e.mValue;
+    }
+
+    public Object put(Object key, Object value) {
+        Entry e = (Entry)mRecentMap.get(key);
+        Object old;
+
+        if (e == null) {
+            old = null;
+            e = new Entry(key, value);
+            mRecentMap.put(key, e);
+        }
+        else {
+            old = e.mValue;
+            e.mValue = value;
+
+            if (e == mMostRecent) {
+                return old;
+            }
+
+            // Delete entry from linked list.
+            if (e.mPrev == null) {
+                mMostRecent = e.mNext;
+            }
+            else {
+                e.mPrev.mNext = e.mNext;
+            }
+            if (e.mNext == null) {
+                mLeastRecent = e.mPrev;
+            }
+            else {
+                e.mNext.mPrev = e.mPrev;
+            }
+            e.mPrev = null;
+        }
+
+        if (mMostRecent == null) {
+            mMostRecent = e;
+        }
+        else {
+            e.mNext = mMostRecent;
+            mMostRecent.mPrev = e;
+            mMostRecent = e;
+        }
+
+        if (mLeastRecent == null) {
+            mLeastRecent = e;
+        }
+
+        return old;
+    }
+
+    public Object remove(Object key) {
+        Entry e = (Entry)mRecentMap.remove(key);
+        
+        if (e == null) {
+            return null;
+        }
+        else {
+            // Delete entry from linked list.
+            if (e.mPrev == null) {
+                mMostRecent = e.mNext;
+            }
+            else {
+                e.mPrev.mNext = e.mNext;
+            }
+            if (e.mNext == null) {
+                mLeastRecent = e.mPrev;
+            }
+            else {
+                e.mNext.mPrev = e.mPrev;
+            }
+
+            return e.mValue;
+        }
+    }
+
+    public void putAll(Map map) {
+        Iterator it = map.entrySet().iterator();
+        while (it.hasNext()) {
+            Map.Entry entry = (Map.Entry)it.next();
+            mRecentMap.put(entry.getKey(), entry.getValue());
+        }
+    }
+
+    public void clear() {
+        mRecentMap.clear();
+        mMostRecent = null;
+        mLeastRecent = null;
+    }
+
+    public Set entrySet() {
+        if (mEntrySet != null) {
+            return mEntrySet;
+        }
+
+        mEntrySet = new AbstractSet() {
+            public Iterator iterator() {
+                if (mReverse) {
+                    return new Iterator() {
+                        private Entry mPrev = mLeastRecent;
+                        private Entry mLast = null;
+
+                        public boolean hasNext() {
+                            return mPrev != null;
+                        }
+
+                        public Object next() {
+                            if ((mLast = mPrev) == null) {
+                                throw new NoSuchElementException();
+                            }
+                            else {
+                                mPrev = mPrev.mPrev;
+                                return mLast;
+                            }
+                        }
+
+                        public void remove() {
+                            if (mLast == null) {
+                                throw new IllegalStateException();
+                            }
+                            else {
+                                UsageMap.this.remove(mLast.mKey);
+                                mLast = null;
+                            }
+                        }
+                    };
+                }
+                else {
+                    return new Iterator() {
+                        private Entry mNext = mMostRecent;
+                        private Entry mLast = null;
+
+                        public boolean hasNext() {
+                            return mNext != null;
+                        }
+
+                        public Object next() {
+                            if ((mLast = mNext) == null) {
+                                throw new NoSuchElementException();
+                            }
+                            else {
+                                mNext = mNext.mNext;
+                                return mLast;
+                            }
+                        }
+
+                        public void remove() {
+                            if (mLast == null) {
+                                throw new IllegalStateException();
+                            }
+                            else {
+                                UsageMap.this.remove(mLast.mKey);
+                                mLast = null;
+                            }
+                        }
+                    };
+                }
+            }
+
+            public int size() {
+                return mRecentMap.size();
+            }
+
+            public boolean isEmpty() {
+                return mRecentMap.isEmpty();
+            }
+            
+            public boolean contains(Object obj) {
+                if (!(obj instanceof Map.Entry)) {
+                    return false;
+                }
+                Entry e = (Entry)mRecentMap.get(((Map.Entry)obj).getKey());
+                return e != null && e.equals(obj);
+            }
+
+            public boolean remove(Object obj) {
+                if (!(obj instanceof Map.Entry)) {
+                    return false;
+                }
+                if (contains(obj)) {
+                    UsageMap.this.remove(((Map.Entry)obj).getKey());
+                    return true;
+                }
+                else {
+                    return false;
+                }
+            }
+
+            public void clear() {
+                UsageMap.this.clear();
+            }
+        };
+
+        return mEntrySet;
+    }
+
+    private static class Entry extends AbstractMapEntry
+        implements java.io.Serializable
+    {
+        public Entry mPrev;
+        public Entry mNext;
+        public Object mKey;
+        public Object mValue;
+
+        public Entry(Object key, Object value) {
+            mKey = key;
+            mValue = value;
+        }
+
+        public Object getKey() {
+            return mKey;
+        }
+
+        public Object getValue() {
+            return mValue;
+        }
+
+        public Object setValue(Object value) {
+            Object old = mValue;
+            mValue = value;
+            return old;
+        }
+    }
+}