• API
• FAQ
• Tools
• Archive
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};
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> {
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.
263. macro_rules! ivset {
264.     ( \$( \$x:expr ),* ) => {
265.         {
266.             let mut iv = IntervalSet::new();
267.             \$(
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() {