binary_search_range/
lib.rs

1use std::ops;
2
3/// ソート済みの列を検索します。
4pub trait BinarySearchRange<T> {
5    fn range(&self, range: ops::Range<T>) -> ops::Range<usize>;
6}
7
8impl<T: Ord> BinarySearchRange<T> for [T] {
9    /// ソート済みの列に対して値の範囲に対応した index の範囲を返します。
10    ///
11    /// # Examples
12    ///
13    /// ```
14    /// use binary_search_range::BinarySearchRange;
15    ///
16    /// let a = vec![3, 3, 4, 5, 7, 7];
17    /// assert_eq!(a.range(0..5), 0..3); // [3, 3, 4         ]
18    /// assert_eq!(a.range(4..5), 2..3); // [      4         ]
19    /// assert_eq!(a.range(4..6), 2..4); // [      4, 5      ]
20    /// assert_eq!(a.range(4..8), 2..6); // [      4, 5, 7, 7]
21    /// ```
22    fn range(&self, range: ops::Range<T>) -> ops::Range<usize> {
23        assert!(!self.is_empty());
24        assert!(range.start < range.end);
25
26        let first_ge = |x: &T| {
27            if x.le(&self[0]) {
28                return 0;
29            }
30            let mut left = 0;
31            // self[left] < x
32            let mut right = self.len();
33            while right - left > 1 {
34                let mid = (right + left) / 2;
35                if self[mid].lt(x) {
36                    left = mid;
37                } else {
38                    right = mid;
39                }
40            }
41            assert!(self[left].lt(x));
42            assert!(right <= self.len());
43            if right < self.len() {
44                assert!(x.le(&self[right]));
45            }
46            right
47        };
48
49        let start_index = first_ge(&range.start);
50        let end_index = first_ge(&range.end);
51        start_index..end_index
52    }
53}
54
55#[cfg(test)]
56mod tests {
57    use crate::BinarySearchRange;
58
59    #[test]
60    #[should_panic]
61    fn test_panic() {
62        vec![].range(0..10);
63    }
64
65    #[test]
66    #[should_panic]
67    fn test_panic2() {
68        vec![1, 2, 3].range(2..2);
69    }
70
71    #[test]
72    fn test_empty() {
73        assert_eq!(vec![3, 4, 8].range(0..3), 0..0);
74        assert_eq!(vec![3, 4, 8].range(5..8), 2..2);
75        assert_eq!(vec![3, 4, 8].range(9..12), 3..3);
76    }
77
78    #[test]
79    fn test_whole() {
80        let a = vec![3, 4, 5];
81        assert_eq!(a.range(3..6), 0..a.len());
82        assert_eq!(a.range(1..6), 0..a.len());
83        assert_eq!(a.range(3..7), 0..a.len());
84        assert_eq!(a.range(0..8), 0..a.len());
85    }
86
87    #[test]
88    fn test() {
89        let a = vec![2, 2, 5, 5, 6, 7, 10];
90        assert_eq!(a.range(0..3), 0..2);
91        assert_eq!(a.range(0..5), 0..2);
92        assert_eq!(a.range(0..6), 0..4);
93        assert_eq!(a.range(0..7), 0..5);
94        assert_eq!(a.range(0..8), 0..6);
95        assert_eq!(a.range(3..5), 2..2);
96        assert_eq!(a.range(3..6), 2..4);
97        assert_eq!(a.range(3..7), 2..5);
98        assert_eq!(a.range(3..8), 2..6);
99    }
100}
binary_search_range/lib.rs

binary_search_range/
lib.rs
