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 }