| WeakBumpyStack.java |
1 /*
2 * Copyright (c) 1998-2005, The University of Sheffield.
3 *
4 * This file is part of GATE (see http://gate.ac.uk/), and is free
5 * software, licenced under the GNU Library General Public License,
6 * Version 2, June 1991 (in the distribution as file licence.html,
7 * and also available at http://gate.ac.uk/gate/licence.html).
8 *
9 * Valentin Tablan, 10/Oct/2001
10 *
11 * $Id: WeakBumpyStack.java,v 1.7 2005/01/11 13:51:37 ian Exp $
12 */
13
14 ////////////////////////////////////////////////////////////////////
15 //////////// DEVELOPERS: SEE WARNING IN JAVADOC COMMENT FOR
16 //////////// THIS CLASS!!!!
17 ////////////////////////////////////////////////////////////////////
18
19 package gate.util;
20
21 import java.lang.ref.ReferenceQueue;
22 import java.lang.ref.WeakReference;
23 import java.util.*;
24
25 /**
26 * Weak stack that allow you to bump an element to the front.
27 * Objects that are only referenced by this stack will be candidates for
28 * garbage collection and wil be removed from the stack as soon as the garbage
29 * collector marks them for collection.
30 * <P>
31 * <B>*** WARNING: ***</B> the test for this class,
32 * <TT>TestBumpyStack.testSelfCleaning</TT> is not a proper test; it doesn't
33 * fail even when it should, and only prints a warning when DEBUG is true.
34 * This is because to test it properly you need to force garbage collection,
35 * and that isn't possible. So, if you work on this class <B>you must
36 * turn DEBUG on on TestBumpyStack</B> in order to run the tests in a
37 * meaningfull way.
38 */
39 public class WeakBumpyStack extends AbstractList
40 {
41
42 /**
43 * Creates a new empty stack.
44 */
45 public WeakBumpyStack(){
46 supportStack = new Stack();
47 refQueue = new ReferenceQueue();
48 }
49
50 /**
51 * Pushes an item onto the top of this stack. This has exactly
52 * the same effect as:
53 * <blockquote><pre>
54 * addElement(item)</pre></blockquote>
55 *
56 * @param item the item to be pushed onto this stack.
57 * @return the <code>item</code> argument.
58 */
59 public Object push(Object item){
60 supportStack.push(new WeakReference(item,refQueue));
61 return item;
62 }
63
64 /**
65 * Removes the object at the top of this stack and returns that
66 * object as the value of this function.
67 *
68 * @return The object at the top of this stack.
69 * @exception EmptyStackException if this stack is empty.
70 */
71 public synchronized Object pop(){
72 processQueue();
73 //we need to check for null in case the top reference has just been cleared
74 Object res = null;
75 while(res == null){
76 res = ((WeakReference)supportStack.pop()).get();
77 }
78 return res;
79 }
80
81
82 /**
83 * Looks at the object at the top of this stack without removing it
84 * from the stack.
85 *
86 * @return the object at the top of this stack.
87 * @exception EmptyStackException if this stack is empty.
88 */
89 public synchronized Object peek(){
90 processQueue();
91 //we need to check for null in case the top reference has just been cleared
92 Object res = null;
93 while(res == null){
94 res = ((WeakReference)supportStack.peek()).get();
95 }
96 return res;
97 }
98
99 /**
100 * Tests if this stack is empty.
101 *
102 * @return <code>true</code> if and only if this stack contains
103 * no items; <code>false</code> otherwise.
104 */
105 public boolean empty() {
106 processQueue();
107 return supportStack.empty();
108 }
109
110
111 /** Bump an item to the front of the stack.
112 * @param item the item to bump
113 * @return true when the item was found, else false
114 */
115 public boolean bump(Object item) {
116 processQueue();
117
118 int itemIndex = search(item);
119
120 if(itemIndex == -1) // not a member of the stack
121 return false;
122 else if(itemIndex == 1) // at the front already
123 return true;
124
125 WeakReference wr = (WeakReference)supportStack.remove(itemIndex - 1);
126 supportStack.push(wr);
127 return true;
128 } // bump
129
130 /**
131 * Returns the 1-based position where an object is on this stack.
132 * If the object <tt>o</tt> occurs as an item in this stack, this
133 * method returns the distance from the top of the stack of the
134 * occurrence nearest the top of the stack; the topmost item on the
135 * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
136 * method is used to compare <tt>o</tt> to the
137 * items in this stack.
138 *
139 * @param o the desired object.
140 * @return the 1-based position from the top of the stack where
141 * the object is located; the return value <code>-1</code>
142 * indicates that the object is not on the stack.
143 */
144 public synchronized int search(Object o) {
145 processQueue();
146 int i = supportStack.size() - 1;
147 while(i >= 0 &&
148 !((WeakReference)supportStack.get(i)).get().equals(o)) i--;
149 if (i >= 0) {
150 return supportStack.size() - i;
151 }
152 return -1;
153 }
154
155
156 /**
157 * Checks the queue for any new weak references that have been cleared and
158 * queued and removes them from the underlying stack.
159 *
160 * This method should be called by every public method before realising its
161 * internal logic.
162 */
163 protected void processQueue(){
164 WeakReference wr;
165 while ((wr = (WeakReference)refQueue.poll()) != null) {
166 supportStack.remove(wr);
167 }
168 }
169
170 /**
171 * Returns the element at the specified position in this list.
172 *
173 * @param index index of element to return.
174 * @return the element at the specified position in this list.
175 * @throws IndexOutOfBoundsException if index is out of range <tt>(index
176 * < 0 || index >= size())</tt>.
177 */
178 public Object get(int index) {
179 processQueue();
180 //we need to check for null in case the top reference has just been cleared
181 Object res = null;
182 while(res == null){
183 res = ((WeakReference)supportStack.get(index)).get();
184 }
185 return res;
186 }
187
188 /**
189 * Returns the number of elements in this list.
190 *
191 * @return the number of elements in this list.
192 */
193 public int size() {
194 processQueue();
195 return supportStack.size();
196 }
197
198 /**
199 * Replaces the element at the specified position in this list with
200 * the specified element.
201 *
202 * @param index index of element to replace.
203 * @param element element to be stored at the specified position.
204 * @return the element previously at the specified position.
205 * @throws IndexOutOfBoundsException if index out of range
206 * <tt>(index < 0 || index >= size())</tt>.
207 */
208 public Object set(int index, Object element) {
209 processQueue();
210 WeakReference ref = (WeakReference)
211 supportStack.set(index,
212 new WeakReference(element, refQueue));
213 return ref.get();
214 }
215
216 /**
217 * Inserts the specified element at the specified position in this
218 * list. Shifts the element currently at that position (if any) and
219 * any subsequent elements to the right (adds one to their indices).
220 *
221 * @param index index at which the specified element is to be inserted.
222 * @param element element to be inserted.
223 * @throws IndexOutOfBoundsException if index is out of range
224 * <tt>(index < 0 || index > size())</tt>.
225 */
226 public void add(int index, Object element) {
227 processQueue();
228 supportStack.add(index, new WeakReference(element, refQueue));
229 }
230
231 /**
232 * Removes the element at the specified position in this list.
233 * Shifts any subsequent elements to the left (subtracts one from their
234 * indices).
235 *
236 * @param index the index of the element to removed.
237 * @return the element that was removed from the list.
238 * @throws IndexOutOfBoundsException if index out of range <tt>(index
239 * < 0 || index >= size())</tt>.
240 */
241 public Object remove(int index) {
242 processQueue();
243 //we need to check for null in case the top reference has just been cleared
244 Object res = null;
245 while(res == null){
246 res = ((WeakReference)supportStack.remove(index)).get();
247 }
248 return res;
249 }
250
251 ReferenceQueue refQueue;
252
253 /**
254 * This is the underlying stack object for this weak stack. It holds weak
255 * references to the objects that are the actual contents of this stack.
256 */
257 Stack supportStack;
258 } // class BumpyStack
259