SHARE
TWEET

Untitled

a guest Apr 19th, 2019 72 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 union(&self, _other: Ranges<T>) -> Ranges<T> {
  49.         Ranges(self.0.clone())
  50.     }
  51.  
  52.     #[inline]
  53.     fn contains_start_end_item(&self, start: T, end: T) -> (bool, bool) {
  54.         let mut start_found = false;
  55.         let mut end_found = false;
  56.         let mut iter = self.0.iter();
  57.         while let (Some(a), Some(b)) = (iter.next(), iter.next()) {
  58.             start_found = start_found || (start > *a && start <= *b);
  59.             end_found = end_found || (end >= *a && end < *b);
  60.             if start_found && end_found {
  61.                 break;
  62.             }
  63.         }
  64.         (start_found, end_found)
  65.     }
  66. }
  67.  
  68. impl<T> Sub for Ranges<T>
  69. where
  70.     T: Ord + Eq + Copy + Debug,
  71. {
  72.     type Output = Ranges<T>;
  73.    
  74.     fn sub(self, other: Ranges<T>) -> Self::Output {
  75.         let mut set = self.0.clone();
  76.         for [start, end] in other.iter() {
  77.             let (start_found, end_found) = self.contains_start_end_item(start, end);
  78.  
  79.             // Remove items contained in range from set.
  80.             for v in self.0.range(start..=end) {
  81.                 set.remove(v);
  82.             }
  83.  
  84.             // Add start and end item to set.
  85.             if start_found {
  86.                 set.insert(start);
  87.             }
  88.             if end_found {
  89.                 set.insert(end);
  90.             }
  91.         }
  92.         Ranges(set)
  93.     }
  94. }
  95.  
  96. impl<T> From<&[[T; 2]]> for Ranges<T>
  97. where
  98.     T: Ord + Eq + Copy + Debug,
  99. {
  100.     fn from(values: &[[T; 2]]) -> Self {
  101.         let mut res: Ranges<T> = Ranges::new();
  102.         for v in values {
  103.             res.push(*v);
  104.         }
  105.         res
  106.     }
  107. }
  108.  
  109. impl<T> From<&[T]> for Ranges<T>
  110. where
  111.     T: Ord + Eq + Copy + Debug,
  112. {
  113.     fn from(slice: &[T]) -> Self {
  114.         let mut res: Ranges<T> = Ranges::new();
  115.         if slice.len() >= 2 {
  116.             res.push([slice[0], slice[slice.len() - 1]]);
  117.         }
  118.         res
  119.     }
  120. }
  121.  
  122. pub struct RangesIter<'a, T>(btree_set::Iter<'a, T>);
  123.  
  124. impl<'a, T> RangesIter<'a, T> {
  125.     pub fn new(iter: btree_set::Iter<'a, T>) -> RangesIter<'a, T> {
  126.         RangesIter(iter)
  127.     }
  128. }
  129.  
  130. impl<'a, T> Iterator for RangesIter<'a, T>
  131. where
  132.     T: Copy,
  133. {
  134.     type Item = [T; 2];
  135.     fn next(&mut self) -> Option<Self::Item> {
  136.         if let (Some(a), Some(b)) = (self.0.next(), self.0.next()) {
  137.             Some([*a, *b])
  138.         } else {
  139.             None
  140.         }
  141.     }
  142. }
  143.  
  144. pub fn remove_inner_items<T>(slice: &mut Vec<T>, ranges: Ranges<T>)
  145. where
  146.     T: Ord + Eq + Copy + Debug,
  147. {
  148.     let ranges = ranges.union(Ranges::from(&slice[..]));
  149.     let mut iter = ranges.iter();
  150.     let mut range = iter.next();
  151.     slice.retain(|item| {
  152.         if let Some(r) = range {
  153.             if *item > r[1] {
  154.                 range = iter.next();
  155.             }
  156.         } else {
  157.             return true;
  158.         }
  159.         if let Some(r) = range {
  160.             if *item > r[0] && *item < r[1] {
  161.                 false
  162.             } else {
  163.                 true
  164.             }
  165.         } else {
  166.             true
  167.         }
  168.     });
  169. }
  170.  
  171. #[cfg(test)]
  172. mod tests {
  173.     use super::*;
  174.  
  175.     #[test]
  176.     fn add_range() {
  177.         for data in vec![
  178.             (vec![[2, 4], [6, 8]], vec![[2, 4], [6, 8]]),
  179.             (vec![[2, 4], [2, 4]], vec![[2, 4]]),
  180.             (vec![[2, 4], [1, 4]], vec![[1, 4]]),
  181.             (vec![[2, 4], [1, 5]], vec![[1, 5]]),
  182.             (vec![[2, 4], [4, 8]], vec![[2, 8]]),
  183.             (vec![[2, 4], [2, 8]], vec![[2, 8]]),
  184.             (vec![[2, 4], [5, 8], [1, 9]], vec![[1, 9]]),
  185.             (vec![[2, 4], [5, 8], [5, 9]], vec![[2, 4], [5, 9]]),
  186.             (vec![[2, 8], [3, 5]], vec![[2, 8]]),
  187.             (vec![[2, 8], [3, 8]], vec![[2, 8]]),
  188.             (vec![[2, 8], [2, 5]], vec![[2, 8]]),
  189.         ] {
  190.             let ranges = Ranges::from(&data.0[..]);
  191.             assert_eq!(data.1, ranges.iter().collect::<Vec<_>>());
  192.         }
  193.     }
  194.  
  195.     #[test]
  196.     fn subtract() {
  197.         for data in vec![
  198.             (vec![[2, 4]], vec![[2, 4]], vec![]),
  199.             (vec![[2, 4]], vec![[4, 6]], vec![[2, 4]]),
  200.             (vec![[2, 8]], vec![[4, 7]], vec![[2, 4], [7, 8]]),
  201.             (vec![[2, 4], [6, 8]], vec![[4, 6]], vec![[2, 4], [6, 8]]),
  202.             (vec![[4, 6]], vec![[3, 7]], vec![]),
  203.             (vec![[0, 9]], vec![[3, 7]], vec![[0, 3], [7, 9]]),
  204.             (vec![[0, 6]], vec![[4, 6]], vec![[0, 4]]),
  205.             (vec![[0, 4], [6, 9]], vec![[3, 7]], vec![[0, 3], [7, 9]]),
  206.         ] {
  207.             let op1: Ranges<i32> = Ranges::from(&data.0[..]);
  208.             let op2: Ranges<i32> = Ranges::from(&data.1[..]);
  209.             let expect = Ranges::from(&data.2[..]);
  210.             assert_eq!(expect, op1 - op2);
  211.         }
  212.     }
  213.  
  214.     #[test]
  215.     fn test_remove_inner_items() {
  216.         for data in vec![
  217.             (vec![[3, 6]], vec![2, 3, 6, 7, 8]),
  218.             //(vec![[3, 9]], vec![2, 3, 8]),
  219.             //(vec![[0, 9]], vec![2, 8]),
  220.             (vec![[2, 8]], vec![2, 8]),
  221.         ] {
  222.             let mut slice = (2..=8).collect::<Vec<i32>>();
  223.             remove_inner_items(&mut slice, Ranges::from(&data.0[..]));
  224.             assert_eq!(data.1, slice);
  225.         }
  226.     }
  227. }
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