btree_range_map/range/
bound.rs

1use super::{direct_bound_partial_cmp, BoundOrd, BoundOrdering, BoundPartialOrd, Measure};
2use range_traits::PartialEnum;
3use std::{
4	cmp::Ordering,
5	hash::{Hash, Hasher},
6	ops::Bound,
7};
8
9/// Types that can be interpreted as range bounds.
10pub trait AsBound {
11	type Item;
12
13	fn bound(&self) -> Bound<&Self::Item>;
14}
15
16impl AsBound for u8 {
17	type Item = u8;
18
19	fn bound(&self) -> Bound<&u8> {
20		Bound::Included(self)
21	}
22}
23
24impl<'a, T> AsBound for Bound<&'a T> {
25	type Item = T;
26
27	fn bound(&self) -> Bound<&T> {
28		*self
29	}
30}
31
32#[inline(always)]
33pub(crate) fn invert_bound<T>(bound: Bound<T>) -> Option<Bound<T>> {
34	match bound {
35		Bound::Unbounded => None,
36		Bound::Included(t) => Some(Bound::Excluded(t)),
37		Bound::Excluded(t) => Some(Bound::Included(t)),
38	}
39}
40
41#[derive(Clone, Copy, Debug)]
42pub enum Directed<T> {
43	Start(T),
44	End(T),
45}
46
47impl<T> Directed<T> {
48	/// Returns the directed value, without direction.
49	pub fn unwrap(self) -> T {
50		match self {
51			Self::Start(t) => t,
52			Self::End(t) => t,
53		}
54	}
55
56	/// Returns a reference to the directed value, without direction.
57	pub fn value(&self) -> &T {
58		match self {
59			Self::Start(t) => t,
60			Self::End(t) => t,
61		}
62	}
63}
64
65impl<T> Directed<Bound<T>> {
66	pub fn as_ref(&self) -> Directed<Bound<&T>> {
67		match self {
68			Directed::Start(b) => Directed::Start(match b {
69				Bound::Included(b) => Bound::Included(b),
70				Bound::Excluded(b) => Bound::Excluded(b),
71				Bound::Unbounded => Bound::Unbounded,
72			}),
73			Directed::End(b) => Directed::End(match b {
74				Bound::Included(b) => Bound::Included(b),
75				Bound::Excluded(b) => Bound::Excluded(b),
76				Bound::Unbounded => Bound::Unbounded,
77			}),
78		}
79	}
80}
81
82impl<'a, T: Hash + PartialEnum> Hash for Directed<Bound<&'a T>> {
83	fn hash<H: Hasher>(&self, h: &mut H) {
84		match self {
85			Directed::Start(b) => match b {
86				Bound::Included(b) => b.hash(h),
87				Bound::Excluded(b) => match b.succ() {
88					Some(c) => c.hash(h),
89					None => b.hash(h),
90				},
91				Bound::Unbounded => (),
92			},
93			Directed::End(b) => match b {
94				Bound::Included(b) => b.hash(h),
95				Bound::Excluded(b) => match b.pred() {
96					Some(c) => c.hash(h),
97					None => b.hash(h),
98				},
99				Bound::Unbounded => (),
100			},
101		}
102	}
103}
104
105impl<T, U> PartialEq<Directed<Bound<&U>>> for Directed<Bound<&T>>
106where
107	T: Measure<U> + PartialOrd<U> + PartialEnum,
108	U: PartialEnum,
109{
110	fn eq(&self, other: &Directed<Bound<&U>>) -> bool {
111		self.partial_cmp(other) == Some(Ordering::Equal)
112	}
113}
114
115impl<T> Eq for Directed<Bound<&T>> where T: Measure + Ord + PartialEnum {}
116
117impl<T, U> PartialOrd<Directed<Bound<&U>>> for Directed<Bound<&T>>
118where
119	T: Measure<U> + PartialOrd<U> + PartialEnum,
120	U: PartialEnum,
121{
122	fn partial_cmp(&self, other: &Directed<Bound<&U>>) -> Option<Ordering> {
123		match self.bound_partial_cmp(other) {
124			Some(BoundOrdering::Included(true)) => Some(Ordering::Equal),
125			Some(BoundOrdering::Included(false)) => match other {
126				Directed::Start(_) => Some(Ordering::Greater),
127				Directed::End(_) => Some(Ordering::Less),
128			},
129			Some(BoundOrdering::Excluded(_)) => match other {
130				Directed::Start(_) => Some(Ordering::Less),
131				Directed::End(_) => Some(Ordering::Greater),
132			},
133			None => None,
134		}
135	}
136}
137
138impl<T> Ord for Directed<Bound<&T>>
139where
140	T: Measure + Ord + PartialEnum,
141{
142	fn cmp(&self, other: &Directed<Bound<&T>>) -> Ordering {
143		match self.bound_cmp(other) {
144			BoundOrdering::Included(true) => Ordering::Equal,
145			BoundOrdering::Included(false) => match other {
146				Directed::Start(_) => Ordering::Greater,
147				Directed::End(_) => Ordering::Less,
148			},
149			BoundOrdering::Excluded(_) => match other {
150				Directed::Start(_) => Ordering::Less,
151				Directed::End(_) => Ordering::Greater,
152			},
153		}
154	}
155}
156
157pub(crate) fn min_bound<'a, T: Measure + PartialOrd + PartialEnum>(
158	a: Bound<&'a T>,
159	b: Bound<&'a T>,
160	start: bool,
161) -> Bound<&'a T> {
162	match direct_bound_partial_cmp(a, b, start) {
163		Some(BoundOrdering::Included(_)) => {
164			if start {
165				b
166			} else {
167				a
168			}
169		}
170		_ => {
171			if start {
172				a
173			} else {
174				b
175			}
176		}
177	}
178}
179
180pub(crate) fn max_bound<'a, T: Measure + PartialOrd + PartialEnum>(
181	a: Bound<&'a T>,
182	b: Bound<&'a T>,
183	start: bool,
184) -> Bound<&'a T> {
185	match direct_bound_partial_cmp(a, b, start) {
186		Some(BoundOrdering::Included(_)) => {
187			if start {
188				a
189			} else {
190				b
191			}
192		}
193		_ => {
194			if start {
195				b
196			} else {
197				a
198			}
199		}
200	}
201}
btree_range_map/range/bound.rs

btree_range_map/range/
bound.rs
