dynamic_weighted_index/
sorted_sequence.rs

1#![allow(dead_code)]
2use smallvec::SmallVec;
3
4#[derive(Debug, Default, Clone)]
5pub struct SortedSequence<T>
6where
7    T: Ord + Default,
8{
9    elements: SmallVec<[T; 32]>,
10}
11
12impl<T> SortedSequence<T>
13where
14    T: Ord + Default,
15{
16    pub fn insert(&mut self, elem: T) -> bool {
17        match self.elements.binary_search(&elem) {
18            Ok(_) => false,
19            Err(pos) => {
20                self.elements.insert(pos, elem);
21                true
22            }
23        }
24    }
25
26    pub fn remove(&mut self, elem: &T) -> bool {
27        match self.elements.binary_search(elem) {
28            Ok(pos) => {
29                self.elements.remove(pos);
30                true
31            }
32            Err(_) => false,
33        }
34    }
35
36    pub fn len(&self) -> usize {
37        self.elements.len()
38    }
39
40    pub fn is_empty(&self) -> bool {
41        self.elements.is_empty()
42    }
43
44    pub fn contains(&self, elem: &T) -> bool {
45        self.elements.binary_search(elem).is_ok()
46    }
47
48    pub fn iter(&self) -> impl Iterator<Item = &T> {
49        self.elements.iter()
50    }
51
52    pub fn iter_rev(&self) -> impl Iterator<Item = &T> {
53        self.elements.iter().rev()
54    }
55}
56
57#[cfg(test)]
58mod test {
59    use super::*;
60    use itertools::Itertools;
61    use rand::{Rng, SeedableRng};
62    use std::collections::HashSet;
63
64    #[test]
65    fn insert() {
66        let mut seq = SortedSequence::default();
67
68        assert!(seq.insert(10));
69        assert!(seq.insert(1));
70        assert!(!seq.insert(1));
71        assert!(seq.insert(5));
72
73        assert_eq!(seq.iter().copied().collect_vec(), [1, 5, 10]);
74        assert_eq!(seq.iter_rev().copied().collect_vec(), [10, 5, 1]);
75    }
76
77    #[test]
78    fn contains() {
79        let mut seq = SortedSequence::default();
80
81        assert!(!seq.contains(&10));
82        assert!(seq.insert(10));
83        assert!(seq.contains(&10));
84        assert!(!seq.contains(&5));
85    }
86
87    #[test]
88    fn remove() {
89        let mut seq = SortedSequence::default();
90
91        assert!(seq.insert(10));
92        assert!(seq.insert(1));
93        assert!(!seq.insert(1));
94        assert!(seq.remove(&1));
95        assert!(!seq.remove(&1));
96        assert!(seq.insert(5));
97
98        assert_eq!(seq.iter().copied().collect_vec(), [5, 10]);
99        assert_eq!(seq.iter_rev().copied().collect_vec(), [10, 5]);
100    }
101
102    #[test]
103    fn len_is_empty() {
104        let mut seq = SortedSequence::default();
105        assert!(seq.is_empty());
106        assert_eq!(seq.len(), 0);
107
108        seq.insert(123);
109
110        assert!(!seq.is_empty());
111        assert_eq!(seq.len(), 1);
112    }
113
114    fn is_sorted<T>(data: &[T]) -> bool
115    where
116        T: Ord,
117    {
118        data.windows(2).all(|w| w[0] <= w[1])
119    }
120
121    fn is_sorted_rev<T>(data: &[T]) -> bool
122    where
123        T: Ord,
124    {
125        data.windows(2).all(|w| w[0] >= w[1])
126    }
127
128    #[test]
129    fn randomized() {
130        let mut rng = pcg_rand::Pcg64::seed_from_u64(0x1234);
131
132        for n in 1..50 {
133            let mut seq = SortedSequence::default();
134            let mut set = HashSet::new();
135
136            for _ in 0..2 * n * n {
137                let elem = rng.gen_range(0..=n);
138
139                assert_eq!(seq.contains(&elem), set.contains(&elem));
140                if rng.gen_bool(0.7) {
141                    // insert
142                    assert_eq!(seq.insert(elem), set.insert(elem));
143                } else {
144                    // delete
145                    assert_eq!(seq.remove(&elem), set.remove(&elem));
146                }
147
148                assert_eq!(seq.contains(&elem), set.contains(&elem));
149                assert_eq!(seq.len(), set.len());
150                assert_eq!(seq.is_empty(), set.is_empty());
151
152                assert!(is_sorted(&seq.iter().copied().collect_vec()));
153                assert!(is_sorted_rev(&seq.iter_rev().copied().collect_vec()));
154            }
155        }
156    }
157}
dynamic_weighted_index/sorted_sequence.rs

dynamic_weighted_index/
sorted_sequence.rs
