Source code: org/activemq/service/impl/DefaultQueueList.java
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.activemq.service.impl;
19
20 import java.io.Serializable;
21 import java.util.Collection;
22 import java.util.Iterator;
23
24 import org.activemq.service.QueueList;
25 import org.activemq.service.QueueListEntry;
26
27 /**
28 * Linked list class to provide uniformly named methods to <tt>get</tt>,<tt>remove</tt> and <tt>insert</tt> an
29 * element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or
30 * double-ended queue (dequeue).
31 * <p/>
32 *
33 * @version $Revision: 1.1.1.1 $
34 */
35 public final class DefaultQueueList implements QueueList, Cloneable, Serializable {
36 /**
37 *
38 */
39 private static final long serialVersionUID = 664118850296696821L;
40 private transient DefaultQueueListEntry header = new DefaultQueueListEntry(null, null, null);
41 private transient int size = 0;
42
43 /**
44 * Constructs an empty list.
45 */
46 public DefaultQueueList() {
47 header.next = header.previous = header;
48 }
49
50 /**
51 * @return the first object from the list or null
52 */
53
54 public synchronized Object getFirst() {
55 if (size == 0) {
56 return null;
57 }
58 return header.next.element;
59 }
60
61 /**
62 * @return the last object from the list
63 */
64
65 public synchronized Object getLast() {
66 if (size == 0) {
67 return null;
68 }
69 return header.previous.element;
70 }
71
72 /**
73 * remove the first object from the list
74 */
75
76 public synchronized Object removeFirst() {
77 if (size == 0) {
78 return null;
79 }
80 Object first = header.next.element;
81 remove(header.next);
82 return first;
83 }
84
85 /**
86 * move the first object to the back of the list
87 */
88
89 public synchronized void rotate() {
90 if (size > 1) {
91 Object obj = removeFirst();
92 if (obj != null) {
93 addLast(obj);
94 }
95 }
96 }
97
98 /**
99 * remove the last object
100 */
101 public synchronized Object removeLast() {
102 if (size == 0) {
103 return null;
104 }
105 Object last = header.previous.element;
106 remove(header.previous);
107 return last;
108 }
109
110
111 public synchronized QueueListEntry addAllFirst(Collection c) {
112 return addAllBefore(c, header.next);
113 }
114
115 public synchronized QueueListEntry addFirst(Object o) {
116 return addBefore(o, header.next);
117 }
118
119 public synchronized QueueListEntry addLast(Object o) {
120 return addBefore(o, header);
121 }
122
123 public synchronized boolean contains(Object o) {
124 return indexOf(o) != -1;
125 }
126
127 public synchronized int size() {
128 return size;
129 }
130
131 public synchronized boolean isEmpty() {
132 return size == 0;
133 }
134
135 public synchronized QueueListEntry add(Object o) {
136 return addBefore(o, header);
137 }
138
139 public synchronized boolean remove(Object o) {
140 if (o == null) {
141 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
142 if (e.element == null) {
143 remove(e);
144 return true;
145 }
146 }
147 }
148 else {
149 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
150 if (o.equals(e.element)) {
151 remove(e);
152 return true;
153 }
154 }
155 }
156 return false;
157 }
158
159 public synchronized void clear() {
160 header.next = header.previous = header;
161 size = 0;
162 }
163
164 // Positional Access Operations
165 public synchronized Object get(int index) {
166 return entry(index).element;
167 }
168
169 /**
170 * get the object from the queue
171 * @param obj
172 * @return
173 */
174 public synchronized Object get(Object obj){
175 int index = indexOf(obj);
176 if (index >= 0){
177 return get(index);
178 }
179 return null;
180 }
181
182 public synchronized Object set(int index, Object element) {
183 DefaultQueueListEntry e = entry(index);
184 Object oldVal = e.element;
185 e.element = element;
186 return oldVal;
187 }
188
189 public synchronized void add(int index, Object element) {
190 addBefore(element, (index == size ? header : entry(index)));
191 }
192
193 public synchronized Object remove(int index) {
194 DefaultQueueListEntry e = entry(index);
195 remove(e);
196 return e.element;
197 }
198
199 public synchronized DefaultQueueListEntry entry(int index) {
200 if (index < 0 || index >= size) {
201 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
202 }
203 DefaultQueueListEntry e = header;
204 if (index < size / 2) {
205 for (int i = 0; i <= index; i++) {
206 e = e.next;
207 }
208 }
209 else {
210 for (int i = size; i > index; i--) {
211 e = e.previous;
212 }
213 }
214 return e;
215 }
216
217 // Search Operations
218 public synchronized int indexOf(Object o) {
219 int index = 0;
220 if (o == null) {
221 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
222 if (e.element == null) {
223 return index;
224 }
225 index++;
226 }
227 }
228 else {
229 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
230 if (o.equals(e.element)) {
231 return index;
232 }
233 index++;
234 }
235 }
236 return -1;
237 }
238
239 public synchronized int lastIndexOf(Object o) {
240 int index = size;
241 if (o == null) {
242 for (DefaultQueueListEntry e = header.previous; e != header; e = e.previous) {
243 index--;
244 if (e.element == null) {
245 return index;
246 }
247 }
248 }
249 else {
250 for (DefaultQueueListEntry e = header.previous; e != header; e = e.previous) {
251 index--;
252 if (o.equals(e.element)) {
253 return index;
254 }
255 }
256 }
257 return -1;
258 }
259
260 public synchronized QueueListEntry getFirstEntry() {
261 DefaultQueueListEntry result = header.next;
262 return result != header ? result : null;
263 }
264
265 public synchronized QueueListEntry getLastEntry() {
266 DefaultQueueListEntry result = header.previous;
267 return result != header ? result : null;
268 }
269
270 public QueueListEntry getNextEntry(QueueListEntry node) {
271 DefaultQueueListEntry entry = (DefaultQueueListEntry) node;
272 if (entry == null) {
273 return null;
274 }
275 DefaultQueueListEntry result = entry.next;
276 return (result != entry && result != header) ? result : null;
277 }
278
279 public QueueListEntry getPrevEntry(QueueListEntry node) {
280 DefaultQueueListEntry entry = (DefaultQueueListEntry) node;
281 if (entry == null) {
282 return null;
283 }
284 DefaultQueueListEntry result = entry.previous;
285 return (result != entry && result != header) ? result : null;
286 }
287
288 public synchronized QueueListEntry addBefore(Object o, QueueListEntry node) {
289 DefaultQueueListEntry e = (DefaultQueueListEntry) node;
290 DefaultQueueListEntry newLinkedListEntry = new DefaultQueueListEntry(o, e, e.previous);
291 newLinkedListEntry.previous.next = newLinkedListEntry;
292 newLinkedListEntry.next.previous = newLinkedListEntry;
293 size++;
294 return newLinkedListEntry;
295 }
296
297 public synchronized QueueListEntry addAllBefore(Collection c, QueueListEntry node) {
298
299 // Nothing to insert?
300 if( c.size() < 1 )
301 return node;
302
303 // Link together the items in the array
304 DefaultQueueListEntry e = (DefaultQueueListEntry) node;
305 DefaultQueueListEntry newLinkedListEntry[] = new DefaultQueueListEntry[c.size()];
306 Iterator iterator = c.iterator();
307 for( int i=0; i < newLinkedListEntry.length; i++) {
308 // Create and link to the previous.
309 newLinkedListEntry[i] = new DefaultQueueListEntry(iterator.next(), e, i==0 ? e.previous : newLinkedListEntry[i-1] );
310 }
311 for( int i=0; i < newLinkedListEntry.length-1; i++) {
312 // Link to the next.
313 newLinkedListEntry[i].next = newLinkedListEntry[i+1];
314 }
315
316 // Now link those items into the rest of the list.
317 synchronized (this) {
318 newLinkedListEntry[0].previous.next = newLinkedListEntry[0];
319 newLinkedListEntry[newLinkedListEntry.length-1].next.previous = newLinkedListEntry[newLinkedListEntry.length-1];
320 size+=newLinkedListEntry.length;
321 }
322 return newLinkedListEntry[0];
323 }
324
325 public synchronized void remove(QueueListEntry node) {
326 DefaultQueueListEntry e = (DefaultQueueListEntry) node;
327 if (e == header) {
328 return;
329 }
330 e.previous.next = e.next;
331 e.next.previous = e.previous;
332 size--;
333 }
334
335 /**
336 * Returns a shallow copy of this <tt>DefaultQueueList</tt>. (The elements themselves are not cloned.)
337 *
338 * @return a shallow copy of this <tt>DefaultQueueList</tt> instance.
339 */
340 public synchronized Object clone() {
341 DefaultQueueList clone = new DefaultQueueList();
342 // Put clone into "virgin" state
343 clone.header = new DefaultQueueListEntry(null, null, null);
344 clone.header.next = clone.header.previous = clone.header;
345 clone.size = 0;
346 // Initialize clone with our elements
347 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
348 clone.add(e.element);
349 }
350 return clone;
351 }
352
353 public synchronized Object[] toArray() {
354 Object[] result = new Object[size];
355 int i = 0;
356 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
357 result[i++] = e.element;
358 }
359 return result;
360 }
361
362 /**
363 * @return pretty print
364 */
365 public synchronized String toString(){
366 String result = super.toString();
367 result += ":";
368 for (DefaultQueueListEntry e = header.next; e != header; e = e.next) {
369 result += e.element;
370 if (e != header){
371 result += ",";
372 }
373 }
374 return result;
375 }
376 }