SHARE
TWEET

Untitled

a guest Apr 21st, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. use std::{
  2.     fmt::Debug,
  3.     //ops::Sub,
  4.     slice,
  5. };
  6.  
  7. #[derive(PartialEq, Clone, Debug)]
  8. pub struct Ranges<T>(Vec<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(vec![])
  18.     }
  19.  
  20.     /// Adds and merges the given range with set.
  21.     pub fn push(&mut self, range: (T, T)) {
  22.         if self.0.is_empty() || range.0 > self.0[self.0.len() - 1] {
  23.             self.0.push(range.0);
  24.             self.0.push(range.1);
  25.             return;
  26.         }
  27.  
  28.         if range.1 > self.0[self.0.len() - 1] {
  29.             let i = match self.0.binary_search(&range.0) {
  30.                 Ok(i) => {
  31.                     if is_start(i) {
  32.                         i + 1
  33.                     } else {
  34.                         i
  35.                     }
  36.                 }
  37.                 Err(i) => {
  38.                     if is_start(i) {
  39.                         self.0[i] = range.0;
  40.                         i + 1
  41.                     } else {
  42.                         i
  43.                     }
  44.                 }
  45.             };
  46.             self.0.drain(i..);
  47.             self.0.push(range.1);
  48.             return;
  49.         }
  50.  
  51.         match (
  52.             self.0.binary_search(&range.0),
  53.             self.0.binary_search(&range.1),
  54.         ) {
  55.             (Err(i), Err(j)) if i == j => {
  56.                 if is_start(i) {
  57.                     self.0.insert(i, range.1);
  58.                     self.0.insert(i, range.0);
  59.                 }
  60.             }
  61.  
  62.             (Err(i), Ok(j)) if i == j => {
  63.                 if is_start(i) {
  64.                     self.0[i] = range.0;
  65.                 }
  66.             }
  67.  
  68.             (Err(mut i), Err(j)) => {
  69.                 if is_start(i) {
  70.                     self.0[i] = range.0;
  71.                     i += 1;
  72.                 }
  73.                 if is_start(j) {
  74.                     self.0.insert(j, range.1);
  75.                 }
  76.                 self.0.drain(i..=j - 1);
  77.             }
  78.  
  79.             (Err(mut i), Ok(mut j)) => {
  80.                 if is_start(i) {
  81.                     self.0[i] = range.0;
  82.                     i += 1;
  83.                 }
  84.                 if is_end(j) {
  85.                     j -= 1;
  86.                 }
  87.                 self.0.drain(i..=j);
  88.             }
  89.  
  90.             (Ok(mut i), Err(j)) => {
  91.                 if is_start(i) {
  92.                     i += 1;
  93.                 }
  94.                 if is_start(j) {
  95.                     self.0.insert(j, range.1);
  96.                 }
  97.                 self.0.drain(i..=j - 1);
  98.             }
  99.  
  100.             (Ok(mut i), Ok(mut j)) => {
  101.                 if is_start(i) {
  102.                     i += 1;
  103.                 }
  104.                 if is_end(j) {
  105.                     j -= 1;
  106.                 }
  107.                 self.0.drain(i..=j);
  108.             }
  109.         }
  110.     }
  111.  
  112.     pub fn iter(&self) -> RangesIter<T> {
  113.         RangesIter::new(self.0.iter())
  114.     }
  115.  
  116.     /*
  117.     pub fn intersection_2(&self, other: Ranges<T>) -> Ranges<T> {
  118.         let mut set = BTreeSet::new();
  119.         for [start, end] in other.iter() {
  120.             let (start_found, end_found) = self.contains_start_end_item(start, end);
  121.             if start_found {
  122.                 set.insert(start);
  123.             }
  124.             if end_found {
  125.                 set.insert(end);
  126.             }
  127.         }
  128.         for [start, end] in self.iter() {
  129.             let (start_found, end_found) = other.contains_start_end_item(start, end);
  130.             if start_found {
  131.                 set.insert(start);
  132.             }
  133.             if end_found {
  134.                 set.insert(end);
  135.             }
  136.         }
  137.         Ranges(set)
  138.     }
  139.  
  140.     pub fn intersection(&self, other: Ranges<T>) -> Ranges<T> {
  141.         let mut set = BTreeSet::new();
  142.         let mut iter = self.0.iter();
  143.         while let (Some(a), Some(b)) = (iter.next(), iter.next()) {
  144.             if other.0.contains(a) && other.0.contains(b) {
  145.                 set.insert(*a);
  146.                 set.insert(*b);
  147.             }
  148.             for v in other.0.range(a..=b) {
  149.                 if v > a && v < b {
  150.                     set.insert(*v);
  151.                 }
  152.             }
  153.         }
  154.         let mut iter = other.0.iter();
  155.         while let (Some(a), Some(b)) = (iter.next(), iter.next()) {
  156.             for v in self.0.range(a..=b) {
  157.                 if v > a && v < b {
  158.                     set.insert(*v);
  159.                 }
  160.             }
  161.         }
  162.         Ranges(set)
  163.     }
  164.  
  165.     #[inline]
  166.     fn contains_start_end_item(&self, start: T, end: T) -> (bool, bool) {
  167.         let mut start_found = false;
  168.         let mut end_found = false;
  169.         let mut iter = self.0.iter();
  170.         while let (Some(a), Some(b)) = (iter.next(), iter.next()) {
  171.             start_found = start_found || (start > *a && start <= *b);
  172.             end_found = end_found || (end >= *a && end < *b);
  173.             if start_found && end_found {
  174.                 break;
  175.             }
  176.         }
  177.         (start_found, end_found)
  178.     }
  179.     */
  180. }
  181.  
  182. fn is_start(i: usize) -> bool {
  183.     i % 2 == 0
  184. }
  185.  
  186. fn is_end(i: usize) -> bool {
  187.     i % 2 != 0
  188. }
  189.  
  190. /*
  191. impl<T> Sub for Ranges<T>
  192. where
  193.     T: Ord + Eq + Copy + Debug,
  194. {
  195.     type Output = Ranges<T>;
  196.  
  197.     fn sub(self, other: Ranges<T>) -> Self::Output {
  198.         let mut set = self.0.clone();
  199.         for [start, end] in other.iter() {
  200.             let (start_found, end_found) = self.contains_start_end_item(start, end);
  201.  
  202.             // Remove items contained in range from set.
  203.             for v in self.0.range(start..=end) {
  204.                 set.remove(v);
  205.             }
  206.  
  207.             // Add start and end item to set.
  208.             if start_found {
  209.                 set.insert(start);
  210.             }
  211.             if end_found {
  212.                 set.insert(end);
  213.             }
  214.         }
  215.         Ranges(set)
  216.     }
  217. }
  218. */
  219.  
  220. impl<T> From<&[(T, T)]> for Ranges<T>
  221. where
  222.     T: Ord + Eq + Copy + Debug,
  223. {
  224.     fn from(values: &[(T, T)]) -> Self {
  225.         let mut res: Ranges<T> = Ranges::new();
  226.         for v in values {
  227.             res.push(*v);
  228.         }
  229.         res
  230.     }
  231. }
  232.  
  233. impl<T> From<&[T]> for Ranges<T>
  234. where
  235.     T: Ord + Eq + Copy + Debug,
  236. {
  237.     fn from(slice: &[T]) -> Self {
  238.         let mut res: Ranges<T> = Ranges::new();
  239.         if slice.len() >= 2 {
  240.             res.push((slice[0], slice[slice.len() - 1]));
  241.         }
  242.         res
  243.     }
  244. }
  245.  
  246. pub struct RangesIter<'a, T>(slice::Iter<'a, T>)
  247. where
  248.     T: Ord + Eq + Copy + Debug;
  249.  
  250. impl<'a, T> RangesIter<'a, T>
  251. where
  252.     T: Ord + Eq + Copy + Debug,
  253. {
  254.     pub fn new(iter: slice::Iter<T>) -> RangesIter<T> {
  255.         RangesIter(iter)
  256.     }
  257. }
  258.  
  259. impl<'a, T> Iterator for RangesIter<'a, T>
  260. where
  261.     T: Ord + Eq + Copy + Debug,
  262. {
  263.     type Item = (T, T);
  264.     fn next(&mut self) -> Option<Self::Item> {
  265.         if let (Some(a), Some(b)) = (self.0.next(), self.0.next()) {
  266.             Some((*a, *b))
  267.         } else {
  268.             None
  269.         }
  270.     }
  271. }
  272.  
  273. pub fn remove_inner_items<T>(slice: &mut Vec<T>, ranges: Ranges<T>)
  274. where
  275.     T: Ord + Eq + Copy + Debug,
  276. {
  277.     //let ranges = ranges.intersection(Ranges::from(&slice[..]));
  278.     let mut iter = ranges.iter();
  279.     let mut range = iter.next();
  280.     slice.retain(|item| {
  281.         if let Some(r) = range {
  282.             if *item > r.1 {
  283.                 range = iter.next();
  284.             }
  285.         } else {
  286.             return true;
  287.         }
  288.         if let Some(r) = range {
  289.             if *item > r.0 && *item < r.1 {
  290.                 false
  291.             } else {
  292.                 true
  293.             }
  294.         } else {
  295.             true
  296.         }
  297.     });
  298. }
  299.  
  300. #[cfg(test)]
  301. mod tests {
  302.     use super::*;
  303.  
  304.     #[test]
  305.     fn add_range() {
  306.         for data in vec![
  307.             (vec![(2, 4), (6, 8)], vec![(2, 4), (6, 8)]),
  308.             (vec![(2, 4), (3, 6)], vec![(2, 6)]),
  309.             (vec![(2, 4), (4, 6)], vec![(2, 6)]),
  310.             (vec![(2, 4), (2, 6)], vec![(2, 6)]),
  311.             (vec![(2, 4), (1, 6)], vec![(1, 6)]),
  312.             (vec![(2, 4), (3, 4)], vec![(2, 4)]),
  313.             (vec![(1, 3), (6, 8), (4, 5)], vec![(1, 3), (4, 5), (6, 8)]),
  314.             (vec![(1, 3), (6, 8), (4, 6)], vec![(1, 3), (4, 8)]),
  315.             (vec![(1, 5), (2, 5)], vec![(1, 5)]),
  316.             (vec![(1, 5), (3, 5)], vec![(1, 5)]),
  317.             (vec![(1, 3), (6, 8), (2, 5)], vec![(1, 5), (6, 8)]),
  318.             (vec![(1, 3), (6, 8), (2, 7)], vec![(1, 8)]),
  319.             (vec![(1, 3), (6, 8), (2, 8)], vec![(1, 8)]),
  320.             (vec![(1, 3), (6, 8), (2, 6)], vec![(1, 8)]),
  321.             (vec![(1, 3), (6, 8), (4, 6)], vec![(1, 3), (4, 8)]),
  322.             (vec![(1, 3), (6, 8), (3, 6)], vec![(1, 8)]),
  323.             (vec![(1, 3), (6, 8), (3, 5)], vec![(1, 5), (6, 8)]),
  324.             (vec![(1, 3), (6, 8), (3, 7)], vec![(1, 8)]),
  325.             (vec![(1, 3), (6, 8), (2, 6)], vec![(1, 8)]),
  326.             (vec![(1, 3), (6, 8), (0, 6)], vec![(0, 8)]),
  327.             (vec![(2, 4), (2, 4)], vec![(2, 4)]),
  328.             (vec![(2, 4), (1, 4)], vec![(1, 4)]),
  329.             (vec![(2, 4), (1, 5)], vec![(1, 5)]),
  330.             (vec![(2, 4), (4, 8)], vec![(2, 8)]),
  331.             (vec![(2, 4), (2, 8)], vec![(2, 8)]),
  332.             (vec![(2, 4), (5, 8), (1, 9)], vec![(1, 9)]),
  333.             (vec![(2, 4), (5, 8), (5, 9)], vec![(2, 4), (5, 9)]),
  334.             (vec![(2, 8), (3, 5)], vec![(2, 8)]),
  335.             (vec![(2, 8), (3, 8)], vec![(2, 8)]),
  336.             (vec![(2, 8), (2, 5)], vec![(2, 8)]),
  337.         ] {
  338.             let ranges = Ranges::from(&data.0[..]);
  339.             assert_eq!(data.1, ranges.iter().collect::<Vec<_>>());
  340.         }
  341.     }
  342.     /*
  343.     #[test]
  344.     fn subtract() {
  345.         for data in vec![
  346.             (vec![[2, 4]], vec![[2, 4]], vec![]),
  347.             (vec![[2, 4]], vec![[4, 6]], vec![[2, 4]]),
  348.             (vec![[2, 8]], vec![[4, 7]], vec![[2, 4], [7, 8]]),
  349.             (vec![[2, 4], [6, 8]], vec![[4, 6]], vec![[2, 4], [6, 8]]),
  350.             (vec![[4, 6]], vec![[3, 7]], vec![]),
  351.             (vec![[0, 9]], vec![[3, 7]], vec![[0, 3], [7, 9]]),
  352.             (vec![[0, 6]], vec![[4, 6]], vec![[0, 4]]),
  353.             (vec![[0, 4], [6, 9]], vec![[3, 7]], vec![[0, 3], [7, 9]]),
  354.             (vec![[0, 6]], vec![[0, 2], [4, 6]], vec![[2, 4]]),
  355.             (vec![[0, 6]], vec![], vec![[0, 6]]),
  356.             (vec![], vec![[0, 6]], vec![[0, 6]]),
  357.             (
  358.                 vec![[0, 9]],
  359.                 vec![[1, 2], [4, 6]],
  360.                 vec![[0, 1], [2, 4], [6, 9]],
  361.             ),
  362.         ] {
  363.             let op1: Ranges<i32> = Ranges::from(&data.0[..]);
  364.             let op2: Ranges<i32> = Ranges::from(&data.1[..]);
  365.             let expect = Ranges::from(&data.2[..]);
  366.             assert_eq!(expect, op1 - op2);
  367.         }
  368.     }
  369.  
  370.     #[test]
  371.     fn intersection() {
  372.         for data in vec![
  373.             (vec![[2, 4]], vec![[2, 4]], vec![[2, 4]]),
  374.             (vec![[2, 6]], vec![[4, 9]], vec![[4, 6]]),
  375.             (vec![[4, 6]], vec![[0, 4]], vec![]),
  376.             (vec![[2, 6]], vec![[6, 9]], vec![]),
  377.             (vec![[2, 8]], vec![[4, 7]], vec![[4, 7]]),
  378.             (vec![[2, 4], [6, 8]], vec![[4, 6]], vec![]),
  379.             (vec![[4, 6]], vec![[3, 7]], vec![[4, 6]]),
  380.             (vec![[0, 9]], vec![[3, 7]], vec![[3, 7]]),
  381.             (vec![[0, 6]], vec![[4, 6]], vec![[4, 6]]),
  382.             (vec![[0, 4], [6, 9]], vec![[3, 7]], vec![[3, 4], [6, 7]]),
  383.         ] {
  384.             let op1: Ranges<i32> = Ranges::from(&data.0[..]);
  385.             let op2: Ranges<i32> = Ranges::from(&data.1[..]);
  386.             let expect = Ranges::from(&data.2[..]);
  387.             assert_eq!(expect, op1.intersection(op2));
  388.         }
  389.     }
  390.  
  391.         #[test]
  392.         fn test_remove_inner_items() {
  393.             for data in vec![
  394.                 (vec![[3, 6]], vec![2, 3, 6, 7, 8]),
  395.                 //(vec![[3, 9]], vec![2, 3, 8]),
  396.                 //(vec![[0, 9]], vec![2, 8]),
  397.                 //(vec![[2, 8]], vec![2, 8]),
  398.             ] {
  399.                 let mut slice = (2..=8).collect::<Vec<i32>>();
  400.                 remove_inner_items(&mut slice, Ranges::from(&data.0[..]));
  401.                 assert_eq!(data.1, slice);
  402.             }
  403.         }
  404.     */
  405. }
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