Queue


1   /*******************************************************************************
2    * Copyright (c) 2003, 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    *
8    * Contributors:
9    *     IBM - Initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.core.internal.jobs;
12  
13  import java.util.*;
14  
15  /**
16   * A Queue of objects.
17   */
18  public class Queue {
19      protected Object  [] elements;
20      protected int head;
21      protected boolean reuse;
22      protected int tail;
23  
24      public Queue() {
25          this(20, false);
26      }
27  
28      /**
29       * The parameter reuse indicates what do you want to happen with
30       * the object reference when you remove it from the queue. If
31       * reuse is false the queue no longer holds a reference to the
32       * object when it is removed. If reuse is true you can use the
33       * method getNextAvailableObject to get an used object, set its
34       * new values and add it again to the queue.
35       */
36      public Queue(int size, boolean reuse) {
37          elements = new Object  [size];
38          head = tail = 0;
39          this.reuse = reuse;
40      }
41  
42      /**
43       * Adds an object to the tail of the queue.
44       */
45      public void enqueue(Object   element) {
46          int newTail = increment(tail);
47          if (newTail == head) {
48              grow();
49              newTail = tail + 1;
50          }
51          elements[tail] = element;
52          tail = newTail;
53      }
54  
55      /**
56       * This method does not affect the queue itself. It is only a
57       * helper to decrement an index in the queue.
58       */
59      public int decrement(int index) {
60          return (index == 0) ? (elements.length - 1) : index - 1;
61      }
62  
63      public Iterator elements() {
64          /**/
65          if (isEmpty())
66              return new ArrayList(0).iterator();
67  
68          /* if head < tail we can use the same array */
69          if (head <= tail)
70              return Arrays.asList(elements).iterator();
71  
72          /* otherwise we need to create a new array */
73          Object  [] newElements = new Object  [size()];
74          int end = (elements.length - head);
75          System.arraycopy(elements, head, newElements, 0, end);
76          System.arraycopy(elements, 0, newElements, end, tail);
77          return Arrays.asList(newElements).iterator();
78      }
79  
80      public Object   get(Object   o) {
81          int index = head;
82          while (index != tail) {
83              if (elements[index].equals(o))
84                  return elements[index];
85              index = increment(index);
86          }
87          return null;
88      }
89  
90      /**
91       * Removes the given object from the queue. Shifts the underlying array.
92       */
93      public boolean remove(Object   o) {
94          int index = head;
95          //find the object to remove
96          while (index != tail) {
97              if (elements[index].equals(o))
98                  break;
99              index = increment(index);
100         }
101         //if element wasn't found, return
102         if (index == tail)
103             return false;
104         //store a reference to it (needed for reuse of objects)
105         Object   toRemove = elements[index];
106         int nextIndex = -1;
107         while (index != tail) {
108             nextIndex = increment(index);
109             if (nextIndex != tail)
110                 elements[index] = elements[nextIndex];
111 
112             index = nextIndex;
113         }
114         //decrement tail
115         tail = decrement(tail);
116 
117         //if objects are reused, transfer the reference that is removed to the end of the queue
118         //otherwise set the element after the last one to null (to avoid duplicate references)
119         elements[tail] = reuse ? toRemove : null;
120         return true;
121     }
122 
123     protected void grow() {
124         int newSize = (int) (elements.length * 1.5);
125         Object  [] newElements = new Object  [newSize];
126         if (tail >= head)
127             System.arraycopy(elements, head, newElements, head, size());
128         else {
129             int newHead = newSize - (elements.length - head);
130             System.arraycopy(elements, 0, newElements, 0, tail + 1);
131             System.arraycopy(elements, head, newElements, newHead, (newSize - newHead));
132             head = newHead;
133         }
134         elements = newElements;
135     }
136 
137     /**
138      * This method does not affect the queue itself. It is only a
139      * helper to increment an index in the queue.
140      */
141     public int increment(int index) {
142         return (index == (elements.length - 1)) ? 0 : index + 1;
143     }
144 
145     public boolean isEmpty() {
146         return tail == head;
147     }
148 
149     public Object   peek() {
150         return elements[head];
151     }
152 
153     /**
154      * Removes an returns the item at the head of the queue.
155      */
156     public Object   dequeue() {
157         if (isEmpty())
158             return null;
159         Object   result = peek();
160         if (!reuse)
161             elements[head] = null;
162         head = increment(head);
163         return result;
164     }
165 
166     public int size() {
167         return tail > head ? (tail - head) : ((elements.length - head) + tail);
168     }
169 
170     public String   toString() {
171         StringBuffer   sb = new StringBuffer  ();
172         sb.append("["); //$NON-NLS-1$
173         if (!isEmpty()) {
174             Iterator it = elements();
175             while (true) {
176                 sb.append(it.next());
177                 if (it.hasNext())
178                     sb.append(", "); //$NON-NLS-1$
179                 else
180                     break;
181             }
182         }
183         sb.append("]"); //$NON-NLS-1$
184         return sb.toString();
185     }
186 }
187
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags