001 /*
002 * LAPIS lightweight structured text processing system
003 *
004 * Copyright (C) 1998-2002 Carnegie Mellon University,
005 * Copyright (C) 2003 Massachusetts Institute of Technology.
006 * All rights reserved.
007 *
008 * This library is free software; you can redistribute it
009 * and/or modify it under the terms of the GNU General
010 * Public License as published by the Free Software
011 * Foundation, version 2.
012 *
013 * LAPIS homepage: http://graphics.lcs.mit.edu/lapis/
014 */
015
016
017 package lapisx.util;
018
019 import java.util.Enumeration;
020 import java.util.Vector;
021
022 /**
023 * Priority queue. Objects stored in a priority queue must implement
024 * the Prioritized interface.
025 *
026 */
027 public class PriorityQueue {
028
029 private Vector q; // the queue of elements
030
031 /**
032 * Make an empty PriorityQueue.
033 */
034 public PriorityQueue () {
035 q = new Vector ();
036 }
037
038 /**
039 * Make an empty PriorityQueue with an initial capacity.
040 * @param initialCapacity number of elements initially allocated in queue
041 */
042 public PriorityQueue (int initialCapacity) {
043 q = new Vector (initialCapacity);
044 }
045
046 /**
047 * Put an object on the queue. Doesn't check for
048 * duplicate puts.
049 * @param x object to put on the queue
050 */
051 public synchronized void put (Prioritized x) {
052 int newSize = q.size()+1;
053 q.setSize (newSize);
054 float priorityX = x.getPriority ();
055
056 int i, p;
057 for (i=newSize-1, p = ((i+1)/2)-1; // i's parent
058 i > 0 && getPriority (p) > priorityX;
059 i = p, p = ((i+1)/2)-1)
060 q.setElementAt (q.elementAt (p), i);
061
062 q.setElementAt (x, i);
063 }
064
065 /**
066 * Get object with lowest priority from queue.
067 * @return object with lowest priority, or null if queue is empty
068 */
069 public synchronized Object getMin () {
070 return !empty() ? q.elementAt (0) : null;
071 }
072
073 /**
074 * Get and delete the object with lowest priority.
075 * @return object with lowest priority, or null if queue is empty
076 */
077 public synchronized Object deleteMin () {
078 if (empty())
079 return null;
080 Object obj = q.elementAt (0);
081 deleteElement (0);
082 return obj;
083 }
084
085 /**
086 * Delete an object from queue. If object was inserted more than
087 * once, this method deletes only one occurrence of it.
088 * @param x object to delete
089 * @return true if x was found and deleted, false if x not found in queue
090 */
091 public synchronized boolean delete (Prioritized x) {
092 int i = q.indexOf (x);
093 if (i == -1)
094 return false;
095 deleteElement (i);
096 return true;
097 }
098
099 /**
100 * Remove all objects from queue.
101 */
102 public synchronized void clear () {
103 q.removeAllElements ();
104 }
105
106
107 /**
108 * Enumerate the objects in the queue, in no particular order
109 * @return enumeration of objects in queue
110 */
111 public synchronized Enumeration elements () {
112 return q.elements ();
113 }
114
115
116 /**
117 * Get number of objects in queue.
118 * @return number of objects
119 */
120 public synchronized int size () {
121 return q.size ();
122 }
123
124
125 /**
126 * Test whether queue is empty.
127 * @return true iff queue is empty.
128 */
129 public synchronized boolean empty () {
130 return q.isEmpty ();
131 }
132
133 /**
134 * Rebuild priority queuein case the priorities of its elements
135 * have changed since they were inserted. If the priority of
136 * any element changes, this method must be called to update
137 * the priority queue.
138 */
139 public synchronized void update () {
140 for (int i = (q.size()/2) - 1; i >= 0; --i)
141 heapify (i);
142 }
143
144 final void deleteElement (int i) {
145 int last = q.size()-1;
146 q.setElementAt (q.elementAt (last), i);
147 q.setElementAt (null, last); // avoid holding extra reference
148 q.setSize (last);
149 heapify (i);
150 }
151
152 /* Establishes the heap property at i's descendents.
153 */
154 final void heapify (int i) {
155 int max = q.size();
156 while (i < max) {
157 int r = 2*(i+1); // right child of i
158 int l = r - 1; // left child of i
159
160 int smallest = i;
161 float prioritySmallest = getPriority (i);
162 float priorityR;
163
164 if (r < max && (priorityR = getPriority (r)) < prioritySmallest) {
165 smallest = r;
166 prioritySmallest = priorityR;
167 }
168 if (l < max && getPriority (l) < prioritySmallest) {
169 smallest = l;
170 }
171
172 if (smallest != i) {
173 swap (i, smallest);
174 i = smallest;
175 }
176 else
177 break;
178 }
179 }
180
181 /* Swap elements at positions i and j in the table.
182 */
183 final void swap (int i, int j) {
184 Object tmp = q.elementAt (i);
185 q.setElementAt (q.elementAt (j), i);
186 q.setElementAt (tmp, j);
187 }
188
189 /* Return the priority of the element at position i. For convenience,
190 positions beyond the end of the table have infinite priority.
191 */
192 final float getPriority (int i) {
193 return ((Prioritized)q.elementAt (i)).getPriority();
194 }
195
196 public static void main (String[] args) {
197 PriorityQueue q = new PriorityQueue ();
198
199 for (int i=0; i<args.length; ++i) {
200 float f = Float.valueOf (args[i]).floatValue();
201 q.put (new PQItem (f));
202 System.out.println ("put (" + f + ")");
203 }
204
205 System.out.println ("getMin() = " + q.getMin());
206 System.out.println ("empty() = " + q.empty());
207
208 dump (q);
209
210 if (q.size() > 0) {
211 Enumeration enum = q.elements ();
212 for (int j=0; j<q.size()/2; ++j)
213 enum.nextElement();
214
215 PQItem deletable = (PQItem)enum.nextElement();
216 q.delete (deletable);
217 System.out.println ("delete (" + deletable + ")");
218
219 dump (q);
220 }
221
222 float last = Float.NEGATIVE_INFINITY;
223 PQItem item;
224 while ((item = (PQItem)q.deleteMin()) != null) {
225 System.out.println ("deleteMin() = " + item);
226 if (item.getPriority() < last)
227 System.out.println ("ERROR! greater than last == " + last);
228 last = item.getPriority ();
229 dump (q);
230 }
231 }
232
233 public static void dump (PriorityQueue q) {
234 Enumeration enum = q.elements ();
235 for (int j=0; enum.hasMoreElements(); ++j) {
236 System.out.println ("elements()[" + (j+1) + "] = " + enum.nextElement());
237 }
238 }
239 }
240
241 // used for testing only (see main() above)
242 class PQItem implements Prioritized {
243 float priority;
244
245 public PQItem (float priority) {
246 this.priority = priority;
247 }
248
249 public float getPriority () {
250 return priority;
251 }
252
253 public String toString () {
254 return String.valueOf (priority);
255 }
256 }