indextreemap 0.2.0

A BTreeMap-like ordered map with key and positional lookup.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

use crate::stc::Node;
use std::cmp::Ordering::{Equal, Greater, Less};

impl<K: Ord, V> Node<K, V> {
    pub fn binary_search(&self, key: &K) -> Result<usize, usize> {
        if self.n == 0 {
            Err(0)
        } else {
            let mut map: [usize; 2] = [0, self.n - 1];
            let mut m;
            while map[0].abs_diff(map[1]) > 1 {
                m = (map[0] + map[1]) / 2;
                if let Some(k) = &self.keys[m] {
                    match key.cmp(&k.key) {
                        Less => map[1] = m - 1,
                        Equal => return Ok(m),
                        Greater => map[0] = m + 1,
                    }
                } else {
                    return Err(m);
                }
            }

            if map[0] == map[1] {
                m = (map[0] + map[1]) / 2;
                if let Some(k) = &self.keys[m] {
                    match key.cmp(&k.key) {
                        Less => Err(m),
                        Equal => Ok(m),
                        Greater => Err(m + 1),
                    }
                } else {
                    Err(m)
                }
            } else {
                m = (map[0] + map[1]) / 2;
                if let Some(k) = &self.keys[m] {
                    match key.cmp(&k.key) {
                        Less => Err(m),
                        Equal => Ok(m),
                        Greater => {
                            m += 1;
                            if let Some(k) = &self.keys[m] {
                                match key.cmp(&k.key) {
                                    Less => Err(m),
                                    Equal => Ok(m),
                                    Greater => Err(m + 1),
                                }
                            } else {
                                Err(m)
                            }
                        }
                    }
                } else {
                    Err(m)
                }
            }
        }
    }
}

// pub fn binary_search(arr: &[usize], key: &usize) -> Result<usize, usize> {
//     if arr.is_empty() {
//         Err(0)
//     } else {
//         let mut map: [usize; 2] = [0, arr.len() - 1];
//         let mut m;
//         while map[0].abs_diff(map[1]) > 1 {
//             m = (map[0] + map[1]) / 2;
//             match key.cmp(&arr[m]) {
//                 Less => map[1] = m - 1,
//                 Equal => return Ok(m),
//                 Greater => map[0] = m + 1,
//             }
//         }

//         if map[0] == map[1] {
//             m = (map[0] + map[1]) / 2;
//             match key.cmp(&arr[m]) {
//                 Less => Err(m),
//                 Equal => Ok(m),
//                 Greater => Err(m + 1),
//             }
//         } else {
//             m = (map[0] + map[1]) / 2;
//             match key.cmp(&arr[m]) {
//                 Less => Err(m),
//                 Equal => Ok(m),
//                 Greater => {
//                     m += 1;
//                     match key.cmp(&arr[m]) {
//                         Less => Err(m),
//                         Equal => Ok(m),
//                         Greater => Err(m + 1),
//                     }
//                 }
//             }
//         }
//     }
// }