Mercurial > hg > blitz_stable

comparison src/com/go/trove/util/UsageMap.java @ 0:3dc0c5604566

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
-1:000000000000 0:3dc0c5604566
1 /* ====================================================================
2 * Trove - Copyright (c) 1997-2000 Walt Disney Internet Group
3 * ====================================================================
4 * The Tea Software License, Version 1.1
5 *
6 * Copyright (c) 2000 Walt Disney Internet Group. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 *
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * 3. The end-user documentation included with the redistribution,
21 * if any, must include the following acknowledgment:
22 * "This product includes software developed by the
23 * Walt Disney Internet Group (http://opensource.go.com/)."
24 * Alternately, this acknowledgment may appear in the software itself,
25 * if and wherever such third-party acknowledgments normally appear.
26 *
27 * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must
28 * not be used to endorse or promote products derived from this
29 * software without prior written permission. For written
30 * permission, please contact opensource@dig.com.
31 *
32 * 5. Products derived from this software may not be called "Tea",
33 * "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet",
34 * "Kettle", "Trove" or "BeanDoc" appear in their name, without prior
35 * written permission of the Walt Disney Internet Group.
36 *
37 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
38 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
39 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
40 * DISCLAIMED. IN NO EVENT SHALL THE WALT DISNEY INTERNET GROUP OR ITS
41 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
42 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
43 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
44 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
45 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
46 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
47 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
48 * ====================================================================
49 *
50 * For more information about Tea, please see http://opensource.go.com/.
51 */
52
53 package com.go.trove.util;
54
55 import java.util.*;
56
57 /******************************************************************************
58 * A Map that orders its keys based on how recently they have been used.
59 * Most recently used keys appear first in the Map. Keys are marked as being
60 * used whenever they are put into to the Map. To re-position a key, put it
61 * back in.
62 *
63 * @author Brian S O'Neill
64 * @version
65 * <!--$$Revision:--> 15 <!-- $-->, <!--$$JustDate:--> 9/07/00 <!-- $-->
66 */
67 public class UsageMap extends AbstractMap implements java.io.Serializable {
68 private Map mRecentMap;
69 private boolean mReverse;
70
71 private Entry mMostRecent;
72 private Entry mLeastRecent;
73
74 private transient Set mEntrySet;
75
76 /**
77 * Creates a UsageMap in forward order, MRU first.
78 */
79 public UsageMap() {
80 this(new HashMap());
81 }
82
83 /**
84 * @param backingMap map to use for storage
85 */
86 public UsageMap(Map backingMap) {
87 mRecentMap = backingMap;
88 }
89
90 /**
91 * With reverse order, keys are ordered least recently used first. The
92 * ordering of the map entries will be consistent with the order they were
93 * put into it. Switching to and from reverse order is performed quickly
94 * and is not affected by the current size of the map.
95 */
96 public void setReverseOrder(boolean reverse) {
97 mReverse = reverse;
98 }
99
100 /**
101 * Returns the first key in the map, the most recently used. If reverse
102 * order, then the least recently used is returned.
103 */
104 public Object firstKey() throws NoSuchElementException {
105 Entry first = (mReverse) ? mLeastRecent : mMostRecent;
106 if (first != null) {
107 return first.mKey;
108 }
109 else if (mRecentMap.size() == 0) {
110 throw new NoSuchElementException();
111 }
112 else {
113 return null;
114 }
115 }
116
117 /**
118 * Returns the last key in the map, the least recently used. If reverse
119 * order, then the most recently used is returned.
120 */
121 public Object lastKey() throws NoSuchElementException {
122 Entry last = (mReverse) ? mMostRecent : mLeastRecent;
123 if (last != null) {
124 return last.mKey;
125 }
126 else if (mRecentMap.size() == 0) {
127 throw new NoSuchElementException();
128 }
129 else {
130 return null;
131 }
132 }
133
134 public int size() {
135 return mRecentMap.size();
136 }
137
138 public boolean isEmpty() {
139 return mRecentMap.isEmpty();
140 }
141
142 public boolean containsKey(Object key) {
143 return mRecentMap.containsKey(key);
144 }
145
146 public Object get(Object key) {
147 Entry e = (Entry)mRecentMap.get(key);
148 return (e == null) ? null : e.mValue;
149 }
150
151 public Object put(Object key, Object value) {
152 Entry e = (Entry)mRecentMap.get(key);
153 Object old;
154
155 if (e == null) {
156 old = null;
157 e = new Entry(key, value);
158 mRecentMap.put(key, e);
159 }
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 }
172 else {
173 e.mPrev.mNext = e.mNext;
174 }
175 if (e.mNext == null) {
176 mLeastRecent = e.mPrev;
177 }
178 else {
179 e.mNext.mPrev = e.mPrev;
180 }
181 e.mPrev = null;
182 }
183
184 if (mMostRecent == null) {
185 mMostRecent = e;
186 }
187 else {
188 e.mNext = mMostRecent;
189 mMostRecent.mPrev = e;
190 mMostRecent = e;
191 }
192
193 if (mLeastRecent == null) {
194 mLeastRecent = e;
195 }
196
197 return old;
198 }
199
200 public Object remove(Object key) {
201 Entry e = (Entry)mRecentMap.remove(key);
202
203 if (e == null) {
204 return null;
205 }
206 else {
207 // Delete entry from linked list.
208 if (e.mPrev == null) {
209 mMostRecent = e.mNext;
210 }
211 else {
212 e.mPrev.mNext = e.mNext;
213 }
214 if (e.mNext == null) {
215 mLeastRecent = e.mPrev;
216 }
217 else {
218 e.mNext.mPrev = e.mPrev;
219 }
220
221 return e.mValue;
222 }
223 }
224
225 public void putAll(Map map) {
226 Iterator it = map.entrySet().iterator();
227 while (it.hasNext()) {
228 Map.Entry entry = (Map.Entry)it.next();
229 mRecentMap.put(entry.getKey(), entry.getValue());
230 }
231 }
232
233 public void clear() {
234 mRecentMap.clear();
235 mMostRecent = null;
236 mLeastRecent = null;
237 }
238
239 public Set entrySet() {
240 if (mEntrySet != null) {
241 return mEntrySet;
242 }
243
244 mEntrySet = new AbstractSet() {
245 public Iterator iterator() {
246 if (mReverse) {
247 return new Iterator() {
248 private Entry mPrev = mLeastRecent;
249 private Entry mLast = null;
250
251 public boolean hasNext() {
252 return mPrev != null;
253 }
254
255 public Object next() {
256 if ((mLast = mPrev) == null) {
257 throw new NoSuchElementException();
258 }
259 else {
260 mPrev = mPrev.mPrev;
261 return mLast;
262 }
263 }
264
265 public void remove() {
266 if (mLast == null) {
267 throw new IllegalStateException();
268 }
269 else {
270 UsageMap.this.remove(mLast.mKey);
271 mLast = null;
272 }
273 }
274 };
275 }
276 else {
277 return new Iterator() {
278 private Entry mNext = mMostRecent;
279 private Entry mLast = null;
280
281 public boolean hasNext() {
282 return mNext != null;
283 }
284
285 public Object next() {
286 if ((mLast = mNext) == null) {
287 throw new NoSuchElementException();
288 }
289 else {
290 mNext = mNext.mNext;
291 return mLast;
292 }
293 }
294
295 public void remove() {
296 if (mLast == null) {
297 throw new IllegalStateException();
298 }
299 else {
300 UsageMap.this.remove(mLast.mKey);
301 mLast = null;
302 }
303 }
304 };
305 }
306 }
307
308 public int size() {
309 return mRecentMap.size();
310 }
311
312 public boolean isEmpty() {
313 return mRecentMap.isEmpty();
314 }
315
316 public boolean contains(Object obj) {
317 if (!(obj instanceof Map.Entry)) {
318 return false;
319 }
320 Entry e = (Entry)mRecentMap.get(((Map.Entry)obj).getKey());
321 return e != null && e.equals(obj);
322 }
323
324 public boolean remove(Object obj) {
325 if (!(obj instanceof Map.Entry)) {
326 return false;
327 }
328 if (contains(obj)) {
329 UsageMap.this.remove(((Map.Entry)obj).getKey());
330 return true;
331 }
332 else {
333 return false;
334 }
335 }
336
337 public void clear() {
338 UsageMap.this.clear();
339 }
340 };
341
342 return mEntrySet;
343 }
344
345 private static class Entry extends AbstractMapEntry
346 implements java.io.Serializable
347 {
348 public Entry mPrev;
349 public Entry mNext;
350 public Object mKey;
351 public Object mValue;
352
353 public Entry(Object key, Object value) {
354 mKey = key;
355 mValue = value;
356 }
357
358 public Object getKey() {
359 return mKey;
360 }
361
362 public Object getValue() {
363 return mValue;
364 }
365
366 public Object setValue(Object value) {
367 Object old = mValue;
368 mValue = value;
369 return old;
370 }
371 }
372 }