dist.rs

use point::Point; 


type PairDistance = (Point, Point, f64);
fn helper(points: &[Point]) ->  PairDistance {
	assert!(points.len() >= 2);
	match points.len() {
		2 => (points[0], points[1], points[0].distance(&points[1])), 
		3 => {
			let p0 = points[0];
			let p1 = points[1];
			let p2 = points[2];
			let d01 = p0.distance(&p1);
			let d02 = p0.distance(&p2);
			let d12 = p1.distance(&p2);
			let v: Vec<PairDistance> = vec![(p0, p1, d01), (p0, p2, d02), (p1, p2, d12)];
			v.sort_by(|a, b| {
				a.2.partial_cmp(&b.2).unwrap()
			});
			v[0]
		}, 
		_ => {
			let mid = points.len() / 2; 
			let mid_point = points[mid];
			let mid_x = mid_point.x.to_f64();
			let pair1 = helper(&points[0 .. (mid+1)]);
			let pair2 = helper(&points[(mid+1) .. points.len()]);
			// which is closer, pair1 or pair2?
			let v_pair12: Vec<PairDistance> = vec![pair1, pair2];
			v_pair12.sort_by(|a, b| {
					a.2.partial_cmp(&b.2).unwrap()
			});
			let min_pair12 = v_pair12[0]; 
			let min_d_pair12 = min_d_pair12.2; 
			// filter out all points that are not in the ±d strip 
			let points_in_strip: Vec<_> = points.iter().filter(move |p| {
					(p.x.to_f64() - mid_point.x.to_f64()).abs() < min_d_pair12
			}).collect(); 
			let pair_in_strip = helper(points_in_strip.as_slice());
			if pair_in_strip.2 < min_d_pair12 {
				pair_in_strip
			} else {
				min_pair12
			}
		}
	}
}