001: /*
002: * <copyright>
003: *
004: * Copyright 1997-2004 BBNT Solutions, LLC
005: * under sponsorship of the Defense Advanced Research Projects
006: * Agency (DARPA).
007: *
008: * You can redistribute this software and/or modify it under the
009: * terms of the Cougaar Open Source License as published on the
010: * Cougaar Open Source Website (www.cougaar.org).
011: *
012: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
013: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
014: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
015: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
016: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
017: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
018: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
019: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
020: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
021: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
022: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
023: *
024: * </copyright>
025: */
026:
027: package org.cougaar.util;
028:
029: import java.util.AbstractCollection;
030: import java.util.Collection;
031: import java.util.Iterator;
032: import java.util.NoSuchElementException;
033:
034: /**
035: * Implements a traditional circular queue, except that it will enlarge
036: * backing array if it runs out of space.
037: * Also implements the Collection API, except for remove methods.
038: * This implementation leaves all synchronization to the caller.
039: * The implementation is optimized to make add(Object) and Object next()
040: * operations as cheap as possible. size, isEmpty and peek are also very
041: * cheap. Other operations may be considerably more expensive.
042: * The iterator supplied does NOT support fast-fail on modification.
043: *
044: * Inspired by _Data Structure and Algorithms_ by Aho, Hopcroft and Ullman.
045: **/
046:
047: public class CircularQueue<E> extends AbstractCollection<E> {
048: protected E[] elements;
049: protected int front;
050: protected int rear;
051: protected int size;
052: protected int max;
053:
054: public CircularQueue() {
055: this (5);
056: }
057:
058: public CircularQueue(int max) {
059: elements = makeArray(max);
060: front = 0;
061: rear = max - 1;
062: size = 0;
063: this .max = max;
064: }
065:
066: private final int nextIndex(int i) {
067: return (i + 1) % max;
068: }
069:
070: public void clear() {
071: front = 0;
072: rear = max - 1;
073: size = 0;
074: }
075:
076: public final boolean isEmpty() {
077: return (nextIndex(rear) == front);
078: }
079:
080: private final boolean isFull() {
081: return (nextIndex(nextIndex(rear)) == front);
082: }
083:
084: public E peek() {
085: if (isEmpty())
086: return null;
087: else
088: return elements[front];
089: }
090:
091: public boolean add(E el) {
092: if (isFull())
093: extend();
094: int adv = nextIndex(rear);
095: rear = adv;
096: elements[adv] = el;
097: size++;
098: return true;
099: }
100:
101: public boolean addAll(Collection<? extends E> c) {
102: for (E t : c) {
103: add(t);
104: }
105: return true;
106: }
107:
108: public boolean remove(Object el) {
109: throw new UnsupportedOperationException();
110: }
111:
112: public boolean removeAll(Collection<?> c) {
113: throw new UnsupportedOperationException();
114: }
115:
116: public boolean retainAll(Collection<?> c) {
117: throw new UnsupportedOperationException();
118: }
119:
120: public boolean contains(Object el) {
121: int i = front;
122: int x = nextIndex(rear);
123: while (i != x) {
124: if (el.equals(elements[i]))
125: return true;
126: i = nextIndex(i);
127: }
128: return false;
129: }
130:
131: public Object[] toArray() {
132: Object[] result = new Object[size];
133: int i = front;
134: int x = nextIndex(rear);
135: int j = 0;
136: while (i != x) {
137: result[j] = elements[i];
138: i = nextIndex(i);
139: j++;
140: }
141: return result;
142: }
143:
144: @SuppressWarnings("unchecked")
145: private final E[] makeArray(int size) {
146: // XXX: Unavoidable (?) warning
147: return (E[]) new Object[size];
148: }
149:
150: @SuppressWarnings("unchecked")
151: public <T> T[] toArray(T[] result) {
152: int i = front;
153: int x = nextIndex(rear);
154: int j = 0;
155: while (i != x) {
156: // XXX: Unavoidable (?) warning
157: result[j] = (T) elements[i];
158: i = nextIndex(i);
159: j++;
160: }
161: return result;
162: }
163:
164: public boolean containsAll(Collection<?> c) {
165: // UGH! n^2
166: for (Object elt : c) {
167: if (!contains(elt))
168: return false;
169: }
170: return true;
171: }
172:
173: public E next() {
174: if (isEmpty()) {
175: return null;
176: } else {
177: E o = elements[front];
178: elements[front] = null; // allow gc
179: front = nextIndex(front);
180: size--;
181: return o;
182: }
183: }
184:
185: private void extend() {
186: //System.err.println("Extending "+this);
187: int nmax = max * 2;
188: E[] nelements = makeArray(nmax);
189: // we could do this with two array copies
190: for (int i = 0; i < size; i++) {
191: nelements[i] = peek();
192: front = nextIndex(front);
193: }
194: elements = nelements;
195: front = 0;
196: rear = size - 1;
197: max = nmax;
198: }
199:
200: public Iterator<E> iterator() {
201: final int capturedFront = front;
202: return new Iterator<E>() {
203: private int i = capturedFront;
204:
205: public final boolean hasNext() {
206: return (nextIndex(rear) != i);
207: }
208:
209: public final E next() {
210: if (!hasNext())
211: throw new NoSuchElementException();
212: E o = elements[i];
213: i = nextIndex(i);
214: return o;
215: }
216:
217: public final void remove() {
218: }
219: };
220: }
221:
222: public int size() {
223: return size;
224: }
225:
226: public String toString() {
227: return "{CircularQueue " + size + "/" + max + "}";
228: }
229:
230: public String toPrettyString() {
231: String s = "{";
232: int i = front;
233: int x = nextIndex(rear);
234: while (i != x) {
235: s = s + (elements[i].toString());
236: i = nextIndex(i);
237: if (i != x)
238: s = s + " ";
239: }
240: return s + "}";
241: }
242: }
|