conjure_cp_core/ast/domains/
range.rs

1use crate::ast::domains::Int;
2use num_traits::Num;
3use polyquine::Quine;
4use serde::{Deserialize, Serialize};
5use std::fmt::Display;
6
7#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize, Quine)]
8#[path_prefix(conjure_cp::ast)]
9pub enum Range<A = Int> {
10    Single(A),
11    Bounded(A, A),
12    UnboundedL(A),
13    UnboundedR(A),
14    Unbounded,
15}
16
17impl<A> Range<A> {
18    /// Whether the range is **bounded** on either side. A bounded range may still be infinite.
19    /// See also: [Range::is_finite].
20    pub fn is_lower_or_upper_bounded(&self) -> bool {
21        match &self {
22            Range::Single(_)
23            | Range::Bounded(_, _)
24            | Range::UnboundedL(_)
25            | Range::UnboundedR(_) => true,
26            Range::Unbounded => false,
27        }
28    }
29
30    /// Whether the range is **unbounded** on both sides.
31    pub fn is_unbounded(&self) -> bool {
32        !self.is_lower_or_upper_bounded()
33    }
34
35    /// Whether the range is **finite**. See also: [Range::is_lower_or_upper_bounded].
36    pub fn is_finite(&self) -> bool {
37        match &self {
38            Range::Single(_) | Range::Bounded(_, _) => true,
39            Range::Unbounded | Range::UnboundedL(_) | Range::UnboundedR(_) => false,
40        }
41    }
42}
43
44impl<A: Ord> Range<A> {
45    pub fn contains(&self, val: &A) -> bool {
46        match self {
47            Range::Single(x) => x == val,
48            Range::Bounded(x, y) => x <= val && val <= y,
49            Range::UnboundedR(x) => x <= val,
50            Range::UnboundedL(x) => val <= x,
51            Range::Unbounded => true,
52        }
53    }
54
55    /// Returns the lower bound of the range, if it has one
56    pub fn low(&self) -> Option<&A> {
57        match self {
58            Range::Single(a) => Some(a),
59            Range::Bounded(a, _) => Some(a),
60            Range::UnboundedR(a) => Some(a),
61            Range::UnboundedL(_) | Range::Unbounded => None,
62        }
63    }
64
65    /// Returns the upper bound of the range, if it has one
66    pub fn high(&self) -> Option<&A> {
67        match self {
68            Range::Single(a) => Some(a),
69            Range::Bounded(_, a) => Some(a),
70            Range::UnboundedL(a) => Some(a),
71            Range::UnboundedR(_) | Range::Unbounded => None,
72        }
73    }
74}
75
76impl<A: Ord + Clone> Range<A> {
77    /// Create a new range with a lower and upper bound
78    pub fn new(lo: Option<A>, hi: Option<A>) -> Range<A> {
79        match (lo, hi) {
80            (None, None) => Range::Unbounded,
81            (Some(l), None) => Range::UnboundedR(l),
82            (None, Some(r)) => Range::UnboundedL(r),
83            (Some(l), Some(r)) => {
84                if l == r {
85                    Range::Single(l)
86                } else {
87                    let min = Ord::min(&l, &r).clone();
88                    let max = Ord::max(l, r);
89                    Range::Bounded(min, max)
90                }
91            }
92        }
93    }
94
95    /// Given a slice of ranges, create a single range that spans from the start
96    /// of the leftmost range to the end of the rightmost range.
97    /// An empty slice is considered equivalent to `Range::unbounded`.
98    pub fn spanning(rngs: &[Range<A>]) -> Range<A> {
99        if rngs.is_empty() {
100            return Range::Unbounded;
101        }
102
103        let mut lo = rngs[0].low();
104        let mut hi = rngs[0].high();
105        for rng in rngs {
106            lo = match (lo, rng.low()) {
107                (Some(curr), Some(new)) => Some(curr.min(new)),
108                _ => None,
109            };
110            hi = match (hi, rng.high()) {
111                (Some(curr), Some(new)) => Some(curr.max(new)),
112                _ => None,
113            };
114        }
115        Range::new(lo.cloned(), hi.cloned())
116    }
117}
118
119impl<A: Num + Ord + Clone> Range<A> {
120    pub fn length(&self) -> Option<A> {
121        match self {
122            Range::Single(_) => Some(A::one()),
123            Range::Bounded(i, j) => Some(j.clone() - i.clone() + A::one()),
124            Range::UnboundedR(_) | Range::UnboundedL(_) | Range::Unbounded => None,
125        }
126    }
127
128    /// Returns true if this interval overlaps another one, i.e. at least one
129    /// number is part of both `self` and `other`
130    /// E.g:
131    /// - [0, 2] overlaps [2, 4]
132    /// - [1, 3] overlaps [2, 4]
133    /// - [4, 6] overlaps [2, 4]
134    pub fn overlaps(&self, other: &Range<A>) -> bool {
135        self.low()
136            .is_none_or(|la| other.high().is_none_or(|rb| la <= rb))
137            && self
138                .high()
139                .is_none_or(|ra| other.low().is_none_or(|lb| ra >= lb))
140    }
141
142    /// Returns true if this interval touches another one on the left
143    /// E.g: [1, 2] touches_left  [3, 4]
144    pub fn touches_left(&self, other: &Range<A>) -> bool {
145        self.high().is_some_and(|ra| {
146            let ra = ra.clone() + A::one();
147            other.low().is_some_and(|lb| ra.eq(lb))
148        })
149    }
150
151    /// Returns true if this interval touches another one on the right
152    /// E.g: [3, 4] touches_right  [1, 2]
153    pub fn touches_right(&self, other: &Range<A>) -> bool {
154        self.low().is_some_and(|la| {
155            let la = la.clone() - A::one();
156            other.high().is_some_and(|rb| la.eq(rb))
157        })
158    }
159
160    /// Returns true if this interval overlaps or touches another one
161    /// E.g:
162    /// - [1, 3] joins [4, 6]
163    /// - [2, 4] joins [4, 6]
164    /// - [3, 5] joins [4, 6]
165    /// - [6, 8] joins [4, 6]
166    /// - [7, 8] joins [4, 6]
167    pub fn joins(&self, other: &Range<A>) -> bool {
168        self.touches_left(other) || self.overlaps(other) || self.touches_right(other)
169    }
170
171    /// Returns true if this interval is strictly before another one
172    pub fn is_before(&self, other: &Range<A>) -> bool {
173        self.high()
174            .is_some_and(|ra| other.low().is_some_and(|lb| ra < &(lb.clone() - A::one())))
175    }
176
177    /// Returns true if this interval is strictly after another one
178    pub fn is_after(&self, other: &Range<A>) -> bool {
179        self.low()
180            .is_some_and(|la| other.high().is_some_and(|rb| la > &(rb.clone() + A::one())))
181    }
182
183    /// If the two ranges join, return a new range which spans both
184    pub fn join(&self, other: &Range<A>) -> Option<Range<A>> {
185        if self.joins(other) {
186            let lo = Ord::min(self.low(), other.low());
187            let hi = Ord::max(self.high(), other.high());
188            return Some(Range::new(lo.cloned(), hi.cloned()));
189        }
190        None
191    }
192
193    /// Merge all joining ranges in the list, and return a new vec of disjoint ranges.
194    /// E.g:
195    /// ```ignore
196    /// [(2..3), (4), (..1), (6..8)] -> [(..4), (6..8)]
197    /// ```
198    ///
199    /// # Performance
200    /// Currently uses a naive O(n^2) algorithm.
201    /// A more optimal approach based on interval trees is planned.
202    pub fn squeeze(rngs: &[Range<A>]) -> Vec<Range<A>> {
203        let mut ans = Vec::from(rngs);
204
205        if ans.is_empty() {
206            return ans;
207        }
208
209        loop {
210            let mut merged = false;
211
212            // Check every pair of ranges and join them if possible
213            'outer: for i in 0..ans.len() {
214                for j in (i + 1)..ans.len() {
215                    if let Some(joined) = ans[i].join(&ans[j]) {
216                        ans[i] = joined;
217                        // Safe to delete here because we restart the outer loop immediately
218                        ans.remove(j);
219                        merged = true;
220                        break 'outer;
221                    }
222                }
223            }
224
225            // If no merges occurred, we're done
226            if !merged {
227                break;
228            }
229        }
230
231        ans
232    }
233
234    /// If this range is bounded, returns a lazy iterator over all values within the range.
235    /// Otherwise, returns None.
236    pub fn iter(&self) -> Option<RangeIterator<A>> {
237        match self {
238            Range::Single(val) => Some(RangeIterator::Single(Some(val.clone()))),
239            Range::Bounded(start, end) => Some(RangeIterator::Bounded {
240                current: start.clone(),
241                end: end.clone(),
242            }),
243            Range::UnboundedL(_) | Range::UnboundedR(_) | Range::Unbounded => None,
244        }
245    }
246
247    pub fn values(rngs: &[Range<A>]) -> Option<impl Iterator<Item = A>> {
248        let itrs = rngs
249            .iter()
250            .map(Range::iter)
251            .collect::<Option<Vec<RangeIterator<A>>>>()?;
252        Some(itrs.into_iter().flatten())
253    }
254}
255
256/// Iterator for Range<A> that yields values lazily
257pub enum RangeIterator<A> {
258    Single(Option<A>),
259    Bounded { current: A, end: A },
260}
261
262impl<A: Num + Ord + Clone> Iterator for RangeIterator<A> {
263    type Item = A;
264
265    fn next(&mut self) -> Option<Self::Item> {
266        match self {
267            RangeIterator::Single(val) => val.take(),
268            RangeIterator::Bounded { current, end } => {
269                if current > end {
270                    return None;
271                }
272
273                let result = current.clone();
274                *current = current.clone() + A::one();
275
276                Some(result)
277            }
278        }
279    }
280}
281
282impl<A: Display> Display for Range<A> {
283    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
284        match self {
285            Range::Single(i) => write!(f, "{i}"),
286            Range::Bounded(i, j) => write!(f, "{i}..{j}"),
287            Range::UnboundedR(i) => write!(f, "{i}.."),
288            Range::UnboundedL(i) => write!(f, "..{i}"),
289            Range::Unbounded => write!(f, ""),
290        }
291    }
292}
293
294#[allow(unused_imports)]
295mod test {
296    use super::*;
297    use crate::range;
298
299    #[test]
300    pub fn test_range_macros() {
301        assert_eq!(range!(1..3), Range::Bounded(1, 3));
302        assert_eq!(range!(1..), Range::UnboundedR(1));
303        assert_eq!(range!(..3), Range::UnboundedL(3));
304        assert_eq!(range!(1), Range::Single(1));
305    }
306
307    #[test]
308    pub fn test_range_low() {
309        assert_eq!(range!(1..3).low(), Some(&1));
310        assert_eq!(range!(1..).low(), Some(&1));
311        assert_eq!(range!(1).low(), Some(&1));
312        assert_eq!(range!(..3).low(), None);
313        assert_eq!(Range::<Int>::Unbounded.low(), None);
314    }
315
316    #[test]
317    pub fn test_range_high() {
318        assert_eq!(range!(1..3).high(), Some(&3));
319        assert_eq!(range!(1..).high(), None);
320        assert_eq!(range!(1).high(), Some(&1));
321        assert_eq!(range!(..3).high(), Some(&3));
322        assert_eq!(Range::<Int>::Unbounded.high(), None);
323    }
324
325    #[test]
326    pub fn test_range_is_finite() {
327        assert!(range!(1..3).is_finite());
328        assert!(range!(1).is_finite());
329        assert!(!range!(1..).is_finite());
330        assert!(!range!(..3).is_finite());
331        assert!(!Range::<Int>::Unbounded.is_finite());
332    }
333
334    #[test]
335    pub fn test_range_bounded() {
336        assert!(range!(1..3).is_lower_or_upper_bounded());
337        assert!(range!(1).is_lower_or_upper_bounded());
338        assert!(range!(1..).is_lower_or_upper_bounded());
339        assert!(range!(..3).is_lower_or_upper_bounded());
340        assert!(!Range::<Int>::Unbounded.is_lower_or_upper_bounded());
341    }
342
343    #[test]
344    pub fn test_range_length() {
345        assert_eq!(range!(1..3).length(), Some(3));
346        assert_eq!(range!(1).length(), Some(1));
347        assert_eq!(range!(1..).length(), None);
348        assert_eq!(range!(..3).length(), None);
349        assert_eq!(Range::<Int>::Unbounded.length(), None);
350    }
351
352    #[test]
353    pub fn test_range_contains_value() {
354        assert!(range!(1..3).contains(&2));
355        assert!(!range!(1..3).contains(&4));
356        assert!(range!(1).contains(&1));
357        assert!(!range!(1).contains(&2));
358        assert!(Range::Unbounded.contains(&42));
359    }
360
361    #[test]
362    pub fn test_range_overlaps() {
363        assert!(range!(1..3).overlaps(&range!(2..4)));
364        assert!(range!(1..3).overlaps(&range!(3..5)));
365        assert!(!range!(1..3).overlaps(&range!(4..6)));
366        assert!(Range::Unbounded.overlaps(&range!(1..3)));
367    }
368
369    #[test]
370    pub fn test_range_touches_left() {
371        assert!(range!(1..2).touches_left(&range!(3..4)));
372        assert!(range!(1..2).touches_left(&range!(3)));
373        assert!(range!(-5..-4).touches_left(&range!(-3..2)));
374        assert!(!range!(1..2).touches_left(&range!(4..5)));
375        assert!(!range!(1..2).touches_left(&range!(2..3)));
376        assert!(!range!(3..4).touches_left(&range!(1..2)));
377    }
378
379    #[test]
380    pub fn test_range_touches_right() {
381        assert!(range!(3..4).touches_right(&range!(1..2)));
382        assert!(range!(3).touches_right(&range!(1..2)));
383        assert!(range!(0..1).touches_right(&range!(-2..-1)));
384        assert!(!range!(1..2).touches_right(&range!(3..4)));
385        assert!(!range!(2..3).touches_right(&range!(1..2)));
386        assert!(!range!(1..2).touches_right(&range!(1..2)));
387    }
388
389    #[test]
390    pub fn test_range_is_before() {
391        assert!(range!(1..2).is_before(&range!(4..5)));
392        assert!(range!(1..2).is_before(&range!(4..)));
393        assert!(!range!(1..2).is_before(&range!(3..)));
394        assert!(!range!(1..2).is_before(&range!(..4)));
395        assert!(!range!(1..2).is_before(&range!(2..4)));
396        assert!(!range!(3..4).is_before(&range!(1..2)));
397        assert!(!range!(1..2).is_before(&Range::Unbounded));
398    }
399
400    #[test]
401    pub fn test_range_is_after() {
402        assert!(range!(5..6).is_after(&range!(1..2)));
403        assert!(range!(4..5).is_after(&range!(..2)));
404        assert!(!range!(4..5).is_after(&range!(..3)));
405        assert!(!range!(2..3).is_after(&range!(1..2)));
406        assert!(!range!(1..2).is_after(&range!(3..4)));
407        assert!(!range!(1..2).is_after(&Range::Unbounded));
408    }
409
410    #[test]
411    pub fn test_range_squeeze() {
412        let input = vec![range!(2..3), range!(4), range!(..1), range!(6..8)];
413        let squeezed = Range::squeeze(&input);
414        assert_eq!(squeezed, vec![range!(..4), range!(6..8)]);
415    }
416
417    #[test]
418    pub fn test_range_spanning() {
419        assert_eq!(Range::<Int>::spanning(&[]), Range::Unbounded);
420        assert_eq!(Range::spanning(&[range!(1..2), range!(4..5)]), range!(1..5));
421        assert_eq!(
422            Range::spanning(&[range!(..0), range!(2..4)]),
423            Range::UnboundedL(4)
424        );
425        assert_eq!(
426            Range::spanning(&[range!(0), range!(2..3), range!(5..)]),
427            Range::UnboundedR(0)
428        );
429        assert_eq!(
430            Range::spanning(&[range!(..0), range!(2..)]),
431            Range::Unbounded
432        );
433    }
434}
conjure_cp_core/ast/domains/range.rs

conjure_cp_core/ast/domains/
range.rs
