ArrayQueue


1   package com.quadcap.util.collections;
2   
3   /* Copyright 1999 - 2003 Quadcap Software.  All rights reserved.
4    *
5    * This software is distributed under the Quadcap Free Software License.
6    * This software may be used or modified for any purpose, personal or
7    * commercial.  Open Source redistributions are permitted.  Commercial
8    * redistribution of larger works derived from, or works which bundle
9    * this software requires a "Commercial Redistribution License"; see
10   * http://www.quadcap.com/purchase.
11   *
12   * Redistributions qualify as "Open Source" under  one of the following terms:
13   *   
14   *    Redistributions are made at no charge beyond the reasonable cost of
15   *    materials and delivery.
16   *
17   *    Redistributions are accompanied by a copy of the Source Code or by an
18   *    irrevocable offer to provide a copy of the Source Code for up to three
19   *    years at the cost of materials and delivery.  Such redistributions
20   *    must allow further use, modification, and redistribution of the Source
21   *    Code under substantially the same terms as this license.
22   *
23   * Redistributions of source code must retain the copyright notices as they
24   * appear in each source code file, these license terms, and the
25   * disclaimer/limitation of liability set forth as paragraph 6 below.
26   *
27   * Redistributions in binary form must reproduce this Copyright Notice,
28   * these license terms, and the disclaimer/limitation of liability set
29   * forth as paragraph 6 below, in the documentation and/or other materials
30   * provided with the distribution.
31   *
32   * The Software is provided on an "AS IS" basis.  No warranty is
33   * provided that the Software is free of defects, or fit for a
34   * particular purpose.  
35   *
36   * Limitation of Liability. Quadcap Software shall not be liable
37   * for any damages suffered by the Licensee or any third party resulting
38   * from use of the Software.
39   */
40  
41  /**
42   * Implements the Queue interface using a growable array.
43   *
44   * @author Stan Bailes
45   */
46  public class ArrayQueue implements Queue {
47      int             head        = 0;
48      int             tail        = 0;
49      int             capacity    = 0;
50      Object  []            queue       = null;
51  
52      /**
53       * Create an empty Array queue with unbounded capacity
54       */
55      public ArrayQueue() {
56      this(0, -1);
57      }
58  
59      /**
60       * Create an empty queue with an initial capacity
61       */
62      public ArrayQueue(int capacity) {
63          this(0, capacity);
64      }
65  
66      /**
67       * Create an ArrayQueue with an initial capacity.
68       */
69      public ArrayQueue(int initialSize, int capacity) {
70      this.capacity = capacity;
71      this.queue = new Object  [initialSize + 1];
72      }
73      
74      /**
75       * Specify the maximum capacity of this queue, -1 means unbounded.
76       *
77       * @param capacity the new capacity of the queue, or -1 to specify a
78       *      queue of unlimited size.
79       */
80      public final void setCapacity(int capacity) {
81      if (capacity < size()) {
82          throw new RuntimeException  ("can't set capacity less than size");
83      }
84      if (capacity < queue.length) {
85          resize(size() + 1);
86      }
87      this.capacity = capacity;
88      }
89      
90      /**
91       * Return the number of items in the queue.
92       * @return the queue's size
93       */
94      public final int size() {
95      int ret = 0;
96      if (head > tail) {
97          ret = head - tail;
98      } else if (head < tail) {
99          ret = queue.length - tail + head;
100     }
101     return ret;
102     }
103     
104     /**
105      * Add an object to the front of the queue.
106      *
107      * @param obj the object to add
108      */
109     public final void pushFront(Object   obj) {
110         addFront(obj);
111     }
112     
113     public final void addFront(Object   obj) {
114     checkSizeForAdd();
115     queue[head++] = obj;
116     if (head == queue.length) head = 0;
117     }
118 
119     /**
120      * Add an object to the back of the queue.
121      * @param obj the object to add
122      */
123     public final void pushBack(Object   obj) {
124         addBack(obj);
125     }
126     
127     public final void addBack(Object   obj) {
128     checkSizeForAdd();
129     if (--tail < 0) tail = queue.length - 1;
130     queue[tail] = obj;
131     }
132 
133     /**
134      * Access the object at the front of the queue.  Return null
135      * if the queue is empty.
136      *
137      * @return the item at the head of the queue
138      */
139     public final Object   head() {
140     Object   ret = null;
141     if (size() > 0) {
142         ret = queue[head > 0 ? head - 1 : queue.length - 1];
143     }
144     return ret;
145     }
146 
147     /**
148      * Access the object at the back of the queue.  Return null
149      * if the queue is empty.
150      *
151      * @return the item at the tail of the queue
152      */
153     public final Object   tail() {
154     Object   ret = null;
155     if (size() > 0) {
156         ret = queue[tail];
157     }
158     return ret;
159     }
160 
161     /**
162      * Remove and return the item at the front of the queue.  Return null
163      * if the queue is empty.
164      *
165      * @return the item at the head of the queue
166      */
167     public final Object   popFront() {
168     Object   ret = null;
169     if (size() > 0) {
170         head = head > 0 ? head - 1 : queue.length - 1;
171         ret = queue[head];
172     }
173     return ret;
174     }
175     
176     /**
177      * Remove and return the item at the back of the queue.  Return null
178      * if the queue is empty.
179      *
180      * @return the item at the tail of the queue
181      */     
182     public final Object   popBack() {
183     Object   ret = null;
184     if (size() > 0) {
185         ret = queue[tail++];
186         if (tail >= queue.length) tail = 0;
187     }
188     return ret;
189     }
190 
191     public final void push(Object   obj) {
192     addBack(obj);
193     }
194 
195     public final Object   pop() {
196     return popBack();
197     }
198 
199     public final Object   top() {
200         return tail();
201     }
202 
203     public final Object   top(int pos) {
204         Object   ret = null;
205         if (pos >= 0 && pos < size()) {
206             int x = tail + pos;
207             if (x >= queue.length) x -= queue.length;
208             ret = queue[x];
209         }
210         return ret;
211     }
212 
213     /**
214      * Remove the specified object
215      */
216     public final void remove(Object   obj) {
217     int pos = head - 1;
218     int cnt = size();
219         int last = -1;
220     for (int i = 0; i < cnt; i++) {
221             if (pos < 0) pos = queue.length - 1;
222             if (last < 0) {
223                 if (queue[pos] == obj) {
224                     last = pos;
225                 }
226             } else {
227                 queue[last] = queue[pos];
228                 tail = last;
229                 last = pos;
230             }
231         }
232     }
233 
234     final void checkSizeForAdd() {
235     int siz = size();
236     if (siz == queue.length - 1) {
237         if (capacity <= 0) {
238         resize(queue.length + queue.length/8 + 1);
239         } else {
240         if (siz >= capacity) {
241             throw new RuntimeException  ("queue full");
242         }
243         resize(Math.min(capacity+1,
244                 queue.length + queue.length/8 + 1));
245         }
246     }
247     }
248 
249     final void resize(int newsize) {
250     Object  [] nq = new Object  [newsize];
251     if (head > tail) {
252         System.arraycopy(queue, tail, nq, 0, head - tail);
253         head -= tail;
254         tail = 0;
255     } else if (head < tail) {
256         System.arraycopy(queue, tail, nq, 0, queue.length - tail);
257         if (head > 0) {
258         System.arraycopy(queue, 0, nq, queue.length - tail, head);
259         }
260         head += queue.length - tail;
261         tail = 0;
262     } else {
263         // queue's empty
264         head = tail = 0;
265     }
266     queue = nq;
267     }
268 
269     public String   toString() {
270     StringBuffer   sb = new StringBuffer  ("ArrayQueue");
271     sb.append('[');
272     int pos = head - 1;
273     int cnt = size();
274     for (int i = 0; i < cnt; i++) {
275         if (pos < 0) pos = queue.length - 1;
276         if (i > 0) sb.append(',');
277         sb.append(queue[pos--]).toString();
278     }
279     sb.append(']');
280     return sb.toString();
281     }   
282 }       
283
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags