Source code: com/eireneh/util/RobustList.java
1
2 package com.eireneh.util;
3
4 import java.io.*;
5 import java.util.*;
6
7 /**
8 * This is a version of LinkedList that is not fail-fast
9 *
10 * <table border='1' cellPadding='3' cellSpacing='0' width="100%">
11 * <tr><td bgColor='white'class='TableRowColor'><font size='-7'>
12 * Distribution Licence:<br />
13 * Project B is free software; you can redistribute it
14 * and/or modify it under the terms of the GNU General Public License,
15 * version 2 as published by the Free Software Foundation.<br />
16 * This program is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * General Public License for more details.<br />
20 * The License is available on the internet
21 * <a href='http://www.gnu.org/copyleft/gpl.html'>here</a>, by writing to
22 * <i>Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
23 * MA 02111-1307, USA</i>, Or locally at the Licence link below.<br />
24 * The copyright to this program is held by it's authors.
25 * </font></td></tr></table>
26 * @see <a href='http://www.eireneh.com/servlets/Web'>Project B Home</a>
27 * @see docs.Licence
28 * @author Joe Walker
29 */
30 public class RobustList implements Serializable
31 {
32 Entry head = null;
33 Entry foot = null;
34 int size = 0;
35 Object sync = new Object();
36
37 void debug(String title)
38 {
39 log.fine(title);
40 log.fine(" head ="+head);
41 log.fine(" foot ="+foot);
42 int i = 0;
43 Entry e = head;
44 while (e != null)
45 {
46 log.fine(" index="+i);
47 e.debug();
48 e = e.next;
49 i++;
50 }
51 }
52
53 /**
54 * Does this list contains the specified element?
55 * @param o element whose presence in this list is to be tested.
56 * @return true if this list contains the specified element.
57 */
58 public boolean contains(Object o)
59 {
60 return indexOf(o) != -1;
61 }
62
63 /**
64 * Returns the number of elements in this list.
65 * @return the number of elements in this list.
66 */
67 public int size()
68 {
69 return size;
70 }
71
72 /**
73 * Appends the specified element to the end of this list.
74 * @param o element to be appended to this list.
75 */
76 public void addElement(Object o)
77 {
78 // debug("pre-add "+o);
79 new Entry(o);
80 // debug("post-add "+o);
81 }
82
83 /**
84 * Removes the element at the specified position in this list. Shifts any
85 * subsequent elements to the left (subtracts one from their indices).
86 * Returns the element that was removed from the list.
87 * @param index the index of the element to removed.
88 * @return the element previously at the specified position.
89 */
90 public void removeElement(int index)
91 {
92 debug("pre-remove "+index);
93 Entry e = findEntry(index);
94 e.remove();
95 debug("post-remove "+index);
96 }
97
98 /**
99 * Removes the first occurrence of the specified element in this list. If
100 * the list does not contain the element, it is unchanged.
101 * @param o element to be removed from this list, if present.
102 * @return true if the list contained the specified element.
103 */
104 public boolean removeElement(Object o)
105 {
106 // debug("pre-remove "+o);
107 if (o == null)
108 {
109 Entry e = head;
110 while (e != null)
111 {
112 if (e.object == null)
113 {
114 e.remove();
115 // debug("post-remove "+o);
116 return true;
117 }
118
119 e = e.next;
120 }
121 }
122 else
123 {
124 Entry e = head;
125 while (e != null)
126 {
127 if (o.equals(e.object))
128 {
129 e.remove();
130 // debug("post-remove "+o);
131 return true;
132 }
133
134 e = e.next;
135 }
136 }
137
138 // debug("post-remove fail "+o);
139 return false;
140 }
141
142 /**
143 * Removes all of the elements from this list.
144 */
145 public void clear()
146 {
147 debug("pre-clear");
148 head = foot = null;
149 size = 0;
150 debug("post-clear");
151 }
152
153 /**
154 * Returns the element at the specified position in this list.
155 * @param index index of element to return.
156 * @return the element at the specified position in this list.
157 */
158 public Object elementAt(int index)
159 {
160 return findEntry(index).object;
161 }
162
163 /**
164 * Return the indexed entry.
165 */
166 private Entry findEntry(int index)
167 {
168 if (index < 0 || index >= size)
169 throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
170
171 Entry e;
172 if (index < size/2)
173 {
174 e = head;
175 for (int i=0; i!=index; i++)
176 e = e.next;
177 }
178 else
179 {
180 e = foot;
181 for (int i=size-1; i!=index; i--)
182 e = e.prev;
183 }
184
185 return e;
186 }
187
188 /**
189 * Returns the index in this list of the first occurrence of the
190 * specified element, or -1 if the List does not contain this element.
191 * @param o element to search for.
192 * @return the index of the first occurrence or -1
193 */
194 public int indexOf(Object o)
195 {
196 int index = 0;
197 if (o == null)
198 {
199 Entry e = head;
200 while (e != null)
201 {
202 if (e.object == null)
203 return index;
204
205 e = e.next;
206 index++;
207 }
208 }
209 else
210 {
211 Entry e = head;
212 while (e != null)
213 {
214 if (o.equals(e.object))
215 return index;
216
217 e = e.next;
218 index++;
219 }
220 }
221
222 return -1;
223 }
224
225 /**
226 * Returns a list-iterator of the elements in this list
227 * @return a ListIterator of the elements in this list
228 */
229 public Enumeration elements()
230 {
231 // debug("pre-enumerate");
232 return new RobustListEnumeration();
233 }
234
235 private class RobustListEnumeration implements Enumeration
236 {
237 private Entry next;
238
239 RobustListEnumeration()
240 {
241 next = head;
242 }
243
244 public boolean hasMoreElements()
245 {
246 return next != null;
247 }
248
249 public Object nextElement()
250 {
251 // next.debug();
252 Object retcode = next.object;
253 next = next.next;
254 return retcode;
255 }
256 }
257
258 private class Entry
259 {
260 Object object;
261 Entry next;
262 Entry prev;
263
264 Entry(Object object)
265 {
266 this.object = object;
267 this.next = null;
268 this.prev = foot;
269
270 if (head == null)
271 head = this;
272
273 if (foot != null)
274 foot.next = this;
275 foot = this;
276
277 size++;
278 }
279
280 void remove()
281 {
282 if (this == foot)
283 {
284 if (prev != null)
285 prev.next = null;
286
287 foot = prev;
288 }
289
290 if (this == head)
291 {
292 if (next != null)
293 next.prev = null;
294
295 head = next;
296 }
297
298 if (prev != null)
299 prev.next = next;
300
301 if (next != null)
302 next.prev = prev;
303
304 size--;
305 }
306
307 void debug()
308 {
309 log.fine(" prev="+prev);
310 log.fine(" this="+this);
311 log.fine(" next="+next);
312 log.fine(" obje="+object);
313 }
314 }
315
316 /** The log stream */
317 protected static Logger log = Logger.getLogger("util.util");
318 }