]>
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 | /// ``` | |
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 | ||
1a4d82fc JJ |
253 | /// Returns the greatest item in the binary heap, or `None` if it is empty. |
254 | /// | |
255 | /// # Examples | |
256 | /// | |
257 | /// ``` | |
258 | /// use std::collections::BinaryHeap; | |
259 | /// let mut heap = BinaryHeap::new(); | |
260 | /// assert_eq!(heap.peek(), None); | |
261 | /// | |
85aaf69f | 262 | /// heap.push(1); |
1a4d82fc JJ |
263 | /// heap.push(5); |
264 | /// heap.push(2); | |
265 | /// assert_eq!(heap.peek(), Some(&5)); | |
266 | /// | |
267 | /// ``` | |
85aaf69f | 268 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
269 | pub fn peek(&self) -> Option<&T> { |
270 | self.data.get(0) | |
271 | } | |
272 | ||
273 | /// Returns the number of elements the binary heap can hold without reallocating. | |
274 | /// | |
275 | /// # Examples | |
276 | /// | |
277 | /// ``` | |
278 | /// use std::collections::BinaryHeap; | |
279 | /// let mut heap = BinaryHeap::with_capacity(100); | |
280 | /// assert!(heap.capacity() >= 100); | |
85aaf69f | 281 | /// heap.push(4); |
1a4d82fc | 282 | /// ``` |
85aaf69f SL |
283 | #[stable(feature = "rust1", since = "1.0.0")] |
284 | pub fn capacity(&self) -> usize { self.data.capacity() } | |
1a4d82fc JJ |
285 | |
286 | /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the | |
287 | /// given `BinaryHeap`. Does nothing if the capacity is already sufficient. | |
288 | /// | |
289 | /// Note that the allocator may give the collection more space than it requests. Therefore | |
290 | /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future | |
291 | /// insertions are expected. | |
292 | /// | |
293 | /// # Panics | |
294 | /// | |
85aaf69f | 295 | /// Panics if the new capacity overflows `usize`. |
1a4d82fc JJ |
296 | /// |
297 | /// # Examples | |
298 | /// | |
299 | /// ``` | |
300 | /// use std::collections::BinaryHeap; | |
301 | /// let mut heap = BinaryHeap::new(); | |
302 | /// heap.reserve_exact(100); | |
303 | /// assert!(heap.capacity() >= 100); | |
85aaf69f | 304 | /// heap.push(4); |
1a4d82fc | 305 | /// ``` |
85aaf69f SL |
306 | #[stable(feature = "rust1", since = "1.0.0")] |
307 | pub fn reserve_exact(&mut self, additional: usize) { | |
1a4d82fc JJ |
308 | self.data.reserve_exact(additional); |
309 | } | |
310 | ||
311 | /// Reserves capacity for at least `additional` more elements to be inserted in the | |
312 | /// `BinaryHeap`. The collection may reserve more space to avoid frequent reallocations. | |
313 | /// | |
314 | /// # Panics | |
315 | /// | |
85aaf69f | 316 | /// Panics if the new capacity overflows `usize`. |
1a4d82fc JJ |
317 | /// |
318 | /// # Examples | |
319 | /// | |
320 | /// ``` | |
321 | /// use std::collections::BinaryHeap; | |
322 | /// let mut heap = BinaryHeap::new(); | |
323 | /// heap.reserve(100); | |
324 | /// assert!(heap.capacity() >= 100); | |
85aaf69f | 325 | /// heap.push(4); |
1a4d82fc | 326 | /// ``` |
85aaf69f SL |
327 | #[stable(feature = "rust1", since = "1.0.0")] |
328 | pub fn reserve(&mut self, additional: usize) { | |
1a4d82fc JJ |
329 | self.data.reserve(additional); |
330 | } | |
331 | ||
332 | /// Discards as much additional capacity as possible. | |
85aaf69f | 333 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
334 | pub fn shrink_to_fit(&mut self) { |
335 | self.data.shrink_to_fit(); | |
336 | } | |
337 | ||
338 | /// Removes the greatest item from the binary heap and returns it, or `None` if it | |
339 | /// is empty. | |
340 | /// | |
341 | /// # Examples | |
342 | /// | |
343 | /// ``` | |
c34b1796 | 344 | /// # #![feature(collections)] |
1a4d82fc | 345 | /// use std::collections::BinaryHeap; |
85aaf69f | 346 | /// let mut heap = BinaryHeap::from_vec(vec![1, 3]); |
1a4d82fc JJ |
347 | /// |
348 | /// assert_eq!(heap.pop(), Some(3)); | |
349 | /// assert_eq!(heap.pop(), Some(1)); | |
350 | /// assert_eq!(heap.pop(), None); | |
351 | /// ``` | |
85aaf69f | 352 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
353 | pub fn pop(&mut self) -> Option<T> { |
354 | self.data.pop().map(|mut item| { | |
355 | if !self.is_empty() { | |
356 | swap(&mut item, &mut self.data[0]); | |
357 | self.sift_down(0); | |
358 | } | |
359 | item | |
360 | }) | |
361 | } | |
362 | ||
363 | /// Pushes an item onto the binary heap. | |
364 | /// | |
365 | /// # Examples | |
366 | /// | |
367 | /// ``` | |
368 | /// use std::collections::BinaryHeap; | |
369 | /// let mut heap = BinaryHeap::new(); | |
85aaf69f | 370 | /// heap.push(3); |
1a4d82fc JJ |
371 | /// heap.push(5); |
372 | /// heap.push(1); | |
373 | /// | |
374 | /// assert_eq!(heap.len(), 3); | |
375 | /// assert_eq!(heap.peek(), Some(&5)); | |
376 | /// ``` | |
85aaf69f | 377 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
378 | pub fn push(&mut self, item: T) { |
379 | let old_len = self.len(); | |
380 | self.data.push(item); | |
381 | self.sift_up(0, old_len); | |
382 | } | |
383 | ||
384 | /// Pushes an item onto the binary heap, then pops the greatest item off the queue in | |
385 | /// an optimized fashion. | |
386 | /// | |
387 | /// # Examples | |
388 | /// | |
389 | /// ``` | |
c34b1796 | 390 | /// # #![feature(collections)] |
1a4d82fc JJ |
391 | /// use std::collections::BinaryHeap; |
392 | /// let mut heap = BinaryHeap::new(); | |
85aaf69f | 393 | /// heap.push(1); |
1a4d82fc JJ |
394 | /// heap.push(5); |
395 | /// | |
396 | /// assert_eq!(heap.push_pop(3), 5); | |
397 | /// assert_eq!(heap.push_pop(9), 9); | |
398 | /// assert_eq!(heap.len(), 2); | |
399 | /// assert_eq!(heap.peek(), Some(&3)); | |
400 | /// ``` | |
401 | pub fn push_pop(&mut self, mut item: T) -> T { | |
402 | match self.data.get_mut(0) { | |
403 | None => return item, | |
404 | Some(top) => if *top > item { | |
405 | swap(&mut item, top); | |
406 | } else { | |
407 | return item; | |
408 | }, | |
409 | } | |
410 | ||
411 | self.sift_down(0); | |
412 | item | |
413 | } | |
414 | ||
415 | /// Pops the greatest item off the binary heap, then pushes an item onto the queue in | |
416 | /// an optimized fashion. The push is done regardless of whether the binary heap | |
417 | /// was empty. | |
418 | /// | |
419 | /// # Examples | |
420 | /// | |
421 | /// ``` | |
c34b1796 | 422 | /// # #![feature(collections)] |
1a4d82fc JJ |
423 | /// use std::collections::BinaryHeap; |
424 | /// let mut heap = BinaryHeap::new(); | |
425 | /// | |
85aaf69f | 426 | /// assert_eq!(heap.replace(1), None); |
1a4d82fc JJ |
427 | /// assert_eq!(heap.replace(3), Some(1)); |
428 | /// assert_eq!(heap.len(), 1); | |
429 | /// assert_eq!(heap.peek(), Some(&3)); | |
430 | /// ``` | |
431 | pub fn replace(&mut self, mut item: T) -> Option<T> { | |
432 | if !self.is_empty() { | |
433 | swap(&mut item, &mut self.data[0]); | |
434 | self.sift_down(0); | |
435 | Some(item) | |
436 | } else { | |
437 | self.push(item); | |
438 | None | |
439 | } | |
440 | } | |
441 | ||
442 | /// Consumes the `BinaryHeap` and returns the underlying vector | |
443 | /// in arbitrary order. | |
444 | /// | |
445 | /// # Examples | |
446 | /// | |
447 | /// ``` | |
c34b1796 | 448 | /// # #![feature(collections)] |
1a4d82fc | 449 | /// use std::collections::BinaryHeap; |
85aaf69f | 450 | /// let heap = BinaryHeap::from_vec(vec![1, 2, 3, 4, 5, 6, 7]); |
1a4d82fc JJ |
451 | /// let vec = heap.into_vec(); |
452 | /// | |
453 | /// // Will print in some order | |
62682a34 | 454 | /// for x in vec { |
1a4d82fc JJ |
455 | /// println!("{}", x); |
456 | /// } | |
457 | /// ``` | |
458 | pub fn into_vec(self) -> Vec<T> { self.data } | |
459 | ||
460 | /// Consumes the `BinaryHeap` and returns a vector in sorted | |
461 | /// (ascending) order. | |
462 | /// | |
463 | /// # Examples | |
464 | /// | |
465 | /// ``` | |
c34b1796 | 466 | /// # #![feature(collections)] |
1a4d82fc JJ |
467 | /// use std::collections::BinaryHeap; |
468 | /// | |
85aaf69f | 469 | /// let mut heap = BinaryHeap::from_vec(vec![1, 2, 4, 5, 7]); |
1a4d82fc JJ |
470 | /// heap.push(6); |
471 | /// heap.push(3); | |
472 | /// | |
473 | /// let vec = heap.into_sorted_vec(); | |
c34b1796 | 474 | /// assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]); |
1a4d82fc JJ |
475 | /// ``` |
476 | pub fn into_sorted_vec(mut self) -> Vec<T> { | |
477 | let mut end = self.len(); | |
478 | while end > 1 { | |
479 | end -= 1; | |
480 | self.data.swap(0, end); | |
481 | self.sift_down_range(0, end); | |
482 | } | |
483 | self.into_vec() | |
484 | } | |
485 | ||
486 | // The implementations of sift_up and sift_down use unsafe blocks in | |
487 | // order to move an element out of the vector (leaving behind a | |
d9579d0f AL |
488 | // hole), shift along the others and move the removed element back into the |
489 | // vector at the final location of the hole. | |
490 | // The `Hole` type is used to represent this, and make sure | |
491 | // the hole is filled back at the end of its scope, even on panic. | |
492 | // Using a hole reduces the constant factor compared to using swaps, | |
493 | // which involves twice as many moves. | |
494 | fn sift_up(&mut self, start: usize, pos: usize) { | |
1a4d82fc | 495 | unsafe { |
d9579d0f AL |
496 | // Take out the value at `pos` and create a hole. |
497 | let mut hole = Hole::new(&mut self.data, pos); | |
1a4d82fc | 498 | |
d9579d0f AL |
499 | while hole.pos() > start { |
500 | let parent = (hole.pos() - 1) / 2; | |
501 | if hole.removed() <= hole.get(parent) { break } | |
502 | hole.move_to(parent); | |
1a4d82fc | 503 | } |
1a4d82fc JJ |
504 | } |
505 | } | |
506 | ||
85aaf69f | 507 | fn sift_down_range(&mut self, mut pos: usize, end: usize) { |
d9579d0f | 508 | let start = pos; |
1a4d82fc | 509 | unsafe { |
d9579d0f | 510 | let mut hole = Hole::new(&mut self.data, pos); |
1a4d82fc JJ |
511 | let mut child = 2 * pos + 1; |
512 | while child < end { | |
513 | let right = child + 1; | |
d9579d0f | 514 | if right < end && !(hole.get(child) > hole.get(right)) { |
1a4d82fc JJ |
515 | child = right; |
516 | } | |
d9579d0f AL |
517 | hole.move_to(child); |
518 | child = 2 * hole.pos() + 1; | |
1a4d82fc JJ |
519 | } |
520 | ||
d9579d0f | 521 | pos = hole.pos; |
1a4d82fc | 522 | } |
d9579d0f | 523 | self.sift_up(start, pos); |
1a4d82fc JJ |
524 | } |
525 | ||
85aaf69f | 526 | fn sift_down(&mut self, pos: usize) { |
1a4d82fc JJ |
527 | let len = self.len(); |
528 | self.sift_down_range(pos, len); | |
529 | } | |
530 | ||
531 | /// Returns the length of the binary heap. | |
85aaf69f SL |
532 | #[stable(feature = "rust1", since = "1.0.0")] |
533 | pub fn len(&self) -> usize { self.data.len() } | |
1a4d82fc JJ |
534 | |
535 | /// Checks if the binary heap is empty. | |
85aaf69f | 536 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
537 | pub fn is_empty(&self) -> bool { self.len() == 0 } |
538 | ||
539 | /// Clears the binary heap, returning an iterator over the removed elements. | |
c34b1796 AL |
540 | /// |
541 | /// The elements are removed in arbitrary order. | |
1a4d82fc | 542 | #[inline] |
62682a34 SL |
543 | #[unstable(feature = "drain", |
544 | reason = "matches collection reform specification, \ | |
545 | waiting for dust to settle")] | |
1a4d82fc | 546 | pub fn drain(&mut self) -> Drain<T> { |
d9579d0f | 547 | Drain { iter: self.data.drain(..) } |
1a4d82fc JJ |
548 | } |
549 | ||
550 | /// Drops all items from the binary heap. | |
85aaf69f | 551 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
552 | pub fn clear(&mut self) { self.drain(); } |
553 | } | |
554 | ||
d9579d0f AL |
555 | /// Hole represents a hole in a slice i.e. an index without valid value |
556 | /// (because it was moved from or duplicated). | |
557 | /// In drop, `Hole` will restore the slice by filling the hole | |
558 | /// position with the value that was originally removed. | |
559 | struct Hole<'a, T: 'a> { | |
560 | data: &'a mut [T], | |
561 | /// `elt` is always `Some` from new until drop. | |
562 | elt: Option<T>, | |
563 | pos: usize, | |
564 | } | |
565 | ||
566 | impl<'a, T> Hole<'a, T> { | |
567 | /// Create a new Hole at index `pos`. | |
568 | fn new(data: &'a mut [T], pos: usize) -> Self { | |
569 | unsafe { | |
570 | let elt = ptr::read(&data[pos]); | |
571 | Hole { | |
572 | data: data, | |
573 | elt: Some(elt), | |
574 | pos: pos, | |
575 | } | |
576 | } | |
577 | } | |
578 | ||
579 | #[inline(always)] | |
580 | fn pos(&self) -> usize { self.pos } | |
581 | ||
582 | /// Return a reference to the element removed | |
583 | #[inline(always)] | |
584 | fn removed(&self) -> &T { | |
585 | self.elt.as_ref().unwrap() | |
586 | } | |
587 | ||
588 | /// Return a reference to the element at `index`. | |
589 | /// | |
590 | /// Panics if the index is out of bounds. | |
591 | /// | |
592 | /// Unsafe because index must not equal pos. | |
593 | #[inline(always)] | |
594 | unsafe fn get(&self, index: usize) -> &T { | |
595 | debug_assert!(index != self.pos); | |
596 | &self.data[index] | |
597 | } | |
598 | ||
599 | /// Move hole to new location | |
600 | /// | |
601 | /// Unsafe because index must not equal pos. | |
602 | #[inline(always)] | |
603 | unsafe fn move_to(&mut self, index: usize) { | |
604 | debug_assert!(index != self.pos); | |
605 | let index_ptr: *const _ = &self.data[index]; | |
606 | let hole_ptr = &mut self.data[self.pos]; | |
607 | ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1); | |
608 | self.pos = index; | |
609 | } | |
610 | } | |
611 | ||
612 | impl<'a, T> Drop for Hole<'a, T> { | |
613 | fn drop(&mut self) { | |
614 | // fill the hole again | |
615 | unsafe { | |
616 | let pos = self.pos; | |
617 | ptr::write(&mut self.data[pos], self.elt.take().unwrap()); | |
618 | } | |
619 | } | |
620 | } | |
621 | ||
1a4d82fc | 622 | /// `BinaryHeap` iterator. |
85aaf69f | 623 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
624 | pub struct Iter <'a, T: 'a> { |
625 | iter: slice::Iter<'a, T>, | |
626 | } | |
627 | ||
628 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` | |
85aaf69f | 629 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
630 | impl<'a, T> Clone for Iter<'a, T> { |
631 | fn clone(&self) -> Iter<'a, T> { | |
632 | Iter { iter: self.iter.clone() } | |
633 | } | |
634 | } | |
635 | ||
85aaf69f | 636 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
637 | impl<'a, T> Iterator for Iter<'a, T> { |
638 | type Item = &'a T; | |
639 | ||
640 | #[inline] | |
641 | fn next(&mut self) -> Option<&'a T> { self.iter.next() } | |
642 | ||
643 | #[inline] | |
85aaf69f | 644 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } |
1a4d82fc JJ |
645 | } |
646 | ||
85aaf69f | 647 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
648 | impl<'a, T> DoubleEndedIterator for Iter<'a, T> { |
649 | #[inline] | |
650 | fn next_back(&mut self) -> Option<&'a T> { self.iter.next_back() } | |
651 | } | |
652 | ||
85aaf69f | 653 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
654 | impl<'a, T> ExactSizeIterator for Iter<'a, T> {} |
655 | ||
656 | /// An iterator that moves out of a `BinaryHeap`. | |
85aaf69f | 657 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
658 | pub struct IntoIter<T> { |
659 | iter: vec::IntoIter<T>, | |
660 | } | |
661 | ||
85aaf69f | 662 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
663 | impl<T> Iterator for IntoIter<T> { |
664 | type Item = T; | |
665 | ||
666 | #[inline] | |
667 | fn next(&mut self) -> Option<T> { self.iter.next() } | |
668 | ||
669 | #[inline] | |
85aaf69f | 670 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } |
1a4d82fc JJ |
671 | } |
672 | ||
85aaf69f | 673 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
674 | impl<T> DoubleEndedIterator for IntoIter<T> { |
675 | #[inline] | |
676 | fn next_back(&mut self) -> Option<T> { self.iter.next_back() } | |
677 | } | |
678 | ||
85aaf69f | 679 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
680 | impl<T> ExactSizeIterator for IntoIter<T> {} |
681 | ||
682 | /// An iterator that drains a `BinaryHeap`. | |
62682a34 | 683 | #[unstable(feature = "drain", reason = "recent addition")] |
1a4d82fc JJ |
684 | pub struct Drain<'a, T: 'a> { |
685 | iter: vec::Drain<'a, T>, | |
686 | } | |
687 | ||
85aaf69f | 688 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
689 | impl<'a, T: 'a> Iterator for Drain<'a, T> { |
690 | type Item = T; | |
691 | ||
692 | #[inline] | |
693 | fn next(&mut self) -> Option<T> { self.iter.next() } | |
694 | ||
695 | #[inline] | |
85aaf69f | 696 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } |
1a4d82fc JJ |
697 | } |
698 | ||
85aaf69f | 699 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
700 | impl<'a, T: 'a> DoubleEndedIterator for Drain<'a, T> { |
701 | #[inline] | |
702 | fn next_back(&mut self) -> Option<T> { self.iter.next_back() } | |
703 | } | |
704 | ||
85aaf69f | 705 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
706 | impl<'a, T: 'a> ExactSizeIterator for Drain<'a, T> {} |
707 | ||
85aaf69f | 708 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 709 | impl<T: Ord> FromIterator<T> for BinaryHeap<T> { |
85aaf69f SL |
710 | fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> BinaryHeap<T> { |
711 | BinaryHeap::from_vec(iter.into_iter().collect()) | |
712 | } | |
713 | } | |
714 | ||
715 | #[stable(feature = "rust1", since = "1.0.0")] | |
716 | impl<T: Ord> IntoIterator for BinaryHeap<T> { | |
717 | type Item = T; | |
718 | type IntoIter = IntoIter<T>; | |
719 | ||
9346a6ac AL |
720 | /// Creates a consuming iterator, that is, one that moves each value out of |
721 | /// the binary heap in arbitrary order. The binary heap cannot be used | |
722 | /// after calling this. | |
723 | /// | |
724 | /// # Examples | |
725 | /// | |
726 | /// ``` | |
727 | /// # #![feature(collections)] | |
728 | /// use std::collections::BinaryHeap; | |
729 | /// let heap = BinaryHeap::from_vec(vec![1, 2, 3, 4]); | |
730 | /// | |
731 | /// // Print 1, 2, 3, 4 in arbitrary order | |
732 | /// for x in heap.into_iter() { | |
733 | /// // x has type i32, not &i32 | |
734 | /// println!("{}", x); | |
735 | /// } | |
736 | /// ``` | |
85aaf69f | 737 | fn into_iter(self) -> IntoIter<T> { |
9346a6ac | 738 | IntoIter { iter: self.data.into_iter() } |
85aaf69f SL |
739 | } |
740 | } | |
741 | ||
742 | #[stable(feature = "rust1", since = "1.0.0")] | |
743 | impl<'a, T> IntoIterator for &'a BinaryHeap<T> where T: Ord { | |
744 | type Item = &'a T; | |
745 | type IntoIter = Iter<'a, T>; | |
746 | ||
747 | fn into_iter(self) -> Iter<'a, T> { | |
748 | self.iter() | |
1a4d82fc JJ |
749 | } |
750 | } | |
751 | ||
85aaf69f | 752 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 753 | impl<T: Ord> Extend<T> for BinaryHeap<T> { |
85aaf69f SL |
754 | fn extend<I: IntoIterator<Item=T>>(&mut self, iterable: I) { |
755 | let iter = iterable.into_iter(); | |
1a4d82fc JJ |
756 | let (lower, _) = iter.size_hint(); |
757 | ||
758 | self.reserve(lower); | |
759 | ||
760 | for elem in iter { | |
761 | self.push(elem); | |
762 | } | |
763 | } | |
764 | } | |
62682a34 SL |
765 | |
766 | #[stable(feature = "extend_ref", since = "1.2.0")] | |
767 | impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BinaryHeap<T> { | |
768 | fn extend<I: IntoIterator<Item=&'a T>>(&mut self, iter: I) { | |
769 | self.extend(iter.into_iter().cloned()); | |
770 | } | |
771 | } |