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.1 $
    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 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 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 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 }