split_iter/
lib.rs

1//! Provides the trait `Splittable`, which allows you to split an iterator
2//! according to a `predicate`.
3//!
4//! # Example
5//!
6//! ```
7//! use split_iter::Splittable;
8//!
9//! fn main() {
10//! 	let (odd, even) = (1..10).split(|v| v % 2 == 0);
11//!
12//! 	assert_eq!(odd.collect::<Vec<_>>(), [1,3,5,7,9]);
13//! 	assert_eq!(even.collect::<Vec<_>>(), [2,4,6,8]);
14//! }
15//! ```
16
17
18use std::rc::Rc;
19use std::collections::VecDeque;
20use std::cell::RefCell;
21use std::fmt::Debug;
22use std::fmt::Formatter;
23use std::fmt::Error as FmtError;
24
25
26/// Shared inner state for two `Split`s.
27struct SharedSplitState<I, P> where
28	I: Iterator,
29	P: FnMut(&I::Item) -> bool
30{
31	/// Inner iterator.
32	iter: I,
33	/// Predicate that chooses whether an item
34	/// goes left (`false`) or right (`true`).
35	predicate: P,
36	/// Cache that saves items that have been skipped by one `Split`.
37	/// They will be returned next for the other `Split`.
38	cache: VecDeque<I::Item>,
39	/// Is the cache currently saving items for the left or for the right split?
40	is_right_cached: bool,
41}
42
43impl<I, P> SharedSplitState<I, P> where
44	I: Iterator,
45	P: FnMut(&I::Item) -> bool
46{
47	/// Creates shared inner state for two `Split`s.
48	fn new(iter: I, predicate: P) -> SharedSplitState<I, P> {
49		SharedSplitState {
50			iter: iter,
51			predicate: predicate,
52			cache: VecDeque::new(),
53			is_right_cached: false,
54		}
55	}
56	
57	/// Returns next item for the given `Split`.
58	fn next(&mut self, is_right: bool) -> Option<I::Item> {
59		// Use cache for correct side
60		if is_right == self.is_right_cached {
61			if let Some(next) = self.cache.pop_front() {
62				return Some(next);
63			}
64		}
65		
66		// From inner iterator
67		while let Some(next) = self.iter.next() {
68			if (self.predicate)(&next) == is_right {
69				return Some(next);
70			} else {
71				// Fill cache with elements for opposite iterator
72				self.is_right_cached = !is_right;
73				self.cache.push_back(next);
74			}
75		}
76		
77		// No element found
78		None
79	}
80}
81
82
83/// One of a pair of iterators. One returns the items for which the predicate
84/// returns `false`, the other one returns the items for which the predicate
85/// returns `true`.
86#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
87pub struct Split<I, P> where
88	I: Iterator,
89	P: FnMut(&I::Item) -> bool
90{
91	/// Shared state with the opposite iterator.
92	shared: Rc<RefCell<SharedSplitState<I, P>>>,
93	/// Is the iterator the right one or the left one?
94	is_right: bool,
95}
96
97impl<I, P> Iterator for Split<I, P> where
98	I: Iterator,
99	P: FnMut(&I::Item) -> bool
100{
101	type Item = I::Item;
102	
103	fn next(&mut self) -> Option<I::Item> {
104		self.shared.borrow_mut().next(self.is_right)
105	}
106}
107
108impl<I, P> Debug for Split<I, P> where
109	I: Iterator + Debug,
110	P: FnMut(&I::Item) -> bool
111{
112	fn fmt(&self, fmt: &mut Formatter) -> Result<(), FmtError> {
113		fmt.debug_struct("Split")
114			.field("iter", &self.shared.borrow().iter)
115			.finish()
116	}
117}
118
119
120/// Provides an iterator adaptor method that splits an iterator into two
121/// iterators according to a predicate.
122pub trait Splittable<I> where
123	I: Iterator
124{
125	/// Splits the iterator. The left iterator iterates over all items for which
126	/// the `predicate` returns `false`. The right iterator returns all items
127	/// for which the `predicate` returns `true`.
128	fn split<P>(self, predicate: P) -> (Split<I, P>, Split<I, P>)
129		where P: FnMut(&I::Item) -> bool;
130}
131
132impl<I> Splittable<I> for I where
133	I: Iterator
134{
135	fn split<P>(self, predicate: P) -> (Split<I, P>, Split<I, P>)
136		where P: FnMut(&I::Item) -> bool
137	{
138		let shared = Rc::new(
139			RefCell::new(
140				SharedSplitState::new(self, predicate)
141			)
142		);
143		
144		let left = Split {
145			shared: shared.clone(),
146			is_right: false,
147		};
148		
149		let right = Split {
150			shared: shared,
151			is_right: true,
152		};
153		
154		(left, right)
155	}
156}
157
158
159#[cfg(test)]
160mod tests {
161	use super::Splittable;
162	
163    #[test]
164    fn it_works() {
165		let (odd, even) = (1..10).split(|v| v % 2 == 0);
166		assert_eq!(odd.collect::<Vec<_>>(), [1,3,5,7,9]);
167		assert_eq!(even.collect::<Vec<_>>(), [2,4,6,8]);
168		
169		let (low, high) = (1..20).split(|v| v >= &10);
170		assert_eq!(high.collect::<Vec<_>>(), (10..20).collect::<Vec<_>>());
171		assert_eq!(low.collect::<Vec<_>>(), (1..10).collect::<Vec<_>>());
172    }
173}
split_iter/lib.rs

split_iter/
lib.rs
