"Shepmaster" published a very elegant implementation of an merging iterator MergeAscending.
It takes to iterators as input and outputs something like
MergeAscending<std::slice::Iter<'_, &_>, std::slice::Iter<'_, _>> : std::iter::Iterator
Here the souce code:
use std::iter::Peekable;
use std::cmp::Ordering;
struct MergeAscending<L, R>
where L: Iterator<Item = R::Item>,
R: Iterator,
{
left: Peekable<L>,
right: Peekable<R>,
}
impl<L, R> MergeAscending<L, R>
where L: Iterator<Item = R::Item>,
R: Iterator,
{
fn new(left: L, right: R) -> Self {
MergeAscending {
left: left.peekable(),
right: right.peekable(),
}
}
}
impl<L, R> Iterator for MergeAscending<L, R>
where L: Iterator<Item = R::Item>,
R: Iterator,
L::Item: Ord,
{
type Item = L::Item;
fn next(&mut self) -> Option<L::Item> {
let which = match (self.left.peek(), self.right.peek()) {
(Some(l), Some(r)) => Some(l.cmp(r)),
(Some(_), None) => Some(Ordering::Less),
(None, Some(_)) => Some(Ordering::Greater),
(None, None) => None,
};
match which {
Some(Ordering::Less) => self.left.next(),
Some(Ordering::Equal) => self.left.next(),
Some(Ordering::Greater) => self.right.next(),
None => None,
}
}
}
fn main() {
let left = [1, 3, 5, 7, 9];
let right = [3, 4, 5, 6, 7];
let result: Vec<_> = MergeAscending::new(left.iter(), right.iter()).collect();
println!("{:?}", result);
I would like to use this code to merge more then one vector. The following works:
fn main() {
let vv: Vec<Vec<_>> = vec![vec![1, 3, 5, 7, 9], vec![3, 4, 5, 6, 7],vec![0, 2, 6, 8]];
let a = MergeAscending::new(vv[0].iter(),vv[1].iter());
let b = MergeAscending::new(a, vv[2].iter());
let result: Vec<_> = b.collect();
println!("{:?}", result);
}
Unfortunately a is of type :
MergeAscending<std::slice::Iter<'_, _>, std::slice::Iter<'_, _>>
which is different from the type of b which is
MergeAscending<MergeAscending<std::slice::Iter<'_, _>, std::slice::Iter<'_, _>>, std::slice::Iter<'_, _>>.
I suppose this is why the following does not work:
fn main() {
let vv: Vec<Vec<_>> = vec![vec![1, 3, 5, 7, 9], vec![3, 4, 5, 6, 7],vec![0, 2, 6, 8]];
let ma = MergeAscending::new(vv[0].iter(),vv[1].iter());
for v in vv.iter().skip(2) {
ma = MergeAscending::new(ma, v.iter()); //error: mismatched types
};
let result: Vec<_> = ma.collect();
}
Another not working approach:
fn main() {
let vv: Vec<Vec<_>> = vec![vec![1, 3, 5, 7, 9], vec![3, 4, 5, 6, 7],vec![0, 2, 6, 8]];
let mut result:Vec<_> = MergeAscending::new(vv[0].iter(),vv[1].iter()).collect() ;
for v in vv.iter().skip(2) {
result = MergeAscending::new(r.iter(), v.iter()).collect::<Vec<_>>();
}
}
How can one fix this? What do you think about memory efficiency and performance of this approach?
Better ideas?
I think this example can be made to work with references as well, I've just used