Mercurial > hg > blitz_stable
comparison 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 |
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 } |