diff options
Diffstat (limited to 'src/libstd/priority_queue.rs')
| -rw-r--r-- | src/libstd/priority_queue.rs | 37 |
1 files changed, 17 insertions, 20 deletions
diff --git a/src/libstd/priority_queue.rs b/src/libstd/priority_queue.rs index c744ba1ca5c..31d6e04ae62 100644 --- a/src/libstd/priority_queue.rs +++ b/src/libstd/priority_queue.rs @@ -76,6 +76,21 @@ impl <T: Copy Ord> PriorityQueue<T> { ret } + /// Consume the PriorityQueue and return the underlying vector + pure fn to_vec(self) -> ~[T] { let PriorityQueue{data: v} = self; v } + + /// Consume the PriorityQueue and return a vector in sorted (ascending) order + pure fn to_sorted_vec(self) -> ~[T] { + let mut q = self; + let mut end = q.len() - 1; + while end > 0 { + q.data[end] <-> q.data[0]; + end -= 1; + unsafe { q.siftup_range(0, end) } // purity-checking workaround + } + q.to_vec() + } + priv fn siftdown(&mut self, startpos: uint, pos: uint) { let mut pos = pos; let newitem = self.data[pos]; @@ -118,24 +133,6 @@ impl <T: Copy Ord> PriorityQueue<T> { } } -/// Consume the PriorityQueue and return the underlying vector -pub pure fn to_vec<T: Copy Ord>(q: PriorityQueue<T>) -> ~[T] { - let PriorityQueue{data: v} = q; - v -} - -/// Consume the PriorityQueue and return a vector in sorted (ascending) order -pub pure fn to_sorted_vec<T: Copy Ord>(q: PriorityQueue<T>) -> ~[T] { - let mut q = q; - let mut end = q.len() - 1; - while end > 0 { - q.data[end] <-> q.data[0]; - end -= 1; - unsafe { q.siftup_range(0, end) } // purity-checking workaround - } - to_vec(q) -} - pub pure fn from_vec<T: Copy Ord>(xs: ~[T]) -> PriorityQueue<T> { let mut q = PriorityQueue{data: xs,}; let mut n = q.len() / 2; @@ -215,7 +212,7 @@ mod tests { #[test] fn test_to_sorted_vec() { let data = ~[2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; - assert to_sorted_vec(from_vec(data)) == merge_sort(data, le); + assert from_vec(data).to_sorted_vec() == merge_sort(data, le); } #[test] @@ -248,6 +245,6 @@ mod tests { fn test_to_vec() { let data = ~[1, 3, 5, 7, 9, 2, 4, 6, 8, 0]; let heap = from_vec(copy data); - assert merge_sort(to_vec(heap), le) == merge_sort(data, le); + assert merge_sort(heap.to_vec(), le) == merge_sort(data, le); } } |
