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.
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.
11 //! A priority queue implemented with a binary heap
13 #![allow(missing_doc)]
15 use std::clone::Clone;
16 use std::mem::{overwrite, zeroed, replace, swap};
19 /// A priority queue implemented with a binary heap
21 pub struct PriorityQueue<T> {
25 impl<T: Ord> Container for PriorityQueue<T> {
26 /// Returns the length of the queue
27 fn len(&self) -> uint { self.data.len() }
30 impl<T: Ord> Mutable for PriorityQueue<T> {
31 /// Drop all items from the queue
32 fn clear(&mut self) { self.data.truncate(0) }
35 impl<T: Ord> PriorityQueue<T> {
36 /// An iterator visiting all values in underlying vector, in
38 pub fn iter<'a>(&'a self) -> Items<'a, T> {
39 Items { iter: self.data.iter() }
42 /// Returns the greatest item in a queue or None if it is empty
43 pub fn top<'a>(&'a self) -> Option<&'a T> {
44 if self.is_empty() { None } else { Some(self.data.get(0)) }
47 #[deprecated="renamed to `top`"]
48 pub fn maybe_top<'a>(&'a self) -> Option<&'a T> { self.top() }
50 /// Returns the number of elements the queue can hold without reallocating
51 pub fn capacity(&self) -> uint { self.data.capacity() }
53 /// Reserve capacity for exactly n elements in the PriorityQueue.
54 /// Do nothing if the capacity is already sufficient.
55 pub fn reserve_exact(&mut self, n: uint) { self.data.reserve_exact(n) }
57 /// Reserve capacity for at least n elements in the PriorityQueue.
58 /// Do nothing if the capacity is already sufficient.
59 pub fn reserve(&mut self, n: uint) {
63 /// Remove the greatest item from a queue and return it, or `None` if it is
65 pub fn pop(&mut self) -> Option<T> {
66 match self.data.pop() {
70 swap(&mut item, self.data.get_mut(0));
78 #[deprecated="renamed to `pop`"]
79 pub fn maybe_pop(&mut self) -> Option<T> { self.pop() }
81 /// Push an item onto the queue
82 pub fn push(&mut self, item: T) {
84 let new_len = self.len() - 1;
85 self.siftup(0, new_len);
88 /// Optimized version of a push followed by a pop
89 pub fn push_pop(&mut self, mut item: T) -> T {
90 if !self.is_empty() && *self.top().unwrap() > item {
91 swap(&mut item, self.data.get_mut(0));
97 /// Optimized version of a pop followed by a push. The push is done
98 /// regardless of whether the queue is empty.
99 pub fn replace(&mut self, mut item: T) -> Option<T> {
100 if !self.is_empty() {
101 swap(&mut item, self.data.get_mut(0));
111 #[deprecated="renamed to `into_vec`"]
112 fn to_vec(self) -> Vec<T> { self.into_vec() }
115 #[deprecated="renamed to `into_sorted_vec`"]
116 fn to_sorted_vec(self) -> Vec<T> { self.into_sorted_vec() }
118 /// Consume the PriorityQueue and return the underlying vector
119 pub fn into_vec(self) -> Vec<T> { let PriorityQueue{data: v} = self; v }
121 /// Consume the PriorityQueue and return a vector in sorted
122 /// (ascending) order
123 pub fn into_sorted_vec(self) -> Vec<T> {
125 let mut end = q.len();
128 q.data.as_mut_slice().swap(0, end);
129 q.siftdown_range(0, end)
134 /// Create an empty PriorityQueue
135 pub fn new() -> PriorityQueue<T> { PriorityQueue{data: vec!(),} }
137 /// Create an empty PriorityQueue with capacity `capacity`
138 pub fn with_capacity(capacity: uint) -> PriorityQueue<T> {
139 PriorityQueue { data: Vec::with_capacity(capacity) }
142 /// Create a PriorityQueue from a vector (heapify)
143 pub fn from_vec(xs: Vec<T>) -> PriorityQueue<T> {
144 let mut q = PriorityQueue{data: xs,};
145 let mut n = q.len() / 2;
153 // The implementations of siftup and siftdown use unsafe blocks in
154 // order to move an element out of the vector (leaving behind a
155 // zeroed element), shift along the others and move it back into the
156 // vector over the junk element. This reduces the constant factor
157 // compared to using swaps, which involves twice as many moves.
158 fn siftup(&mut self, start: uint, mut pos: uint) {
160 let new = replace(self.data.get_mut(pos), zeroed());
163 let parent = (pos - 1) >> 1;
164 if new > *self.data.get(parent) {
165 let x = replace(self.data.get_mut(parent), zeroed());
166 overwrite(self.data.get_mut(pos), x);
172 overwrite(self.data.get_mut(pos), new);
176 fn siftdown_range(&mut self, mut pos: uint, end: uint) {
179 let new = replace(self.data.get_mut(pos), zeroed());
181 let mut child = 2 * pos + 1;
183 let right = child + 1;
184 if right < end && !(*self.data.get(child) > *self.data.get(right)) {
187 let x = replace(self.data.get_mut(child), zeroed());
188 overwrite(self.data.get_mut(pos), x);
193 overwrite(self.data.get_mut(pos), new);
194 self.siftup(start, pos);
198 fn siftdown(&mut self, pos: uint) {
199 let len = self.len();
200 self.siftdown_range(pos, len);
204 /// PriorityQueue iterator
205 pub struct Items <'a, T> {
206 iter: slice::Items<'a, T>,
209 impl<'a, T> Iterator<&'a T> for Items<'a, T> {
211 fn next(&mut self) -> Option<(&'a T)> { self.iter.next() }
214 fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
217 impl<T: Ord> FromIterator<T> for PriorityQueue<T> {
218 fn from_iter<Iter: Iterator<T>>(iter: Iter) -> PriorityQueue<T> {
219 let mut q = PriorityQueue::new();
225 impl<T: Ord> Extendable<T> for PriorityQueue<T> {
226 fn extend<Iter: Iterator<T>>(&mut self, mut iter: Iter) {
227 let (lower, _) = iter.size_hint();
229 let len = self.capacity();
230 self.reserve(len + lower);
240 use priority_queue::PriorityQueue;
244 let data = vec!(5, 9, 3);
245 let iterout = [9, 5, 3];
246 let pq = PriorityQueue::from_vec(data);
248 for el in pq.iter() {
249 assert_eq!(*el, iterout[i]);
255 fn test_top_and_pop() {
256 let data = vec!(2u, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1);
257 let mut sorted = data.clone();
259 let mut heap = PriorityQueue::from_vec(data);
260 while !heap.is_empty() {
261 assert_eq!(heap.top().unwrap(), sorted.last().unwrap());
262 assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
268 let mut heap = PriorityQueue::from_vec(vec!(2, 4, 9));
269 assert_eq!(heap.len(), 3);
270 assert!(*heap.top().unwrap() == 9);
272 assert_eq!(heap.len(), 4);
273 assert!(*heap.top().unwrap() == 11);
275 assert_eq!(heap.len(), 5);
276 assert!(*heap.top().unwrap() == 11);
278 assert_eq!(heap.len(), 6);
279 assert!(*heap.top().unwrap() == 27);
281 assert_eq!(heap.len(), 7);
282 assert!(*heap.top().unwrap() == 27);
284 assert_eq!(heap.len(), 8);
285 assert!(*heap.top().unwrap() == 103);
289 fn test_push_unique() {
290 let mut heap = PriorityQueue::from_vec(vec!(box 2, box 4, box 9));
291 assert_eq!(heap.len(), 3);
292 assert!(*heap.top().unwrap() == box 9);
294 assert_eq!(heap.len(), 4);
295 assert!(*heap.top().unwrap() == box 11);
297 assert_eq!(heap.len(), 5);
298 assert!(*heap.top().unwrap() == box 11);
300 assert_eq!(heap.len(), 6);
301 assert!(*heap.top().unwrap() == box 27);
303 assert_eq!(heap.len(), 7);
304 assert!(*heap.top().unwrap() == box 27);
306 assert_eq!(heap.len(), 8);
307 assert!(*heap.top().unwrap() == box 103);
312 let mut heap = PriorityQueue::from_vec(vec!(5, 5, 2, 1, 3));
313 assert_eq!(heap.len(), 5);
314 assert_eq!(heap.push_pop(6), 6);
315 assert_eq!(heap.len(), 5);
316 assert_eq!(heap.push_pop(0), 5);
317 assert_eq!(heap.len(), 5);
318 assert_eq!(heap.push_pop(4), 5);
319 assert_eq!(heap.len(), 5);
320 assert_eq!(heap.push_pop(1), 4);
321 assert_eq!(heap.len(), 5);
326 let mut heap = PriorityQueue::from_vec(vec!(5, 5, 2, 1, 3));
327 assert_eq!(heap.len(), 5);
328 assert_eq!(heap.replace(6).unwrap(), 5);
329 assert_eq!(heap.len(), 5);
330 assert_eq!(heap.replace(0).unwrap(), 6);
331 assert_eq!(heap.len(), 5);
332 assert_eq!(heap.replace(4).unwrap(), 5);
333 assert_eq!(heap.len(), 5);
334 assert_eq!(heap.replace(1).unwrap(), 4);
335 assert_eq!(heap.len(), 5);
338 fn check_to_vec(mut data: Vec<int>) {
339 let heap = PriorityQueue::from_vec(data.clone());
340 let mut v = heap.clone().into_vec();
345 assert_eq!(heap.into_sorted_vec(), data);
350 check_to_vec(vec!());
351 check_to_vec(vec!(5));
352 check_to_vec(vec!(3, 2));
353 check_to_vec(vec!(2, 3));
354 check_to_vec(vec!(5, 1, 2));
355 check_to_vec(vec!(1, 100, 2, 3));
356 check_to_vec(vec!(1, 3, 5, 7, 9, 2, 4, 6, 8, 0));
357 check_to_vec(vec!(2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1));
358 check_to_vec(vec!(9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0));
359 check_to_vec(vec!(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
360 check_to_vec(vec!(10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0));
361 check_to_vec(vec!(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2));
362 check_to_vec(vec!(5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1));
366 fn test_empty_pop() {
367 let mut heap: PriorityQueue<int> = PriorityQueue::new();
368 assert!(heap.pop().is_none());
372 fn test_empty_top() {
373 let empty: PriorityQueue<int> = PriorityQueue::new();
374 assert!(empty.top().is_none());
378 fn test_empty_replace() {
379 let mut heap: PriorityQueue<int> = PriorityQueue::new();
380 heap.replace(5).is_none();
384 fn test_from_iter() {
385 let xs = vec!(9u, 8, 7, 6, 5, 4, 3, 2, 1);
387 let mut q: PriorityQueue<uint> = xs.as_slice().iter().rev().map(|&x| x).collect();
389 for &x in xs.iter() {
390 assert_eq!(q.pop().unwrap(), x);