001: package bdd.util;
002:
003: /** Written by Tim Macinta 1997 <br>
004: * Distributed under the GNU Public License
005: * (a copy of which is enclosed with the source). <br>
006: * <br>
007: * This class provides a simple First In First Out Queue.
008: * <b>Please Note:</b> this implementation of a FIFOQueue is not
009: * thread safe so if you plan on accessing the same queue with
010: * multiple threads you wil need to handle synchronization yourself
011: * (e.g., by creating a synchronized subclass).
012: */
013:
014: public class FIFOQueue implements java.util.Enumeration {
015: int grow_size;
016: int insert_point = 0; // Point in array where next Object can be stored
017: int read_point = 0; //
018: Object[] q; // Where the queued objects are stored
019:
020: public FIFOQueue() {
021: this (15, 10);
022: }
023:
024: /** "initial_cap" specifies the initial capacity of the queue and
025: * "grow_size" specifies the amount that the capacity grows by when
026: * capacity is reached. Both parameters must be positive.
027: */
028: public FIFOQueue(int initial_cap, int grow_size) {
029: this .grow_size = grow_size;
030: q = new Object[initial_cap];
031: }
032:
033: /** Adds "object" to the queue. "object" CAN be null. */
034: public void addElement(Object object) {
035: if (insert_point == q.length) { // make sure insertion point is valid
036: if (read_point == 0) {
037: grow(); // queue is full so grow it
038: } else {
039: shift(); // shift elements over to make room for insertion
040: }
041: }
042: q[insert_point] = object; // insert object
043: insert_point++;
044: }
045:
046: /** Enlarges the queue capacity by "grow_size". */
047: void grow() {
048: Object[] q2 = new Object[q.length + grow_size];
049: System.arraycopy(q, 0, q2, 0, q.length);
050: q = q2;
051: }
052:
053: /** Shifts all elements so that "read_point" is set to 0. */
054: void shift() {
055: System
056: .arraycopy(q, read_point, q, 0, insert_point
057: - read_point);
058: insert_point -= read_point;
059: read_point = 0;
060: }
061:
062: /** Removes the next element from the queue and returns it.
063: * <p>
064: * Throws a java.util.NoSuchElementException if the queue is empty.
065: */
066: public Object nextElement() {
067: if (read_point == insert_point) {
068: throw new java.util.NoSuchElementException("Queue is empty");
069: }
070: Object obj = q[read_point];
071: q[read_point] = null; // clear reference to allow for garbage collection
072: read_point++;
073: return obj;
074: }
075:
076: /** Returns the next element that on the queue, but leaves the element
077: * on the queue so that the next call to nextElement() or
078: * readNextElement() will return the same element.
079: * <p>
080: * Throws a java.util.NoSuchElementException if the queue is empty.
081: */
082: public Object readNextElement() {
083: if (read_point == insert_point) {
084: throw new java.util.NoSuchElementException("Queue is empty");
085: }
086: return q[read_point];
087: }
088:
089: /** Returns true if this queue contains more elements and false otherwise. */
090: public boolean hasMoreElements() {
091: return insert_point != read_point;
092: }
093:
094: /** Returns the number of elements in this queue. */
095: public int countElements() {
096: return insert_point - read_point;
097: }
098:
099: /** Conserves memory by shrinking the capacity of the queue to
100: * "new_capacity". Of course, you can also use this method to manually
101: * grow the size of the queue, but this is unecessary.
102: * "new_capacity" should be greater than or equal to
103: * the number of elements in the queue - if it is less than the
104: * number of elements in the queue, the capacity will be set to
105: * the number of elements in the queue.
106: */
107: public void setCapacity(int new_capacity) {
108: int current_size = insert_point - read_point;
109: if (new_capacity < current_size)
110: new_capacity = current_size;
111: Object q2 = new Object[new_capacity];
112: System.arraycopy(q, read_point, q2, 0, current_size);
113: }
114:
115: /** Sets the capacity to the number of elements in the queue.
116: * Equivalent to setCapacity(countElements()) .
117: */
118: public void shrinkCapacityToSize() {
119: setCapacity(countElements());
120: }
121:
122: /** Returns the element at index number "index" (index number 0 is
123: * the first element that is read with the nextElement() method). */
124: public Object readElementAt(int index) {
125: if (index > insert_point - read_point) {
126: throw new IndexOutOfBoundsException(index + " > "
127: + (insert_point - read_point));
128: } else if (index < 0) {
129: throw new IndexOutOfBoundsException(index + " < " + 0);
130: }
131: return q[index + read_point];
132: }
133:
134: /** Insert "element" in the queue at index number "index." */
135: public void insertElementAt(Object element, int index) {
136: if (insert_point == q.length) { // make sure insertion point is valid
137: if (read_point == 0) {
138: grow(); // queue is full so grow it
139: } else {
140: shift(); // shift elements over to make room for insertion
141: }
142: }
143:
144: // shift all objects from "index" on to the right one`
145:
146: index += read_point;
147: System.arraycopy(q, index, q, index + 1, insert_point - index);
148: q[index] = element; // insert object
149: insert_point++;
150: }
151:
152: }
|