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) if i > j => Some(A::zero()),
158            Range::Bounded(i, j) => Some(j.clone() - i.clone() + A::one()),
159            Range::UnboundedR(_) | Range::UnboundedL(_) | Range::Unbounded => None,
160        }
161    }
162
163    /// Returns true if this interval overlaps another one, i.e. at least one
164    /// number is part of both `self` and `other`
165    /// E.g:
166    /// - [0, 2] overlaps [2, 4]
167    /// - [1, 3] overlaps [2, 4]
168    /// - [4, 6] overlaps [2, 4]
169    pub fn overlaps(&self, other: &Range<A>) -> bool {
170        self.low()
171            .is_none_or(|la| other.high().is_none_or(|rb| la <= rb))
172            && self
173                .high()
174                .is_none_or(|ra| other.low().is_none_or(|lb| ra >= lb))
175    }
176
177    /// Returns true if this interval touches another one on the left
178    /// E.g: [1, 2] touches_left  [3, 4]
179    pub fn touches_left(&self, other: &Range<A>) -> bool {
180        self.high().is_some_and(|ra| {
181            let ra = ra.clone() + A::one();
182            other.low().is_some_and(|lb| ra.eq(lb))
183        })
184    }
185
186    /// Returns true if this interval touches another one on the right
187    /// E.g: [3, 4] touches_right  [1, 2]
188    pub fn touches_right(&self, other: &Range<A>) -> bool {
189        self.low().is_some_and(|la| {
190            let la = la.clone() - A::one();
191            other.high().is_some_and(|rb| la.eq(rb))
192        })
193    }
194
195    /// Returns true if this interval overlaps or touches another one
196    /// E.g:
197    /// - [1, 3] joins [4, 6]
198    /// - [2, 4] joins [4, 6]
199    /// - [3, 5] joins [4, 6]
200    /// - [6, 8] joins [4, 6]
201    /// - [7, 8] joins [4, 6]
202    pub fn joins(&self, other: &Range<A>) -> bool {
203        self.touches_left(other) || self.overlaps(other) || self.touches_right(other)
204    }
205
206    /// Returns true if this interval is strictly before another one
207    pub fn is_before(&self, other: &Range<A>) -> bool {
208        self.high()
209            .is_some_and(|ra| other.low().is_some_and(|lb| ra < &(lb.clone() - A::one())))
210    }
211
212    /// Returns true if this interval is strictly after another one
213    pub fn is_after(&self, other: &Range<A>) -> bool {
214        self.low()
215            .is_some_and(|la| other.high().is_some_and(|rb| la > &(rb.clone() + A::one())))
216    }
217
218    /// If the two ranges join, return a new range which spans both
219    pub fn join(&self, other: &Range<A>) -> Option<Range<A>> {
220        if self.joins(other) {
221            let lo = Ord::min(self.low(), other.low());
222            let hi = match (self.high(), other.high()) {
223                (Some(a), Some(b)) => Some(Ord::max(a, b)),
224                _ => None,
225            };
226            return Some(Range::new(lo.cloned(), hi.cloned()));
227        }
228        None
229    }
230
231    /// Merge all joining ranges in the list, and return a new vec of disjoint ranges.
232    /// E.g:
233    /// ```ignore
234    /// [(2..3), (4), (..1), (6..8)] -> [(..4), (6..8)]
235    /// ```
236    ///
237    /// # Performance
238    /// Currently uses a naive O(n^2) algorithm.
239    /// A more optimal approach based on interval trees is planned.
240    pub fn squeeze(rngs: &[Range<A>]) -> Vec<Range<A>> {
241        let mut ans = Vec::from(rngs);
242
243        if ans.is_empty() {
244            return ans;
245        }
246
247        loop {
248            let mut merged = false;
249
250            // Check every pair of ranges and join them if possible
251            'outer: for i in 0..ans.len() {
252                for j in (i + 1)..ans.len() {
253                    if let Some(joined) = ans[i].join(&ans[j]) {
254                        ans[i] = joined;
255                        // Safe to delete here because we restart the outer loop immediately
256                        ans.remove(j);
257                        merged = true;
258                        break 'outer;
259                    }
260                }
261            }
262
263            // If no merges occurred, we're done
264            if !merged {
265                break;
266            }
267        }
268
269        ans
270    }
271
272    /// If this range is bounded, returns a lazy iterator over all values within the range.
273    /// Otherwise, returns None.
274    pub fn iter(&self) -> Option<RangeIterator<A>> {
275        match self {
276            Range::Single(val) => Some(RangeIterator::Single(Some(val.clone()))),
277            Range::Bounded(start, end) => Some(RangeIterator::Bounded {
278                current: start.clone(),
279                end: end.clone(),
280            }),
281            Range::UnboundedL(_) | Range::UnboundedR(_) | Range::Unbounded => None,
282        }
283    }
284
285    /// Lazily iterate all values in a list of ranges
286    pub fn values(rngs: &[Range<A>]) -> Option<impl Iterator<Item = A>> {
287        let itrs = rngs
288            .iter()
289            .map(Range::iter)
290            .collect::<Option<Vec<RangeIterator<A>>>>()?;
291        Some(itrs.into_iter().flatten())
292    }
293
294    /// True if the list of ranges is contiguous
295    pub fn is_contiguous(rngs: &[Range<A>]) -> bool {
296        Self::squeeze(rngs).len() <= 1
297    }
298
299    /// Lowest value from a sequence of ranges
300    pub fn low_of(rngs: &[Range<A>]) -> Option<&A> {
301        let mut low = rngs.first()?.low()?;
302        for rng in rngs {
303            low = Ord::min(low, rng.low()?);
304        }
305        Some(low)
306    }
307
308    /// Lowest value from a sequence of ranges
309    pub fn high_of(rngs: &[Range<A>]) -> Option<&A> {
310        let mut hi = rngs.first()?.high()?;
311        for rng in rngs {
312            hi = Ord::min(hi, rng.low()?);
313        }
314        Some(hi)
315    }
316
317    /// Total number of values across a slice of ranges.
318    /// Returns `None` if any range is unbounded.
319    pub fn total_length(rngs: &[Range<A>]) -> Option<A> {
320        rngs.iter()
321            .try_fold(A::zero(), |acc, r| Some(acc + r.length()?))
322    }
323}
324
325/// Iterator for Range<A> that yields values lazily
326pub enum RangeIterator<A> {
327    Single(Option<A>),
328    Bounded { current: A, end: A },
329}
330
331impl<A: Num + Ord + Clone> Iterator for RangeIterator<A> {
332    type Item = A;
333
334    fn next(&mut self) -> Option<Self::Item> {
335        match self {
336            RangeIterator::Single(val) => val.take(),
337            RangeIterator::Bounded { current, end } => {
338                if current > end {
339                    return None;
340                }
341
342                let result = current.clone();
343                *current = current.clone() + A::one();
344
345                Some(result)
346            }
347        }
348    }
349}
350
351impl<A: Display> Display for Range<A> {
352    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
353        match self {
354            Range::Single(i) => write!(f, "{i}"),
355            Range::Bounded(i, j) => write!(f, "{i}..{j}"),
356            Range::UnboundedR(i) => write!(f, "{i}.."),
357            Range::UnboundedL(i) => write!(f, "..{i}"),
358            Range::Unbounded => write!(f, ""),
359        }
360    }
361}
362
363#[allow(unused_imports)]
364mod test {
365    use super::*;
366    use crate::range;
367
368    #[test]
369    pub fn test_range_macros() {
370        assert_eq!(range!(1..3), Range::Bounded(1, 3));
371        assert_eq!(range!(1..), Range::UnboundedR(1));
372        assert_eq!(range!(..3), Range::UnboundedL(3));
373        assert_eq!(range!(1), Range::Single(1));
374    }
375
376    #[test]
377    pub fn test_range_low() {
378        assert_eq!(range!(1..3).low(), Some(&1));
379        assert_eq!(range!(1..).low(), Some(&1));
380        assert_eq!(range!(1).low(), Some(&1));
381        assert_eq!(range!(..3).low(), None);
382        assert_eq!(Range::<Int>::Unbounded.low(), None);
383    }
384
385    #[test]
386    pub fn test_range_high() {
387        assert_eq!(range!(1..3).high(), Some(&3));
388        assert_eq!(range!(1..).high(), None);
389        assert_eq!(range!(1).high(), Some(&1));
390        assert_eq!(range!(..3).high(), Some(&3));
391        assert_eq!(Range::<Int>::Unbounded.high(), None);
392    }
393
394    #[test]
395    pub fn test_range_is_finite() {
396        assert!(range!(1..3).is_finite());
397        assert!(range!(1).is_finite());
398        assert!(!range!(1..).is_finite());
399        assert!(!range!(..3).is_finite());
400        assert!(!Range::<Int>::Unbounded.is_finite());
401    }
402
403    #[test]
404    pub fn test_range_bounded() {
405        assert!(range!(1..3).is_lower_or_upper_bounded());
406        assert!(range!(1).is_lower_or_upper_bounded());
407        assert!(range!(1..).is_lower_or_upper_bounded());
408        assert!(range!(..3).is_lower_or_upper_bounded());
409        assert!(!Range::<Int>::Unbounded.is_lower_or_upper_bounded());
410    }
411
412    #[test]
413    pub fn test_range_length() {
414        assert_eq!(range!(1..3).length(), Some(3));
415        assert_eq!(range!(1).length(), Some(1));
416        assert_eq!(range!(1..).length(), None);
417        assert_eq!(range!(..3).length(), None);
418        assert_eq!(Range::<Int>::Unbounded.length(), None);
419    }
420
421    #[test]
422    pub fn test_range_contains_value() {
423        assert!(range!(1..3).contains(&2));
424        assert!(!range!(1..3).contains(&4));
425        assert!(range!(1).contains(&1));
426        assert!(!range!(1).contains(&2));
427        assert!(Range::Unbounded.contains(&42));
428    }
429
430    #[test]
431    pub fn test_range_overlaps() {
432        assert!(range!(1..3).overlaps(&range!(2..4)));
433        assert!(range!(1..3).overlaps(&range!(3..5)));
434        assert!(!range!(1..3).overlaps(&range!(4..6)));
435        assert!(Range::Unbounded.overlaps(&range!(1..3)));
436    }
437
438    #[test]
439    pub fn test_range_touches_left() {
440        assert!(range!(1..2).touches_left(&range!(3..4)));
441        assert!(range!(1..2).touches_left(&range!(3)));
442        assert!(range!(-5..-4).touches_left(&range!(-3..2)));
443        assert!(!range!(1..2).touches_left(&range!(4..5)));
444        assert!(!range!(1..2).touches_left(&range!(2..3)));
445        assert!(!range!(3..4).touches_left(&range!(1..2)));
446    }
447
448    #[test]
449    pub fn test_range_touches_right() {
450        assert!(range!(3..4).touches_right(&range!(1..2)));
451        assert!(range!(3).touches_right(&range!(1..2)));
452        assert!(range!(0..1).touches_right(&range!(-2..-1)));
453        assert!(!range!(1..2).touches_right(&range!(3..4)));
454        assert!(!range!(2..3).touches_right(&range!(1..2)));
455        assert!(!range!(1..2).touches_right(&range!(1..2)));
456    }
457
458    #[test]
459    pub fn test_range_is_before() {
460        assert!(range!(1..2).is_before(&range!(4..5)));
461        assert!(range!(1..2).is_before(&range!(4..)));
462        assert!(!range!(1..2).is_before(&range!(3..)));
463        assert!(!range!(1..2).is_before(&range!(..4)));
464        assert!(!range!(1..2).is_before(&range!(2..4)));
465        assert!(!range!(3..4).is_before(&range!(1..2)));
466        assert!(!range!(1..2).is_before(&Range::Unbounded));
467    }
468
469    #[test]
470    pub fn test_range_is_after() {
471        assert!(range!(5..6).is_after(&range!(1..2)));
472        assert!(range!(4..5).is_after(&range!(..2)));
473        assert!(!range!(4..5).is_after(&range!(..3)));
474        assert!(!range!(2..3).is_after(&range!(1..2)));
475        assert!(!range!(1..2).is_after(&range!(3..4)));
476        assert!(!range!(1..2).is_after(&Range::Unbounded));
477    }
478
479    #[test]
480    pub fn test_range_squeeze() {
481        let input = vec![range!(2..3), range!(4), range!(..1), range!(6..8)];
482        let squeezed = Range::squeeze(&input);
483        assert_eq!(squeezed, vec![range!(..4), range!(6..8)]);
484    }
485
486    #[test]
487    pub fn test_range_spanning() {
488        assert_eq!(Range::<Int>::spanning(&[]), Range::Unbounded);
489        assert_eq!(Range::spanning(&[range!(1..2), range!(4..5)]), range!(1..5));
490        assert_eq!(
491            Range::spanning(&[range!(..0), range!(2..4)]),
492            Range::UnboundedL(4)
493        );
494        assert_eq!(
495            Range::spanning(&[range!(0), range!(2..3), range!(5..)]),
496            Range::UnboundedR(0)
497        );
498        assert_eq!(
499            Range::spanning(&[range!(..0), range!(2..)]),
500            Range::Unbounded
501        );
502    }
503
504    #[test]
505    pub fn test_range_join() {
506        assert_eq!(range!(1..3).join(&range!(2..4)), Some(range!(1..4)));
507        assert_eq!(range!(1..3).join(&range!(3..4)), Some(range!(1..4)));
508        assert_eq!(range!(1..3).join(&range!(4..5)), Some(range!(1..5)));
509        assert_eq!(range!(..3).join(&range!(4..5)), Some(range!(..5)));
510        assert_eq!(range!(1..3).join(&range!(4..)), Some(range!(1..)));
511        assert_eq!(range!(4..).join(&range!(1..3)), Some(range!(1..)));
512        assert_eq!(range!(..3).join(&range!(4..)), Some(Range::Unbounded));
513        assert_eq!(range!(1..3).join(&range!(5..6)), None);
514    }
515}
conjure_cp_core/ast/domains/range.rs

conjure_cp_core/ast/domains/
range.rs
