Queue


1   /*******************************************************************************
2    * Copyright (c) 2000, 2005 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 Corporation - initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.core.internal.utils;
12  
13  import java.util.Collections  ;
14  import java.util.Iterator  ;
15  
16  /**
17   * A Queue of objects.
18   */
19  public class Queue {
20      protected Object  [] elements;
21      protected int head;
22      protected int tail;
23      protected boolean reuse;
24  
25      public Queue() {
26          this(20, false);
27      }
28  
29      /**
30       * The parameter reuse indicates what do you want to happen with
31       * the object reference when you remove it from the queue. If
32       * reuse is false the queue no longer holds a reference to the
33       * object when it is removed. If reuse is true you can use the
34       * method getNextAvailableObject to get an used object, set its
35       * new values and add it again to the queue.
36       */
37      public Queue(int size, boolean reuse) {
38          elements = new Object  [size];
39          head = tail = 0;
40          this.reuse = reuse;
41      }
42  
43      public void add(Object   element) {
44          int newTail = increment(tail);
45          if (newTail == head) {
46              grow();
47              newTail = tail + 1;
48          }
49          elements[tail] = element;
50          tail = newTail;
51      }
52  
53      /**
54       * This method does not affect the queue itself. It is only a
55       * helper to decrement an index in the queue.
56       */
57      public int decrement(int index) {
58          return (index == 0) ? (elements.length - 1) : index - 1;
59      }
60  
61      public Object   elementAt(int index) {
62          return elements[index];
63      }
64  
65      public Iterator   iterator() {
66          /**/
67          if (isEmpty())
68              return Collections.EMPTY_LIST.iterator();
69  
70          /* if head < tail we can use the same array */
71          if (head <= tail)
72              return new ArrayIterator(elements, head, tail - 1);
73  
74          /* otherwise we need to create a new array */
75          Object  [] newElements = new Object  [size()];
76          int end = (elements.length - head);
77          System.arraycopy(elements, head, newElements, 0, end);
78          System.arraycopy(elements, 0, newElements, end, tail);
79          return new ArrayIterator(newElements);
80      }
81  
82      /**
83       * Returns an object that has been removed from the queue, if any.
84       * The intention is to support reuse of objects that have already
85       * been processed and removed from the queue.  Returns null if there
86       * are no available objects.
87       */
88      public Object   getNextAvailableObject() {
89          int index = tail;
90          while (index != head) {
91              if (elements[index] != null) {
92                  Object   result = elements[index];
93                  elements[index] = null;
94                  return result;
95              }
96              index = increment(index);
97          }
98          return null;
99      }
100 
101     protected void grow() {
102         int newSize = (int) (elements.length * 1.5);
103         Object  [] newElements = new Object  [newSize];
104         if (tail >= head)
105             System.arraycopy(elements, head, newElements, head, size());
106         else {
107             int newHead = newSize - (elements.length - head);
108             System.arraycopy(elements, 0, newElements, 0, tail + 1);
109             System.arraycopy(elements, head, newElements, newHead, (newSize - newHead));
110             head = newHead;
111         }
112         elements = newElements;
113     }
114 
115     /**
116      * This method does not affect the queue itself. It is only a
117      * helper to increment an index in the queue.
118      */
119     public int increment(int index) {
120         return (index == (elements.length - 1)) ? 0 : index + 1;
121     }
122 
123     public int indexOf(Object   target) {
124         if (tail >= head) {
125             for (int i = head; i < tail; i++)
126                 if (target.equals(elements[i]))
127                     return i;
128         } else {
129             for (int i = head; i < elements.length; i++)
130                 if (target.equals(elements[i]))
131                     return i;
132             for (int i = 0; i < tail; i++)
133                 if (target.equals(elements[i]))
134                     return i;
135         }
136         return -1;
137     }
138 
139     public boolean isEmpty() {
140         return tail == head;
141     }
142 
143     public Object   peek() {
144         return elements[head];
145     }
146 
147     public Object   peekTail() {
148         return elements[decrement(tail)];
149     }
150 
151     public Object   remove() {
152         if (isEmpty())
153             return null;
154         Object   result = peek();
155         if (!reuse)
156             elements[head] = null;
157         head = increment(head);
158         return result;
159     }
160 
161     public Object   removeTail() {
162         Object   result = peekTail();
163         tail = decrement(tail);
164         if (!reuse)
165             elements[tail] = null;
166         return result;
167     }
168 
169     public void reset() {
170         tail = head = 0;
171     }
172 
173     public int size() {
174         return tail > head ? (tail - head) : ((elements.length - head) + tail);
175     }
176 
177     public String   toString() {
178         StringBuffer   sb = new StringBuffer  ();
179         sb.append('[');
180         int count = 0;
181         if (!isEmpty()) {
182             Iterator   it = iterator();
183             //only print a fixed number of elements to prevent debugger from choking
184             while (count < 100) {
185                 sb.append(it.next());
186                 if (it.hasNext())
187                     sb.append(',').append(' ');
188                 else
189                     break;
190             }
191         }
192         if (count < size())
193             sb.append('.').append('.').append('.');
194         sb.append(']');
195         return sb.toString();
196     }
197 }
198
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags