]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | //! A priority queue implemented with a binary heap. | |
12 | //! | |
13 | //! Insertion and popping the largest element have `O(log n)` time complexity. Checking the largest | |
14 | //! element is `O(1)`. Converting a vector to a binary heap can be done in-place, and has `O(n)` | |
15 | //! complexity. A binary heap can also be converted to a sorted vector in-place, allowing it to | |
16 | //! be used for an `O(n log n)` in-place heapsort. | |
17 | //! | |
18 | //! # Examples | |
19 | //! | |
20 | //! This is a larger example that implements [Dijkstra's algorithm][dijkstra] | |
21 | //! to solve the [shortest path problem][sssp] on a [directed graph][dir_graph]. | |
22 | //! It shows how to use `BinaryHeap` with custom types. | |
23 | //! | |
24 | //! [dijkstra]: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm | |
25 | //! [sssp]: http://en.wikipedia.org/wiki/Shortest_path_problem | |
26 | //! [dir_graph]: http://en.wikipedia.org/wiki/Directed_graph | |
27 | //! | |
28 | //! ``` | |
29 | //! use std::cmp::Ordering; | |
30 | //! use std::collections::BinaryHeap; | |
85aaf69f | 31 | //! use std::usize; |
1a4d82fc | 32 | //! |
c34b1796 | 33 | //! #[derive(Copy, Clone, Eq, PartialEq)] |
1a4d82fc | 34 | //! struct State { |
85aaf69f SL |
35 | //! cost: usize, |
36 | //! position: usize, | |
1a4d82fc JJ |
37 | //! } |
38 | //! | |
39 | //! // The priority queue depends on `Ord`. | |
40 | //! // Explicitly implement the trait so the queue becomes a min-heap | |
41 | //! // instead of a max-heap. | |
42 | //! impl Ord for State { | |
43 | //! fn cmp(&self, other: &State) -> Ordering { | |
44 | //! // Notice that the we flip the ordering here | |
45 | //! other.cost.cmp(&self.cost) | |
46 | //! } | |
47 | //! } | |
48 | //! | |
49 | //! // `PartialOrd` needs to be implemented as well. | |
50 | //! impl PartialOrd for State { | |
51 | //! fn partial_cmp(&self, other: &State) -> Option<Ordering> { | |
52 | //! Some(self.cmp(other)) | |
53 | //! } | |
54 | //! } | |
55 | //! | |
85aaf69f | 56 | //! // Each node is represented as an `usize`, for a shorter implementation. |
1a4d82fc | 57 | //! struct Edge { |
85aaf69f SL |
58 | //! node: usize, |
59 | //! cost: usize, | |
1a4d82fc JJ |
60 | //! } |
61 | //! | |
62 | //! // Dijkstra's shortest path algorithm. | |
63 | //! | |
64 | //! // Start at `start` and use `dist` to track the current shortest distance | |
65 | //! // to each node. This implementation isn't memory-efficient as it may leave duplicate | |
85aaf69f | 66 | //! // nodes in the queue. It also uses `usize::MAX` as a sentinel value, |
1a4d82fc | 67 | //! // for a simpler implementation. |
85aaf69f | 68 | //! fn shortest_path(adj_list: &Vec<Vec<Edge>>, start: usize, goal: usize) -> usize { |
1a4d82fc | 69 | //! // dist[node] = current shortest distance from `start` to `node` |
85aaf69f | 70 | //! let mut dist: Vec<_> = (0..adj_list.len()).map(|_| usize::MAX).collect(); |
1a4d82fc JJ |
71 | //! |
72 | //! let mut heap = BinaryHeap::new(); | |
73 | //! | |
74 | //! // We're at `start`, with a zero cost | |
75 | //! dist[start] = 0; | |
76 | //! heap.push(State { cost: 0, position: start }); | |
77 | //! | |
78 | //! // Examine the frontier with lower cost nodes first (min-heap) | |
79 | //! while let Some(State { cost, position }) = heap.pop() { | |
80 | //! // Alternatively we could have continued to find all shortest paths | |
81 | //! if position == goal { return cost; } | |
82 | //! | |
83 | //! // Important as we may have already found a better way | |
84 | //! if cost > dist[position] { continue; } | |
85 | //! | |
86 | //! // For each node we can reach, see if we can find a way with | |
87 | //! // a lower cost going through this node | |
88 | //! for edge in adj_list[position].iter() { | |
89 | //! let next = State { cost: cost + edge.cost, position: edge.node }; | |
90 | //! | |
91 | //! // If so, add it to the frontier and continue | |
92 | //! if next.cost < dist[next.position] { | |
93 | //! heap.push(next); | |
94 | //! // Relaxation, we have now found a better way | |
95 | //! dist[next.position] = next.cost; | |
96 | //! } | |
97 | //! } | |
98 | //! } | |
99 | //! | |
100 | //! // Goal not reachable | |
85aaf69f | 101 | //! usize::MAX |
1a4d82fc JJ |
102 | //! } |
103 | //! | |
104 | //! fn main() { | |
105 | //! // This is the directed graph we're going to use. | |
106 | //! // The node numbers correspond to the different states, | |
107 | //! // and the edge weights symbolize the cost of moving | |
108 | //! // from one node to another. | |
109 | //! // Note that the edges are one-way. | |
110 | //! // | |
111 | //! // 7 | |
112 | //! // +-----------------+ | |
113 | //! // | | | |
114 | //! // v 1 2 | | |
115 | //! // 0 -----> 1 -----> 3 ---> 4 | |
116 | //! // | ^ ^ ^ | |
117 | //! // | | 1 | | | |
118 | //! // | | | 3 | 1 | |
119 | //! // +------> 2 -------+ | | |
120 | //! // 10 | | | |
121 | //! // +---------------+ | |
122 | //! // | |
123 | //! // The graph is represented as an adjacency list where each index, | |
124 | //! // corresponding to a node value, has a list of outgoing edges. | |
125 | //! // Chosen for its efficiency. | |
126 | //! let graph = vec![ | |
127 | //! // Node 0 | |
128 | //! vec![Edge { node: 2, cost: 10 }, | |
129 | //! Edge { node: 1, cost: 1 }], | |
130 | //! // Node 1 | |
131 | //! vec![Edge { node: 3, cost: 2 }], | |
132 | //! // Node 2 | |
133 | //! vec![Edge { node: 1, cost: 1 }, | |
134 | //! Edge { node: 3, cost: 3 }, | |
135 | //! Edge { node: 4, cost: 1 }], | |
136 | //! // Node 3 | |
137 | //! vec![Edge { node: 0, cost: 7 }, | |
138 | //! Edge { node: 4, cost: 2 }], | |
139 | //! // Node 4 | |
140 | //! vec![]]; | |
141 | //! | |
142 | //! assert_eq!(shortest_path(&graph, 0, 1), 1); | |
143 | //! assert_eq!(shortest_path(&graph, 0, 3), 3); | |
144 | //! assert_eq!(shortest_path(&graph, 3, 0), 7); | |
145 | //! assert_eq!(shortest_path(&graph, 0, 4), 5); | |
85aaf69f | 146 | //! assert_eq!(shortest_path(&graph, 4, 0), usize::MAX); |
1a4d82fc JJ |
147 | //! } |
148 | //! ``` | |
149 | ||
150 | #![allow(missing_docs)] | |
85aaf69f | 151 | #![stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
152 | |
153 | use core::prelude::*; | |
154 | ||
155 | use core::default::Default; | |
85aaf69f | 156 | use core::iter::{FromIterator, IntoIterator}; |
1a4d82fc JJ |
157 | use core::mem::{zeroed, replace, swap}; |
158 | use core::ptr; | |
159 | ||
160 | use slice; | |
161 | use vec::{self, Vec}; | |
162 | ||
163 | /// A priority queue implemented with a binary heap. | |
164 | /// | |
165 | /// This will be a max-heap. | |
c34b1796 AL |
166 | /// |
167 | /// It is a logic error for an item to be modified in such a way that the | |
168 | /// item's ordering relative to any other item, as determined by the `Ord` | |
169 | /// trait, changes while it is in the heap. This is normally only possible | |
170 | /// through `Cell`, `RefCell`, global state, I/O, or unsafe code. | |
1a4d82fc | 171 | #[derive(Clone)] |
85aaf69f | 172 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
173 | pub struct BinaryHeap<T> { |
174 | data: Vec<T>, | |
175 | } | |
176 | ||
85aaf69f | 177 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
178 | impl<T: Ord> Default for BinaryHeap<T> { |
179 | #[inline] | |
180 | fn default() -> BinaryHeap<T> { BinaryHeap::new() } | |
181 | } | |
182 | ||
183 | impl<T: Ord> BinaryHeap<T> { | |
184 | /// Creates an empty `BinaryHeap` as a max-heap. | |
185 | /// | |
186 | /// # Examples | |
187 | /// | |
188 | /// ``` | |
189 | /// use std::collections::BinaryHeap; | |
190 | /// let mut heap = BinaryHeap::new(); | |
85aaf69f | 191 | /// heap.push(4); |
1a4d82fc | 192 | /// ``` |
85aaf69f | 193 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
194 | pub fn new() -> BinaryHeap<T> { BinaryHeap { data: vec![] } } |
195 | ||
196 | /// Creates an empty `BinaryHeap` with a specific capacity. | |
197 | /// This preallocates enough memory for `capacity` elements, | |
198 | /// so that the `BinaryHeap` does not have to be reallocated | |
199 | /// until it contains at least that many values. | |
200 | /// | |
201 | /// # Examples | |
202 | /// | |
203 | /// ``` | |
204 | /// use std::collections::BinaryHeap; | |
205 | /// let mut heap = BinaryHeap::with_capacity(10); | |
85aaf69f | 206 | /// heap.push(4); |
1a4d82fc | 207 | /// ``` |
85aaf69f SL |
208 | #[stable(feature = "rust1", since = "1.0.0")] |
209 | pub fn with_capacity(capacity: usize) -> BinaryHeap<T> { | |
1a4d82fc JJ |
210 | BinaryHeap { data: Vec::with_capacity(capacity) } |
211 | } | |
212 | ||
213 | /// Creates a `BinaryHeap` from a vector. This is sometimes called | |
214 | /// `heapifying` the vector. | |
215 | /// | |
216 | /// # Examples | |
217 | /// | |
218 | /// ``` | |
c34b1796 | 219 | /// # #![feature(collections)] |
1a4d82fc | 220 | /// use std::collections::BinaryHeap; |
85aaf69f | 221 | /// let heap = BinaryHeap::from_vec(vec![9, 1, 2, 7, 3, 2]); |
1a4d82fc JJ |
222 | /// ``` |
223 | pub fn from_vec(vec: Vec<T>) -> BinaryHeap<T> { | |
224 | let mut heap = BinaryHeap { data: vec }; | |
225 | let mut n = heap.len() / 2; | |
226 | while n > 0 { | |
227 | n -= 1; | |
228 | heap.sift_down(n); | |
229 | } | |
230 | heap | |
231 | } | |
232 | ||
233 | /// Returns an iterator visiting all values in the underlying vector, in | |
234 | /// arbitrary order. | |
235 | /// | |
236 | /// # Examples | |
237 | /// | |
238 | /// ``` | |
c34b1796 | 239 | /// # #![feature(collections)] |
1a4d82fc | 240 | /// use std::collections::BinaryHeap; |
85aaf69f | 241 | /// let heap = BinaryHeap::from_vec(vec![1, 2, 3, 4]); |
1a4d82fc JJ |
242 | /// |
243 | /// // Print 1, 2, 3, 4 in arbitrary order | |
244 | /// for x in heap.iter() { | |
245 | /// println!("{}", x); | |
246 | /// } | |
247 | /// ``` | |
85aaf69f | 248 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
249 | pub fn iter(&self) -> Iter<T> { |
250 | Iter { iter: self.data.iter() } | |
251 | } | |
252 | ||
253 | /// Creates a consuming iterator, that is, one that moves each value out of | |
254 | /// the binary heap in arbitrary order. The binary heap cannot be used | |
255 | /// after calling this. | |
256 | /// | |
257 | /// # Examples | |
258 | /// | |
259 | /// ``` | |
c34b1796 | 260 | /// # #![feature(collections)] |
1a4d82fc | 261 | /// use std::collections::BinaryHeap; |
85aaf69f | 262 | /// let heap = BinaryHeap::from_vec(vec![1, 2, 3, 4]); |
1a4d82fc JJ |
263 | /// |
264 | /// // Print 1, 2, 3, 4 in arbitrary order | |
265 | /// for x in heap.into_iter() { | |
85aaf69f | 266 | /// // x has type i32, not &i32 |
1a4d82fc JJ |
267 | /// println!("{}", x); |
268 | /// } | |
269 | /// ``` | |
85aaf69f | 270 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
271 | pub fn into_iter(self) -> IntoIter<T> { |
272 | IntoIter { iter: self.data.into_iter() } | |
273 | } | |
274 | ||
275 | /// Returns the greatest item in the binary heap, or `None` if it is empty. | |
276 | /// | |
277 | /// # Examples | |
278 | /// | |
279 | /// ``` | |
280 | /// use std::collections::BinaryHeap; | |
281 | /// let mut heap = BinaryHeap::new(); | |
282 | /// assert_eq!(heap.peek(), None); | |
283 | /// | |
85aaf69f | 284 | /// heap.push(1); |
1a4d82fc JJ |
285 | /// heap.push(5); |
286 | /// heap.push(2); | |
287 | /// assert_eq!(heap.peek(), Some(&5)); | |
288 | /// | |
289 | /// ``` | |
85aaf69f | 290 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
291 | pub fn peek(&self) -> Option<&T> { |
292 | self.data.get(0) | |
293 | } | |
294 | ||
295 | /// Returns the number of elements the binary heap can hold without reallocating. | |
296 | /// | |
297 | /// # Examples | |
298 | /// | |
299 | /// ``` | |
300 | /// use std::collections::BinaryHeap; | |
301 | /// let mut heap = BinaryHeap::with_capacity(100); | |
302 | /// assert!(heap.capacity() >= 100); | |
85aaf69f | 303 | /// heap.push(4); |
1a4d82fc | 304 | /// ``` |
85aaf69f SL |
305 | #[stable(feature = "rust1", since = "1.0.0")] |
306 | pub fn capacity(&self) -> usize { self.data.capacity() } | |
1a4d82fc JJ |
307 | |
308 | /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the | |
309 | /// given `BinaryHeap`. Does nothing if the capacity is already sufficient. | |
310 | /// | |
311 | /// Note that the allocator may give the collection more space than it requests. Therefore | |
312 | /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future | |
313 | /// insertions are expected. | |
314 | /// | |
315 | /// # Panics | |
316 | /// | |
85aaf69f | 317 | /// Panics if the new capacity overflows `usize`. |
1a4d82fc JJ |
318 | /// |
319 | /// # Examples | |
320 | /// | |
321 | /// ``` | |
322 | /// use std::collections::BinaryHeap; | |
323 | /// let mut heap = BinaryHeap::new(); | |
324 | /// heap.reserve_exact(100); | |
325 | /// assert!(heap.capacity() >= 100); | |
85aaf69f | 326 | /// heap.push(4); |
1a4d82fc | 327 | /// ``` |
85aaf69f SL |
328 | #[stable(feature = "rust1", since = "1.0.0")] |
329 | pub fn reserve_exact(&mut self, additional: usize) { | |
1a4d82fc JJ |
330 | self.data.reserve_exact(additional); |
331 | } | |
332 | ||
333 | /// Reserves capacity for at least `additional` more elements to be inserted in the | |
334 | /// `BinaryHeap`. The collection may reserve more space to avoid frequent reallocations. | |
335 | /// | |
336 | /// # Panics | |
337 | /// | |
85aaf69f | 338 | /// Panics if the new capacity overflows `usize`. |
1a4d82fc JJ |
339 | /// |
340 | /// # Examples | |
341 | /// | |
342 | /// ``` | |
343 | /// use std::collections::BinaryHeap; | |
344 | /// let mut heap = BinaryHeap::new(); | |
345 | /// heap.reserve(100); | |
346 | /// assert!(heap.capacity() >= 100); | |
85aaf69f | 347 | /// heap.push(4); |
1a4d82fc | 348 | /// ``` |
85aaf69f SL |
349 | #[stable(feature = "rust1", since = "1.0.0")] |
350 | pub fn reserve(&mut self, additional: usize) { | |
1a4d82fc JJ |
351 | self.data.reserve(additional); |
352 | } | |
353 | ||
354 | /// Discards as much additional capacity as possible. | |
85aaf69f | 355 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
356 | pub fn shrink_to_fit(&mut self) { |
357 | self.data.shrink_to_fit(); | |
358 | } | |
359 | ||
360 | /// Removes the greatest item from the binary heap and returns it, or `None` if it | |
361 | /// is empty. | |
362 | /// | |
363 | /// # Examples | |
364 | /// | |
365 | /// ``` | |
c34b1796 | 366 | /// # #![feature(collections)] |
1a4d82fc | 367 | /// use std::collections::BinaryHeap; |
85aaf69f | 368 | /// let mut heap = BinaryHeap::from_vec(vec![1, 3]); |
1a4d82fc JJ |
369 | /// |
370 | /// assert_eq!(heap.pop(), Some(3)); | |
371 | /// assert_eq!(heap.pop(), Some(1)); | |
372 | /// assert_eq!(heap.pop(), None); | |
373 | /// ``` | |
85aaf69f | 374 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
375 | pub fn pop(&mut self) -> Option<T> { |
376 | self.data.pop().map(|mut item| { | |
377 | if !self.is_empty() { | |
378 | swap(&mut item, &mut self.data[0]); | |
379 | self.sift_down(0); | |
380 | } | |
381 | item | |
382 | }) | |
383 | } | |
384 | ||
385 | /// Pushes an item onto the binary heap. | |
386 | /// | |
387 | /// # Examples | |
388 | /// | |
389 | /// ``` | |
390 | /// use std::collections::BinaryHeap; | |
391 | /// let mut heap = BinaryHeap::new(); | |
85aaf69f | 392 | /// heap.push(3); |
1a4d82fc JJ |
393 | /// heap.push(5); |
394 | /// heap.push(1); | |
395 | /// | |
396 | /// assert_eq!(heap.len(), 3); | |
397 | /// assert_eq!(heap.peek(), Some(&5)); | |
398 | /// ``` | |
85aaf69f | 399 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
400 | pub fn push(&mut self, item: T) { |
401 | let old_len = self.len(); | |
402 | self.data.push(item); | |
403 | self.sift_up(0, old_len); | |
404 | } | |
405 | ||
406 | /// Pushes an item onto the binary heap, then pops the greatest item off the queue in | |
407 | /// an optimized fashion. | |
408 | /// | |
409 | /// # Examples | |
410 | /// | |
411 | /// ``` | |
c34b1796 | 412 | /// # #![feature(collections)] |
1a4d82fc JJ |
413 | /// use std::collections::BinaryHeap; |
414 | /// let mut heap = BinaryHeap::new(); | |
85aaf69f | 415 | /// heap.push(1); |
1a4d82fc JJ |
416 | /// heap.push(5); |
417 | /// | |
418 | /// assert_eq!(heap.push_pop(3), 5); | |
419 | /// assert_eq!(heap.push_pop(9), 9); | |
420 | /// assert_eq!(heap.len(), 2); | |
421 | /// assert_eq!(heap.peek(), Some(&3)); | |
422 | /// ``` | |
423 | pub fn push_pop(&mut self, mut item: T) -> T { | |
424 | match self.data.get_mut(0) { | |
425 | None => return item, | |
426 | Some(top) => if *top > item { | |
427 | swap(&mut item, top); | |
428 | } else { | |
429 | return item; | |
430 | }, | |
431 | } | |
432 | ||
433 | self.sift_down(0); | |
434 | item | |
435 | } | |
436 | ||
437 | /// Pops the greatest item off the binary heap, then pushes an item onto the queue in | |
438 | /// an optimized fashion. The push is done regardless of whether the binary heap | |
439 | /// was empty. | |
440 | /// | |
441 | /// # Examples | |
442 | /// | |
443 | /// ``` | |
c34b1796 | 444 | /// # #![feature(collections)] |
1a4d82fc JJ |
445 | /// use std::collections::BinaryHeap; |
446 | /// let mut heap = BinaryHeap::new(); | |
447 | /// | |
85aaf69f | 448 | /// assert_eq!(heap.replace(1), None); |
1a4d82fc JJ |
449 | /// assert_eq!(heap.replace(3), Some(1)); |
450 | /// assert_eq!(heap.len(), 1); | |
451 | /// assert_eq!(heap.peek(), Some(&3)); | |
452 | /// ``` | |
453 | pub fn replace(&mut self, mut item: T) -> Option<T> { | |
454 | if !self.is_empty() { | |
455 | swap(&mut item, &mut self.data[0]); | |
456 | self.sift_down(0); | |
457 | Some(item) | |
458 | } else { | |
459 | self.push(item); | |
460 | None | |
461 | } | |
462 | } | |
463 | ||
464 | /// Consumes the `BinaryHeap` and returns the underlying vector | |
465 | /// in arbitrary order. | |
466 | /// | |
467 | /// # Examples | |
468 | /// | |
469 | /// ``` | |
c34b1796 | 470 | /// # #![feature(collections)] |
1a4d82fc | 471 | /// use std::collections::BinaryHeap; |
85aaf69f | 472 | /// let heap = BinaryHeap::from_vec(vec![1, 2, 3, 4, 5, 6, 7]); |
1a4d82fc JJ |
473 | /// let vec = heap.into_vec(); |
474 | /// | |
475 | /// // Will print in some order | |
476 | /// for x in vec.iter() { | |
477 | /// println!("{}", x); | |
478 | /// } | |
479 | /// ``` | |
480 | pub fn into_vec(self) -> Vec<T> { self.data } | |
481 | ||
482 | /// Consumes the `BinaryHeap` and returns a vector in sorted | |
483 | /// (ascending) order. | |
484 | /// | |
485 | /// # Examples | |
486 | /// | |
487 | /// ``` | |
c34b1796 | 488 | /// # #![feature(collections)] |
1a4d82fc JJ |
489 | /// use std::collections::BinaryHeap; |
490 | /// | |
85aaf69f | 491 | /// let mut heap = BinaryHeap::from_vec(vec![1, 2, 4, 5, 7]); |
1a4d82fc JJ |
492 | /// heap.push(6); |
493 | /// heap.push(3); | |
494 | /// | |
495 | /// let vec = heap.into_sorted_vec(); | |
c34b1796 | 496 | /// assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]); |
1a4d82fc JJ |
497 | /// ``` |
498 | pub fn into_sorted_vec(mut self) -> Vec<T> { | |
499 | let mut end = self.len(); | |
500 | while end > 1 { | |
501 | end -= 1; | |
502 | self.data.swap(0, end); | |
503 | self.sift_down_range(0, end); | |
504 | } | |
505 | self.into_vec() | |
506 | } | |
507 | ||
508 | // The implementations of sift_up and sift_down use unsafe blocks in | |
509 | // order to move an element out of the vector (leaving behind a | |
510 | // zeroed element), shift along the others and move it back into the | |
511 | // vector over the junk element. This reduces the constant factor | |
512 | // compared to using swaps, which involves twice as many moves. | |
85aaf69f | 513 | fn sift_up(&mut self, start: usize, mut pos: usize) { |
1a4d82fc JJ |
514 | unsafe { |
515 | let new = replace(&mut self.data[pos], zeroed()); | |
516 | ||
517 | while pos > start { | |
518 | let parent = (pos - 1) >> 1; | |
519 | ||
520 | if new <= self.data[parent] { break; } | |
521 | ||
522 | let x = replace(&mut self.data[parent], zeroed()); | |
523 | ptr::write(&mut self.data[pos], x); | |
524 | pos = parent; | |
525 | } | |
526 | ptr::write(&mut self.data[pos], new); | |
527 | } | |
528 | } | |
529 | ||
85aaf69f | 530 | fn sift_down_range(&mut self, mut pos: usize, end: usize) { |
1a4d82fc JJ |
531 | unsafe { |
532 | let start = pos; | |
533 | let new = replace(&mut self.data[pos], zeroed()); | |
534 | ||
535 | let mut child = 2 * pos + 1; | |
536 | while child < end { | |
537 | let right = child + 1; | |
538 | if right < end && !(self.data[child] > self.data[right]) { | |
539 | child = right; | |
540 | } | |
541 | let x = replace(&mut self.data[child], zeroed()); | |
542 | ptr::write(&mut self.data[pos], x); | |
543 | pos = child; | |
544 | child = 2 * pos + 1; | |
545 | } | |
546 | ||
547 | ptr::write(&mut self.data[pos], new); | |
548 | self.sift_up(start, pos); | |
549 | } | |
550 | } | |
551 | ||
85aaf69f | 552 | fn sift_down(&mut self, pos: usize) { |
1a4d82fc JJ |
553 | let len = self.len(); |
554 | self.sift_down_range(pos, len); | |
555 | } | |
556 | ||
557 | /// Returns the length of the binary heap. | |
85aaf69f SL |
558 | #[stable(feature = "rust1", since = "1.0.0")] |
559 | pub fn len(&self) -> usize { self.data.len() } | |
1a4d82fc JJ |
560 | |
561 | /// Checks if the binary heap is empty. | |
85aaf69f | 562 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
563 | pub fn is_empty(&self) -> bool { self.len() == 0 } |
564 | ||
565 | /// Clears the binary heap, returning an iterator over the removed elements. | |
c34b1796 AL |
566 | /// |
567 | /// The elements are removed in arbitrary order. | |
1a4d82fc | 568 | #[inline] |
85aaf69f SL |
569 | #[unstable(feature = "collections", |
570 | reason = "matches collection reform specification, waiting for dust to settle")] | |
1a4d82fc JJ |
571 | pub fn drain(&mut self) -> Drain<T> { |
572 | Drain { iter: self.data.drain() } | |
573 | } | |
574 | ||
575 | /// Drops all items from the binary heap. | |
85aaf69f | 576 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
577 | pub fn clear(&mut self) { self.drain(); } |
578 | } | |
579 | ||
580 | /// `BinaryHeap` iterator. | |
85aaf69f | 581 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
582 | pub struct Iter <'a, T: 'a> { |
583 | iter: slice::Iter<'a, T>, | |
584 | } | |
585 | ||
586 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` | |
85aaf69f | 587 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
588 | impl<'a, T> Clone for Iter<'a, T> { |
589 | fn clone(&self) -> Iter<'a, T> { | |
590 | Iter { iter: self.iter.clone() } | |
591 | } | |
592 | } | |
593 | ||
85aaf69f | 594 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
595 | impl<'a, T> Iterator for Iter<'a, T> { |
596 | type Item = &'a T; | |
597 | ||
598 | #[inline] | |
599 | fn next(&mut self) -> Option<&'a T> { self.iter.next() } | |
600 | ||
601 | #[inline] | |
85aaf69f | 602 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } |
1a4d82fc JJ |
603 | } |
604 | ||
85aaf69f | 605 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
606 | impl<'a, T> DoubleEndedIterator for Iter<'a, T> { |
607 | #[inline] | |
608 | fn next_back(&mut self) -> Option<&'a T> { self.iter.next_back() } | |
609 | } | |
610 | ||
85aaf69f | 611 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
612 | impl<'a, T> ExactSizeIterator for Iter<'a, T> {} |
613 | ||
614 | /// An iterator that moves out of a `BinaryHeap`. | |
85aaf69f | 615 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
616 | pub struct IntoIter<T> { |
617 | iter: vec::IntoIter<T>, | |
618 | } | |
619 | ||
85aaf69f | 620 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
621 | impl<T> Iterator for IntoIter<T> { |
622 | type Item = T; | |
623 | ||
624 | #[inline] | |
625 | fn next(&mut self) -> Option<T> { self.iter.next() } | |
626 | ||
627 | #[inline] | |
85aaf69f | 628 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } |
1a4d82fc JJ |
629 | } |
630 | ||
85aaf69f | 631 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
632 | impl<T> DoubleEndedIterator for IntoIter<T> { |
633 | #[inline] | |
634 | fn next_back(&mut self) -> Option<T> { self.iter.next_back() } | |
635 | } | |
636 | ||
85aaf69f | 637 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
638 | impl<T> ExactSizeIterator for IntoIter<T> {} |
639 | ||
640 | /// An iterator that drains a `BinaryHeap`. | |
85aaf69f | 641 | #[unstable(feature = "collections", reason = "recent addition")] |
1a4d82fc JJ |
642 | pub struct Drain<'a, T: 'a> { |
643 | iter: vec::Drain<'a, T>, | |
644 | } | |
645 | ||
85aaf69f | 646 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
647 | impl<'a, T: 'a> Iterator for Drain<'a, T> { |
648 | type Item = T; | |
649 | ||
650 | #[inline] | |
651 | fn next(&mut self) -> Option<T> { self.iter.next() } | |
652 | ||
653 | #[inline] | |
85aaf69f | 654 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } |
1a4d82fc JJ |
655 | } |
656 | ||
85aaf69f | 657 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
658 | impl<'a, T: 'a> DoubleEndedIterator for Drain<'a, T> { |
659 | #[inline] | |
660 | fn next_back(&mut self) -> Option<T> { self.iter.next_back() } | |
661 | } | |
662 | ||
85aaf69f | 663 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
664 | impl<'a, T: 'a> ExactSizeIterator for Drain<'a, T> {} |
665 | ||
85aaf69f | 666 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 667 | impl<T: Ord> FromIterator<T> for BinaryHeap<T> { |
85aaf69f SL |
668 | fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> BinaryHeap<T> { |
669 | BinaryHeap::from_vec(iter.into_iter().collect()) | |
670 | } | |
671 | } | |
672 | ||
673 | #[stable(feature = "rust1", since = "1.0.0")] | |
674 | impl<T: Ord> IntoIterator for BinaryHeap<T> { | |
675 | type Item = T; | |
676 | type IntoIter = IntoIter<T>; | |
677 | ||
678 | fn into_iter(self) -> IntoIter<T> { | |
679 | self.into_iter() | |
680 | } | |
681 | } | |
682 | ||
683 | #[stable(feature = "rust1", since = "1.0.0")] | |
684 | impl<'a, T> IntoIterator for &'a BinaryHeap<T> where T: Ord { | |
685 | type Item = &'a T; | |
686 | type IntoIter = Iter<'a, T>; | |
687 | ||
688 | fn into_iter(self) -> Iter<'a, T> { | |
689 | self.iter() | |
1a4d82fc JJ |
690 | } |
691 | } | |
692 | ||
85aaf69f | 693 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 694 | impl<T: Ord> Extend<T> for BinaryHeap<T> { |
85aaf69f SL |
695 | fn extend<I: IntoIterator<Item=T>>(&mut self, iterable: I) { |
696 | let iter = iterable.into_iter(); | |
1a4d82fc JJ |
697 | let (lower, _) = iter.size_hint(); |
698 | ||
699 | self.reserve(lower); | |
700 | ||
701 | for elem in iter { | |
702 | self.push(elem); | |
703 | } | |
704 | } | |
705 | } |