SHARE
TWEET

Untitled

a guest Jun 26th, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * A module to handle simple interval and interval set arithmetic.
  3.  */
  4.  
  5. use std::cmp::{Ordering, min, max};
  6. use std::ops::{Add, Sub, RangeBounds};
  7.  
  8. /// Represents a bound that is capable of total ordering.
  9. #[derive(Debug, Copy, Clone, PartialEq, Eq)]
  10. pub enum Bound<T> {
  11.     /// The value is part of the interval.
  12.     Included(T),
  13.     /// The value is not part of the interval (less).
  14.     LowerExcluded(T),
  15.     /// The value is not part of the interval (greater).
  16.     UpperExcluded(T),
  17.     /// The value goes to negative infinity.
  18.     LowerUnbounded,
  19.     /// The value goes to positive infinity.
  20.     UpperUnbounded,
  21. }
  22.  
  23. // Simple construction methods
  24.  
  25. impl <T> Bound<T> where T: Copy + Eq {
  26.     /// Constructs a lower bound from a Rust Bound type.
  27.     fn from_bound_lower(b: std::ops::Bound<&T>) -> Self {
  28.         match b {
  29.             std::ops::Bound::Unbounded => Bound::LowerUnbounded,
  30.             std::ops::Bound::Included(x) => Bound::Included(*x),
  31.             std::ops::Bound::Excluded(x) => Bound::LowerExcluded(*x),
  32.         }
  33.     }
  34.  
  35.     /// Constructs an upper bound from a Rust Bound type.
  36.     fn from_bound_upper(b: std::ops::Bound<&T>) -> Self {
  37.         match b {
  38.             std::ops::Bound::Unbounded => Bound::UpperUnbounded,
  39.             std::ops::Bound::Included(x) => Bound::Included(*x),
  40.             std::ops::Bound::Excluded(x) => Bound::UpperExcluded(*x),
  41.         }
  42.     }
  43.  
  44.     /// Returns true if the bound is touching another (no inclusion).
  45.     fn is_touching(&self, other: &Self) -> bool {
  46.         match (self, other) {
  47.             (Bound::LowerExcluded(x), Bound::Included(y)) => x == y,
  48.             (Bound::UpperExcluded(x), Bound::Included(y)) => x == y,
  49.  
  50.             (Bound::Included(x), Bound::LowerExcluded(y)) => x == y,
  51.             (Bound::Included(x), Bound::UpperExcluded(y)) => x == y,
  52.  
  53.             _ => false,
  54.         }
  55.     }
  56. }
  57.  
  58. // Define the ordering /////////////////////////////////////////////////////////
  59.  
  60. impl <T> Ord for Bound<T> where T: Ord {
  61.     fn cmp(&self, other: &Self) -> Ordering {
  62.         match (self, other) {
  63.             (Bound::LowerUnbounded, Bound::LowerUnbounded) => Ordering::Equal,
  64.             (Bound::UpperUnbounded, Bound::UpperUnbounded) => Ordering::Equal,
  65.  
  66.             (Bound::LowerUnbounded, _) => Ordering::Less,
  67.             (Bound::UpperUnbounded, _) => Ordering::Greater,
  68.  
  69.             (_, Bound::LowerUnbounded) => Ordering::Greater,
  70.             (_, Bound::UpperUnbounded) => Ordering::Less,
  71.  
  72.             (Bound::LowerExcluded(x), Bound::LowerExcluded(y)) => x.cmp(y),
  73.             (Bound::UpperExcluded(x), Bound::UpperExcluded(y)) => x.cmp(y),
  74.             (Bound::Included(x), Bound::Included(y)) => x.cmp(y),
  75.  
  76.             (Bound::Included(x), Bound::LowerExcluded(y)) => {
  77.                 match x.cmp(y) {
  78.                     Ordering::Equal => Ordering::Less,
  79.                     o => o,
  80.                 }
  81.             },
  82.  
  83.             (Bound::Included(x), Bound::UpperExcluded(y)) => {
  84.                 match x.cmp(y) {
  85.                     Ordering::Equal => Ordering::Greater,
  86.                     o => o,
  87.                 }
  88.             },
  89.  
  90.             (Bound::LowerExcluded(x), Bound::Included(y)) => {
  91.                 match x.cmp(y) {
  92.                     Ordering::Equal => Ordering::Greater,
  93.                     o => o,
  94.                 }
  95.             },
  96.  
  97.             (Bound::UpperExcluded(x), Bound::Included(y)) => {
  98.                 match x.cmp(y) {
  99.                     Ordering::Equal => Ordering::Less,
  100.                     o => o,
  101.                 }
  102.             },
  103.  
  104.             (Bound::LowerExcluded(x), Bound::UpperExcluded(y)) => {
  105.                 match x.cmp(y) {
  106.                     Ordering::Equal => Ordering::Greater,
  107.                     o => o,
  108.                 }
  109.             },
  110.  
  111.             (Bound::UpperExcluded(x), Bound::LowerExcluded(y)) => {
  112.                 match x.cmp(y) {
  113.                     Ordering::Equal => Ordering::Less,
  114.                     o => o,
  115.                 }
  116.             },
  117.         }
  118.     }
  119. }
  120.  
  121. impl <T> PartialOrd for Bound<T> where T: Ord {
  122.     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
  123.         Some(self.cmp(other))
  124.     }
  125. }
  126.  
  127. ////////////////////////////////////////////////////////////////////////////////
  128.  
  129. /// Represents a single, continuous interval. The bounds are given with
  130. /// LowerBound and UpperBound.
  131. #[derive(Debug, Copy, Clone, PartialEq, Eq)]
  132. pub struct Interval<T> {
  133.     start: Bound<T>,
  134.     end:   Bound<T>,
  135. }
  136.  
  137. impl <T> Interval<T> where T: Ord + Copy {
  138.     /// Constructs an interval from the given Rust range.
  139.     pub fn from_range<R>(r: R) -> Self where R: RangeBounds<T> {
  140.         Interval{
  141.             start: Bound::from_bound_lower(r.start_bound()),
  142.             end: Bound::from_bound_upper(r.end_bound()),
  143.         }
  144.     }
  145.  
  146.     /// Constructs an interval from lower and upper interval bounds.
  147.     pub fn from_bounds(start: Bound<T>, end: Bound<T>) -> Self {
  148.         Interval{ start, end }
  149.     }
  150.  
  151.     /// Returns true if the interval comes before another interval, no
  152.     /// intersection allowed.
  153.     pub fn is_before(&self, other: &Self) -> bool {
  154.         self.end < other.start
  155.     }
  156.  
  157.     /// Returns true if the interval is disjunct with another.
  158.     pub fn is_disjunct(&self, other: &Self) -> bool {
  159.         self.is_before(other) || other.is_before(self)
  160.     }
  161.  
  162.     /// Returns true if the interval intersects with another.
  163.     pub fn is_intersecting(&self, other: &Self) -> bool {
  164.         !self.is_disjunct(other)
  165.     }
  166.  
  167.     /// Returns true if two intervals are touching.
  168.     pub fn is_touching(&self, other: &Self) -> bool {
  169.            self.end.is_touching(&other.start)
  170.         || self.start.is_touching(&other.end)
  171.     }
  172.  
  173.     /// Returns the union of two intervals or None if the intervals cannot be
  174.     /// unified into a single one.
  175.     pub fn union_with(&self, other: &Self) -> Option<Self> {
  176.         if !self.is_intersecting(other) && !self.is_touching(other) {
  177.             None
  178.         }
  179.         else {
  180.             let start = min(self.start, other.start);
  181.             let end = max(self.end, other.end);
  182.             Some(Interval::from_bounds(start, end))
  183.         }
  184.     }
  185. }
  186.  
  187. /// Represents a union of multiple intervals. It's always the union of disjoint,
  188. /// non-touching intervals.
  189. #[derive(Debug, PartialEq, Eq)]
  190. pub struct IntervalSet<T> {
  191.     intervals: Vec<Interval<T>>,
  192. }
  193.  
  194. impl <T> IntervalSet<T> where T: Ord + Copy {
  195.     /// Constructs an empty interval set.
  196.     pub fn new() -> Self {
  197.         IntervalSet{ intervals: Vec::new() }
  198.     }
  199.  
  200.     /// Adds an interval to the interval set. Only inserts it if it's disjoint
  201.     /// with all other intervals. Otherwise modifies existing intervals.
  202.     pub fn add_interval(&mut self, interval: Interval<T>) {
  203.         let (from, to) = self.overlapping_index(&interval);
  204.  
  205.         if from == to {
  206.             self.intervals.insert(from, interval);
  207.         }
  208.         else {
  209.             self.intervals[from].start = min(
  210.                 self.intervals[from].start,
  211.                 interval.start
  212.             );
  213.             self.intervals[from].end = max(
  214.                 self.intervals[to - 1].end,
  215.                 interval.end
  216.             );
  217.             self.intervals.drain((from + 1)..to);
  218.         }
  219.     }
  220.  
  221.     /// Adds a native rust-range to the interval set. Basically calls
  222.     /// add_interval after the range is converted into an interval.
  223.     pub fn add_range<R>(&mut self, r: R) where R: RangeBounds<T> {
  224.         self.add_interval(Interval::from_range(r));
  225.     }
  226.  
  227.     /// Returns the index pair [from; to) where the given interval intersects
  228.     /// with the ones in the interval set.
  229.     fn intersecting_index(&self, interval: &Interval<T>) -> (usize, usize) {
  230.         let from =
  231.         match self.intervals.binary_search_by_key(&interval.start, |x| x.end) {
  232.             Ok(idx) => idx,
  233.             Err(idx) => idx,
  234.         };
  235.  
  236.         let to =
  237.         match self.intervals[from..].binary_search_by_key(&interval.end, |x| x.start) {
  238.             Ok(idx) => idx,
  239.             Err(idx) => idx,
  240.         } + from;
  241.  
  242.         (from, to)
  243.     }
  244.  
  245.     /// Returns the index pair [from; to) where the given interval overlaps
  246.     /// (intersect or touch) with the ones in the interval set.
  247.     fn overlapping_index(&self, interval: &Interval<T>) -> (usize, usize) {
  248.         // Check for intersection
  249.         let (mut from, mut to) = self.intersecting_index(interval);
  250.         // Check for touches
  251.         if from != 0 && interval.is_touching(&self.intervals[from - 1]) {
  252.             from -= 1;
  253.         }
  254.         if to != self.intervals.len() && interval.is_touching(&self.intervals[to]) {
  255.             to += 1;
  256.         }
  257.  
  258.         (from, to)
  259.     }
  260. }
  261.  
  262. /// Creates an interval-set by adding each interval with add_interval.
  263. macro_rules! ivset {
  264.     ( $( $x:expr ),* ) => {
  265.         {
  266.             let mut iv = IntervalSet::new();
  267.             $(
  268.                 iv.add_range($x);
  269.             )*
  270.             iv
  271.         }
  272.     };
  273. }
  274.  
  275. /// Creates an interval-set from the elements provided, without checking order
  276. /// or overlaps.
  277. macro_rules! ivset_raw {
  278.     ( $( $x:expr ),* ) => {
  279.         {
  280.             IntervalSet{
  281.                 intervals: vec![
  282.                     $(
  283.                         Interval::from_range($x)
  284.                     ),*
  285.                 ],
  286.             }
  287.         }
  288.     };
  289. }
  290.  
  291. fn add_interval_04() -> IntervalSet<u32> {
  292.     ivset![22..65, 78..82, 65..78]
  293. }
  294.  
  295. fn main() {
  296.     let iv = add_interval_04();
  297. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top