surrealdb_common/
range.rs

1//! A range parameterised by a concrete element type.
2//!
3//! Lives below the value layer because the sql AST embeds `TypedRange<i64>`
4//! in `Mock::Range`, and the parser constructs one directly.
5
6use std::cmp::Ordering;
7use std::ops::{Bound, RangeBounds};
8
9/// A range of a specific type, can be converted back into a general range and
10/// coerced from a general range.
11#[derive(Debug, Eq, PartialEq, Clone, Hash)]
12#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
13pub struct TypedRange<T> {
14	pub start: Bound<T>,
15	pub end: Bound<T>,
16}
17
18impl<T: PartialOrd> PartialOrd for TypedRange<T> {
19	fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
20		fn compare_bounds<T: PartialOrd>(a: &Bound<T>, b: &Bound<T>) -> Option<Ordering> {
21			match a {
22				Bound::Unbounded => match b {
23					Bound::Unbounded => Some(Ordering::Equal),
24					_ => Some(Ordering::Less),
25				},
26				Bound::Included(a) => match b {
27					Bound::Unbounded => Some(Ordering::Greater),
28					Bound::Included(b) => a.partial_cmp(b),
29					Bound::Excluded(_) => Some(Ordering::Less),
30				},
31				Bound::Excluded(a) => match b {
32					Bound::Excluded(b) => a.partial_cmp(b),
33					_ => Some(Ordering::Greater),
34				},
35			}
36		}
37
38		match compare_bounds(&self.start, &other.start) {
39			Some(Ordering::Equal) => compare_bounds(&self.end, &other.end),
40			x => x,
41		}
42	}
43}
44
45impl<T: Clone> TypedRange<T> {
46	pub fn from_range<R: RangeBounds<T>>(r: R) -> Self {
47		TypedRange {
48			start: r.start_bound().map(|x| x.clone()),
49			end: r.end_bound().map(|x| x.clone()),
50		}
51	}
52}
53
54impl TypedRange<i64> {
55	/// Returns an iterator over this range.
56	pub fn iter(self) -> IntegerRangeIter {
57		let cur = match self.start {
58			Bound::Included(x) => x,
59			Bound::Excluded(x) => match x.checked_add(1) {
60				Some(x) => x,
61				// i64::MAX is excluded so the iterator will never return anything.
62				None => {
63					return IntegerRangeIter {
64						cur: i64::MAX,
65						end: Some(i64::MIN),
66					};
67				}
68			},
69			Bound::Unbounded => i64::MIN,
70		};
71
72		match self.end {
73			Bound::Included(x) => IntegerRangeIter {
74				cur,
75				end: x.checked_add(1),
76			},
77			Bound::Excluded(x) => IntegerRangeIter {
78				cur,
79				end: Some(x),
80			},
81			Bound::Unbounded => IntegerRangeIter {
82				cur,
83				end: None,
84			},
85		}
86	}
87
88	pub fn slice<'a, T>(&self, s: &'a [T]) -> Option<&'a [T]> {
89		let r = match self.end {
90			Bound::Included(x) => s.get(..=(x as usize))?,
91			Bound::Excluded(x) => s.get(..(x as usize))?,
92			Bound::Unbounded => s,
93		};
94		match self.start {
95			Bound::Included(x) => r.get((x as usize)..),
96			Bound::Excluded(x) => {
97				let x = (x as usize).checked_add(1)?;
98				r.get(x..)
99			}
100			Bound::Unbounded => Some(r),
101		}
102	}
103
104	pub fn slice_mut<'a, T>(&self, s: &'a mut [T]) -> Option<&'a mut [T]> {
105		let r = match self.end {
106			Bound::Included(x) => s.get_mut(..=(x as usize))?,
107			Bound::Excluded(x) => s.get_mut(..(x as usize))?,
108			Bound::Unbounded => s,
109		};
110		match self.start {
111			Bound::Included(x) => r.get_mut((x as usize)..),
112			Bound::Excluded(x) => {
113				let x = (x as usize).checked_add(1)?;
114				r.get_mut(x..)
115			}
116			Bound::Unbounded => Some(r),
117		}
118	}
119
120	/// Returns the length of this range, or `None` when the range is unbounded
121	/// on either side or its length does not fit in a `usize`.
122	#[allow(clippy::len_without_is_empty)]
123	pub fn len(&self) -> Option<usize> {
124		let end = match self.end {
125			Bound::Unbounded => return None,
126			Bound::Included(x) => x,
127			Bound::Excluded(x) => match x.checked_sub(1) {
128				Some(x) => x,
129				None => return Some(0),
130			},
131		};
132
133		let start = match self.start {
134			Bound::Unbounded => return None,
135			Bound::Included(x) => x,
136			Bound::Excluded(x) => match x.checked_add(1) {
137				Some(x) => x,
138				None => return Some(0),
139			},
140		};
141
142		if start > end {
143			return Some(0);
144		}
145
146		usize::try_from(start.abs_diff(end)).ok()
147	}
148}
149
150/// Iterator over `TypedRange<i64>`.
151pub struct IntegerRangeIter {
152	cur: i64,
153	// Signifies the end of the iterator.
154	// The iterator will stop returning if self.cur >= self.end
155	// If end is None then i64::MAX is included.
156	end: Option<i64>,
157}
158
159impl Iterator for IntegerRangeIter {
160	type Item = i64;
161
162	fn next(&mut self) -> Option<i64> {
163		let cur = self.cur;
164		if let Some(end) = self.end
165			&& cur >= end
166		{
167			return None;
168		}
169		if let Some(x) = cur.checked_add(1) {
170			self.cur = x
171		} else {
172			// we have reached i64::MAX so after this we need to avoid returning anything.
173			self.end = Some(i64::MIN)
174		}
175
176		Some(cur)
177	}
178
179	fn size_hint(&self) -> (usize, Option<usize>) {
180		let len = if let Some(x) = self.end {
181			if self.cur >= x {
182				return (0, Some(0));
183			}
184			self.cur.abs_diff(x) - 1
185		} else {
186			self.cur.abs_diff(i64::MAX)
187		};
188		// handling if u64::MAX > usize::MAX
189		let upper: Option<usize> = len.try_into().ok();
190		(upper.unwrap_or(usize::MAX), upper)
191	}
192}
surrealdb_common/range.rs

surrealdb_common/
range.rs
