Last active
August 22, 2019 22:57
-
-
Save Mathspy/ac0976169aef450a48d629fc7fff25f4 to your computer and use it in GitHub Desktop.
A Tuple Combination iterator like the one in Itertools but with short-circuiting
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// This is the trait that has .tuple_combinations_while() | |
trait HasTupleCombinationWhile: Iterator { | |
/// Return an iterator adaptor that iterates over the combinations of the elements from an iterator. | |
/// With the added beneift of being able to short-circuit | |
fn tuple_combinations_while<P>( | |
mut self, | |
predicate: P, | |
) -> TupleCombinationsWhile<Self, Self::Item, P> | |
where | |
Self: Clone, | |
Self::Item: Clone, | |
P: Fn(&(Self::Item, Self::Item)) -> bool, | |
{ | |
TupleCombinationsWhile { | |
current: self.next(), | |
iterator: self.clone(), | |
copy: self, | |
predicate, | |
} | |
} | |
} | |
// We blanket implement it for all Iterators | |
impl<T: ?Sized> HasTupleCombinationWhile for T where T: Iterator {} | |
// The Iterator itself | |
struct TupleCombinationsWhile<I, T, P> | |
where | |
T: Clone, | |
I: Iterator<Item = T> + Clone, | |
P: Fn(&(T, T)) -> bool, | |
{ | |
current: Option<T>, | |
iterator: I, | |
copy: I, | |
predicate: P, | |
} | |
// The Iterator's implementation of Iterator | |
impl<I, T, P> Iterator for TupleCombinationsWhile<I, T, P> | |
where | |
T: Clone, | |
I: Iterator<Item = T> + Clone, | |
P: Fn(&(T, T)) -> bool, | |
{ | |
type Item = (T, T); | |
fn next(&mut self) -> Option<Self::Item> { | |
loop { | |
// dbg!("iteration"); | |
if self.current.is_none() { | |
return None; | |
} | |
if let Some(val) = self.iterator.next() { | |
let potential_next = (self.current.clone()?, val); | |
if (self.predicate)(&potential_next) { | |
return Some(potential_next); | |
} | |
} | |
self.current = self.copy.next(); | |
self.iterator = self.copy.clone(); | |
} | |
} | |
} | |
fn main() { | |
// Executing the code below will result in "iteration" (if uncommented) being printed | |
// To the terminal 26 times (so we will need to do 26 iterations total) instead of... | |
(1..10) | |
.tuple_combinations_while(|(a, b)| a + b < 10) | |
.all(|_| true); | |
// the 46 "iterations" this will result in: | |
(1..10) | |
// This is equivalent to Itertools' tuple_combinations | |
.tuple_combinations_while(|_| true) | |
.filter(|(a, b)| a + b < 10) | |
.all(|_| true); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment