conjure_cp_core/ast/domains/
range.rs

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

conjure_cp_core/ast/domains/
range.rs
