repr/
interval.rs

1//! <https://en.wikipedia.org/wiki/Boundary_(topology)>
2//! <https://en.wikipedia.org/wiki/Partition_of_a_set>
3//! <https://en.wikipedia.org/wiki/Sequence>
4
5use core::{
6    cmp::{max, min},
7    iter::{IntoIterator, Step},
8    ops::RangeInclusive,
9};
10
11use unconst::unconst;
12
13use crate::repr::Repr::{self, Or, Zero};
14use crate::traits::Integral;
15
16#[unconst]
17// TODO(rinarakaki) Does negative Interval (self.1 < self.0) have use case?
18#[derive_const(Clone, Default, PartialEq, PartialOrd, Ord)]
19#[derive(Copy, Debug, Eq)]
20pub struct Interval<I: const Integral>(pub I, pub I);
21
22#[unconst]
23impl<I: const Integral> Interval<I> {
24    pub const fn new(from: I, to: I) -> Self {
25        if from <= to {
26            Interval(from, to)
27        } else {
28            Interval(to, from)
29        }
30    }
31
32    pub const fn full() -> Self {
33        Interval(I::MIN, I::MAX)
34    }
35
36    /// Intersect this Interval with the given Interval and return the result.
37    ///
38    /// If the intersection is empty, then return Zero.
39    pub const fn and(self, other: Self) -> Repr<I> {
40        if max(self.0, other.0) <= min(self.1, other.1) {
41            Repr::Interval(Self::new(max(self.0, other.0), min(self.1, other.1)))
42        } else {
43            Zero
44        }
45    }
46
47    /// Union the given overlapping Interval into this Interval.
48    ///
49    /// If the two Seqs aren't contiguous, then don't union them.
50    pub const fn or(self, other: Self) -> Repr<I> {
51        if max(self.0, other.0) <= min(self.1, other.1).succ() {
52            Repr::Interval(Self::new(min(self.0, other.0), max(self.1, other.1)))
53        } else {
54            Or(
55                Box::new(Repr::Interval(self)),
56                Box::new(Repr::Interval(other)),
57            )
58        }
59    }
60
61    // /// Compute the symmetric difference the given Interval from this Interval. This
62    // /// returns the union of the two Intervals minus its intersection.
63    // pub const fn xor(self, other: Self) -> Repr<I> {
64    //     let or = match self.or(other) {
65    //         Or(lhs, rhs) => return Or(lhs, rhs),
66    //         Repr::Interval(or) => or,
67    //     };
68    //     let and = match self.and(other) {
69    //         Or(lhs, rhs) => return Or(lhs, rhs),
70    //         Repr::Interval(and) => and,
71    //     };
72    //     or.sub(and)
73    // }
74
75    // /// Subtract the given Interval from this Interval and return the resulting
76    // /// Seqs.
77    // ///
78    // /// If subtraction would result in an empty Interval, then no Seqs are
79    // /// returned.
80    // ///
81    // /// other.0 <= self.0 <= self.1 <= other.1 (self <= other) => Zero
82    // /// self.0 <= other.0 <= other.1 <= self.1 (other <= self) => (lower, upper)
83    // /// self.0 <= other.0 <= self.1 <= other.1 => (lower, None)
84    // /// other.0 <= self.0 <= other.1 <= self.1 => (None, uppper)
85    // pub const fn sub(self, other: Self) -> Repr<I> {
86    //     if self.le(&other) {
87    //         return Zero;
88    //     }
89    //     if self.contiguous(&other) {
90    //         return Repr::Interval(self.clone());
91    //     }
92    //     let mut ret = (None, None);
93    //     if self.0 < other.0 {
94    //         ret.0 = Some(Self::new(self.0, other.0.pred()));
95    //     }
96    //     if other.1 < self.1 {
97    //         let range = Self::new(other.1.succ(), self.1);
98    //         if ret.0.is_none() {
99    //             ret.0 = Some(range);
100    //         } else {
101    //             ret.1 = Some(range);
102    //         }
103    //     }
104    //     ret
105    // }
106
107    ///
108    pub const fn contiguous(&self, other: &Self) -> bool {
109        max(self.0, other.0) <= min(self.1, other.1)
110    }
111
112    // /// Negate this Interval.
113    // ///
114    // /// For all `a` where `a` is any element, if `a` is in this interval, then it will not be in this set after negation.
115    // pub const fn not(self) -> Repr<I> {
116    //     Self::full().sub(self)
117    // }
118
119    // TODO(rinarakaki) Why not simply `other.0 <= self.0 && self.1 <= other.1`
120    /// a ⊆ b
121    pub const fn le(&self, other: &Self) -> bool {
122        (other.0 <= self.0 && self.0 <= other.1) && (other.0 <= self.1 && self.1 <= other.1)
123    }
124
125    /// i ∈ a
126    pub fn has(&self, i: I) -> bool {
127        self.0 <= i && i <= self.1
128    }
129
130    pub const fn len(&self) -> usize {
131        <I as Step>::steps_between(&self.0, &self.1).1.unwrap()
132    }
133}
134
135#[unconst]
136impl<I: const Integral> const IntoIterator for Interval<I> {
137    type Item = I;
138    type IntoIter = RangeInclusive<I>;
139
140    fn into_iter(self) -> Self::IntoIter {
141        self.0..=self.1
142    }
143}
144
145impl Interval<char> {
146    /// Returns true if and only if this character class will either match
147    /// nothing or only ASCII bytes. Stated differently, this returns false
148    /// if and only if this class contains a non-ASCII codepoint.
149    pub fn is_all_ascii(&self) -> bool {
150        self.1 <= '\x7F'
151    }
152}
repr/interval.rs

repr/
interval.rs
