conjure_cp_core/ast/domains/
range.rs

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

conjure_cp_core/ast/domains/
range.rs
