API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 21st, 2019
93
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.60 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!