ps_range/
partial_range_ext.rs

1use num_traits::{One, Zero};
2
3use crate::{PartialRange, Range, RangeEnd, RangeStart};
4
5/// A range that may be unbounded above or empty.
6///
7/// Implementors provide [`start`](RangeStart::start) via the
8/// [`RangeStart`] supertrait and override
9/// [`end_bound`](PartialRangeExt::end_bound) when the range is bounded; the
10/// default returns [`None`], describing a range unbounded above. An
11/// implementor whose emptiness is not derivable from those two accessors,
12/// such as a type with hidden exhaustion state like
13/// [`std::ops::RangeInclusive`], must also override
14/// [`is_empty`](PartialRangeExt::is_empty); every derived operation consults
15/// [`is_empty`](PartialRangeExt::is_empty) before the bounds. The standard
16/// library leaves the endpoint values of a drained
17/// [`std::ops::RangeInclusive`] unspecified, so the position of an empty
18/// result derived from one is likewise unspecified; only emptiness is
19/// guaranteed.
20///
21/// The operations interpret `Idx` as a discrete domain in which `x + one` is
22/// the successor of `x`, and convert a bound between its inclusive and
23/// exclusive forms only where the converted bound is provably at most the
24/// window's end. Empty results from the [`PartialRange`]-returning
25/// operations anchor at the raised or joint start; the
26/// [`std::ops::Range`]- and [`Range`]-returning operations instead lower the
27/// start to the computed end, so their results are always slice-safe.
28///
29/// # Examples
30///
31/// ```
32/// use ps_range::{PartialRange, PartialRangeExt, Range};
33///
34/// assert_eq!((5usize..=10).clamp_exclusive(0usize, 7usize), 5..7);
35/// assert_eq!((5usize..).clamp_inclusive(0usize, 7usize), Range::inclusive(5, 7));
36/// assert!((5usize..=10).clamp_exclusive(20usize, 25usize).is_empty());
37///
38/// assert_eq!(
39///     (5usize..=10).intersection(&(8usize..)),
40///     PartialRange::Inclusive { start: 8, end: 10 }
41/// );
42/// ```
43pub trait PartialRangeExt<Idx = usize>: RangeStart<Idx>
44where
45    Idx: Clone + Ord,
46{
47    /// Returns the upper bound, or [`None`] if the range is unbounded above.
48    #[inline]
49    #[must_use]
50    fn end_bound(&self) -> Option<RangeEnd<Idx>> {
51        None
52    }
53
54    /// Returns `true` if the range contains no indices.
55    #[inline]
56    #[must_use]
57    fn is_empty(&self) -> bool {
58        match self.end_bound() {
59            Some(RangeEnd::Exclusive(end)) => end <= self.start(),
60            Some(RangeEnd::Inclusive(end)) => end < self.start(),
61            None => false,
62        }
63    }
64
65    /// Restricts the range to the window `start..exclusive_end`.
66    ///
67    /// The result is slice-safe: its start does not exceed its end, and its
68    /// end does not exceed the window's. An empty input yields an empty
69    /// range at its start clamped into the window; a disjoint input yields
70    /// one at the computed end, which may fall below the window's start.
71    #[inline]
72    #[must_use]
73    fn clamp_exclusive(
74        &self,
75        start: impl Into<Idx>,
76        exclusive_end: impl Into<Idx>,
77    ) -> std::ops::Range<Idx>
78    where
79        Idx: std::ops::Add<Output = Idx> + One,
80    {
81        let window_start = start.into();
82        let window_end = exclusive_end.into();
83
84        if self.is_empty() {
85            let anchor = self.start().max(window_start).min(window_end);
86
87            return anchor.clone()..anchor;
88        }
89
90        let end = match self.end_bound() {
91            None => window_end,
92            Some(RangeEnd::Exclusive(end)) => end.min(window_end),
93            Some(RangeEnd::Inclusive(end)) => {
94                // `end < window_end <= MAX`, so the successor is representable
95                // and does not exceed the window's end.
96                if end < window_end {
97                    end + Idx::one()
98                } else {
99                    window_end
100                }
101            }
102        };
103        let start = self.start().max(window_start).min(end.clone());
104
105        start..end
106    }
107
108    /// Restricts the range to the window `start..=inclusive_end`.
109    ///
110    /// The result is always bounded, so it is expressed as a [`Range`]. An
111    /// empty input yields an empty exclusive [`Range`] at its start clamped
112    /// into the window; a disjoint input yields one at the computed end,
113    /// which may fall below the window's start.
114    #[inline]
115    #[must_use]
116    fn clamp_inclusive(&self, start: impl Into<Idx>, inclusive_end: impl Into<Idx>) -> Range<Idx> {
117        let window_start = start.into();
118        let window_end = inclusive_end.into();
119
120        if self.is_empty() {
121            let anchor = self.start().max(window_start).min(window_end);
122
123            return Range::exclusive(anchor.clone(), anchor);
124        }
125
126        let end = match self.end_bound() {
127            None => RangeEnd::Inclusive(window_end),
128            Some(end) => end.min(RangeEnd::Inclusive(window_end)),
129        };
130        let start = self.start().max(window_start);
131
132        match end {
133            RangeEnd::Inclusive(end) if start <= end => Range::inclusive(start, end),
134            RangeEnd::Exclusive(end) if start < end => Range::exclusive(start, end),
135            RangeEnd::Inclusive(end) | RangeEnd::Exclusive(end) => {
136                Range::exclusive(end.clone(), end)
137            }
138        }
139    }
140
141    /// Caps the upper bound at `inclusive_end`.
142    #[inline]
143    #[must_use]
144    fn clamp_right_inclusive(&self, inclusive_end: impl Into<Idx>) -> Range<Idx> {
145        self.clamp_inclusive(self.start(), inclusive_end)
146    }
147
148    /// Caps the upper bound at `exclusive_end`.
149    #[inline]
150    #[must_use]
151    fn clamp_right_exclusive(&self, exclusive_end: impl Into<Idx>) -> std::ops::Range<Idx>
152    where
153        Idx: std::ops::Add<Output = Idx> + One,
154    {
155        self.clamp_exclusive(self.start(), exclusive_end)
156    }
157
158    /// Raises the lower bound to at least `start`, preserving boundedness
159    /// above.
160    ///
161    /// If the range is empty, or `start` is disjoint from it, the result is
162    /// the [`Empty`](PartialRange::Empty) variant anchored at the raised
163    /// start.
164    #[inline]
165    #[must_use]
166    fn clamp_left(&self, start: impl Into<Idx>) -> PartialRange<Idx> {
167        let start = self.start().max(start.into());
168
169        if self.is_empty() {
170            return PartialRange::Empty { idx: start };
171        }
172
173        match self.end_bound() {
174            None => PartialRange::From { inner: start.. },
175            Some(RangeEnd::Inclusive(end)) if start <= end => {
176                PartialRange::Inclusive { start, end }
177            }
178            Some(RangeEnd::Exclusive(end)) if start < end => {
179                PartialRange::Exclusive { inner: start..end }
180            }
181            Some(_) => PartialRange::Empty { idx: start },
182        }
183    }
184
185    /// Returns the overlap between this range and `other`.
186    ///
187    /// The result is unbounded above only when both ranges are. If either
188    /// range is empty, or the ranges are disjoint, the result is the
189    /// [`Empty`](PartialRange::Empty) variant anchored at the joint start.
190    #[inline]
191    #[must_use]
192    fn intersection<R>(&self, other: &R) -> PartialRange<Idx>
193    where
194        R: PartialRangeExt<Idx>,
195    {
196        let start = self.start().max(other.start());
197
198        if self.is_empty() || other.is_empty() {
199            return PartialRange::Empty { idx: start };
200        }
201
202        let end = match (self.end_bound(), other.end_bound()) {
203            (None, None) => return PartialRange::From { inner: start.. },
204            (Some(end), None) | (None, Some(end)) => end,
205            (Some(lhs), Some(rhs)) => lhs.min(rhs),
206        };
207
208        match end {
209            RangeEnd::Inclusive(end) if start <= end => PartialRange::Inclusive { start, end },
210            RangeEnd::Exclusive(end) if start < end => {
211                PartialRange::Exclusive { inner: start..end }
212            }
213            _ => PartialRange::Empty { idx: start },
214        }
215    }
216}
217
218impl<Idx: Clone + Ord> PartialRangeExt<Idx> for std::ops::Range<Idx> {
219    #[inline]
220    fn end_bound(&self) -> Option<RangeEnd<Idx>> {
221        Some(RangeEnd::Exclusive(self.end.clone()))
222    }
223}
224
225impl<Idx: Clone + Ord> PartialRangeExt<Idx> for std::ops::RangeFrom<Idx> {}
226
227impl<Idx: Clone + Ord + Zero> PartialRangeExt<Idx> for std::ops::RangeFull {}
228
229impl<Idx: Clone + Ord> PartialRangeExt<Idx> for std::ops::RangeInclusive<Idx> {
230    #[inline]
231    fn end_bound(&self) -> Option<RangeEnd<Idx>> {
232        Some(RangeEnd::Inclusive(self.end().clone()))
233    }
234
235    #[inline]
236    fn is_empty(&self) -> bool {
237        Self::is_empty(self)
238    }
239}
240
241impl<Idx: Clone + Ord + Zero> PartialRangeExt<Idx> for std::ops::RangeTo<Idx> {
242    #[inline]
243    fn end_bound(&self) -> Option<RangeEnd<Idx>> {
244        Some(RangeEnd::Exclusive(self.end.clone()))
245    }
246}
247
248impl<Idx: Clone + Ord + Zero> PartialRangeExt<Idx> for std::ops::RangeToInclusive<Idx> {
249    #[inline]
250    fn end_bound(&self) -> Option<RangeEnd<Idx>> {
251        Some(RangeEnd::Inclusive(self.end.clone()))
252    }
253}
254
255/// [`None`] is the empty range, anchored at [`Idx::zero()`](Zero::zero), so
256/// a possibly-absent range remains usable as a range.
257impl<Idx, T> PartialRangeExt<Idx> for Option<T>
258where
259    Idx: Clone + Ord + Zero,
260    T: PartialRangeExt<Idx>,
261{
262    #[inline]
263    fn end_bound(&self) -> Option<RangeEnd<Idx>> {
264        self.as_ref().map_or_else(
265            || Some(RangeEnd::Exclusive(Idx::zero())),
266            PartialRangeExt::end_bound,
267        )
268    }
269
270    #[inline]
271    fn is_empty(&self) -> bool {
272        self.as_ref().is_none_or(PartialRangeExt::is_empty)
273    }
274}
275
276impl<Idx, T> PartialRangeExt<Idx> for &T
277where
278    Idx: Clone + Ord,
279    T: PartialRangeExt<Idx>,
280{
281    #[inline]
282    fn end_bound(&self) -> Option<RangeEnd<Idx>> {
283        (*self).end_bound()
284    }
285
286    #[inline]
287    fn is_empty(&self) -> bool {
288        (*self).is_empty()
289    }
290}
291
292impl<Idx, T> PartialRangeExt<Idx> for &mut T
293where
294    Idx: Clone + Ord,
295    T: PartialRangeExt<Idx>,
296{
297    #[inline]
298    fn end_bound(&self) -> Option<RangeEnd<Idx>> {
299        (**self).end_bound()
300    }
301
302    #[inline]
303    fn is_empty(&self) -> bool {
304        (**self).is_empty()
305    }
306}
307
308#[cfg(test)]
309mod tests {
310    use super::PartialRangeExt;
311    use crate::PartialRange;
312
313    struct StartOnlyRange;
314
315    impl crate::RangeStart<usize> for StartOnlyRange {
316        fn start(&self) -> usize {
317            42
318        }
319    }
320
321    impl PartialRangeExt<usize> for StartOnlyRange {}
322
323    #[test]
324    fn a_start_only_implementor_is_unbounded_above() {
325        let range = StartOnlyRange;
326
327        assert_eq!(range.end_bound(), None);
328        assert!(!range.is_empty());
329        assert_eq!(range.clamp_right_exclusive(50usize), 42..50);
330        assert_eq!(
331            range.clamp_left(50usize),
332            PartialRange::From { inner: 50.. }
333        );
334    }
335}
ps_range/partial_range_ext.rs

ps_range/
partial_range_ext.rs
