search

contain-rs / ordered_iter

Ordered iterators
https://contain-rs.github.io/ordered_iter/ordered_iter
Apache License 2.0
13 stars 4 forks source link

Add set operations #6

Open apasel422 opened 9 years ago

apasel422 commented 9 years ago

The traits can be extended with additional methods that yield the difference and symmetric difference between two ordered iterators. The union is already handled by outer_join, and the intersection is already handled by inner_join.

apasel422 commented 9 years ago

I think we should rename the join methods to their appropriate set operation name.

Gankra commented 9 years ago

It's worth noting that these are established terms in relational algebra. I have no strong feelings on the names, otherwise.

apasel422 commented 9 years ago

Is there a difference other than the names? I've been thinking that it's silly for every (ordered) set implementation to define its own {Difference, Intersection, SymmetricDifference, Union} iterators. It would make sense for this crate to provide a generic implementation as extension methods. The same goes for ordered map iterators.

Note that this is different from optimized set operations that return a new set (e.g. BitSet).

Gankra commented 9 years ago

That... is an interesting idea. It's not clear to me that the optimal impl is necessarily blanket-able in general, though.

apasel422 commented 9 years ago

Another reason I favor the generic iterator adaptors here is that it avoids the theoretical combinatoric problem with iteration modes. Right now, the the sets in std and contain-rs only provide by-ref iterators, but there's no reason they couldn't have by-value or by-mut-ref ones, too.

apasel422 commented 9 years ago

Not to mention the bounded iterators.