001    /** 
002     * 
003     * Copyright 2004 Protique Ltd
004     * 
005     * Licensed under the Apache License, Version 2.0 (the "License"); 
006     * you may not use this file except in compliance with the License. 
007     * You may obtain a copy of the License at 
008     * 
009     * http://www.apache.org/licenses/LICENSE-2.0
010     * 
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS, 
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
014     * See the License for the specific language governing permissions and 
015     * limitations under the License. 
016     * 
017     **/
018    package org.activemq.service.impl;
019    
020    import java.io.Serializable;
021    import java.util.Collection;
022    import java.util.Iterator;
023    
024    import org.activemq.service.QueueList;
025    import org.activemq.service.QueueListEntry;
026    
027    /**
028     * Linked list class to provide uniformly named methods to <tt>get</tt>,<tt>remove</tt> and <tt>insert</tt> an
029     * element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or
030     * double-ended queue (dequeue).
031     * <p/>
032     *
033     * @version $Revision: 1.1.1.1 $
034     */
035    public final class DefaultQueueList implements QueueList, Cloneable, Serializable {
036        /**
037         * 
038         */
039        private static final long serialVersionUID = 664118850296696821L;
040        private transient DefaultQueueListEntry header = new DefaultQueueListEntry(null, null, null);
041        private transient int size = 0;
042    
043        /**
044         * Constructs an empty list.
045         */
046        public DefaultQueueList() {
047            header.next = header.previous = header;
048        }
049    
050        /**
051         * @return the first object from the list or null
052         */
053    
054        public synchronized Object getFirst() {
055            if (size == 0) {
056                return null;
057            }
058            return header.next.element;
059        }
060    
061        /**
062         * @return the last object from the list
063         */
064    
065        public synchronized Object getLast() {
066            if (size == 0) {
067                return null;
068            }
069            return header.previous.element;
070        }
071    
072        /**
073         * remove the first object from the list
074         */
075    
076        public synchronized Object removeFirst() {
077            if (size == 0) {
078                return null;
079            }
080            Object first = header.next.element;
081            remove(header.next);
082            return first;
083        }
084    
085        /**
086         * move the first object to the back of the list
087         */
088    
089        public synchronized void rotate() {
090            if (size > 1) {
091                Object obj = removeFirst();
092                if (obj != null) {
093                    addLast(obj);
094                }
095            }
096        }
097    
098        /**
099         * 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    }