ordered_vector/
lib.rs

1use std::cmp::Ordering;
2use std::ops::Index;
3use bisection::bisect_left_by;
4
5pub trait Resort<T> where Self: Index<usize, Output = T> {
6    fn resort_element_by<F>(&mut self, index: usize, f: F) -> usize
7        where F: FnMut(&T, &T) -> Ordering;
8    /// Sort again already sorted sequence after the element at `index` changed.
9    /// Returns new index.
10    fn resort_element(&mut self, index: usize) -> usize
11        where Self::Output: Ord
12    {
13        self.resort_element_by(index, |e, value| T::cmp(e, &value))
14    }
15}
16
17pub trait InsertSorted<T> where Self: Index<usize, Output = T> {
18    fn insert_sorted_by<F>(&mut self, value: T, f: F) -> usize
19        where F: FnMut(&T, &T) -> Ordering;
20    fn insert_sorted(&mut self, value: T) -> usize
21        where Self::Output: Ord
22    {
23        self.insert_sorted_by(value, |e, value| T::cmp(e, &value))
24    }
25}
26
27impl<T: Ord> InsertSorted<T> for Vec<T> {
28    fn insert_sorted_by<F>(&mut self, value: T, mut f: F) -> usize
29        where F: FnMut(&T, &T) -> Ordering
30    {
31        let index = bisect_left_by(self.as_slice(), |e| f(e,&value));
32        self.insert(index, value);
33        index
34    }
35}
36
37impl<T: Ord> Resort<T> for Vec<T> {
38    // TODO: It can be made more efficient.
39    fn resort_element_by<F>(&mut self, index: usize, f: F) -> usize
40        where F: FnMut(&T, &T) -> Ordering
41    {
42        let value = self.remove(index);
43        self.insert_sorted_by(value, f)
44    }
45}
46
47#[cfg(test)]
48mod tests {
49    use crate::Resort;
50
51    #[test]
52    fn decrease() {
53        let mut v1 = vec![0, 1, 2];
54        v1[1] = -1;
55        v1.resort_element(1);
56        assert_eq!(v1, [-1, 0, 2]);
57    }
58
59    #[test]
60    fn increase() {
61        let mut v1 = vec![0, 1, 2];
62        v1[1] = 3;
63        v1.resort_element(1);
64        assert_eq!(v1, [0, 2, 3]);
65    }
66
67    #[test]
68    fn no_change() {
69        let mut v1 = vec![0, 1, 2];
70        v1.resort_element(1);
71        assert_eq!(v1, [0, 1, 2]);
72    }
73}
ordered_vector/lib.rs

ordered_vector/
lib.rs
