extern crate rand;

use rand::Rng;

use std::cmp::Ordering;
use std::fmt;
use std::ops::Bound::Included;
use std::cmp::Ordering::Less;

use std::collections::BTreeSet;
use std::time::{Duration, Instant};

static mut cnt: u64 = 0;

fn main() {
    for dimension in 2..=6 {
        let mut v = makerandompoints(1600, dimension);
        get_closest_pair(&mut v);
    }

}

#[derive(Debug, Clone)]
pub struct Point {
    pub coordinates: Vec<f64>,
}

impl Point {
    pub fn new(coordinates: Vec<f64>) -> Point {
        Point { coordinates }
    }
    pub fn distance(point1: &Point, point2: &Point) -> f64 {
        point1
            .coordinates
            .iter()
            .zip(point2.coordinates.iter())
            .map(|(x1, x2)| (x1 - x2).powi(2))
            .sum::<f64>()
            .sqrt()
    }

}

pub fn get_closest_pair<'a>(points: &'a mut Vec<Point>) -> (&'a Point, &'a Point) {
    let mut total_time = Duration::from_secs(0);
    let mut total_cmp = 0;

    let firstco = |p: &Point| p.coordinates[0];
    let secondco = |p: &Point| p.coordinates[1];
    points.sort_unstable_by(|p1, p2| firstco(p1).partial_cmp(&firstco(p2)).unwrap_or(Less));

    let mut closest_pair = (&points[0], &points[1]);
    let mut min_distance = Point::distance(closest_pair.0, closest_pair.1);

    let mut set = BTreeSet::new();
    set.insert(&points[0]);
    if !set.insert(&points[1]) {
        return (&points[0], &points[1]);
    }

    let mut points = points.iter();
    points.nth(1);

    let mut rangepoints = make_zero_points(closest_pair.0.coordinates.len());

    let mut removalvec: Vec<&Point> = Vec::new();

    for firstpoint in points {
        remove_left_points(&mut removalvec, &mut set);
        set_range(
            secondco(firstpoint),
            min_distance,
            &mut rangepoints.0,
            &mut rangepoints.1,
        );

        {
        //timing occurs here!
        let startcnt = unsafe { cnt };
        let starttime = Instant::now();
        let range = set.range::<Point, _>((Included(&rangepoints.0), Included(&rangepoints.1)));
        //let foo = set.contains(&rangepoints.0);
        total_time += starttime.elapsed();
        total_cmp += unsafe {  cnt } - startcnt;
        //println!("{}", unsafe {  cnt } - startcnt);

        for secondpoint in
            set.range::<Point, _>((Included(&rangepoints.0), Included(&rangepoints.1)))
        {
            if firstco(secondpoint) <= firstco(firstpoint) - min_distance {
                removalvec.push(secondpoint);
                continue;
            }

            let distance = Point::distance(firstpoint, secondpoint);
            if distance < min_distance {
                min_distance = distance;
                closest_pair = (secondpoint, firstpoint);
            }
        }
        }

        if !set.insert(firstpoint) {
            //if we want references to two seperate points, we can do
            //a search in the points vector, which takes O(n) time
            return (firstpoint, firstpoint);
        }
    }
    println!("partialtiming: {}", time_to_string(total_time));
    println!("total_cmp: {}", total_cmp);
    closest_pair
}

fn remove_left_points(removalvec: &mut Vec<&Point>, set: &mut BTreeSet<&Point>) {
    for point in removalvec.drain(..) {
        if !set.remove(point) {
            panic!("tried to remove nonexistant item");
        }
    }
}

fn set_range(coordinate: f64, distance: f64, point1: &mut Point, point2: &mut Point) {
    point1.coordinates[1] = coordinate - distance;
    point2.coordinates[1] = coordinate + distance;
}

fn make_zero_points(length: usize) -> (Point, Point) {
    let zero_vec1 = vec![0.0; length];
    let zero_vec2 = vec![0.0; length];
    (Point::new(zero_vec1), Point::new(zero_vec2))
}


impl fmt::Display for Point {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "{}",
            self.coordinates
                .iter()
                .map(ToString::to_string)
                .collect::<Vec<String>>()
                .join(" ")
        )
    }
}

impl PartialEq for Point {
    fn eq(&self, other: &Point) -> bool {
        self.coordinates.eq(&other.coordinates)
    }
}

impl Eq for Point {}

impl PartialOrd for Point {
    fn partial_cmp(&self, other: &Point) -> Option<Ordering> {

    // cutsom cmp:
        (&self.coordinates[1..], &self.coordinates[0])
            .partial_cmp(&(&other.coordinates[1..], &other.coordinates[0]))

      // vec cmp:
      //              self.coordinates.partial_cmp(&other.coordinates)

    }
}

impl Ord for Point {
    fn cmp(&self, other: &Point) -> Ordering {
        unsafe { cnt += 1;}
        match Point::partial_cmp(self, other) {
            Some(ordering) => ordering,
            None => unreachable!(),
        }
    }
}

pub fn makerandompoints(amount: usize, dimension: usize) -> Vec<Point> {
    let mut rng = rand::thread_rng();
    (0..amount)
        .map(|_| Point::new((0..dimension).map(|_| rng.gen_range(0.0, 10.0)).collect()))
        .collect()
}

pub fn time_to_string(time: Duration) -> String {
    let time = time.as_secs() as f64 * 1e9 + time.subsec_nanos() as f64;
    format!("{}", time)
}

pub fn time_to_string_ms(time: Duration) -> String {
    let time = time.as_secs() as f64 * 1e3 + time.subsec_nanos() as f64 / 1e6;
    format!("{}", time)
}