Support multiway_union, etc., with iterators of different types

[CarlKCarlK]

After a few days of puzzling over this, I think I have a solution to union over multiple types. Here is an example of it working:

    let primes = btreeset! { 2u64, 3, 5, 7, 11, 13 };
    let fibs = [1u64, 2, 3, 5, 8, 13];
    let one_digit = 0..=9;
    let primes = primes.into_iter().dyn_sorted_by_item();
    let fibs = fibs
        .iter()
        .assume_sorted_by_item()
        .copied()
        .dyn_sorted_by_item();
    let one_digit = one_digit.dyn_sorted_by_item();
    let union = multiway_union(vec![primes, fibs, one_digit].into_iter());
    println!("Union: {:?}", union.collect::<Vec<_>>());

It works by using a DynamicSortedByItem struct (modeled on AssumeSortedByItem):

pub struct DynSortedByItem<'a, T> {
    iter: Box<dyn Iterator<Item = T> + 'a>,
}
impl<'a, T> SortedByItem for DynSortedByItem<'a, T> {}

impl<'a, T> DynSortedByItem<'a, T> {
    pub fn new(iter: impl Iterator<Item = T> + SortedByItem + 'a) -> Self {
        DynSortedByItem {
            iter: Box::new(iter),
        }
    }
}

impl<'a, T> Iterator for DynSortedByItem<'a, T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}

/// extension trait for any iterator to add a assume_sorted_by_item method
pub trait DynSortedByItemExt<'a>: Iterator + Sized + SortedByItem + 'a {
    /// create dynamic version of the iterator
    fn dyn_sorted_by_item(self) -> DynSortedByItem<'a, Self::Item> {
        DynSortedByItem::new(self)
    }
}

impl<'a, I: Iterator + Sized + SortedByItem + 'a> DynSortedByItemExt<'a> for I {}

// todo: create a struct that is both dyn and assume (to avoid two layers of indirection)
// todo: do everything for SortByKey
// todo: Add note that RFC 2515 may someday make this obsolete https://github.com/rust-lang/rust/issues/63063

If you like this, let me know if you'd like to finish the 'todos' and submit it as a pull request or if you'd rather do it.

Thanks!
Carl

[CarlKCarlK]

With this macro (and the stuff above):

#[macro_export]
macro_rules! multiway_union_dyn {
    ($($val:expr),*) => {
        multiway_union(vec![$($val.dyn_sorted_by_item()),*].into_iter())
    }
}

Uses can do this:

  let primes = btreeset! { 2u64, 3, 5, 7, 11, 13 };
    let fibs = [1u64, 2, 3, 5, 8, 13]
        .iter()
        .cloned()
        .assume_sorted_by_item();
    let one_digit = 0..=9u64;

    let union = multiway_union_dyn!(primes.into_iter(), fibs, one_digit);
    println!("Union: {:?}", union.collect::<Vec<_>>());

[CarlKCarlK]

[I updated the previous comment to simplify the macro and fix the example]

[rklaehn]

Isn't DynSortedByItem basically Box<dyn Iterator<Item = T> + SortedByItem>, so with the new box support you won't need a separate type anymore?

Is the output of multiway_union strictly sorted, or just sorted?

[CarlKCarlK]

I tried to extend examples/set.rs to work with just Box, but can't get it to work:

doesn't compile

    let primes = btreeset! { 2u64, 3, 5, 7, 11, 13 };
    let fibs = btreeset! { 1u64, 2, 3, 5, 8, 13 };
    let nats = 1u64..;
    let primes: Box<dyn Iterator<Item = &u64> + SortedByItem + Sized> = Box::new(primes.iter());
    let fibs: Box<dyn Iterator<Item = &u64> + SortedByItem + Sized> = Box::new(fibs.iter());
    let nats: Box<dyn Iterator<Item = &u64> + SortedByItem + Sized> = Box::new(nats.iter());
    let all = multiway_union([primes, fibs, nats]);
    println!("All: {:?}", v(all));

Is the output of multiway_union strictly sorted, or just sorted?

The current code in sorted_iterators.rs says:

impl<I: Iterator> SortedByItem for MultiwayUnion<I> {}

[CarlKCarlK]

By the way, I mention sorted-iter as an inspiration in an article about Rust data structures:
https://towardsdatascience.com/nine-rules-for-creating-fast-safe-and-compatible-data-structures-in-rust-part-1-c0973092e0a3