001: /*
002: * Copyright (c) 1998-2002 Carnegie Mellon University. All rights
003: * reserved.
004: *
005: * Redistribution and use in source and binary forms, with or without
006: * modification, are permitted provided that the following conditions
007: * are met:
008: *
009: * 1. Redistributions of source code must retain the above copyright
010: * notice, this list of conditions and the following disclaimer.
011: *
012: * 2. Redistributions in binary form must reproduce the above copyright
013: * notice, this list of conditions and the following disclaimer in
014: * the documentation and/or other materials provided with the
015: * distribution.
016: *
017: * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
018: * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
019: * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
020: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
021: * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
022: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
023: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
024: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
025: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
026: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
027: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
028: *
029: */
030:
031: package rcm.util;
032:
033: import java.util.Enumeration;
034: import java.util.Vector;
035:
036: /**
037: * Priority queue. Objects stored in a priority queue must implement
038: * the Prioritized interface.
039: *
040: */
041: public class PriorityQueue {
042:
043: private Vector q; // the queue of elements
044:
045: /**
046: * Make an empty PriorityQueue.
047: */
048: public PriorityQueue() {
049: q = new Vector();
050: }
051:
052: /**
053: * Make an empty PriorityQueue with an initial capacity.
054: * @param initialCapacity number of elements initially allocated in queue
055: */
056: public PriorityQueue(int initialCapacity) {
057: q = new Vector(initialCapacity);
058: }
059:
060: /**
061: * Put an object on the queue. Doesn't check for
062: * duplicate puts.
063: * @param x object to put on the queue
064: */
065: public synchronized void put(Prioritized x) {
066: int newSize = q.size() + 1;
067: q.setSize(newSize);
068: float priorityX = x.getPriority();
069:
070: int i, p;
071: for (i = newSize - 1, p = ((i + 1) / 2) - 1; // i's parent
072: i > 0 && getPriority(p) > priorityX; i = p, p = ((i + 1) / 2) - 1)
073: q.setElementAt(q.elementAt(p), i);
074:
075: q.setElementAt(x, i);
076: }
077:
078: /**
079: * Get object with lowest priority from queue.
080: * @return object with lowest priority, or null if queue is empty
081: */
082: public synchronized Object getMin() {
083: return !empty() ? q.elementAt(0) : null;
084: }
085:
086: /**
087: * Get and delete the object with lowest priority.
088: * @return object with lowest priority, or null if queue is empty
089: */
090: public synchronized Object deleteMin() {
091: if (empty())
092: return null;
093: Object obj = q.elementAt(0);
094: deleteElement(0);
095: return obj;
096: }
097:
098: /**
099: * Delete an object from queue. If object was inserted more than
100: * once, this method deletes only one occurrence of it.
101: * @param x object to delete
102: * @return true if x was found and deleted, false if x not found in queue
103: */
104: public synchronized boolean delete(Prioritized x) {
105: int i = q.indexOf(x);
106: if (i == -1)
107: return false;
108: deleteElement(i);
109: return true;
110: }
111:
112: /**
113: * Remove all objects from queue.
114: */
115: public synchronized void clear() {
116: q.removeAllElements();
117: }
118:
119: /**
120: * Enumerate the objects in the queue, in no particular order
121: * @return enumeration of objects in queue
122: */
123: public synchronized Enumeration elements() {
124: return q.elements();
125: }
126:
127: /**
128: * Get number of objects in queue.
129: * @return number of objects
130: */
131: public synchronized int size() {
132: return q.size();
133: }
134:
135: /**
136: * Test whether queue is empty.
137: * @return true iff queue is empty.
138: */
139: public synchronized boolean empty() {
140: return q.isEmpty();
141: }
142:
143: /**
144: * Rebuild priority queuein case the priorities of its elements
145: * have changed since they were inserted. If the priority of
146: * any element changes, this method must be called to update
147: * the priority queue.
148: */
149: public synchronized void update() {
150: for (int i = (q.size() / 2) - 1; i >= 0; --i)
151: heapify(i);
152: }
153:
154: final void deleteElement(int i) {
155: int last = q.size() - 1;
156: q.setElementAt(q.elementAt(last), i);
157: q.setElementAt(null, last); // avoid holding extra reference
158: q.setSize(last);
159: heapify(i);
160: }
161:
162: /* Establishes the heap property at i's descendents.
163: */
164: final void heapify(int i) {
165: int max = q.size();
166: while (i < max) {
167: int r = 2 * (i + 1); // right child of i
168: int l = r - 1; // left child of i
169:
170: int smallest = i;
171: float prioritySmallest = getPriority(i);
172: float priorityR;
173:
174: if (r < max
175: && (priorityR = getPriority(r)) < prioritySmallest) {
176: smallest = r;
177: prioritySmallest = priorityR;
178: }
179: if (l < max && getPriority(l) < prioritySmallest) {
180: smallest = l;
181: }
182:
183: if (smallest != i) {
184: swap(i, smallest);
185: i = smallest;
186: } else
187: break;
188: }
189: }
190:
191: /* Swap elements at positions i and j in the table.
192: */
193: final void swap(int i, int j) {
194: Object tmp = q.elementAt(i);
195: q.setElementAt(q.elementAt(j), i);
196: q.setElementAt(tmp, j);
197: }
198:
199: /* Return the priority of the element at position i. For convenience,
200: positions beyond the end of the table have infinite priority.
201: */
202: final float getPriority(int i) {
203: return ((Prioritized) q.elementAt(i)).getPriority();
204: }
205:
206: public static void main (String[] args) {
207: PriorityQueue q = new PriorityQueue ();
208:
209: for (int i=0; i<args.length; ++i) {
210: float f = Float.valueOf (args[i]).floatValue();
211: q.put (new PQItem (f));
212: System.out.println ("put (" + f + ")");
213: }
214:
215: System.out.println ("getMin() = " + q.getMin());
216: System.out.println ("empty() = " + q.empty());
217:
218: dump (q);
219:
220: if (q.size() > 0) {
221: Enumeration enum = q.elements ();
222: for (int j=0; j<q.size()/2; ++j)
223: enum.nextElement();
224:
225: PQItem deletable = (PQItem)enum.nextElement();
226: q.delete (deletable);
227: System.out.println ("delete (" + deletable + ")");
228:
229: dump (q);
230: }
231:
232: float last = Float.NEGATIVE_INFINITY;
233: PQItem item;
234: while ((item = (PQItem)q.deleteMin()) != null) {
235: System.out.println ("deleteMin() = " + item);
236: if (item.getPriority() < last)
237: System.out.println ("ERROR! greater than last == " + last);
238: last = item.getPriority ();
239: dump (q);
240: }
241: }
242:
243: public static void dump (PriorityQueue q) {
244: Enumeration enum = q.elements ();
245: for (int j=0; enum.hasMoreElements(); ++j) {
246: System.out.println ("elements()[" + (j+1) + "] = " + enum.nextElement());
247: }
248: }
249: }
250:
251: // used for testing only (see main() above)
252: class PQItem implements Prioritized {
253: float priority;
254:
255: public PQItem(float priority) {
256: this .priority = priority;
257: }
258:
259: public float getPriority() {
260: return priority;
261: }
262:
263: public String toString() {
264: return String.valueOf(priority);
265: }
266: }
|