KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > go > trove > util > UsageMap


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 JavaDoc {
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 JavaDoc 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 JavaDoc 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 JavaDoc key) {
143         return mRecentMap.containsKey(key);
144     }
145
146     public Object JavaDoc get(Object JavaDoc key) {
147         Entry e = (Entry)mRecentMap.get(key);
148         return (e == null) ? null : e.mValue;
149     }
150
151     public Object JavaDoc put(Object JavaDoc key, Object JavaDoc value) {
152         Entry e = (Entry)mRecentMap.get(key);
153         Object JavaDoc 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 JavaDoc remove(Object JavaDoc 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 JavaDoc 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 JavaDoc();
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 JavaDoc 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 JavaDoc();
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 JavaDoc 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 JavaDoc 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 JavaDoc
347     {
348         public Entry mPrev;
349         public Entry mNext;
350         public Object JavaDoc mKey;
351         public Object JavaDoc mValue;
352
353         public Entry(Object JavaDoc key, Object JavaDoc value) {
354             mKey = key;
355             mValue = value;
356         }
357
358         public Object JavaDoc getKey() {
359             return mKey;
360         }
361
362         public Object JavaDoc getValue() {
363             return mValue;
364         }
365
366         public Object JavaDoc setValue(Object JavaDoc value) {
367             Object JavaDoc old = mValue;
368             mValue = value;
369             return old;
370         }
371     }
372 }
373
Popular Tags