wyz/
range.rs

1//! Range utilities.
2
3use core::ops::{
4	Bound,
5	Range,
6	RangeBounds,
7};
8
9/// Extension methods for working with various range types.
10pub trait RangeExt<T>: RangeBounds<T>
11where T: Ord
12{
13	/// Normalizes a range-like type to a canonical half-open `Range`.
14	///
15	/// ## Parameters
16	///
17	/// - `self`: The range to normalize.
18	/// - `start`: An optional fallback *inclusive* lower bound.
19	/// - `end`: An optional fallback *exclusive* upper bound.
20	///
21	/// ## Returns
22	///
23	/// A `Range` whose start and end values are the following, in order of
24	/// decreasing priority:
25	///
26	/// - `self.start()`, or if absent, the `start` parameter, or if it is
27	///   `None`, `0`.
28	/// - `self.end()`, or if absent, the `end` parameter, or if it is `None`,
29	///   !0`.
30	fn normalize(
31		self,
32		start: impl Into<Option<T>>,
33		end: impl Into<Option<T>>,
34	) -> Range<T>;
35
36	/// Finds the intersection between two range-likes. The produced `Range`
37	/// spans only the elements common to both.
38	///
39	/// This returns `None` if the ranges do not have an intersection (at least
40	/// one element present in both ranges).
41	fn intersection<R>(self, other: R) -> Option<Range<T>>
42	where R: RangeExt<T>;
43
44	/// Finds the union between two range-likes. The produced `Range` spans all
45	/// elements present in at least one of them.
46	///
47	/// This returns `None` if the ranges do not have an intersection (at least
48	/// one element present in both ranges).
49	fn union<R>(self, other: R) -> Option<Range<T>>
50	where R: RangeExt<T>;
51}
52
53//  TODO(myrrlyn): Use funty to extend this for all integers.
54impl<R> RangeExt<usize> for R
55where R: RangeBounds<usize>
56{
57	fn normalize(
58		self,
59		start: impl Into<Option<usize>>,
60		end: impl Into<Option<usize>>,
61	) -> Range<usize> {
62		let start = match self.start_bound() {
63			Bound::Unbounded => start.into().unwrap_or(0),
64			Bound::Included(&v) => v,
65			Bound::Excluded(&v) => v.saturating_add(1),
66		};
67		let end = match self.end_bound() {
68			Bound::Unbounded => end.into().unwrap_or(!0),
69			Bound::Included(&v) => v.saturating_add(1),
70			Bound::Excluded(&v) => v,
71		};
72		if start > end {
73			end .. start
74		}
75		else {
76			start .. end
77		}
78	}
79
80	fn intersection<R2>(self, other: R2) -> Option<Range<usize>>
81	where R2: RangeExt<usize> {
82		let Range { start: a1, end: a2 } = self.normalize(None, None);
83		let Range { start: b1, end: b2 } = other.normalize(None, None);
84		if b1 < a1 {
85			return (b1 .. b2).intersection(a1 .. a2);
86		}
87		if !(a1 .. a2).contains(&b1) {
88			return None;
89		}
90		let start = a1.max(b1);
91		let end = a2.min(b2);
92		if start > end {
93			Some(end .. start)
94		}
95		else {
96			Some(start .. end)
97		}
98	}
99
100	fn union<R2>(self, other: R2) -> Option<Range<usize>>
101	where R2: RangeExt<usize> {
102		let Range { start: a1, end: a2 } = self.normalize(None, None);
103		let Range { start: b1, end: b2 } = other.normalize(None, None);
104		if b1 < a1 {
105			return (b1 .. b2).intersection(a1 .. a2);
106		}
107		if !(a1 .. a2).contains(&b1) {
108			return None;
109		}
110		let start = a1.min(b1);
111		let end = a2.max(b2);
112		if start > end {
113			Some(end .. start)
114		}
115		else {
116			Some(start .. end)
117		}
118	}
119}
120
121#[cfg(test)]
122mod tests {
123	use super::*;
124
125	#[test]
126	fn normalize() {
127		let r = (..).normalize(1, 10);
128		assert!(r.contains(&1));
129		assert!(r.contains(&9));
130		assert!(!r.contains(&0));
131		assert!(!r.contains(&10));
132
133		let r = (.. 10).normalize(1, 20);
134		assert!(r.contains(&1));
135		assert!(r.contains(&9));
136		assert!(!r.contains(&0));
137		assert!(!r.contains(&10));
138
139		let r = (4 ..).normalize(6, 10);
140		assert!(r.contains(&4));
141		assert!(r.contains(&9));
142		assert!(!r.contains(&3));
143		assert!(!r.contains(&10));
144
145		let r = (4 ..= 10).normalize(6, 8);
146		assert!(r.contains(&4));
147		assert!(r.contains(&10));
148		assert!(!r.contains(&3));
149		assert!(!r.contains(&11));
150
151		let r = (..= 10).normalize(1, 8);
152		assert!(r.contains(&1));
153		assert!(r.contains(&10));
154		assert!(!r.contains(&0));
155		assert!(!r.contains(&11));
156	}
157
158	#[test]
159	fn intersect() {
160		let a = 3 .. 10;
161		let b = 7 ..= 20;
162		assert_eq!(a.intersection(b), Some(7 .. 10));
163
164		let c = 3 .. 10;
165		let d = 13 ..= 20;
166		assert!(c.intersection(d).is_none());
167	}
168
169	#[test]
170	fn union() {
171		let a = 3 .. 10;
172		let b = 7 ..= 20;
173		assert_eq!(a.union(b), Some(3 .. 21));
174
175		let c = 3 .. 10;
176		let d = 13 ..= 20;
177		assert!(c.union(d).is_none());
178	}
179}
wyz/range.rs

wyz/
range.rs
