venator_engine/filter/
util.rs

1use std::cmp::Ordering;
2
3#[allow(dead_code)]
4pub(crate) trait BoundSearch<T> {
5    // This finds the first index of an item that is not less than the provided
6    // item. This works via a binary-search algorithm.
7    //
8    // NOTE: The result is only meaningful if the input is sorted.
9    fn lower_bound(&self, item: &T) -> usize;
10
11    // This finds the first index of an item that is greater than the provided
12    // item. This works via a binary-search algorithm.
13    //
14    // NOTE: The result is only meaningful if the input is sorted.
15    fn upper_bound(&self, item: &T) -> usize;
16
17    // This finds the first index of an item that is not less than the provided
18    // item. This works via a binary-expansion-search algorithm, i.e. it checks
19    // indexes geometrically starting from the beginning and then uses binary
20    // -search within those bounds. This method is good if the item is expected
21    // near the beginning.
22    //
23    // NOTE: The result is only meaningful if the input is sorted.
24    fn lower_bound_via_expansion(&self, item: &T) -> usize;
25
26    // This finds the first index of an item that is greater than the provided
27    // item. This works via a binary-expansion-search algorithm, i.e. it checks
28    // indexes geometrically starting from the end and then uses binary-search
29    // within those bounds. This method is good if the item is expected near the
30    // end.
31    //
32    // NOTE: The result is only meaningful if the input is sorted.
33    fn upper_bound_via_expansion(&self, item: &T) -> usize;
34}
35
36impl<T: Ord> BoundSearch<T> for [T] {
37    fn lower_bound(&self, item: &T) -> usize {
38        self.binary_search_by(|current_item| match current_item.cmp(item) {
39            Ordering::Greater => Ordering::Greater,
40            Ordering::Equal => Ordering::Greater,
41            Ordering::Less => Ordering::Less,
42        })
43        .unwrap_or_else(|idx| idx)
44    }
45
46    fn upper_bound(&self, item: &T) -> usize {
47        self.binary_search_by(|current_item| match current_item.cmp(item) {
48            Ordering::Greater => Ordering::Greater,
49            Ordering::Equal => Ordering::Less,
50            Ordering::Less => Ordering::Less,
51        })
52        .unwrap_or_else(|idx| idx)
53    }
54
55    fn lower_bound_via_expansion(&self, item: &T) -> usize {
56        let len = self.len();
57        for (start, mut end) in std::iter::successors(Some((0, 1)), |&(_, j)| Some((j, j * 2))) {
58            if end >= len {
59                end = len
60            } else if &self[end] < item {
61                continue;
62            }
63
64            return self[start..end].lower_bound(item) + start;
65        }
66
67        unreachable!()
68    }
69
70    fn upper_bound_via_expansion(&self, item: &T) -> usize {
71        let len = self.len();
72        for (start, mut end) in std::iter::successors(Some((0, 1)), |&(_, j)| Some((j, j * 2))) {
73            if end >= len {
74                end = len
75            } else if &self[len - end] > item {
76                continue;
77            }
78
79            return self[len - end..len - start].upper_bound(item) + (len - end);
80        }
81
82        unreachable!()
83    }
84}
85
86pub(crate) fn merge<T>(a: Option<T>, b: Option<T>, f: impl FnOnce(T, T) -> T) -> Option<T> {
87    // I wish this was in the standard library
88
89    match (a, b) {
90        (Some(a), Some(b)) => Some(f(a, b)),
91        (Some(a), None) => Some(a),
92        (None, Some(b)) => Some(b),
93        (None, None) => None,
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100
101    #[test]
102    fn bounds_on_empty_slice() {
103        assert_eq!([].lower_bound(&0), 0);
104        assert_eq!([].upper_bound(&0), 0);
105        assert_eq!([].lower_bound_via_expansion(&0), 0);
106        assert_eq!([].upper_bound_via_expansion(&0), 0);
107    }
108
109    #[test]
110    fn bounds_on_single_slice() {
111        assert_eq!([1].lower_bound(&0), 0);
112        assert_eq!([1].upper_bound(&0), 0);
113        assert_eq!([1].lower_bound_via_expansion(&0), 0);
114        assert_eq!([1].upper_bound_via_expansion(&0), 0);
115
116        assert_eq!([1].lower_bound(&1), 0);
117        assert_eq!([1].upper_bound(&1), 1);
118        assert_eq!([1].lower_bound_via_expansion(&1), 0);
119        assert_eq!([1].upper_bound_via_expansion(&1), 1);
120
121        assert_eq!([1].lower_bound(&2), 1);
122        assert_eq!([1].upper_bound(&2), 1);
123        assert_eq!([1].lower_bound_via_expansion(&2), 1);
124        assert_eq!([1].upper_bound_via_expansion(&2), 1);
125    }
126
127    #[test]
128    fn bounds_for_duplicate_item() {
129        assert_eq!([0, 0, 1, 1, 2, 2].lower_bound(&-1), 0);
130        assert_eq!([0, 0, 1, 1, 2, 2].upper_bound(&-1), 0);
131        assert_eq!([0, 0, 1, 1, 2, 2].lower_bound_via_expansion(&-1), 0);
132        assert_eq!([0, 0, 1, 1, 2, 2].upper_bound_via_expansion(&-1), 0);
133
134        assert_eq!([0, 0, 1, 1, 2, 2].lower_bound(&0), 0);
135        assert_eq!([0, 0, 1, 1, 2, 2].upper_bound(&0), 2);
136        assert_eq!([0, 0, 1, 1, 2, 2].lower_bound_via_expansion(&0), 0);
137        assert_eq!([0, 0, 1, 1, 2, 2].upper_bound_via_expansion(&0), 2);
138
139        assert_eq!([0, 0, 1, 1, 2, 2].lower_bound(&1), 2);
140        assert_eq!([0, 0, 1, 1, 2, 2].upper_bound(&1), 4);
141        assert_eq!([0, 0, 1, 1, 2, 2].lower_bound_via_expansion(&1), 2);
142        assert_eq!([0, 0, 1, 1, 2, 2].upper_bound_via_expansion(&1), 4);
143
144        assert_eq!([0, 0, 1, 1, 2, 2].lower_bound(&2), 4);
145        assert_eq!([0, 0, 1, 1, 2, 2].upper_bound(&2), 6);
146        assert_eq!([0, 0, 1, 1, 2, 2].lower_bound_via_expansion(&2), 4);
147        assert_eq!([0, 0, 1, 1, 2, 2].upper_bound_via_expansion(&2), 6);
148
149        assert_eq!([0, 0, 1, 1, 2, 2].lower_bound(&3), 6);
150        assert_eq!([0, 0, 1, 1, 2, 2].upper_bound(&3), 6);
151        assert_eq!([0, 0, 1, 1, 2, 2].lower_bound_via_expansion(&3), 6);
152        assert_eq!([0, 0, 1, 1, 2, 2].upper_bound_via_expansion(&3), 6);
153    }
154
155    #[test]
156    fn bounds_for_missing_item() {
157        assert_eq!([0, 0, 2, 2].lower_bound(&1), 2);
158        assert_eq!([0, 0, 2, 2].upper_bound(&1), 2);
159        assert_eq!([0, 0, 2, 2].lower_bound_via_expansion(&1), 2);
160        assert_eq!([0, 0, 2, 2].upper_bound_via_expansion(&1), 2);
161    }
162}
venator_engine/filter/util.rs

venator_engine/filter/
util.rs
