1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
use std::cmp::Ordering; use super::{SortOrder, SortedIterator}; pub struct Union<I, J> where I: SortedIterator, I::Ordering: SortOrder<I::Item>, J: SortedIterator<Item = I::Item, Ordering = I::Ordering> { i: I, j: J, a: Option<I::Item>, b: Option<J::Item>, } impl<I, J> SortedIterator for Union<I, J> where I: SortedIterator, I::Ordering: SortOrder<I::Item>, J: SortedIterator<Item = I::Item, Ordering = I::Ordering> { type Ordering = I::Ordering; } impl<I, J> Iterator for Union<I, J> where I: SortedIterator, I::Ordering: SortOrder<I::Item>, J: SortedIterator<Item = I::Item, Ordering = I::Ordering> { type Item = I::Item; fn next(&mut self) -> Option<Self::Item> { let a = self.a.take().or_else(|| self.i.next()); let b = self.b.take().or_else(|| self.j.next()); match (a, b) { (a @ Some(_), None) => a, (None, b @ Some(_)) => b, (Some(a), Some(b)) => { if I::Ordering::cmp(&a, &b) == Ordering::Less { self.b = Some(b); Some(a) } else { self.a = Some(a); Some(b) } } (None, None) => None, } } } pub trait UnionExt where Self: SortedIterator + Sized, Self::Ordering: SortOrder<Self::Item> { fn union<J>(self, J) -> Union<Self, J> where J: SortedIterator<Ordering = Self::Ordering, Item = Self::Item>; } impl<I> UnionExt for I where I: SortedIterator, I::Ordering: SortOrder<I::Item> { fn union<J>(self, j: J) -> Union<Self, J> where J: SortedIterator<Ordering = Self::Ordering, Item = Self::Item> { Union { i: self, j, a: None, b: None, } } }