1 /***
2 *
3 * Copyright 2004 Protique Ltd
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 *
17 **/
18 package org.codehaus.activemq.service.impl;
19
20 import org.codehaus.activemq.service.QueueList;
21 import org.codehaus.activemq.service.QueueListEntry;
22
23 import java.io.Serializable;
24
25 /***
26 * Linked list class to provide uniformly named methods to <tt>get</tt>,<tt>remove</tt> and <tt>insert</tt> an
27 * element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or
28 * double-ended queue (deque).
29 * <p/>
30 *
31 * @version $Revision: 1.2 $
32 */
33 public final class DefaultQueueList implements QueueList, Cloneable, Serializable {
34 private transient DefaultQueueListEntry header = new DefaultQueueListEntry(null, null, null);
35 private transient int size = 0;
36
37 /***
38 * Constructs an empty list.
39 */
40 public DefaultQueueList() {
41 header.next = header.previous = header;
42 }
43
44 /***
45 * @return the first object from the list or null
46 */
47
48 public synchronized Object getFirst() {
49 if (size == 0) {
50 return null;
51 }
52 return header.next.element;
53 }
54
55 /***
56 * @return the last object from the list
57 */
58
59 public synchronized Object getLast() {
60 if (size == 0) {
61 return null;
62 }
63 return header.previous.element;
64 }
65
66 /***
67 * remove the first object from the list
68 */
69
70 public synchronized Object removeFirst() {
71 if (size == 0) {
72 return null;
73 }
74 Object first = header.next.element;
75 remove(header.next);
76 return first;
77 }
78
79 /***
80 * move the first object to the back of the list
81 */
82
83 public synchronized void rotate() {
84 if (size > 1) {
85 Object obj = removeFirst();
86 if (obj != null) {
87 addLast(obj);
88 }
89 }
90 }
91
92 /***
93 * remove the last object
94 */
95 public synchronized Object removeLast() {
96 if (size == 0) {
97 return null;
98 }
99 Object last = header.previous.element;
100 remove(header.previous);
101 return last;
102 }
103
104
105 public synchronized QueueListEntry addFirst(Object o) {
106 return addBefore(o, header.next);
107 }
108
109 public synchronized QueueListEntry addLast(Object o) {
110 return addBefore(o, header);
111 }
112
113 public synchronized boolean contains(Object o) {
114 return indexOf(o) != -1;
115 }
116
117 public synchronized int size() {
118 return size;
119 }
120
121 public synchronized boolean isEmpty() {
122 return size == 0;
123 }
124
125 public synchronized QueueListEntry add(Object o) {
126 return addBefore(o, header);
127 }
128
129 public synchronized boolean remove(Object o) {
130 if (o == null) {
131 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
132 if (e.element == null) {
133 remove(e);
134 return true;
135 }
136 }
137 }
138 else {
139 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
140 if (o.equals(e.element)) {
141 remove(e);
142 return true;
143 }
144 }
145 }
146 return false;
147 }
148
149 public synchronized void clear() {
150 header.next = header.previous = header;
151 size = 0;
152 }
153
154
155 public synchronized Object get(int index) {
156 return entry(index).element;
157 }
158
159 public synchronized Object set(int index, Object element) {
160 DefaultQueueListEntry e = entry(index);
161 Object oldVal = e.element;
162 e.element = element;
163 return oldVal;
164 }
165
166 public synchronized void add(int index, Object element) {
167 addBefore(element, (index == size ? header : entry(index)));
168 }
169
170 public synchronized Object remove(int index) {
171 DefaultQueueListEntry e = entry(index);
172 remove(e);
173 return e.element;
174 }
175
176 public synchronized DefaultQueueListEntry entry(int index) {
177 if (index < 0 || index >= size) {
178 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
179 }
180 DefaultQueueListEntry e = header;
181 if (index < size / 2) {
182 for (int i = 0; i <= index; i++) {
183 e = e.next;
184 }
185 }
186 else {
187 for (int i = size; i > index; i--) {
188 e = e.previous;
189 }
190 }
191 return e;
192 }
193
194
195 public synchronized int indexOf(Object o) {
196 int index = 0;
197 if (o == null) {
198 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
199 if (e.element == null) {
200 return index;
201 }
202 index++;
203 }
204 }
205 else {
206 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
207 if (o.equals(e.element)) {
208 return index;
209 }
210 index++;
211 }
212 }
213 return -1;
214 }
215
216 public synchronized int lastIndexOf(Object o) {
217 int index = size;
218 if (o == null) {
219 for (DefaultQueueListEntry e = header.previous; e != header; e = e.previous) {
220 index--;
221 if (e.element == null) {
222 return index;
223 }
224 }
225 }
226 else {
227 for (DefaultQueueListEntry e = header.previous; e != header; e = e.previous) {
228 index--;
229 if (o.equals(e.element)) {
230 return index;
231 }
232 }
233 }
234 return -1;
235 }
236
237 public synchronized QueueListEntry getFirstEntry() {
238 DefaultQueueListEntry result = header.next;
239 return result != header ? result : null;
240 }
241
242 public synchronized QueueListEntry getLastEntry() {
243 DefaultQueueListEntry result = header.previous;
244 return result != header ? result : null;
245 }
246
247 public QueueListEntry getNextEntry(QueueListEntry node) {
248 DefaultQueueListEntry entry = (DefaultQueueListEntry) node;
249 if (entry == null) {
250 return null;
251 }
252 DefaultQueueListEntry result = entry.next;
253 return (result != entry && result != header) ? result : null;
254 }
255
256 public QueueListEntry getPrevEntry(QueueListEntry node) {
257 DefaultQueueListEntry entry = (DefaultQueueListEntry) node;
258 if (entry == null) {
259 return null;
260 }
261 DefaultQueueListEntry result = entry.previous;
262 return (result != entry && result != header) ? result : null;
263 }
264
265 public synchronized QueueListEntry addBefore(Object o, QueueListEntry node) {
266 DefaultQueueListEntry e = (DefaultQueueListEntry) node;
267 DefaultQueueListEntry newLinkedListEntry = new DefaultQueueListEntry(o, e, e.previous);
268 newLinkedListEntry.previous.next = newLinkedListEntry;
269 newLinkedListEntry.next.previous = newLinkedListEntry;
270 size++;
271 return newLinkedListEntry;
272 }
273
274 public synchronized void remove(QueueListEntry node) {
275 DefaultQueueListEntry e = (DefaultQueueListEntry) node;
276 if (e == header) {
277 return;
278 }
279 e.previous.next = e.next;
280 e.next.previous = e.previous;
281 size--;
282 }
283
284 /***
285 * Returns a shallow copy of this <tt>DefaultQueueList</tt>. (The elements themselves are not cloned.)
286 *
287 * @return a shallow copy of this <tt>DefaultQueueList</tt> instance.
288 */
289 public synchronized Object clone() {
290 DefaultQueueList clone = new DefaultQueueList();
291
292 clone.header = new DefaultQueueListEntry(null, null, null);
293 clone.header.next = clone.header.previous = clone.header;
294 clone.size = 0;
295
296 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
297 clone.add(e.element);
298 }
299 return clone;
300 }
301
302 public synchronized Object[] toArray() {
303 Object[] result = new Object[size];
304 int i = 0;
305 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
306 result[i++] = e.element;
307 }
308 return result;
309 }
310 }