Parent Directory | Revision Log

Revision **1.4** -
(**show annotations**)

*Mon May 19 02:45:07 2003 UTC*
(16 years, 3 months ago)
by *tim*

Branch:**MAIN**

Changes since**1.3: +0 -4 lines**

Branch:

Changes since

Use temp version of Sorted to allow a portion of PQ impl to be uncommented.

1 | package java.util; |

2 | |

3 | /* |

4 | * Todo |

5 | * |

6 | * 1) Make it serializable. |

7 | */ |

8 | |

9 | /** |

10 | * An unbounded priority queue based on a priority heap. This queue orders |

11 | * elements according to the order specified at creation time. This order is |

12 | * specified as for {@link TreeSet} and {@link TreeMap}: Elements are ordered |

13 | * either according to their <i>natural order</i> (see {@link Comparable}), or |

14 | * according to a {@link Comparator}, depending on which constructor is used. |

15 | * The {@link #peek}, {@link #poll}, and {@link #remove} methods return the |

16 | * minimal element with respect to the specified ordering. If multiple |

17 | * these elements are tied for least value, no guarantees are made as to |

18 | * which of elements is returned. |

19 | * |

20 | * <p>Each priority queue has a <i>capacity</i>. The capacity is the size of |

21 | * the array used to store the elements on the queue. It is always at least |

22 | * as large as the queue size. As elements are added to a priority list, |

23 | * its capacity grows automatically. The details of the growth policy are not |

24 | * specified. |

25 | * |

26 | *<p>Implementation note: this implementation provides O(log(n)) time for |

27 | * the <tt>offer</tt>, <tt>poll</tt>, <tt>remove()</tt> and <tt>add</tt> |

28 | * methods; linear time for the <tt>remove(Object)</tt> and |

29 | * <tt>contains</tt> methods; and constant time for the <tt>peek</tt>, |

30 | * <tt>element</tt>, and <tt>size</tt> methods. |

31 | * |

32 | * <p>This class is a member of the |

33 | * <a href="{@docRoot}/../guide/collections/index.html"> |

34 | * Java Collections Framework</a>. |

35 | */ |

36 | public class PriorityQueue<E> extends AbstractQueue<E> |

37 | implements Queue<E> |

38 | { |

39 | private static final int DEFAULT_INITIAL_CAPACITY = 11; |

40 | |

41 | /** |

42 | * Priority queue represented as a balanced binary heap: the two children |

43 | * of queue[n] are queue[2*n] and queue[2*n + 1]. The priority queue is |

44 | * ordered by comparator, or by the elements' natural ordering, if |

45 | * comparator is null: For each node n in the heap, and each descendant |

46 | * of n, d, n <= d. |

47 | * |

48 | * The element with the lowest value is in queue[1] (assuming the queue is |

49 | * nonempty). A one-based array is used in preference to the traditional |

50 | * zero-based array to simplify parent and child calculations. |

51 | * |

52 | * queue.length must be >= 2, even if size == 0. |

53 | */ |

54 | private E[] queue; |

55 | |

56 | /** |

57 | * The number of elements in the priority queue. |

58 | */ |

59 | private int size = 0; |

60 | |

61 | /** |

62 | * The comparator, or null if priority queue uses elements' |

63 | * natural ordering. |

64 | */ |

65 | private final Comparator<E> comparator; |

66 | |

67 | /** |

68 | * The number of times this priority queue has been |

69 | * <i>structurally modified</i>. See AbstractList for gory details. |

70 | */ |

71 | private int modCount = 0; |

72 | |

73 | /** |

74 | * Create a new priority queue with the default initial capacity (11) |

75 | * that orders its elements according to their natural ordering. |

76 | */ |

77 | public PriorityQueue() { |

78 | this(DEFAULT_INITIAL_CAPACITY); |

79 | } |

80 | |

81 | /** |

82 | * Create a new priority queue with the specified initial capacity |

83 | * that orders its elements according to their natural ordering. |

84 | * |

85 | * @param initialCapacity the initial capacity for this priority queue. |

86 | */ |

87 | public PriorityQueue(int initialCapacity) { |

88 | this(initialCapacity, null); |

89 | } |

90 | |

91 | /** |

92 | * Create a new priority queue with the specified initial capacity (11) |

93 | * that orders its elements according to the specified comparator. |

94 | * |

95 | * @param initialCapacity the initial capacity for this priority queue. |

96 | * @param comparator the comparator used to order this priority queue. |

97 | */ |

98 | public PriorityQueue(int initialCapacity, Comparator<E> comparator) { |

99 | if (initialCapacity < 1) |

100 | initialCapacity = 1; |

101 | queue = new E[initialCapacity + 1]; |

102 | this.comparator = comparator; |

103 | } |

104 | |

105 | /** |

106 | * Create a new priority queue containing the elements in the specified |

107 | * collection. The priority queue has an initial capacity of 110% of the |

108 | * size of the specified collection. If the specified collection |

109 | * implements the {@link Sorted} interface, the priority queue will be |

110 | * sorted according to the same comparator, or according to its elements' |

111 | * natural order if the collection is sorted according to its elements' |

112 | * natural order. If the specified collection does not implement the |

113 | * <tt>Sorted</tt> interface, the priority queue is ordered according to |

114 | * its elements' natural order. |

115 | * |

116 | * @param initialElements the collection whose elements are to be placed |

117 | * into this priority queue. |

118 | * @throws ClassCastException if elements of the specified collection |

119 | * cannot be compared to one another according to the priority |

120 | * queue's ordering. |

121 | * @throws NullPointerException if the specified collection or an |

122 | * element of the specified collection is <tt>null</tt>. |

123 | */ |

124 | public PriorityQueue(Collection<E> initialElements) { |

125 | int sz = initialElements.size(); |

126 | int initialCapacity = (int)Math.min((sz * 110L) / 100, |

127 | Integer.MAX_VALUE - 1); |

128 | if (initialCapacity < 1) |

129 | initialCapacity = 1; |

130 | queue = new E[initialCapacity + 1]; |

131 | |

132 | if (initialElements instanceof Sorted) { |

133 | comparator = ((Sorted)initialElements).comparator(); |

134 | for (Iterator<E> i = initialElements.iterator(); i.hasNext(); ) |

135 | queue[++size] = i.next(); |

136 | } else { |

137 | comparator = null; |

138 | for (Iterator<E> i = initialElements.iterator(); i.hasNext(); ) |

139 | add(i.next()); |

140 | } |

141 | } |

142 | |

143 | // Queue Methods |

144 | |

145 | /** |

146 | * Remove and return the minimal element from this priority queue if |

147 | * it contains one or more elements, otherwise <tt>null</tt>. The term |

148 | * <i>minimal</i> is defined according to this priority queue's order. |

149 | * |

150 | * @return the minimal element from this priority queue if it contains |

151 | * one or more elements, otherwise <tt>null</tt>. |

152 | */ |

153 | public E poll() { |

154 | if (size == 0) |

155 | return null; |

156 | return remove(1); |

157 | } |

158 | |

159 | /** |

160 | * Return, but do not remove, the minimal element from the priority queue, |

161 | * or <tt>null</tt> if the queue is empty. The term <i>minimal</i> is |

162 | * defined according to this priority queue's order. This method returns |

163 | * the same object reference that would be returned by by the |

164 | * <tt>poll</tt> method. The two methods differ in that this method |

165 | * does not remove the element from the priority queue. |

166 | * |

167 | * @return the minimal element from this priority queue if it contains |

168 | * one or more elements, otherwise <tt>null</tt>. |

169 | */ |

170 | public E peek() { |

171 | return queue[1]; |

172 | } |

173 | |

174 | // Collection Methods |

175 | |

176 | /** |

177 | * Removes a single instance of the specified element from this priority |

178 | * queue, if it is present. Returns true if this collection contained the |

179 | * specified element (or equivalently, if this collection changed as a |

180 | * result of the call). |

181 | * |

182 | * @param o element to be removed from this collection, if present. |

183 | * @return <tt>true</tt> if this collection changed as a result of the |

184 | * call |

185 | * @throws ClassCastException if the specified element cannot be compared |

186 | * with elements currently in the priority queue according |

187 | * to the priority queue's ordering. |

188 | * @throws NullPointerException if the specified element is null. |

189 | */ |

190 | public boolean remove(Object element) { |

191 | if (element == null) |

192 | throw new NullPointerException(); |

193 | |

194 | if (comparator == null) { |

195 | for (int i = 1; i <= size; i++) { |

196 | if (((Comparable)queue[i]).compareTo(element) == 0) { |

197 | remove(i); |

198 | return true; |

199 | } |

200 | } |

201 | } else { |

202 | for (int i = 1; i <= size; i++) { |

203 | if (comparator.compare(queue[i], (E) element) == 0) { |

204 | remove(i); |

205 | return true; |

206 | } |

207 | } |

208 | } |

209 | return false; |

210 | } |

211 | |

212 | /** |

213 | * Returns an iterator over the elements in this priority queue. The |

214 | * first element returned by this iterator is the same element that |

215 | * would be returned by a call to <tt>peek</tt>. |

216 | * |

217 | * @return an <tt>Iterator</tt> over the elements in this priority queue. |

218 | */ |

219 | public Iterator<E> iterator() { |

220 | return new Itr(); |

221 | } |

222 | |

223 | private class Itr implements Iterator<E> { |

224 | /** |

225 | * Index (into queue array) of element to be returned by |

226 | * subsequent call to next. |

227 | */ |

228 | int cursor = 1; |

229 | |

230 | /** |

231 | * Index of element returned by most recent call to next or |

232 | * previous. Reset to 0 if this element is deleted by a call |

233 | * to remove. |

234 | */ |

235 | int lastRet = 0; |

236 | |

237 | /** |

238 | * The modCount value that the iterator believes that the backing |

239 | * List should have. If this expectation is violated, the iterator |

240 | * has detected concurrent modification. |

241 | */ |

242 | int expectedModCount = modCount; |

243 | |

244 | public boolean hasNext() { |

245 | return cursor <= size; |

246 | } |

247 | |

248 | public E next() { |

249 | checkForComodification(); |

250 | if (cursor > size) |

251 | throw new NoSuchElementException(); |

252 | E result = queue[cursor]; |

253 | lastRet = cursor++; |

254 | return result; |

255 | } |

256 | |

257 | public void remove() { |

258 | if (lastRet == 0) |

259 | throw new IllegalStateException(); |

260 | checkForComodification(); |

261 | |

262 | PriorityQueue.this.remove(lastRet); |

263 | if (lastRet < cursor) |

264 | cursor--; |

265 | lastRet = 0; |

266 | expectedModCount = modCount; |

267 | } |

268 | |

269 | final void checkForComodification() { |

270 | if (modCount != expectedModCount) |

271 | throw new ConcurrentModificationException(); |

272 | } |

273 | } |

274 | |

275 | /** |

276 | * Returns the number of elements in this priority queue. |

277 | * |

278 | * @return the number of elements in this priority queue. |

279 | */ |

280 | public int size() { |

281 | return size; |

282 | } |

283 | |

284 | /** |

285 | * Add the specified element to this priority queue. |

286 | * |

287 | * @param element the element to add. |

288 | * @return true |

289 | * @throws ClassCastException if the specified element cannot be compared |

290 | * with elements currently in the priority queue according |

291 | * to the priority queue's ordering. |

292 | * @throws NullPointerException if the specified element is null. |

293 | */ |

294 | public boolean offer(E element) { |

295 | if (element == null) |

296 | throw new NullPointerException(); |

297 | modCount++; |

298 | |

299 | // Grow backing store if necessary |

300 | if (++size == queue.length) { |

301 | E[] newQueue = new E[2 * queue.length]; |

302 | System.arraycopy(queue, 0, newQueue, 0, size); |

303 | queue = newQueue; |

304 | } |

305 | |

306 | queue[size] = element; |

307 | fixUp(size); |

308 | return true; |

309 | } |

310 | |

311 | /** |

312 | * Remove all elements from the priority queue. |

313 | */ |

314 | public void clear() { |

315 | modCount++; |

316 | |

317 | // Null out element references to prevent memory leak |

318 | for (int i=1; i<=size; i++) |

319 | queue[i] = null; |

320 | |

321 | size = 0; |

322 | } |

323 | |

324 | /** |

325 | * Removes and returns the ith element from queue. Recall |

326 | * that queue is one-based, so 1 <= i <= size. |

327 | * |

328 | * XXX: Could further special-case i==size, but is it worth it? |

329 | * XXX: Could special-case i==0, but is it worth it? |

330 | */ |

331 | private E remove(int i) { |

332 | assert i <= size; |

333 | modCount++; |

334 | |

335 | E result = queue[i]; |

336 | queue[i] = queue[size]; |

337 | queue[size--] = null; // Drop extra ref to prevent memory leak |

338 | if (i <= size) |

339 | fixDown(i); |

340 | return result; |

341 | } |

342 | |

343 | /** |

344 | * Establishes the heap invariant (described above) assuming the heap |

345 | * satisfies the invariant except possibly for the leaf-node indexed by k |

346 | * (which may have a nextExecutionTime less than its parent's). |

347 | * |

348 | * This method functions by "promoting" queue[k] up the hierarchy |

349 | * (by swapping it with its parent) repeatedly until queue[k] |

350 | * is greater than or equal to its parent. |

351 | */ |

352 | private void fixUp(int k) { |

353 | if (comparator == null) { |

354 | while (k > 1) { |

355 | int j = k >> 1; |

356 | if (((Comparable)queue[j]).compareTo(queue[k]) <= 0) |

357 | break; |

358 | E tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; |

359 | k = j; |

360 | } |

361 | } else { |

362 | while (k > 1) { |

363 | int j = k >> 1; |

364 | if (comparator.compare(queue[j], queue[k]) <= 0) |

365 | break; |

366 | E tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; |

367 | k = j; |

368 | } |

369 | } |

370 | } |

371 | |

372 | /** |

373 | * Establishes the heap invariant (described above) in the subtree |

374 | * rooted at k, which is assumed to satisfy the heap invariant except |

375 | * possibly for node k itself (which may be greater than its children). |

376 | * |

377 | * This method functions by "demoting" queue[k] down the hierarchy |

378 | * (by swapping it with its smaller child) repeatedly until queue[k] |

379 | * is less than or equal to its children. |

380 | */ |

381 | private void fixDown(int k) { |

382 | int j; |

383 | if (comparator == null) { |

384 | while ((j = k << 1) <= size) { |

385 | if (j<size && ((Comparable)queue[j]).compareTo(queue[j+1]) > 0) |

386 | j++; // j indexes smallest kid |

387 | if (((Comparable)queue[k]).compareTo(queue[j]) <= 0) |

388 | break; |

389 | E tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; |

390 | k = j; |

391 | } |

392 | } else { |

393 | while ((j = k << 1) <= size) { |

394 | if (j < size && comparator.compare(queue[j], queue[j+1]) > 0) |

395 | j++; // j indexes smallest kid |

396 | if (comparator.compare(queue[k], queue[j]) <= 0) |

397 | break; |

398 | E tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; |

399 | k = j; |

400 | } |

401 | } |

402 | } |

403 | |

404 | /** |

405 | * Returns the comparator associated with this priority queue, or |

406 | * <tt>null</tt> if it uses its elements' natural ordering. |

407 | * |

408 | * @return the comparator associated with this priority queue, or |

409 | * <tt>null</tt> if it uses its elements' natural ordering. |

410 | */ |

411 | Comparator<E> comparator() { |

412 | return comparator; |

413 | } |

414 | } |

dl@cs.oswego.edu | ViewVC Help |

Powered by ViewVC 1.1.27 |