View Javadoc

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     // Positional Access Operations
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     // Search Operations
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         // Put clone into "virgin" state
292         clone.header = new DefaultQueueListEntry(null, null, null);
293         clone.header.next = clone.header.previous = clone.header;
294         clone.size = 0;
295         // Initialize clone with our elements
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 }