b_trees/
lib.rs

1mod avl;
2mod node;
3use std::cmp::Ordering;
4
5use node::*;
6
7mod map;
8pub use map::*;
9
10pub use avl::*;
11
12pub trait Nearness {
13    fn nearer<'a>(&'a self, other: &'a Self, target: &Self) -> &'a Self;
14    fn farther<'a>(&'a self, other: &'a Self, target: &Self) -> &'a Self;
15}
16
17macro_rules! impl_nearer_signed {
18    ($tp:ty) => {
19        impl Nearness for $tp {
20            fn nearer<'a>(&'a self, other: &'a Self, target: &Self) -> &'a Self {
21                if <$tp>::abs(self - target) < <$tp>::abs(other - target) {
22                    self
23                } else {
24                    other
25                }
26            }
27            fn farther<'a>(&'a self, other: &'a Self, target: &Self) -> &'a Self {
28                if <$tp>::abs(self - target) > <$tp>::abs(other - target) {
29                    self
30                } else {
31                    other
32                }
33            }
34        }
35    };
36}
37
38
39pub struct Pair<K, V> {
40    key: K,
41    val: V,
42}
43
44impl<K: Ord, V> PartialEq for Pair<K, V> {
45    fn eq(&self, other: &Self) -> bool {
46        matches!(self.key.cmp(&other.key), Ordering::Equal)
47    }
48}
49
50impl<K: Ord, V> Eq for Pair<K, V> {}
51
52impl<K: Ord, V> Ord for Pair<K, V> {
53    fn cmp(&self, other: &Self) -> Ordering {
54        self.key.cmp(&other.key)
55    }
56}
57
58
59
60impl<K: Ord, V> PartialOrd for Pair<K, V> {
61    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
62        Some(self.key.cmp(&other.key))
63    }
64}
65
66macro_rules! impl_nearer_unsigned {
67    ($tp:ty) => {
68        impl Nearness for $tp {
69            fn nearer<'a>(&'a self, other: &'a Self, target: &Self) -> &'a Self {
70                if self < target && other < target {
71                    if self > other {
72                        self
73                    } else {
74                        other
75                    }
76                } else if self > target && other > target {
77                    if self < other {
78                        self
79                    } else {
80                        other
81                    }
82                } else {
83                    let (larger, smaller) = if self > target {
84                        (self, other)
85                    } else {
86                        (other, self)
87                    };
88                    if larger - target < target - smaller {
89                        larger
90                    } else {
91                        smaller
92                    }
93                }
94            }
95            fn farther<'a>(&'a self, other: &'a Self, target: &Self) -> &'a Self {
96                if self < target && other < target {
97                    if self > other {
98                        other
99                    } else {
100                        self
101                    }
102                } else if self > target && other > target {
103                    if self < other {
104                        other
105                    } else {
106                        self
107                    }
108                } else {
109                    let (larger, smaller) = if self > target {
110                        (self, other)
111                    } else {
112                        (other, self)
113                    };
114                    if larger - target > target - smaller {
115                        larger
116                    } else {
117                        smaller
118                    }
119                }
120            }
121        }
122    };
123}
124
125impl_nearer_signed!(isize);
126impl_nearer_signed!(i128);
127impl_nearer_signed!(i64);
128impl_nearer_signed!(i32);
129impl_nearer_signed!(i16);
130impl_nearer_signed!(i8);
131
132impl_nearer_unsigned!(usize);
133impl_nearer_unsigned!(u128);
134impl_nearer_unsigned!(u64);
135impl_nearer_unsigned!(u32);
136impl_nearer_unsigned!(u16);
137impl_nearer_unsigned!(u8);
b_trees/lib.rs

b_trees/
lib.rs
