1  //! This module exposes helpers for working with types that implement
  2  //! [`RangeBounds`].
  3  
  4  use std::cmp::{self, Ord};
  5  use std::ops::{Bound, RangeBounds};
  6  
  7  /// An extension trait for [`RangeBounds`].
  8  pub trait RangeBoundsExt<T>: RangeBounds<T> {
  9      /// Compute the intersection of two `RangeBound`s.
 10      ///
 11      /// In essence, this computes the intersection of the intervals described by bounds of the
 12      /// two objects.
 13      ///
 14      /// Returns `None` if the intersection of the two ranges is the empty set.
 15      fn intersect<'a, U: RangeBounds<T>>(
 16          &'a self,
 17          other: &'a U,
 18      ) -> Option<(Bound<&'a T>, Bound<&'a T>)>;
 19  }
 20  
 21  impl<T, R> RangeBoundsExt<T> for R
 22  where
 23      R: RangeBounds<T>,
 24      T: Ord,
 25  {
 26      fn intersect<'a, U: RangeBounds<T>>(
 27          &'a self,
 28          other: &'a U,
 29      ) -> Option<(Bound<&'a T>, Bound<&'a T>)> {
 30          use Bound::*;
 31  
 32          let this_start = self.start_bound();
 33          let other_start = other.start_bound();
 34          let this_end = self.end_bound();
 35          let other_end = other.end_bound();
 36  
 37          let start = bounds_max(this_start, other_start);
 38          let end = bounds_min(this_end, other_end);
 39  
 40          match (start, end) {
 41              (Excluded(start), Excluded(end)) | (Included(start), Excluded(end)) if start == end => {
 42                  // The interval (n, n) = [n, n) = {} (empty set).
 43                  None
 44              }
 45              (Included(start), Included(end))
 46              | (Included(start), Excluded(end))
 47              | (Excluded(start), Included(end))
 48              | (Excluded(start), Excluded(end))
 49                  if start > end =>
 50              {
 51                  // For any a > b, the intervals [a, b], [a, b), (a, b], (a, b) are empty.
 52                  None
 53              }
 54              _ => Some((start, end)),
 55          }
 56      }
 57  }
 58  
 59  /// Return the largest of `b1` and `b2`.
 60  ///
 61  /// If one of the bounds is [Unbounded](Bound::Unbounded), the other will be returned.
 62  fn bounds_max<'a, T: Ord>(b1: Bound<&'a T>, b2: Bound<&'a T>) -> Bound<&'a T> {
 63      use Bound::*;
 64  
 65      match (b1, b2) {
 66          (Included(b1), Included(b2)) => Included(cmp::max(b1, b2)),
 67          (Excluded(b1), Excluded(b2)) => Excluded(cmp::max(b1, b2)),
 68  
 69          (Excluded(b1), Included(b2)) if b1 >= b2 => Excluded(b1),
 70          (Excluded(_), Included(b2)) => Included(b2),
 71  
 72          (Included(b1), Excluded(b2)) if b2 >= b1 => Excluded(b2),
 73          (Included(b1), Excluded(_)) => Included(b1),
 74  
 75          (b, Unbounded) | (Unbounded, b) => b,
 76      }
 77  }
 78  
 79  /// Return the smallest of `b1` and `b2`.
 80  ///
 81  /// If one of the bounds is [Unbounded](Bound::Unbounded), the other will be returned.
 82  fn bounds_min<'a, T: Ord>(b1: Bound<&'a T>, b2: Bound<&'a T>) -> Bound<&'a T> {
 83      use Bound::*;
 84  
 85      match (b1, b2) {
 86          (Included(b1), Included(b2)) => Included(cmp::min(b1, b2)),
 87          (Excluded(b1), Excluded(b2)) => Excluded(cmp::min(b1, b2)),
 88  
 89          (Excluded(b1), Included(b2)) if b1 <= b2 => Excluded(b1),
 90          (Excluded(_), Included(b2)) => Included(b2),
 91  
 92          (Included(b1), Excluded(b2)) if b2 <= b1 => Excluded(b2),
 93          (Included(b1), Excluded(_)) => Included(b1),
 94  
 95          (b, Unbounded) | (Unbounded, b) => b,
 96      }
 97  }
 98  
 99  #[cfg(test)]
100  mod test {
101      // @@ begin test lint list maintained by maint/add_warning @@
102      #![allow(clippy::bool_assert_comparison)]
103      #![allow(clippy::clone_on_copy)]
104      #![allow(clippy::dbg_macro)]
105      #![allow(clippy::mixed_attributes_style)]
106      #![allow(clippy::print_stderr)]
107      #![allow(clippy::print_stdout)]
108      #![allow(clippy::single_char_pattern)]
109      #![allow(clippy::unwrap_used)]
110      #![allow(clippy::unchecked_duration_subtraction)]
111      #![allow(clippy::useless_vec)]
112      #![allow(clippy::needless_pass_by_value)]
113      //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
114      use super::*;
115      use std::fmt::Debug;
116      use std::time::{Duration, SystemTime};
117      use Bound::{Excluded as Excl, Included as Incl, Unbounded};
118  
119      /// A helper that computes the intersection of `range1` and `range2`.
120      ///
121      /// This function also asserts that the intersection operation is commutative.
122      fn intersect<'a, T, R: RangeBounds<T>>(
123          range1: &'a R,
124          range2: &'a R,
125      ) -> Option<(Bound<&'a T>, Bound<&'a T>)>
126      where
127          T: PartialEq + Ord + Debug,
128      {
129          let intersection1 = range1.intersect(range2);
130          let intersection2 = range2.intersect(range1);
131  
132          assert_eq!(intersection1, intersection2);
133  
134          intersection1
135      }
136  
137      /// A helper for randomly generating either an inclusive or an exclusive bound with a
138      /// particular value.
139      fn random_bound<T>(value: T) -> Bound<T> {
140          if rand::random() {
141              Bound::Included(value)
142          } else {
143              Bound::Excluded(value)
144          }
145      }
146  
147      #[test]
148      fn no_overlap() {
149          #[allow(clippy::type_complexity)]
150          const NON_OVERLAPPING_RANGES: &[(
151              (Bound<usize>, Bound<usize>),
152              (Bound<usize>, Bound<usize>),
153          )] = &[
154              // (1, 2) and (3, 4)
155              ((Excl(1), Excl(2)), (Excl(3), Excl(4))),
156              // (1, 2) and (2, 3)
157              ((Excl(1), Excl(2)), (Excl(2), Excl(3))),
158              // (1, 2) and [2, 3)
159              ((Excl(1), Excl(2)), (Incl(2), Excl(3))),
160              // (1, 2) and [2, 3]
161              ((Excl(1), Excl(2)), (Incl(3), Incl(4))),
162              // (-inf, 2) and [2, 3]
163              ((Unbounded, Excl(2)), (Incl(2), Incl(3))),
164              // (-inf, 2) and (2, inf)
165              ((Unbounded, Excl(2)), (Excl(2), Unbounded)),
166              // (-inf, 2) and [2, inf)
167              ((Unbounded, Excl(2)), (Incl(2), Unbounded)),
168          ];
169  
170          for (range1, range2) in NON_OVERLAPPING_RANGES {
171              let intersection = intersect(range1, range2);
172              assert!(
173                  intersection.is_none(),
174                  "{:?} and {:?} => {:?}",
175                  range1,
176                  range2,
177                  intersection
178              );
179          }
180      }
181  
182      #[test]
183      fn intersect_unbounded_start() {
184          // (-inf, 3)
185          let range1 = (Unbounded, Excl(3));
186          // [2, 5]
187          let range2 = (Incl(2), Incl(5));
188  
189          let intersection = intersect(&range1, &range2).unwrap();
190  
191          // intersection = [2 3]
192          assert_eq!(intersection.start_bound(), Bound::Included(&2));
193          assert_eq!(intersection.end_bound(), Bound::Excluded(&3));
194      }
195  
196      #[test]
197      fn intersect_unbounded_end() {
198          // (8, inf)
199          let range1 = (Excl(8), Unbounded);
200          // [8, 20]
201          let range2 = (Incl(8), Incl(20));
202  
203          let intersection = intersect(&range1, &range2).unwrap();
204  
205          // intersection = (8, 20]
206          assert_eq!(intersection.start_bound(), Bound::Excluded(&8));
207          assert_eq!(intersection.end_bound(), Bound::Included(&20));
208      }
209  
210      #[test]
211      fn intersect_unbounded_range() {
212          #[allow(clippy::type_complexity)]
213          const RANGES: &[(Bound<usize>, Bound<usize>)] = &[
214              // (1, 2)
215              (Excl(1), Excl(2)),
216              // (1, 2]
217              (Excl(1), Incl(2)),
218              // [1, 2]
219              (Incl(1), Incl(2)),
220              // [1, 2)
221              (Incl(1), Excl(2)),
222              // (1, inf)
223              (Excl(1), Unbounded),
224              // [1, inf)
225              (Incl(1), Unbounded),
226              // (-inf, 2)
227              (Unbounded, Excl(2)),
228              // (-inf, 2]
229              (Unbounded, Incl(2)),
230          ];
231  
232          // The intersection of any interval I with (Unbounded, Unbounded) will be I.
233          let range1 = (Unbounded, Unbounded);
234  
235          for range2 in RANGES {
236              let range2 = (range2.0.as_ref(), range2.1.as_ref());
237              assert_eq!(intersect(&range1, &range2).unwrap(), range2);
238          }
239      }
240  
241      #[test]
242      fn intersect_time_bounds() {
243          const MIN: Duration = Duration::from_secs(60);
244  
245          // time (relative to now):  0   1   2   3
246          //                          |   |   |   |
247          // [t1, t2]:                [.......]
248          // [t3, t4]:                    [.......]
249          // intersection:                [...]
250          let now = SystemTime::now();
251          let t1 = now;
252          let t2 = now + 2 * MIN;
253  
254          let t3 = now + 1 * MIN;
255          let t4 = now + 3 * MIN;
256  
257          let b1 = (Bound::Included(t1), Bound::Included(t2));
258          let b2 = (Bound::Included(t3), Bound::Included(t4));
259          let expected = (Bound::Included(&t3), Bound::Included(&t2));
260          assert_eq!(intersect(&b1, &b2).unwrap(), expected);
261  
262          //  t1  -  -  t2  -  -
263          //                   t3  -  -  t4
264          //
265          // time (relative to now):  0   1   2   3   4   5   6   7
266          //                          |   |   |   |   |   |   |   |
267          // [t1, t2]:                [.......]
268          // [t3, t4]:                                [............]
269          let t3 = now + 4 * MIN;
270          let t4 = now + 7 * MIN;
271          let b2 = (Bound::Included(t3), Bound::Included(t4));
272          assert!(intersect(&b1, &b2).is_none());
273      }
274  
275      #[test]
276      fn combinatorial() {
277          for i in 0..10 {
278              for j in 0..10 {
279                  for k in 0..10 {
280                      for l in 0..10 {
281                          let range1 = (random_bound(i), random_bound(j));
282                          let range2 = (random_bound(k), random_bound(l));
283  
284                          let intersection = intersect(&range1, &range2);
285  
286                          for witness in 0..10 {
287                              let c1 = range1.contains(&witness);
288                              let c2 = range2.contains(&witness);
289                              let both_contain_witness = c1 && c2;
290  
291                              if both_contain_witness {
292                                  // If both ranges contain `witness` they definitely intersect.
293                                  assert!(intersection.unwrap().contains(&witness));
294                              } else if let Some(intersection) = intersection {
295                                  // If one of them doesn't contain `witness`, `witness` is
296                                  // definitely not part of the intersection.
297                                  assert!(!intersection.contains(&witness));
298                              }
299                          }
300                      }
301                  }
302              }
303          }
304      }
305  }