close.rs

use point::Point;


type PairDistance = (Point, Point, f64);

pub fn closest_pair(points: &mut Vec<Point>) -> PairDistance {
    fn helper(points: &[Point]) -> PairDistance {
		#[cfg(feature = "verbose")] 
		{
			println!("{:?}", points);
		}
        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 mut 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]);
                let pair2 = helper(&points[mid..points.len()]);
//                let pair1 = helper(&points[0..(mid + 1)]);
//                let pair2 = helper(&points[(mid + 1)..points.len()]);
                // which is closer, pair1 or pair2?
                let mut 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_pair12.2;
                // filter out all points that are not in the ±d strip
                let points_in_strip: Vec<_> = points.iter()
                    .cloned()
                    .filter(|p| (p.x.to_f64() - mid_x).abs() < min_d_pair12)
                    .collect();
				if points_in_strip.len() >= 2 {
					let pair_in_strip = helper(points_in_strip.as_slice());
					if pair_in_strip.2 < min_d_pair12 {
						pair_in_strip
					} else {
						min_pair12
					}
				} else {
					min_pair12
				}
            }
        }
    }

	points.sort(); 
	let res = helper(points.as_slice());
	#[cfg(feature = "verbose")]
	{
		println!("{:?}", res);
	}
	res
}