001: /* ====================================================================
002: * Trove - Copyright (c) 1997-2000 Walt Disney Internet Group
003: * ====================================================================
004: * The Tea Software License, Version 1.1
005: *
006: * Copyright (c) 2000 Walt Disney Internet Group. All rights reserved.
007: *
008: * Redistribution and use in source and binary forms, with or without
009: * modification, are permitted provided that the following conditions
010: * are met:
011: *
012: * 1. Redistributions of source code must retain the above copyright
013: * notice, this list of conditions and the following disclaimer.
014: *
015: * 2. Redistributions in binary form must reproduce the above copyright
016: * notice, this list of conditions and the following disclaimer in
017: * the documentation and/or other materials provided with the
018: * distribution.
019: *
020: * 3. The end-user documentation included with the redistribution,
021: * if any, must include the following acknowledgment:
022: * "This product includes software developed by the
023: * Walt Disney Internet Group (http://opensource.go.com/)."
024: * Alternately, this acknowledgment may appear in the software itself,
025: * if and wherever such third-party acknowledgments normally appear.
026: *
027: * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must
028: * not be used to endorse or promote products derived from this
029: * software without prior written permission. For written
030: * permission, please contact opensource@dig.com.
031: *
032: * 5. Products derived from this software may not be called "Tea",
033: * "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet",
034: * "Kettle", "Trove" or "BeanDoc" appear in their name, without prior
035: * written permission of the Walt Disney Internet Group.
036: *
037: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
038: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
039: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
040: * DISCLAIMED. IN NO EVENT SHALL THE WALT DISNEY INTERNET GROUP OR ITS
041: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
042: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
043: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
044: * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
045: * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
046: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
047: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
048: * ====================================================================
049: *
050: * For more information about Tea, please see http://opensource.go.com/.
051: */
052:
053: package com.go.trove.util;
054:
055: import java.util.*;
056:
057: /******************************************************************************
058: * A Map that orders its keys based on how recently they have been used.
059: * Most recently used keys appear first in the Map. Keys are marked as being
060: * used whenever they are put into to the Map. To re-position a key, put it
061: * back in.
062: *
063: * parametrized for GJ by Stefan Reich (doc@drjava.de);
064: * removed putAll because it doesn't conform to the overridden definition
065: * of putAll in Map<A,B>
066: *
067: * @author Brian S O'Neill
068: * @version
069: * <!--$$Revision: 1.2 $-->, <!--$$JustDate:--> 9/07/00 <!-- $-->
070: */
071: public class UsageMap<A, B> extends AbstractMap<A, B> implements
072: java.io.Serializable {
073: private Map<A, Entry<A, B>> mRecentMap;
074: private boolean mReverse;
075:
076: private Entry<A, B> mMostRecent;
077: private Entry<A, B> mLeastRecent;
078:
079: private transient Set mEntrySet;
080:
081: /**
082: * Creates a UsageMap in forward order, MRU first.
083: */
084: public UsageMap() {
085: this (new HashMap());
086: }
087:
088: /**
089: * @param backingMap map to use for storage
090: */
091: public UsageMap(Map backingMap) {
092: mRecentMap = backingMap;
093: }
094:
095: /**
096: * With reverse order, keys are ordered least recently used first. The
097: * ordering of the map entries will be consistent with the order they were
098: * put into it. Switching to and from reverse order is performed quickly
099: * and is not affected by the current size of the map.
100: */
101: public void setReverseOrder(boolean reverse) {
102: mReverse = reverse;
103: }
104:
105: /**
106: * Returns the first key in the map, the most recently used. If reverse
107: * order, then the least recently used is returned.
108: */
109: public A firstKey() throws NoSuchElementException {
110: Entry<A, B> first = (mReverse) ? mLeastRecent : mMostRecent;
111: if (first != null) {
112: return first.mKey;
113: } else if (mRecentMap.size() == 0) {
114: throw new NoSuchElementException();
115: } else {
116: return null;
117: }
118: }
119:
120: /**
121: * Returns the last key in the map, the least recently used. If reverse
122: * order, then the most recently used is returned.
123: */
124: public A lastKey() throws NoSuchElementException {
125: Entry<A, B> last = (mReverse) ? mMostRecent : mLeastRecent;
126: if (last != null) {
127: return last.mKey;
128: } else if (mRecentMap.size() == 0) {
129: throw new NoSuchElementException();
130: } else {
131: return null;
132: }
133: }
134:
135: public int size() {
136: return mRecentMap.size();
137: }
138:
139: public boolean isEmpty() {
140: return mRecentMap.isEmpty();
141: }
142:
143: public boolean containsKey(A key) {
144: return mRecentMap.containsKey(key);
145: }
146:
147: public B get(A key) {
148: Entry<A, B> e = mRecentMap.get(key);
149: return (e == null) ? null : e.mValue;
150: }
151:
152: public B put(A key, B value) {
153: Entry<A, B> e = mRecentMap.get(key);
154: B old;
155:
156: if (e == null) {
157: old = null;
158: e = new Entry<A, B>(key, value);
159: mRecentMap.put(key, e);
160: } else {
161: old = e.mValue;
162: e.mValue = value;
163:
164: if (e == mMostRecent) {
165: return old;
166: }
167:
168: // Delete entry from linked list.
169: if (e.mPrev == null) {
170: mMostRecent = e.mNext;
171: } else {
172: e.mPrev.mNext = e.mNext;
173: }
174: if (e.mNext == null) {
175: mLeastRecent = e.mPrev;
176: } else {
177: e.mNext.mPrev = e.mPrev;
178: }
179: e.mPrev = null;
180: }
181:
182: if (mMostRecent == null) {
183: mMostRecent = e;
184: } else {
185: e.mNext = mMostRecent;
186: mMostRecent.mPrev = e;
187: mMostRecent = e;
188: }
189:
190: if (mLeastRecent == null) {
191: mLeastRecent = e;
192: }
193:
194: return old;
195: }
196:
197: public B remove(A key) {
198: Entry<A, B> e = mRecentMap.remove(key);
199:
200: if (e == null) {
201: return null;
202: } else {
203: // Delete entry from linked list.
204: if (e.mPrev == null) {
205: mMostRecent = e.mNext;
206: } else {
207: e.mPrev.mNext = e.mNext;
208: }
209: if (e.mNext == null) {
210: mLeastRecent = e.mPrev;
211: } else {
212: e.mNext.mPrev = e.mPrev;
213: }
214:
215: return e.mValue;
216: }
217: }
218:
219: /*public void putAll(Map<A,Entry<A,B>> map) {
220: Iterator<Map.Entry<A,Entry<A,B>>> it = map.entrySet().iterator();
221: while (it.hasNext()) {
222: Map.Entry<A,Entry<A,B>> entry = it.next();
223: mRecentMap.put(entry.getKey(), entry.getValue());
224: }
225: }*/
226:
227: public void clear() {
228: mRecentMap.clear();
229: mMostRecent = null;
230: mLeastRecent = null;
231: }
232:
233: public Set<Map.Entry<A, B>> entrySet() {
234: if (mEntrySet != null) {
235: return mEntrySet;
236: }
237:
238: mEntrySet = new AbstractSet<Map.Entry<A, B>>() {
239: public Iterator<Map.Entry<A, B>> iterator() {
240: if (mReverse) {
241: return new Iterator<Map.Entry<A, B>>() {
242: private Entry<A, B> mPrev = mLeastRecent;
243: private Entry<A, B> mLast = null;
244:
245: public boolean hasNext() {
246: return mPrev != null;
247: }
248:
249: public Map.Entry<A, B> next() {
250: if ((mLast = mPrev) == null) {
251: throw new NoSuchElementException();
252: } else {
253: mPrev = mPrev.mPrev;
254: return mLast;
255: }
256: }
257:
258: public void remove() {
259: if (mLast == null) {
260: throw new IllegalStateException();
261: } else {
262: UsageMap.this .remove(mLast.mKey);
263: mLast = null;
264: }
265: }
266: };
267: } else {
268: return new Iterator<Map.Entry<A, B>>() {
269: private Entry<A, B> mNext = mMostRecent;
270: private Entry<A, B> mLast = null;
271:
272: public boolean hasNext() {
273: return mNext != null;
274: }
275:
276: public Map.Entry<A, B> next() {
277: if ((mLast = mNext) == null) {
278: throw new NoSuchElementException();
279: } else {
280: mNext = mNext.mNext;
281: return mLast;
282: }
283: }
284:
285: public void remove() {
286: if (mLast == null) {
287: throw new IllegalStateException();
288: } else {
289: UsageMap.this .remove(mLast.mKey);
290: mLast = null;
291: }
292: }
293: };
294: }
295: }
296:
297: public int size() {
298: return mRecentMap.size();
299: }
300:
301: public boolean isEmpty() {
302: return mRecentMap.isEmpty();
303: }
304:
305: public boolean contains(Map.Entry<A, B> obj) {
306: Entry<A, B> e = mRecentMap.get(obj.getKey());
307: return e != null && e.equals(obj);
308: }
309:
310: public boolean remove(Map.Entry<A, B> obj) {
311: if (contains(obj)) {
312: UsageMap.this .remove(obj.getKey());
313: return true;
314: } else {
315: return false;
316: }
317: }
318:
319: public void clear() {
320: UsageMap.this .clear();
321: }
322: };
323:
324: return mEntrySet;
325: }
326:
327: private static class Entry<A, B> extends AbstractMapEntry<A, B>
328: implements java.io.Serializable {
329: public Entry mPrev;
330: public Entry mNext;
331: public A mKey;
332: public B mValue;
333:
334: public Entry(A key, B value) {
335: mKey = key;
336: mValue = value;
337: }
338:
339: public A getKey() {
340: return mKey;
341: }
342:
343: public B getValue() {
344: return mValue;
345: }
346:
347: public B setValue(B value) {
348: B old = mValue;
349: mValue = value;
350: return old;
351: }
352: }
353: }
|