use std::collections::BinaryHeap;
use std::cmp::Reverse;
use std::io::{Read, Write};
use std::marker::PhantomData;
pub trait Sortable<W: Write, R: Read>: Ord + Sized {
type Error;
fn serialize(&self, w: &mut W) -> Result<(), Self::Error>;
fn deserialize(r: &mut R) -> Option<Result<Self, Self::Error>>;
}
pub struct ExtSortedIterator<T, R, W> {
tips: BinaryHeap<Reverse<(T, usize)>>,
readers: Vec<R>,
failed: bool,
phantom: PhantomData<W>,
}
impl<T, R, W> ExtSortedIterator<T, R, W>
where T: Sortable<W, R>,
W: Write, R: Read,
{
pub fn new(mut readers: Vec<R>) -> Result<Self, T::Error> {
let mut tips = BinaryHeap::with_capacity(readers.len());
for (idx, r) in readers.iter_mut().enumerate() {
let item = T::deserialize(r).unwrap()?;
tips.push(Reverse((item, idx)));
}
Ok(Self {
tips,
readers,
failed: false,
phantom: PhantomData,
})
}
}
impl<T, R, W> Iterator for ExtSortedIterator<T, R, W>
where
T: Sortable<W, R>,
R: Read,
W: Write,
{
type Item = Result<T, T::Error>;
fn next(&mut self) -> Option<Self::Item> {
if self.failed {
return None;
}
let Reverse((r, idx)) = self.tips.pop()?;
match T::deserialize(&mut self.readers[idx]) {
Some(Ok(n)) => {
self.tips.push(Reverse((n, idx)));
},
Some(Err(e)) => {
self.failed = true;
return Some(Err(e));
},
None => { },
};
Some(Ok(r))
}
}