Skip to content

Instantly share code, notes, and snippets.

@dat2
Created March 30, 2017 14:05
Show Gist options
  • Save dat2/9702652e3d81a91f464f9772470cd2fb to your computer and use it in GitHub Desktop.
Save dat2/9702652e3d81a91f464f9772470cd2fb to your computer and use it in GitHub Desktop.
Rust implementation of sorted iterator based on 2 input iterators
use std::iter::{Iterator, Peekable};
// this struct lets you create an iterator from 2 sub iterators, and it will
// automatically return the interleaved, sorted results without much cost
struct OrderedIterator<I: Ord + Clone, P: Iterator<Item = I>> {
first: Peekable<P>,
second: Peekable<P>,
pop_from: usize,
first_empty: bool,
second_empty: bool,
max: Option<I>
}
impl<I, P> OrderedIterator<I, P>
where I: Ord + Clone,
P: Iterator<Item = I>
{
pub fn new(first: P, second: P) -> OrderedIterator<I, P> {
let mut first_peekable = first.peekable();
let mut second_peekable = second.peekable();
let first_empty = match first_peekable.peek() {
Some(_) => false,
None => true
};
let second_empty = match second_peekable.peek() {
Some(_) => false,
None => true
};
OrderedIterator {
first: first_peekable,
second: second_peekable,
first_empty: first_empty,
second_empty: second_empty,
pop_from: 0,
max: None
}
}
}
impl<I, P> Iterator for OrderedIterator<I, P>
where I: Ord + Clone,
P: Iterator<Item = I>
{
type Item = I;
fn next(&mut self) -> Option<Self::Item> {
if self.first_empty {
self.second.next()
} else if self.second_empty {
self.first.next()
} else if let Some(max_item) = self.max.clone() {
// popped <- pop_from
let pop = if self.pop_from == 0 {
self.first.next()
} else {
self.second.next()
};
if let Some(pop_item) = pop {
// if pop_item < max_item, then we just return
if pop_item < max_item {
Some(pop_item)
// otherwise, we need to switch pop from
// need to set self.max to pop_item
} else {
self.pop_from = if self.pop_from == 0 { 1 } else { 0 };
self.max = Some(pop_item);
Some(max_item)
}
} else {
// if we popped, and we got none, then we set the appropriate iterator
// to empty
if self.pop_from == 0 {
self.first_empty = true;
} else {
self.second_empty = true;
}
Some(max_item.clone())
}
} else {
// we know that first is not empty, and that second is not empty, so
// we compare the two, return the smallest, and set self.pop_from
let first_item = self.first.next().unwrap();
let second_item = self.second.next().unwrap();
let (min, max, pop_from) = if first_item < second_item {
(first_item, second_item, 0)
} else {
(second_item, first_item, 1)
};
self.max = Some(max);
self.pop_from = pop_from;
Some(min)
}
}
}
fn main() {
let first_vec = vec![ 1, 5, 7, 11, 13 ];
let second_vec = vec![ 2, 3, 4, 6, 8, 9, 10, 12 ];
for item in OrderedIterator::new(first_vec.into_iter(), second_vec.into_iter()) {
println!("{}", item);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment