001: package com.quadcap.util.collections;
002:
003: /* Copyright 1999 - 2003 Quadcap Software. All rights reserved.
004: *
005: * This software is distributed under the Quadcap Free Software License.
006: * This software may be used or modified for any purpose, personal or
007: * commercial. Open Source redistributions are permitted. Commercial
008: * redistribution of larger works derived from, or works which bundle
009: * this software requires a "Commercial Redistribution License"; see
010: * http://www.quadcap.com/purchase.
011: *
012: * Redistributions qualify as "Open Source" under one of the following terms:
013: *
014: * Redistributions are made at no charge beyond the reasonable cost of
015: * materials and delivery.
016: *
017: * Redistributions are accompanied by a copy of the Source Code or by an
018: * irrevocable offer to provide a copy of the Source Code for up to three
019: * years at the cost of materials and delivery. Such redistributions
020: * must allow further use, modification, and redistribution of the Source
021: * Code under substantially the same terms as this license.
022: *
023: * Redistributions of source code must retain the copyright notices as they
024: * appear in each source code file, these license terms, and the
025: * disclaimer/limitation of liability set forth as paragraph 6 below.
026: *
027: * Redistributions in binary form must reproduce this Copyright Notice,
028: * these license terms, and the disclaimer/limitation of liability set
029: * forth as paragraph 6 below, in the documentation and/or other materials
030: * provided with the distribution.
031: *
032: * The Software is provided on an "AS IS" basis. No warranty is
033: * provided that the Software is free of defects, or fit for a
034: * particular purpose.
035: *
036: * Limitation of Liability. Quadcap Software shall not be liable
037: * for any damages suffered by the Licensee or any third party resulting
038: * from use of the Software.
039: */
040:
041: /**
042: * Implements the Queue interface using a growable array.
043: *
044: * @author Stan Bailes
045: */
046: public class ArrayQueue implements Queue {
047: int head = 0;
048: int tail = 0;
049: int capacity = 0;
050: Object[] queue = null;
051:
052: /**
053: * Create an empty Array queue with unbounded capacity
054: */
055: public ArrayQueue() {
056: this (0, -1);
057: }
058:
059: /**
060: * Create an empty queue with an initial capacity
061: */
062: public ArrayQueue(int capacity) {
063: this (0, capacity);
064: }
065:
066: /**
067: * Create an ArrayQueue with an initial capacity.
068: */
069: public ArrayQueue(int initialSize, int capacity) {
070: this .capacity = capacity;
071: this .queue = new Object[initialSize + 1];
072: }
073:
074: /**
075: * Specify the maximum capacity of this queue, -1 means unbounded.
076: *
077: * @param capacity the new capacity of the queue, or -1 to specify a
078: * queue of unlimited size.
079: */
080: public final void setCapacity(int capacity) {
081: if (capacity < size()) {
082: throw new RuntimeException(
083: "can't set capacity less than size");
084: }
085: if (capacity < queue.length) {
086: resize(size() + 1);
087: }
088: this .capacity = capacity;
089: }
090:
091: /**
092: * Return the number of items in the queue.
093: * @return the queue's size
094: */
095: public final int size() {
096: int ret = 0;
097: if (head > tail) {
098: ret = head - tail;
099: } else if (head < tail) {
100: ret = queue.length - tail + head;
101: }
102: return ret;
103: }
104:
105: /**
106: * Add an object to the front of the queue.
107: *
108: * @param obj the object to add
109: */
110: public final void pushFront(Object obj) {
111: addFront(obj);
112: }
113:
114: public final void addFront(Object obj) {
115: checkSizeForAdd();
116: queue[head++] = obj;
117: if (head == queue.length)
118: head = 0;
119: }
120:
121: /**
122: * Add an object to the back of the queue.
123: * @param obj the object to add
124: */
125: public final void pushBack(Object obj) {
126: addBack(obj);
127: }
128:
129: public final void addBack(Object obj) {
130: checkSizeForAdd();
131: if (--tail < 0)
132: tail = queue.length - 1;
133: queue[tail] = obj;
134: }
135:
136: /**
137: * Access the object at the front of the queue. Return null
138: * if the queue is empty.
139: *
140: * @return the item at the head of the queue
141: */
142: public final Object head() {
143: Object ret = null;
144: if (size() > 0) {
145: ret = queue[head > 0 ? head - 1 : queue.length - 1];
146: }
147: return ret;
148: }
149:
150: /**
151: * Access the object at the back of the queue. Return null
152: * if the queue is empty.
153: *
154: * @return the item at the tail of the queue
155: */
156: public final Object tail() {
157: Object ret = null;
158: if (size() > 0) {
159: ret = queue[tail];
160: }
161: return ret;
162: }
163:
164: /**
165: * Remove and return the item at the front of the queue. Return null
166: * if the queue is empty.
167: *
168: * @return the item at the head of the queue
169: */
170: public final Object popFront() {
171: Object ret = null;
172: if (size() > 0) {
173: head = head > 0 ? head - 1 : queue.length - 1;
174: ret = queue[head];
175: }
176: return ret;
177: }
178:
179: /**
180: * Remove and return the item at the back of the queue. Return null
181: * if the queue is empty.
182: *
183: * @return the item at the tail of the queue
184: */
185: public final Object popBack() {
186: Object ret = null;
187: if (size() > 0) {
188: ret = queue[tail++];
189: if (tail >= queue.length)
190: tail = 0;
191: }
192: return ret;
193: }
194:
195: public final void push(Object obj) {
196: addBack(obj);
197: }
198:
199: public final Object pop() {
200: return popBack();
201: }
202:
203: public final Object top() {
204: return tail();
205: }
206:
207: public final Object top(int pos) {
208: Object ret = null;
209: if (pos >= 0 && pos < size()) {
210: int x = tail + pos;
211: if (x >= queue.length)
212: x -= queue.length;
213: ret = queue[x];
214: }
215: return ret;
216: }
217:
218: /**
219: * Remove the specified object
220: */
221: public final void remove(Object obj) {
222: int pos = head - 1;
223: int cnt = size();
224: int last = -1;
225: for (int i = 0; i < cnt; i++) {
226: if (pos < 0)
227: pos = queue.length - 1;
228: if (last < 0) {
229: if (queue[pos] == obj) {
230: last = pos;
231: }
232: } else {
233: queue[last] = queue[pos];
234: tail = last;
235: last = pos;
236: }
237: }
238: }
239:
240: final void checkSizeForAdd() {
241: int siz = size();
242: if (siz == queue.length - 1) {
243: if (capacity <= 0) {
244: resize(queue.length + queue.length / 8 + 1);
245: } else {
246: if (siz >= capacity) {
247: throw new RuntimeException("queue full");
248: }
249: resize(Math.min(capacity + 1, queue.length
250: + queue.length / 8 + 1));
251: }
252: }
253: }
254:
255: final void resize(int newsize) {
256: Object[] nq = new Object[newsize];
257: if (head > tail) {
258: System.arraycopy(queue, tail, nq, 0, head - tail);
259: head -= tail;
260: tail = 0;
261: } else if (head < tail) {
262: System.arraycopy(queue, tail, nq, 0, queue.length - tail);
263: if (head > 0) {
264: System.arraycopy(queue, 0, nq, queue.length - tail,
265: head);
266: }
267: head += queue.length - tail;
268: tail = 0;
269: } else {
270: // queue's empty
271: head = tail = 0;
272: }
273: queue = nq;
274: }
275:
276: public String toString() {
277: StringBuffer sb = new StringBuffer("ArrayQueue");
278: sb.append('[');
279: int pos = head - 1;
280: int cnt = size();
281: for (int i = 0; i < cnt; i++) {
282: if (pos < 0)
283: pos = queue.length - 1;
284: if (i > 0)
285: sb.append(',');
286: sb.append(queue[pos--]).toString();
287: }
288: sb.append(']');
289: return sb.toString();
290: }
291: }
|