001 /*
002 * Default Queue Implementation
003 *
004 * Developed for "Rethinking CS101", a project of Lynn Andrea Stein's AP Group.
005 * For more information, see <a href="http://www.ai.mit.edu/projects/cs101/">the
006 * CS101 homepage</a> or email <las@ai.mit.edu>.
007 *
008 * Copyright (C) 1998 Massachusetts Institute of Technology.
009 * Please do not redistribute without obtaining permission.
010 */
011
012 package cs101.util.queue;
013
014 import java.util.Enumeration;
015 import java.util.NoSuchElementException;
016
017 /**
018 * Default Queue class. Allows insertion/deletion at either end.
019 * Throws EmptyQueueException in some situations, but
020 * EmptyQueueException is a subclass of RuntimeException, so you don't
021 * have to protect Queue access with try/catch blocks.
022 * <p>
023 * Copyright (c) 1998 Massachusetts Institute of Technology
024 *
025 * @author Todd C. Parnell, tparnell@ai.mit.edu
026 * @version $Id: DefaultQueue.java,v 1.2 2003/09/23 14:46:57 gus Exp $
027 *
028 * @see cs101.util.queue.EmptyQueueException
029 */
030 public class DefaultQueue implements Queue {
031
032 private Link first, last;
033 private int count;
034
035 /** Creates a new, empty Queue */
036 public DefaultQueue () {}
037
038 /** Creates a new Queue contining obj as the only element */
039 public DefaultQueue (Object obj) {
040 this.first = this.last = new Link (obj);
041 this.count = 1;
042 }
043
044 /** Returns the number of elements in this. */
045 public synchronized int size() { return this.count; }
046
047 /**
048 * Gets the tail object from the queue </B>without</B> removing
049 * it.
050 */
051 public synchronized Object peek() {
052 return this.peek(Queue.BACK);
053 }
054
055 /**
056 * Gets the object from the specified end of the queue
057 * </B>without</B> removing it.
058 */
059 public synchronized Object peek(int end) {
060 if (this.isEmpty()) throw new EmptyQueueException();
061 if (end == Queue.FRONT)
062 return this.first.contents();
063 else
064 return this.last.contents();
065 }
066
067 /** Puts obj into the front the queue. */
068 public synchronized void enqueue(Object obj) {
069 this.enqueue(obj, Queue.FRONT);
070 }
071
072 /** Puts obj into the specified end of the queue. */
073 public synchronized void enqueue(Object obj, int end) {
074 if (this.isEmpty()) {
075 this.first = this.last = new Link(obj);
076 } else {
077 if (end == Queue.FRONT) {
078 Link tmp = new Link(obj);
079 tmp.setNext(this.first);
080 this.first.setPrevious(tmp);
081 this.first = tmp;
082 }
083 else /* end == Queue.BACK */ {
084 Link tmp = new Link(obj);
085 tmp.setPrevious(this.last);
086 this.last.setNext(tmp);
087 this.last = tmp;
088 }
089 }
090 this.count++;
091 }
092
093 /** Removes and returns the Object at the tail of the queue. */
094 public synchronized Object dequeue() {
095 return this.dequeue(Queue.BACK);
096 }
097
098 /** Removes and returns the Object at the specified end of the queue. */
099 public synchronized Object dequeue(int end) {
100 if (this.isEmpty()) throw new EmptyQueueException();
101 this.count--;
102 if (end == Queue.FRONT) {
103 Object tmp = this.first.contents();
104 Link l_tmp = this.first.next();
105 this.first.setNext(null); // remove reference
106 this.first = l_tmp;
107 if (this.first == null) {
108 this.last = null;
109 }
110 else {
111 // remove dangling reference for gc
112 this.first.setPrevious(null);
113 }
114 return tmp;
115 }
116 else /* end == Queue.BACK */ {
117 Object tmp = this.last.contents();
118 Link l_tmp = this.last.previous();
119 this.last.setPrevious(null);
120 this.last = l_tmp;
121 if (this.last == null) {
122 this.first = null;
123 }
124 else {
125 this.last.setNext(null);
126 }
127 return tmp;
128 }
129 }
130
131 /** Tests whether the queue is empty. */
132 public synchronized boolean isEmpty () {
133 return (this.first == null);
134 }
135
136 /**
137 * Returns an Enumeration of the Objects in the queue.<p>
138 *
139 * <I>Note: Do not modify the queue while enumerating--unpredictable
140 * behavior may result.</I>
141 *
142 * @see java.util.Enumeration
143 */
144 public Enumeration elements() {
145 return new QueueEnumeration(this.first);
146 }
147
148 public synchronized String toString() {
149 StringBuffer sb = new StringBuffer("cs101.util.Queue: [");
150 Enumeration enum = this.elements();
151 while (enum.hasMoreElements()) {
152 sb.append(enum.nextElement());
153 if (enum.hasMoreElements()) sb.append(", ");
154 }
155 sb.append("]");
156 return sb.toString();
157 }
158
159 /** Inner class to make Queue.elements() happen. */
160 private class QueueEnumeration implements Enumeration {
161 private Link current;
162
163 public QueueEnumeration(Link l) {
164 current = l;
165 }
166
167 public boolean hasMoreElements() {
168 return (current != null);
169 }
170
171 public Object nextElement() {
172 if (current == null) throw new NoSuchElementException();
173 Object tmp = current.contents();
174 current = current.next();
175 return tmp;
176 }
177 } // class QueueEnumeration
178
179
180 /**
181 * Links form the building blocks for Queues.
182 *
183 * @see Queue
184 */
185 class Link {
186
187 private Link previous = null;
188 private Link next = null;
189 private Object contents;
190
191 protected Link(Object obj) {
192 this.contents = obj;
193 }
194
195 public Object contents() {
196 return this.contents;
197 }
198
199 public Link next() {
200 return this.next;
201 }
202
203 public Link previous() {
204 return this.previous;
205 }
206
207 protected synchronized void setPrevious(Link link) {
208 this.previous = link;
209 }
210
211 protected synchronized void setNext(Link link) {
212 this.next = link;
213 }
214
215 public synchronized String toString() {
216 StringBuffer sb = new StringBuffer("cs101.util.Link: [previous:");
217 if (this.previous != null)
218 sb.append("linked");
219 else sb.append("null");
220 sb.append("] [contents:" + this.contents + "] [next:");
221 if (this.next != null)
222 sb.append("linked]");
223 else sb.append("null]");
224 return sb.toString();
225 }
226 } // class Link
227 }
228
229 /*
230 * $Log: DefaultQueue.java,v $
231 * Revision 1.2 2003/09/23 14:46:57 gus
232 * javadoc fix
233 *
234 * Revision 1.1.1.1 2002/06/05 21:56:32 root
235 * CS101 comes to Olin finally.
236 *
237 * Revision 1.1 2000/04/24 22:17:18 nathanw
238 * Bulk reorganization
239 *
240 * Revision 1.3 1999/07/27 18:59:33 jsmthng
241 * Changed *all* instances of 'peak' to 'peek' this time. Really. (I
242 * hope.)
243 *
244 * Revision 1.2 1999/07/27 18:51:12 jsmthng
245 * Instances of 'peak' changed to the new spelling, 'peek', in compliance
246 * with the new version of cs101.util.Queue.
247 *
248 * Revision 1.1 1999/01/21 20:49:18 tparnell
249 * Made Queue.java an interface and added DefaultQueue.java as an implementation.
250 *
251 */