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