ferroui_base/utilities/
binary_search_extension.rs

1// RichTextKit
2// Copyright © 2019-2020 Topten Software. All Rights Reserved.
3//
4// Licensed under the Apache License, Version 2.0 (the "License"); you may
5// not use this product except in compliance with the License. You may obtain
6// a copy of the License at
7//
8// https://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13// License for the specific language governing permissions and limitations
14// under the License.
15// Copied from: https://github.com/toptensoftware/RichTextKit
16
17use std::cmp::Ordering;
18
19/// Binary searching of a list with a comparer.
20///
21/// Unlike `slice::binary_search_by`, which may return any of several equal
22/// items, the search visits the items in a fixed order. The result is the
23/// index of the found item or the bitwise complement of the index of the
24/// next larger item.
25pub struct BinarySearchExtension;
26
27impl BinarySearchExtension {
28    fn get_median(low: i32, hi: i32) -> i32 {
29        debug_assert!(low <= hi);
30        debug_assert!(hi - low >= 0, "Length overflow!");
31        low + ((hi - low) >> 1)
32    }
33
34    /// Performs a binary search on the entire contents of a list.
35    ///
36    /// Returns the index of the found item; otherwise the bitwise complement
37    /// of the index of the next larger item.
38    pub fn binary_search<T>(list: &[T], value: &T, comparer: impl Fn(&T, &T) -> Ordering) -> i32 {
39        Self::binary_search_range(list, 0, list.len() as i32, value, comparer)
40    }
41
42    /// Performs a binary search on a subset of a list: `length` items
43    /// starting at `index`.
44    ///
45    /// Returns the index of the found item; otherwise the bitwise complement
46    /// of the index of the next larger item.
47    pub fn binary_search_range<T>(
48        list: &[T],
49        index: i32,
50        length: i32,
51        value: &T,
52        comparer: impl Fn(&T, &T) -> Ordering,
53    ) -> i32 {
54        // Based on this: https://referencesource.microsoft.com/#mscorlib/system/array.cs,957
55        let mut lo = index;
56        let mut hi = index + length - 1;
57        while lo <= hi {
58            let i = Self::get_median(lo, hi);
59            match comparer(&list[i as usize], value) {
60                Ordering::Equal => return i,
61                Ordering::Less => lo = i + 1,
62                Ordering::Greater => hi = i - 1,
63            }
64        }
65        !lo
66    }
67}
68
69#[cfg(test)]
70mod tests {
71    // Not from upstream: the original has no tests of this type.
72    use super::*;
73
74    fn compare(a: &i32, b: &i32) -> Ordering {
75        a.cmp(b)
76    }
77
78    #[test]
79    fn finds_an_item_or_the_complement_of_the_next_larger_one() {
80        let list = [1, 3, 5, 7];
81        let empty: [i32; 0] = [];
82
83        assert_eq!(0, BinarySearchExtension::binary_search(&list, &1, compare));
84        assert_eq!(3, BinarySearchExtension::binary_search(&list, &7, compare));
85        assert_eq!(!0, BinarySearchExtension::binary_search(&list, &0, compare));
86        assert_eq!(!2, BinarySearchExtension::binary_search(&list, &4, compare));
87        assert_eq!(!4, BinarySearchExtension::binary_search(&list, &8, compare));
88        assert_eq!(!0, BinarySearchExtension::binary_search(&empty, &8, compare));
89    }
90
91    #[test]
92    fn searches_a_range() {
93        let list = [9, 1, 3, 5, 0];
94
95        assert_eq!(2, BinarySearchExtension::binary_search_range(&list, 1, 3, &3, compare));
96        assert_eq!(!1, BinarySearchExtension::binary_search_range(&list, 1, 3, &0, compare));
97        assert_eq!(!4, BinarySearchExtension::binary_search_range(&list, 1, 3, &6, compare));
98    }
99
100    #[test]
101    fn the_first_item_visited_wins_among_equal_items() {
102        let list = [2, 2, 2, 2, 2];
103        assert_eq!(2, BinarySearchExtension::binary_search(&list, &2, compare));
104    }
105}
ferroui_base/utilities/binary_search_extension.rs

ferroui_base/utilities/
binary_search_extension.rs
