Mercurial > hg > blitz_condensed
view src/com/go/trove/util/UsageMap.java @ 0:3dc0c5604566
Initial checkin of blitz 2.0 fcs - no installer yet.
author | Dan Creswell <dan.creswell@gmail.com> |
---|---|
date | Sat, 21 Mar 2009 11:00:06 +0000 |
parents | |
children |
line wrap: on
line source
/* ==================================================================== * 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; } } }