range_set/
range_compare.rs

1//! Type and functions for comparing inclusive ranges
2
3use std;
4use num_traits::PrimInt;
5
6////////////////////////////////////////////////////////////////////////////////
7//  enums                                                                     //
8////////////////////////////////////////////////////////////////////////////////
9
10/// Result of comparing a pair of ranges `(A,B)`
11#[derive(Debug,Eq,PartialEq)]
12pub enum RangeCompare {
13  Disjoint  (RangeDisjoint),
14  Intersect (RangeIntersect)
15}
16
17/// Ways in which a pair of ranges `(A,B)` can be disjoint
18#[derive(Debug,Eq,PartialEq)]
19pub enum RangeDisjoint {
20  /// `A = B = {}`
21  EmptyBoth,
22  /// `A = {}`
23  EmptyLhs,
24  /// `B = {}`
25  EmptyRhs,
26  /// `[ A ]  [ B ]`
27  LessThanProper,
28  /// `[ A ][ B ]`
29  LessThanAdjacent,
30  /// `[ B ]  [ A ]`
31  GreaterThanProper,
32  /// `[ B ][ A ]`
33  GreaterThanAdjacent
34}
35
36/// Ways in which a pair of ranges `(A,B)` can intersect
37#[derive(Debug,Eq,PartialEq)]
38pub enum RangeIntersect {
39  /// `[ A=B ]`
40  EqualTo,
41  /// `[ A [ ] B ]`
42  OverlapsLeft,
43  /// `[ B [ ] A ]`
44  OverlapsRight,
45  /// `[ B ] A ]`
46  ContainsFirst,
47  /// `[ A [ B ] ]`
48  ContainsProper,
49  /// `[ A [ B ]`
50  ContainsLast,
51  /// `[ A ] B ]`
52  ContainedByFirst,
53  /// `[ [ A ] B ]`
54  ContainedByProper,
55  /// `[ B [ A ]`
56  ContainedByLast
57}
58
59////////////////////////////////////////////////////////////////////////////////
60//  functions                                                                 //
61////////////////////////////////////////////////////////////////////////////////
62
63/// Compare two inclusive ranges.
64///
65/// ```
66/// # use range_set::*;
67/// assert_eq!(
68///   range_compare (&(0..=5), &(0..=5)),
69///   RangeCompare::Intersect (RangeIntersect::EqualTo));
70/// assert_eq!(
71///   range_compare (&(1..=0), &(1..=0)),
72///   RangeCompare::Disjoint (RangeDisjoint::EmptyBoth));
73/// ```
74pub fn range_compare <T : PrimInt> (
75  left : &std::ops::RangeInclusive <T>, right : &std::ops::RangeInclusive <T>
76) -> RangeCompare {
77  if let Some (disjoint) = RangeDisjoint::compare (left, right) {
78    disjoint.into()
79  } else if let Some (intersect) = RangeIntersect::compare (left, right) {
80    intersect.into()
81  } else {
82    unreachable!()
83  }
84}
85
86/// Compute the intersection of two inclusive ranges. Returns an empty range
87/// if they are disjoint.
88///
89/// ```
90/// # use range_set::*;
91/// assert_eq!(intersection (&(0..=3), &(2..=5)), 2..=3);
92/// assert!(intersection (&(0..=2), &(3..=5)).is_empty());
93/// ```
94pub fn intersection <T : PrimInt> (
95  left : &std::ops::RangeInclusive <T>, right : &std::ops::RangeInclusive <T>
96) -> std::ops::RangeInclusive <T> {
97  if RangeDisjoint::compare (left, right).is_none() {
98    std::cmp::max (*left.start(), *right.start())..=
99    std::cmp::min (*left.end(), *right.end())
100  } else {
101    T::one()..=T::zero()
102  }
103}
104
105////////////////////////////////////////////////////////////////////////////////
106//  impls                                                                     //
107////////////////////////////////////////////////////////////////////////////////
108
109impl From <RangeDisjoint> for RangeCompare {
110  fn from (disjoint : RangeDisjoint) -> Self {
111    RangeCompare::Disjoint (disjoint)
112  }
113}
114
115impl From <RangeIntersect> for RangeCompare {
116  fn from (intersect : RangeIntersect) -> Self {
117    RangeCompare::Intersect (intersect)
118  }
119}
120
121impl RangeDisjoint {
122  /// Tests two inclusive ranges for disjointness, returning `None` if they
123  /// intersect.
124  ///
125  /// ```
126  /// # use range_set::*;
127  /// assert_eq!(RangeDisjoint::compare (&(0..=5), &(0..=5)), None);
128  /// assert_eq!(
129  ///   RangeDisjoint::compare (&(1..=0), &(1..=0)),
130  ///   Some (RangeDisjoint::EmptyBoth));
131  /// assert_eq!(
132  ///   RangeDisjoint::compare (&(1..=0), &(0..=5)),
133  ///   Some (RangeDisjoint::EmptyLhs));
134  /// assert_eq!(
135  ///   RangeDisjoint::compare (&(0..=5), &(1..=0)),
136  ///   Some (RangeDisjoint::EmptyRhs));
137  /// assert_eq!(
138  ///   RangeDisjoint::compare (&(0..=2), &(4..=5)),
139  ///   Some (RangeDisjoint::LessThanProper));
140  /// assert_eq!(
141  ///   RangeDisjoint::compare (&(0..=2), &(3..=5)),
142  ///   Some (RangeDisjoint::LessThanAdjacent));
143  /// assert_eq!(
144  ///   RangeDisjoint::compare (&(4..=5), &(0..=2)),
145  ///   Some (RangeDisjoint::GreaterThanProper));
146  /// assert_eq!(
147  ///   RangeDisjoint::compare (&(3..=5), &(0..=2)),
148  ///   Some (RangeDisjoint::GreaterThanAdjacent));
149  /// ```
150  pub fn compare <T : PrimInt> (
151    left : &std::ops::RangeInclusive <T>, right : &std::ops::RangeInclusive <T>
152  ) -> Option <Self> {
153    match (left.is_empty(), right.is_empty()) {
154      (true, true)   => Some (RangeDisjoint::EmptyBoth),
155      (true, false)  => Some (RangeDisjoint::EmptyLhs),
156      (false, true)  => Some (RangeDisjoint::EmptyRhs),
157      (false, false) => if right.start() <= left.end()
158        && left.start() <= right.end()
159        || left.start() <= right.end() && right.start() <= left.end()
160      {
161        None  // intersection
162      } else {
163        Some (
164          if left.end() < right.start() {
165            match *right.start() - *left.end() {
166              x if x == T::one() => RangeDisjoint::LessThanAdjacent,
167              _                  => RangeDisjoint::LessThanProper
168            }
169          } else {
170            debug_assert!(right.end() < left.start());
171            match *left.start() - *right.end() {
172              x if x == T::one() => RangeDisjoint::GreaterThanAdjacent,
173              _                  => RangeDisjoint::GreaterThanProper
174            }
175          }
176        )
177      }
178    }
179  }
180}
181
182impl RangeIntersect {
183  /// Test two inclusive ranges for intersection, returning `None` if the
184  /// ranges are disjoint.
185  ///
186  /// ```
187  /// # use range_set::*;
188  /// assert_eq!(RangeIntersect::compare (&(0..=1), &(4..=5)), None);
189  /// assert_eq!(
190  ///   RangeIntersect::compare (&(0..=5), &(0..=5)),
191  ///   Some (RangeIntersect::EqualTo));
192  /// assert_eq!(
193  ///   RangeIntersect::compare (&(0..=5), &(1..=4)),
194  ///   Some (RangeIntersect::ContainsProper));
195  /// assert_eq!(
196  ///   RangeIntersect::compare (&(1..=4), &(0..=5)),
197  ///   Some (RangeIntersect::ContainedByProper));
198  /// assert_eq!(
199  ///   RangeIntersect::compare (&(0..=5), &(0..=3)),
200  ///   Some (RangeIntersect::ContainsFirst));
201  /// assert_eq!(
202  ///   RangeIntersect::compare (&(0..=5), &(4..=5)),
203  ///   Some (RangeIntersect::ContainsLast));
204  /// assert_eq!(
205  ///   RangeIntersect::compare (&(0..=2), &(0..=5)),
206  ///   Some (RangeIntersect::ContainedByFirst));
207  /// assert_eq!(
208  ///   RangeIntersect::compare (&(4..=5), &(0..=5)),
209  ///   Some (RangeIntersect::ContainedByLast));
210  /// assert_eq!(
211  ///   RangeIntersect::compare (&(0..=3), &(3..=5)),
212  ///   Some (RangeIntersect::OverlapsLeft));
213  /// assert_eq!(
214  ///   RangeIntersect::compare (&(3..=5), &(0..=3)),
215  ///   Some (RangeIntersect::OverlapsRight));
216  /// ```
217  pub fn compare <T : PrimInt> (
218    left : &std::ops::RangeInclusive <T>, right : &std::ops::RangeInclusive <T>
219  ) -> Option <Self> {
220    match (left.is_empty(), right.is_empty()) {
221      (true, true) | (true, false) | (false, true) => None,
222      (false, false) => if left.end() < right.start() ||
223        right.end() < left.start()
224      {
225        None  // disjoint
226      } else {
227        Some (if left == right {
228          RangeIntersect::EqualTo
229        } else {
230          match left.start().cmp (right.start()) {
231            std::cmp::Ordering::Less => match left.end().cmp (right.end()) {
232              std::cmp::Ordering::Less    => RangeIntersect::OverlapsLeft,
233              std::cmp::Ordering::Equal   => RangeIntersect::ContainsLast,
234              std::cmp::Ordering::Greater => RangeIntersect::ContainsProper
235            }
236            std::cmp::Ordering::Equal => match left.end().cmp (right.end()) {
237              std::cmp::Ordering::Less    => RangeIntersect::ContainedByFirst,
238              std::cmp::Ordering::Equal   => unreachable!(),
239              std::cmp::Ordering::Greater => RangeIntersect::ContainsFirst
240            }
241            std::cmp::Ordering::Greater => match left.end().cmp (right.end()) {
242              std::cmp::Ordering::Less    => RangeIntersect::ContainedByProper,
243              std::cmp::Ordering::Equal   => RangeIntersect::ContainedByLast,
244              std::cmp::Ordering::Greater => RangeIntersect::OverlapsRight
245            }
246          }
247        })
248      }
249    }
250  }
251}
range_set/range_compare.rs

range_set/
range_compare.rs
