use na::{Pnt2,origin,zero,one,AsVec,ToPnt,ToVec};
use num::NumCast;
use num::traits::cast;
use std::cmp::Ordering;
use std::ops::{Index, IndexMut};
use std::convert::AsRef;
use std::slice;
use std::iter::{FromIterator, IntoIterator};
use alga;

#[derive(Clone, Debug)]
pub struct Polyline<T: alga::general::Real>{
    points: Vec<Pnt2<T>>,
    closed: bool
}

impl<T:alga::general::Real + NumCast> Polyline<T>{
    /// creates an empty polyline
    pub fn new() -> Polyline<T>{
        Polyline{points:Vec::new(), closed:false}
    }

    /// creates a new polyline from the vector of points but orders them CCW first
    pub fn new_from_disordered_points(points: Vec<Pnt2<T>>, closed: bool) -> Polyline<T>{
        let mut polyline = Polyline{points: points, closed: closed};
        let centroid = polyline.centroid();
        polyline.points.sort_by(|p1,p2| less(p1,p2,&centroid));
        polyline
    }

    /// returns the area of the polygon, only works if the polyline represents
    /// a polygon
    pub fn area(&self) -> T{
        let mut area: T = zero();
        for i in 0 .. self.len()-1{
            area = area + (self.points[i].x * self.points[i+1].y - self.points[i+1].x * self.points[i].y);
        }
        area = area + (self.points[self.len()-1].x * self.points[0].y - self.points[0].x * self.points[self.len()-1].y);
        area = area * cast(0.5).unwrap();
        area
    }

    /// centroid of the polyline, should work for any collection of points
    /// although it will only make sense if it's a polygon
    pub fn centroid(&self) -> Pnt2<T>{
        let mut centroid: Pnt2<T> = origin();
        if self.points.len()<3{
            return centroid;
        }

        let area = self.area();

        for i in 0 .. self.len()-1{
            let p = self.points[i];
            let next_p = self.points[i+1];
            centroid.x = centroid.x + ((p.x + next_p.x) * (p.x*next_p.y - next_p.x*p.y));
            centroid.y = centroid.y + ((p.y + next_p.y) * (p.x*next_p.y - next_p.x*p.y));
        }

        let p = self.points.last().unwrap();
        let next_p = self.points[0];
        centroid.x = centroid.x + ((p.x + next_p.x) * (p.x*next_p.y - next_p.x*p.y));
        centroid.y = centroid.y + ((p.y + next_p.y) * (p.x*next_p.y - next_p.x*p.y));

        let six: T = cast(6.0).unwrap();
        centroid.x = centroid.x / (six*area);
        centroid.y = centroid.y / (six*area);
        centroid
    }

    /// mark this polyline as being a closed shape, although not necesarily a
    /// polygon. Any rendering or calculation will take into account that the
    /// first and last points are joined
    pub fn close(&mut self){
        self.closed = true;
    }

    /// returns true if the polyline is closed
    pub fn is_closed(&self) -> bool{
        self.closed
    }

    /// returns total number of points
    pub fn len(&self) -> usize{
        self.points.len()
    }

    /// add a new point at the end of the polyline
    pub fn push(&mut self, p: Pnt2<T>){
        self.points.push(p);
    }


    /// Returns a smoothed version of the polyline.
	///
	/// `window_size` is the size of the smoothing window. So if
	/// `window_size` is 2, then 2 points from the left, 1 in the center,
	/// and 2 on the right (5 total) will be used for smoothing each point.
    ///
	/// `window_shape` describes whether to use a triangular window (0) or
	/// box window (1) or something in between (for example, .5).
    pub fn smoothed(&self, window_size: usize, window_shape: T) -> Polyline<T>{
        let n = self.points.len();
        let size = ::clamp(window_size, 0, n);
        let shape = ::clamp(window_shape, zero(), one());

        let weights = (0..size).map(|i| ::map(cast(i).unwrap(), zero(), cast(size).unwrap(), one(), shape))
            .collect::<Vec<_>>();

        let mut result = self.clone();
        for i in 0..n {
            let mut sum: T = one();
            for j in 1..size{
                let mut cur: Pnt2<T> = origin();
                let mut left = i as isize - j as isize;
                let mut right = i + j;
                if left < 0 && self.closed{
                    left += n as isize;
                }
                if left >= 0 {
                    cur += self.points[left as usize].as_vec();
                    sum += weights[j];
                }
                if right > n && self.closed {
                    right -= n;
                }
                if right < n{
                    cur += self.points[right].as_vec();
                    sum += weights[j];
                }
                result[i] += cur.as_vec() * weights[j];
            }
            result[i] /= sum;
        }

        result
    }

    pub fn subdivide_linear(&self, resolution: usize) -> Polyline<T>{
        let points = self.points.windows(2).enumerate()
            .flat_map(|(segment, current_next)| (0..resolution).map(move |i|{
                let i_f: T = cast(i).unwrap();
                let t: T = i_f / if segment == self.points.len() - 2{
                    cast(resolution - 1).unwrap()
                }else{
                    cast(resolution).unwrap()
                };
                ::lerp(current_next[0].to_vec(), current_next[1].to_vec(), t).to_pnt()
            }));

        Polyline{
            points: points.collect(),
            closed: self.closed
        }
    }

    pub fn iter(&self) -> slice::Iter<Pnt2<T>>{
        self.points.iter()
    }

    pub fn first(&self) -> Option<&Pnt2<T>>{
        self.points.first()
    }

    pub fn first_mut(&mut self) -> Option<&mut Pnt2<T>>{
        self.points.first_mut()
    }

    pub fn last(&self) -> Option<&Pnt2<T>>{
        self.points.last()
    }

    pub fn last_mut(&mut self) -> Option<&mut Pnt2<T>>{
        self.points.last_mut()
    }

    pub fn is_empty(&self) -> bool {
        self.points.is_empty()
    }
}

impl<T:alga::general::Real> AsRef<[Pnt2<T>]> for Polyline<T>{
	fn as_ref(&self) -> &[Pnt2<T>]{
		self.points.as_ref()
	}
}

impl<T:alga::general::Real> Index<usize> for Polyline<T>{
	type Output = Pnt2<T>;
    fn index(&self, idx: usize) -> &Pnt2<T>{
        self.points.index(idx)
    }
}

impl<T:alga::general::Real> IndexMut<usize> for Polyline<T>{
    fn index_mut(&mut self, idx: usize) -> &mut Pnt2<T>{
        self.points.index_mut(idx)
    }
}

impl<T> FromIterator<Pnt2<T>> for Polyline<T>
    where T: alga::general::Real
{
    fn from_iter<I>(iter: I) -> Polyline<T>
        where I: IntoIterator<Item=Pnt2<T>>
    {
        Polyline{
            points: iter.into_iter().collect(),
            closed: false,
        }
    }
}

impl<T> Into<Vec<Pnt2<T>>> for Polyline<T>
    where T: alga::general::Real
{
    fn into(self) -> Vec<Pnt2<T>>{
        self.points
    }
}

fn less<T:alga::general::Real>(a: &Pnt2<T>, b: &Pnt2<T>, center: &Pnt2<T>) -> Ordering{
    if a.x - center.x >= zero() && b.x - center.x < zero(){
        return Ordering::Less;
    }
    if a.x - center.x < zero() && b.x - center.x >= zero(){
        return Ordering::Greater;
    }
    if a.x - center.x == zero() && b.x - center.x == zero(){
        if a.y - center.y >= zero() || b.y - center.y >= zero(){
            return if a.y > b.y { Ordering::Less } else { Ordering::Greater };
        }
        return if b.y > a.y  {Ordering::Less} else {Ordering::Greater};
    }

    // compute the cross product of vectors (center -> a) x (center -> b)
    let det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
    if det < zero(){
        return Ordering::Less;
    }
    if det > zero(){
        return Ordering::Greater;
    }

    // points a and b are on the same line from the center
    // check which point is closer to the center
    let d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
    let d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
    if d1 > d2 { Ordering::Less } else { Ordering::Greater }
}