001: /*
002: * @(#)Queue.java 1.14 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package sun.misc;
029:
030: import java.util.Enumeration;
031: import java.util.NoSuchElementException;
032:
033: /**
034: * Queue: implements a simple queue mechanism. Allows for enumeration of the
035: * elements.
036: *
037: * @version 1.10, 08/19/02
038: * @author Herb Jellinek
039: */
040:
041: public class Queue {
042: int length = 0;
043: QueueElement head = null;
044: QueueElement tail = null;
045:
046: public Queue() {
047: }
048:
049: /**
050: * Enqueue an object.
051: */
052: public synchronized void enqueue(Object obj) {
053: QueueElement newElt = new QueueElement(obj);
054: if (head == null) {
055: head = newElt;
056: tail = newElt;
057: length = 1;
058: } else {
059: newElt.next = head;
060: head.prev = newElt;
061: head = newElt;
062: length++;
063: }
064: notify();
065: }
066:
067: /**
068: * Dequeue the oldest object on the queue. Will wait indefinitely.
069: *
070: * @return the oldest object on the queue.
071: * @exception java.lang.InterruptedException if another thread has
072: * interrupted this thread.
073: */
074: public Object dequeue() throws InterruptedException {
075: return dequeue(0L);
076: }
077:
078: /**
079: * Dequeue the oldest object on the queue.
080: * @param timeOut the number of milliseconds to wait for something
081: * to arrive.
082: *
083: * @return the oldest object on the queue.
084: * @exception java.lang.InterruptedException if another thread has
085: * interrupted this thread.
086: */
087: public synchronized Object dequeue(long timeOut)
088: throws InterruptedException {
089: while (tail == null) {
090: wait(timeOut);
091: }
092: QueueElement elt = tail;
093: tail = elt.prev;
094: if (tail == null) {
095: head = null;
096: } else {
097: tail.next = null;
098: }
099: length--;
100: return elt.obj;
101: }
102:
103: /**
104: * Is the queue empty?
105: * @return true if the queue is empty.
106: */
107: public synchronized boolean isEmpty() {
108: return (tail == null);
109: }
110:
111: /**
112: * Returns an enumeration of the elements in Last-In, First-Out
113: * order. Use the Enumeration methods on the returned object to
114: * fetch the elements sequentially.
115: */
116: public final synchronized Enumeration elements() {
117: return new LIFOQueueEnumerator(this );
118: }
119:
120: /**
121: * Returns an enumeration of the elements in First-In, First-Out
122: * order. Use the Enumeration methods on the returned object to
123: * fetch the elements sequentially.
124: */
125: public final synchronized Enumeration reverseElements() {
126: return new FIFOQueueEnumerator(this );
127: }
128:
129: public synchronized void dump(String msg) {
130: System.err.println(">> " + msg);
131: System.err.println("[" + length + " elt(s); head = "
132: + (head == null ? "null" : (head.obj) + "")
133: + " tail = "
134: + (tail == null ? "null" : (tail.obj) + ""));
135: QueueElement cursor = head;
136: QueueElement last = null;
137: while (cursor != null) {
138: System.err.println(" " + cursor);
139: last = cursor;
140: cursor = cursor.next;
141: }
142: if (last != tail) {
143: System.err.println(" tail != last: " + tail + ", " + last);
144: }
145: System.err.println("]");
146: }
147: }
148:
149: final class FIFOQueueEnumerator implements Enumeration {
150: Queue queue;
151: QueueElement cursor;
152:
153: FIFOQueueEnumerator(Queue q) {
154: queue = q;
155: cursor = q.tail;
156: }
157:
158: public boolean hasMoreElements() {
159: return (cursor != null);
160: }
161:
162: public Object nextElement() {
163: synchronized (queue) {
164: if (cursor != null) {
165: QueueElement result = cursor;
166: cursor = cursor.prev;
167: return result.obj;
168: }
169: }
170: throw new NoSuchElementException("FIFOQueueEnumerator");
171: }
172: }
173:
174: final class LIFOQueueEnumerator implements Enumeration {
175: Queue queue;
176: QueueElement cursor;
177:
178: LIFOQueueEnumerator(Queue q) {
179: queue = q;
180: cursor = q.head;
181: }
182:
183: public boolean hasMoreElements() {
184: return (cursor != null);
185: }
186:
187: public Object nextElement() {
188: synchronized (queue) {
189: if (cursor != null) {
190: QueueElement result = cursor;
191: cursor = cursor.next;
192: return result.obj;
193: }
194: }
195: throw new NoSuchElementException("LIFOQueueEnumerator");
196: }
197: }
198:
199: class QueueElement {
200: QueueElement next = null;
201: QueueElement prev = null;
202: Object obj = null;
203:
204: QueueElement(Object obj) {
205: this .obj = obj;
206: }
207:
208: public String toString() {
209: return "QueueElement[obj=" + obj
210: + (prev == null ? " null" : " prev")
211: + (next == null ? " null" : " next") + "]";
212: }
213: }
|