SHARE
TWEET

Untitled

a guest Apr 19th, 2019 113 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. use std::{
  2.     collections::{btree_set, BTreeSet},
  3.     fmt::Debug,
  4.     ops::Sub,
  5. };
  6.  
  7. #[derive(PartialEq, Clone, Debug)]
  8. pub struct Ranges<T>(BTreeSet<T>)
  9. where
  10.     T: Ord + Eq + Copy + Debug;
  11.  
  12. impl<T> Ranges<T>
  13. where
  14.     T: Ord + Eq + Copy + Debug,
  15. {
  16.     pub fn new() -> Ranges<T> {
  17.         Ranges(BTreeSet::new())
  18.     }
  19.  
  20.     /// Adds and merges the given range with set.
  21.     pub fn push(&mut self, range: [T; 2]) {
  22.         // Search if start or end item are contained in set ranges.
  23.         let [start, end] = range;
  24.         if start >= end {
  25.             panic!("start item must be smaller than end item");
  26.         }
  27.         let (start_found, end_found) = self.contains_start_end_item(start, end);
  28.  
  29.         // Remove items contained in range from set.
  30.         let values: Vec<_> = self.0.range(start..=end).map(|v| *v).collect();
  31.         for v in &values {
  32.             self.0.remove(v);
  33.         }
  34.  
  35.         // Add start and end item to set.
  36.         if !start_found {
  37.             self.0.insert(start);
  38.         }
  39.         if !end_found {
  40.             self.0.insert(end);
  41.         }
  42.     }
  43.  
  44.     pub fn iter(&self) -> RangesIter<T> {
  45.         RangesIter::new(self.0.iter())
  46.     }
  47.  
  48.     pub fn intersection_2(&self, other: Ranges<T>) -> Ranges<T> {
  49.         let mut set = BTreeSet::new();
  50.         for [start, end] in other.iter() {
  51.             let (start_found, end_found) = self.contains_start_end_item(start, end);
  52.             if start_found {
  53.                 set.insert(start);
  54.             }
  55.             if end_found {
  56.                 set.insert(end);
  57.             }
  58.         }
  59.         for [start, end] in self.iter() {
  60.             let (start_found, end_found) = other.contains_start_end_item(start, end);
  61.             if start_found {
  62.                 set.insert(start);
  63.             }
  64.             if end_found {
  65.                 set.insert(end);
  66.             }
  67.         }
  68.         Ranges(set)
  69.     }
  70.  
  71.     pub fn intersection(&self, other: Ranges<T>) -> Ranges<T> {
  72.         let mut set = BTreeSet::new();
  73.         let mut iter = self.0.iter();
  74.         while let (Some(a), Some(b)) = (iter.next(), iter.next()) {
  75.             if other.0.contains(a) && other.0.contains(b) {
  76.                 set.insert(*a);
  77.                 set.insert(*b);
  78.             }
  79.             for v in other.0.range(a..=b) {
  80.                 if v > a && v < b {
  81.                     set.insert(*v);
  82.                 }
  83.             }
  84.         }
  85.         let mut iter = other.0.iter();
  86.         while let (Some(a), Some(b)) = (iter.next(), iter.next()) {
  87.             for v in self.0.range(a..=b) {
  88.                 if v > a && v < b {
  89.                     set.insert(*v);
  90.                 }
  91.             }
  92.         }
  93.         Ranges(set)
  94.     }
  95.  
  96.     #[inline]
  97.     fn contains_start_end_item(&self, start: T, end: T) -> (bool, bool) {
  98.         let mut start_found = false;
  99.         let mut end_found = false;
  100.         let mut iter = self.0.iter();
  101.         while let (Some(a), Some(b)) = (iter.next(), iter.next()) {
  102.             start_found = start_found || (start > *a && start <= *b);
  103.             end_found = end_found || (end >= *a && end < *b);
  104.             if start_found && end_found {
  105.                 break;
  106.             }
  107.         }
  108.         (start_found, end_found)
  109.     }
  110. }
  111.  
  112. impl<T> Sub for Ranges<T>
  113. where
  114.     T: Ord + Eq + Copy + Debug,
  115. {
  116.     type Output = Ranges<T>;
  117.  
  118.     fn sub(self, other: Ranges<T>) -> Self::Output {
  119.         let mut set = self.0.clone();
  120.         for [start, end] in other.iter() {
  121.             let (start_found, end_found) = self.contains_start_end_item(start, end);
  122.  
  123.             // Remove items contained in range from set.
  124.             for v in self.0.range(start..=end) {
  125.                 set.remove(v);
  126.             }
  127.  
  128.             // Add start and end item to set.
  129.             if start_found {
  130.                 set.insert(start);
  131.             }
  132.             if end_found {
  133.                 set.insert(end);
  134.             }
  135.         }
  136.         Ranges(set)
  137.     }
  138. }
  139.  
  140. impl<T> From<&[[T; 2]]> for Ranges<T>
  141. where
  142.     T: Ord + Eq + Copy + Debug,
  143. {
  144.     fn from(values: &[[T; 2]]) -> Self {
  145.         let mut res: Ranges<T> = Ranges::new();
  146.         for v in values {
  147.             res.push(*v);
  148.         }
  149.         res
  150.     }
  151. }
  152.  
  153. impl<T> From<&[T]> for Ranges<T>
  154. where
  155.     T: Ord + Eq + Copy + Debug,
  156. {
  157.     fn from(slice: &[T]) -> Self {
  158.         let mut res: Ranges<T> = Ranges::new();
  159.         if slice.len() >= 2 {
  160.             res.push([slice[0], slice[slice.len() - 1]]);
  161.         }
  162.         res
  163.     }
  164. }
  165.  
  166. pub struct RangesIter<'a, T>(btree_set::Iter<'a, T>);
  167.  
  168. impl<'a, T> RangesIter<'a, T> {
  169.     pub fn new(iter: btree_set::Iter<'a, T>) -> RangesIter<'a, T> {
  170.         RangesIter(iter)
  171.     }
  172. }
  173.  
  174. impl<'a, T> Iterator for RangesIter<'a, T>
  175. where
  176.     T: Copy,
  177. {
  178.     type Item = [T; 2];
  179.     fn next(&mut self) -> Option<Self::Item> {
  180.         if let (Some(a), Some(b)) = (self.0.next(), self.0.next()) {
  181.             Some([*a, *b])
  182.         } else {
  183.             None
  184.         }
  185.     }
  186. }
  187.  
  188. pub fn remove_inner_items<T>(slice: &mut Vec<T>, ranges: Ranges<T>)
  189. where
  190.     T: Ord + Eq + Copy + Debug,
  191. {
  192.     let ranges = ranges.intersection(Ranges::from(&slice[..]));
  193.     let mut iter = ranges.iter();
  194.     let mut range = iter.next();
  195.     slice.retain(|item| {
  196.         if let Some(r) = range {
  197.             if *item > r[1] {
  198.                 range = iter.next();
  199.             }
  200.         } else {
  201.             return true;
  202.         }
  203.         if let Some(r) = range {
  204.             if *item > r[0] && *item < r[1] {
  205.                 false
  206.             } else {
  207.                 true
  208.             }
  209.         } else {
  210.             true
  211.         }
  212.     });
  213. }
  214.  
  215. #[cfg(test)]
  216. mod tests {
  217.     use super::*;
  218.  
  219.     #[test]
  220.     fn add_range() {
  221.         for data in vec![
  222.             (vec![[2, 4], [6, 8]], vec![[2, 4], [6, 8]]),
  223.             (vec![[2, 4], [2, 4]], vec![[2, 4]]),
  224.             (vec![[2, 4], [1, 4]], vec![[1, 4]]),
  225.             (vec![[2, 4], [1, 5]], vec![[1, 5]]),
  226.             (vec![[2, 4], [4, 8]], vec![[2, 8]]),
  227.             (vec![[2, 4], [2, 8]], vec![[2, 8]]),
  228.             (vec![[2, 4], [5, 8], [1, 9]], vec![[1, 9]]),
  229.             (vec![[2, 4], [5, 8], [5, 9]], vec![[2, 4], [5, 9]]),
  230.             (vec![[2, 8], [3, 5]], vec![[2, 8]]),
  231.             (vec![[2, 8], [3, 8]], vec![[2, 8]]),
  232.             (vec![[2, 8], [2, 5]], vec![[2, 8]]),
  233.         ] {
  234.             let ranges = Ranges::from(&data.0[..]);
  235.             assert_eq!(data.1, ranges.iter().collect::<Vec<_>>());
  236.         }
  237.     }
  238.  
  239.     #[test]
  240.     fn subtract() {
  241.         for data in vec![
  242.             (vec![[2, 4]], vec![[2, 4]], vec![]),
  243.             (vec![[2, 4]], vec![[4, 6]], vec![[2, 4]]),
  244.             (vec![[2, 8]], vec![[4, 7]], vec![[2, 4], [7, 8]]),
  245.             (vec![[2, 4], [6, 8]], vec![[4, 6]], vec![[2, 4], [6, 8]]),
  246.             (vec![[4, 6]], vec![[3, 7]], vec![]),
  247.             (vec![[0, 9]], vec![[3, 7]], vec![[0, 3], [7, 9]]),
  248.             (vec![[0, 6]], vec![[4, 6]], vec![[0, 4]]),
  249.             (vec![[0, 4], [6, 9]], vec![[3, 7]], vec![[0, 3], [7, 9]]),
  250.             (vec![[0, 6]], vec![[0, 2], [4, 6]], vec![[2, 4]]),
  251.             (vec![[0, 6]], vec![], vec![[0, 6]]),
  252.             (vec![], vec![[0, 6]], vec![[0, 6]]),
  253.             (
  254.                 vec![[0, 9]],
  255.                 vec![[1, 2], [4, 6]],
  256.                 vec![[0, 1], [2, 4], [6, 9]],
  257.             ),
  258.         ] {
  259.             let op1: Ranges<i32> = Ranges::from(&data.0[..]);
  260.             let op2: Ranges<i32> = Ranges::from(&data.1[..]);
  261.             let expect = Ranges::from(&data.2[..]);
  262.             assert_eq!(expect, op1 - op2);
  263.         }
  264.     }
  265.  
  266.     #[test]
  267.     fn intersection() {
  268.         for data in vec![
  269.             (vec![[2, 4]], vec![[2, 4]], vec![[2, 4]]),
  270.             (vec![[2, 6]], vec![[4, 9]], vec![[4, 6]]),
  271.             (vec![[4, 6]], vec![[0, 4]], vec![]),
  272.             (vec![[2, 6]], vec![[6, 9]], vec![]),
  273.             (vec![[2, 8]], vec![[4, 7]], vec![[4, 7]]),
  274.             (vec![[2, 4], [6, 8]], vec![[4, 6]], vec![]),
  275.             (vec![[4, 6]], vec![[3, 7]], vec![[4, 6]]),
  276.             (vec![[0, 9]], vec![[3, 7]], vec![[3, 7]]),
  277.             (vec![[0, 6]], vec![[4, 6]], vec![[4, 6]]),
  278.             (vec![[0, 4], [6, 9]], vec![[3, 7]], vec![[3, 4], [6, 7]]),
  279.         ] {
  280.             let op1: Ranges<i32> = Ranges::from(&data.0[..]);
  281.             let op2: Ranges<i32> = Ranges::from(&data.1[..]);
  282.             let expect = Ranges::from(&data.2[..]);
  283.             assert_eq!(expect, op1.intersection(op2));
  284.         }
  285.     }
  286.     /*
  287.         #[test]
  288.         fn test_remove_inner_items() {
  289.             for data in vec![
  290.                 (vec![[3, 6]], vec![2, 3, 6, 7, 8]),
  291.                 //(vec![[3, 9]], vec![2, 3, 8]),
  292.                 //(vec![[0, 9]], vec![2, 8]),
  293.                 //(vec![[2, 8]], vec![2, 8]),
  294.             ] {
  295.                 let mut slice = (2..=8).collect::<Vec<i32>>();
  296.                 remove_inner_items(&mut slice, Ranges::from(&data.0[..]));
  297.                 assert_eq!(data.1, slice);
  298.             }
  299.         }
  300.     */
  301. }
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