How to satisfy the Iterator trait bound in order t

Question

I'm attempting to parallelise the Ramer–Douglas-Peucker line simplification algorithm by using Rayon's par_iter instead of iter:

extern crate num_traits;
use num_traits::{Float, ToPrimitive};
extern crate rayon;
use self::rayon::prelude::*;

#[derive(PartialEq, Clone, Copy, Debug)]
pub struct Coordinate<T>
    where T: Float
{
    pub x: T,
    pub y: T,
}

#[derive(PartialEq, Clone, Copy, Debug)]
pub struct Point<T>(pub Coordinate<T>) where T: Float;

impl<T> Point<T>
    where T: Float + ToPrimitive
{
    pub fn new(x: T, y: T) -> Point<T> {
        Point(Coordinate { x: x, y: y })
    }
    pub fn x(&self) -> T {
        self.0.x
    }
    pub fn y(&self) -> T {
        self.0.y
    }
}

unsafe impl<T> Send for Point<T> where T: Float {}
unsafe impl<T> Sync for Point<T> where T: Float {}

fn distance<T>(a: &Point<T>, p: &Point<T>) -> T 
    where T: Float
{
    let (dx, dy) = (a.x() - p.x(), a.y() - p.y());
    dx.hypot(dy)
}

// perpendicular distance from a point to a line
fn point_line_distance<T>(point: &Point<T>, start: &Point<T>, end: &Point<T>) -> T
    where T: Float
{
    if start == end {
        distance(point, start)
    } else {
        let numerator = ((end.x() - start.x()) * (start.y() - point.y()) -
                         (start.x() - point.x()) * (end.y() - start.y()))
            .abs();
        let denominator = distance(start, end);
        numerator / denominator
    }
}

// Ramer–Douglas-Peucker line simplification algorithm
fn rdp<T>(points: &[Point<T>], epsilon: &T) -> Vec<Point<T>>
    where T: Float + Send + Sync
{
    if points.is_empty() {
        return points.to_vec();
    }
    let mut dmax = T::zero();
    let mut index: usize = 0;
    let mut distance: T;

    for (i, _) in points.par_iter().enumerate().take(points.len() - 1).skip(1) {
        distance = point_line_distance(&points[i], &points[0], &*points.last().unwrap());
        if distance > dmax {
            index = i;
            dmax = distance;
        }
    }
    if dmax > *epsilon {
        let mut intermediate = rdp(&points[..index + 1], &*epsilon);
        intermediate.pop();
        intermediate.extend_from_slice(&rdp(&points[index..], &*epsilon));
        intermediate
    } else {
        vec![*points.first().unwrap(), *points.last().unwrap()]
    }
}

#[cfg(test)]
mod test {
    use super::{Point};
    use super::{rdp};
        #[test]
    fn rdp_test() {
        let mut vec = Vec::new();
        vec.push(Point::new(0.0, 0.0));
        vec.push(Point::new(5.0, 4.0));
        vec.push(Point::new(11.0, 5.5));
        vec.push(Point::new(17.3, 3.2));
        vec.push(Point::new(27.8, 0.1));
        let mut compare = Vec::new();
        compare.push(Point::new(0.0, 0.0));
        compare.push(Point::new(5.0, 4.0));
        compare.push(Point::new(11.0, 5.5));
        compare.push(Point::new(27.8, 0.1));
        let simplified = rdp(&vec, &1.0);
        assert_eq!(simplified, compare);
    }
}

I've impld Send and Sync for Point<T>, but when I switch to par_iter, I get the following error:

error[E0277]: the trait bound rayon::par_iter::skip::Skip<rayon::par_iter::take::Take<rayon::par_iter::enumerate::Enumerate<rayon::par_iter::slice::SliceIter<'_, Point<T>>>>>: std::iter::Iterator is not satisfied
   --> lib.rs:107:5

= note: rayon::par_iter::skip::Skip<rayon::par_iter::take::Take<rayon::par_iter::enumerate::Enumerate<rayon::par_iter::slice::SliceIter<'_, Point<T>>>>> is not an iterator; maybe try calling .iter() or a similar method
= note: required by std::iter::IntoIterator::into_iter

I don't understand what it's asking for. Is the problem that I'm operating on a tuple?

Answer 1

Rayon's parallel iterators implement ParallelIterator, not Iterator. In particular, this means you cannot just put a par_iter() in a for-loop header and expect it to suddenly be parallel. for is sequential.

Since your original code isn't written in terms of iterator functions, but rather as for loops, you can't parallelize it simply with the switch to par_iter(), but have to actually redesign the code.

In particular, the failing part of the code seems to be implementing the max_by_key function.