interval_tree/
range.rs

1use std::{
2    cmp::Ordering,
3    fmt::Debug,
4    ops::{Bound, Range, RangeBounds},
5};
6
7/// a half-open interval in ℕ, [start, end)
8#[derive(Clone, Copy, Debug, PartialEq, Eq)]
9pub struct TextRange {
10    pub start: usize,
11    pub end: usize,
12}
13
14impl Ord for TextRange {
15    fn cmp(&self, other: &Self) -> Ordering {
16        match self.start.cmp(&other.start) {
17            Ordering::Equal => self.end.cmp(&other.end),
18            x => x,
19        }
20    }
21}
22
23impl PartialOrd for TextRange {
24    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
25        Some(self.cmp(other))
26    }
27}
28
29impl RangeBounds<usize> for TextRange {
30    fn start_bound(&self) -> Bound<&usize> {
31        Bound::Included(&self.start)
32    }
33
34    fn end_bound(&self) -> Bound<&usize> {
35        Bound::Excluded(&self.start)
36    }
37}
38
39impl<T: Into<usize>> From<Range<T>> for TextRange {
40    fn from(range: Range<T>) -> Self {
41        Self { start: range.start.into(), end: range.end.into() }
42    }
43}
44impl<T: Into<usize>> From<(T, T)> for TextRange {
45    fn from((start, end): (T, T)) -> Self {
46        Self { start: start.into(), end: end.into() }
47    }
48}
49
50impl TextRange {
51    /// caller should check that start < end
52    pub fn new(start: usize, end: usize) -> Self {
53        if start <= end { Self { start, end } } else { panic!("invalid TextRange") }
54    }
55
56    /// Creates a new `TextRange` only if start < end (non-empty interval).
57    /// Returns None if start >= end.
58    pub fn new_valid(start: usize, end: usize) -> Option<Self> {
59        (start < end).then_some(Self { start, end })
60    }
61
62    pub fn as_range(&self) -> Range<usize> {
63        self.start..self.end
64    }
65
66    pub fn empty(&self) -> bool {
67        self.start >= self.end
68    }
69
70    pub fn contains(&self, pos: usize) -> bool {
71        self.start <= pos && pos < self.end
72    }
73
74    /// Determines the strict ordering relationship between two ranges.
75    ///
76    /// Returns `Some(Ordering::Less)` if this range is completely before the other range.
77    /// Returns `Some(Ordering::Greater)` if this range is completely after the other range.
78    /// Returns `None` if the ranges overlap.
79    ///
80    /// # Examples
81    ///
82    /// ```
83    /// use std::cmp::Ordering;
84    /// use interval_tree::TextRange;
85    ///
86    /// let a = TextRange::new(0, 5);
87    /// let b = TextRange::new(6, 10);
88    /// assert_eq!(a.strict_order(&b), Some(Ordering::Less));
89    ///
90    /// let c = TextRange::new(7, 8);
91    /// assert_eq!(c.strict_order(&b), None);
92    /// ```
93    pub fn strict_order(&self, other: &Self) -> Option<Ordering> {
94        if self.end <= other.start {
95            return Some(Ordering::Less);
96        }
97        if self.start >= other.end {
98            return Some(Ordering::Greater);
99        }
100        None
101    }
102    /// split self, return the split out interval.
103    /// if `left` is true, the left part is split out and returned.
104    /// This function does not check whether `position` is valid.
105    pub fn split_at(&mut self, position: usize, left: bool) -> Self {
106        if left {
107            let start = self.start;
108            self.start = position;
109            Self::new(start, position)
110        } else {
111            let end = self.end;
112            self.end = position;
113            Self::new(position, end)
114        }
115    }
116
117    pub fn includes(&self, other: Self) -> bool {
118        self.end >= other.end && self.start <= other.start
119    }
120
121    pub fn intersects(&self, other: Self) -> bool {
122        self.end > other.start && self.start < other.end
123    }
124
125    fn intersection_uncheck(&self, other: Self) -> Self {
126        Self::new(self.start.max(other.start), self.end.min(other.end))
127    }
128
129    pub fn intersection(&self, other: impl Into<Self>) -> Option<Self> {
130        let other = other.into();
131        self.intersects(other).then(|| self.intersection_uncheck(other))
132    }
133
134    pub fn advance(&mut self, offset: usize) {
135        self.start += offset;
136        self.end += offset;
137    }
138
139    pub fn move_back(&self, offset: usize) -> Self {
140        Self::new(self.start + offset, self.end + offset)
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147    use std::cmp::Ordering;
148
149    #[test]
150    #[allow(clippy::many_single_char_names)]
151    fn test_strict_order() {
152        // Test ranges that are completely before
153        let a = TextRange::new(0, 5);
154        let b = TextRange::new(6, 10);
155        assert_eq!(a.strict_order(&b), Some(Ordering::Less));
156        assert_eq!(b.strict_order(&a), Some(Ordering::Greater));
157
158        // Test ranges that are completely after
159        let c = TextRange::new(15, 20);
160        assert_eq!(b.strict_order(&c), Some(Ordering::Less));
161        assert_eq!(c.strict_order(&b), Some(Ordering::Greater));
162
163        // Test overlapping ranges
164        let d = TextRange::new(7, 8);
165        assert_eq!(b.strict_order(&d), None);
166        assert_eq!(d.strict_order(&b), None);
167
168        // Test adjacent ranges
169        let e = TextRange::new(10, 15);
170        assert_eq!(b.strict_order(&e), Some(Ordering::Less));
171        assert_eq!(e.strict_order(&b), Some(Ordering::Greater));
172
173        // Test equal ranges
174        let f = TextRange::new(6, 10);
175        assert_eq!(b.strict_order(&f), None);
176        assert_eq!(f.strict_order(&b), None);
177    }
178}
interval_tree/range.rs

interval_tree/
range.rs
