itertools icon indicating copy to clipboard operation
itertools copied to clipboard

Add iterator versions of BTreeSet operations

Open DevinR528 opened this issue 4 years ago • 1 comments

The motivation for this is when using union, intersection, difference, and symmetric_difference the items have to be cloned, this avoids that and can return borrowed items. What I was shooting for was as if the signature to BTreeSet::intersection was

pub fn difference<'a>(&'a self, other: &'a BTreeSet<Q>) -> Difference<'a, Q>
where
    T: Borrow<Q>,
    Q: Ord,
{...}

The code is taken from the std lib and altered to work with iterators so it should be sound, still working out a few kinks but nothing major.

I did try implementing the above signature in the std lib but was unable (could be just me) so I tried this out and got it working! Let me know if this is helpful as part of itertools.

Thanks by the way for a great crate!

Huge problem

This relies on the iterator returning items in sorted order, is this an acceptable invariant to only document (is there any way to add a trait to signify that the iterator needs to be sorted?).

DevinR528 avatar Jun 27 '21 21:06 DevinR528

@DevinR528 This is quite some work you done here!

This is huge (even without the now unneeded first commit): small PRs are more likely to be considered/reviewed/merged. So as is, it will likely be closed. There is no SortedIterator trait and it seems an uncommon requirement to me, it seems contrived to work with iterators, but it could be documented. Maybe a simpler version of those could wrap MergeJoinBy and roughly-filter_map the elements.

But I wonder if other people would be interested in this, and this is the major block point to me here. In which use cases would it be useful?

EDIT: That being said, I found a related issue #695.

Philippe-Cholet avatar May 15 '24 08:05 Philippe-Cholet