conjure_cp_core/ast/domains/
range.rs

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

conjure_cp_core/ast/domains/
range.rs
