Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

implement cmp, partial_cmp, and friends for parallel iterator #152

Closed
nikomatsakis opened this issue Nov 17, 2016 · 0 comments
Closed

implement cmp, partial_cmp, and friends for parallel iterator #152

nikomatsakis opened this issue Nov 17, 2016 · 0 comments

Comments

@nikomatsakis
Copy link
Member

nikomatsakis commented Nov 17, 2016

To achieve parity with sequential iterators, we need to support cmp and friends. These are methods which basically zip two iterators and compare corresponding elements; so long as the elements are equal, it proceeds to the next.

We can parallelize this fairly easily by using the existing zip, map, and reduce combinators I think. Roughly speaking I would do something like left.zip(right).map(Ord::cmp).reduce(|| Equal, |cmp_a, cmp_b| if cmp_a != Equal { cmp_b } else { cmp_a }). This won't, however, be the most efficient thing, because it will do all the comparisons, even if it already knows the final answer.

To support the most efficient thing, we probably want find_first (#151), I should think, so that we can basically search for the first "non-equal" result.

Here are the full set of methods:

  • fn cmp<I>(self, other: I) -> Ordering where I: IntoIterator<Item=Self::Item>, Self::Item: Ord { ... }
  • fn partial_cmp<I>(self, other: I) -> Option<Ordering> where I: IntoIterator, Self::Item: PartialOrd<I::Item> { ... }
  • fn eq<I>(self, other: I) -> bool where I: IntoIterator, Self::Item: PartialEq<I::Item> { ... }
  • fn ne<I>(self, other: I) -> bool where I: IntoIterator, Self::Item: PartialEq<I::Item> { ... }
  • fn lt<I>(self, other: I) -> bool where I: IntoIterator, Self::Item: PartialOrd<I::Item> { ... }
  • fn le<I>(self, other: I) -> bool where I: IntoIterator, Self::Item: PartialOrd<I::Item> { ... }
  • fn gt<I>(self, other: I) -> bool where I: IntoIterator, Self::Item: PartialOrd<I::Item> { ... }
  • fn ge<I>(self, other: I) -> bool where I: IntoIterator, Self::Item: PartialOrd<I::Item> { ... }

If you've not hacked on Rayon before, also check out the guide to development.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant