1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
use std::cmp::Ordering;
use std::convert;
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub struct SortedVector<T>
where
T: PartialOrd,
{
pub array: Vec<T>,
}
impl<T> SortedVector<T>
where
T: PartialOrd,
{
#[inline]
pub fn new() -> SortedVector<T> {
SortedVector { array: vec![] }
}
#[inline]
pub fn push(&mut self, value: T) {
let index = self.binary_search_by(|other| {
other.partial_cmp(&value).unwrap_or(Ordering::Less)
}).unwrap_or_else(convert::identity);
self.array.insert(index, value);
}
#[inline]
pub fn peek(&self) -> Option<&T> {
self.array.last()
}
#[inline]
pub fn pop(&mut self) -> Option<T> {
self.array.pop()
}
#[inline]
pub fn clear(&mut self) {
self.array.clear()
}
#[allow(dead_code)]
#[inline]
pub fn is_empty(&self) -> bool {
self.array.is_empty()
}
#[inline]
pub fn len(&self) -> usize {
self.array.len()
}
#[inline]
pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize>
where F: FnMut(&'a T) -> Ordering {
self.array.binary_search_by(f)
}
}
#[cfg(test)]
mod test {
use crate::sorted_vector::SortedVector;
use quickcheck;
#[test]
fn test_sorted_vec() {
quickcheck::quickcheck(prop_sorted_vec as fn(Vec<i32>) -> bool);
fn prop_sorted_vec(mut values: Vec<i32>) -> bool {
let mut sorted_vec = SortedVector::new();
for &value in &values {
sorted_vec.push(value)
}
values.sort();
let mut results = Vec::with_capacity(values.len());
while !sorted_vec.is_empty() {
results.push(sorted_vec.pop().unwrap());
}
results.reverse();
assert_eq!(&values, &results);
true
}
}
}