extern crate itertools;

#[cfg(test)]
mod tests;

use std::collections::HashMap;

use itertools::Itertools;

#[derive(Copy, Clone, Eq, PartialEq, Debug, Hash)]
pub struct Coord {
    pub x: usize,
    pub y: usize
}
impl From<(usize, usize)> for Coord {
    fn from(obj: (usize, usize)) -> Coord {
        Coord {
            x: obj.0,
            y: obj.1
        }
    }
}
impl From<[usize; 2]> for Coord {
    fn from(obj: [usize; 2]) -> Coord {
        Coord {
            x: obj[0].into(),
            y: obj[1].into()
        }
    }
}

#[derive(Copy, Clone, Debug, Eq, Hash)]
pub struct Harmony<'a> {
    pub start: Coord,
    pub end: Coord,
    pub owner: &'a Player
}
impl<'a> Harmony<'a> {
    fn new<X, Y>(x: X, y: Y, owner: &'a Player) -> Harmony<'a> where X: Into<Coord>, Y: Into<Coord> {
        Harmony {
            start: x.into(),
            end: y.into(),
            owner: owner
        }
    }

    pub fn get_length(&self) -> usize {
        (((self.start.x as i64 - self.end.x as i64) + 
         (self.start.y as i64 - self.end.y as i64)).abs() - 1) as usize
    }
}

impl<'a> PartialEq for Harmony<'a> {
    fn eq(&self, rhs: &Harmony) -> bool {
        if self.start == rhs.start && self.end == rhs.end {
            true
        } else if self.start == rhs.end && self.end == rhs.start {
            true
        } else {
            false
        }
    }
}

#[derive(Debug, Clone)]
pub struct Board<'a> {
    pub players: Vec<&'a Player>,
    pub size: usize,
    pub board: Vec<Option<Stone<'a>>>
}
impl<'a> Board<'a> {
    pub fn new(size: usize) -> Board<'a> {
        Board {
            players: Vec::new(),
            size: size,
            board: vec![None; size.pow(2)]
        }
    }

    pub fn seat(&mut self, player: &'a Player) {
        self.players.push(player);
    }

    pub fn play<Q>(&mut self, position: Q, player: &'a Player) -> Result<(), PiecePlacementErr>
        where Q: Into<Coord>
    {
        let position = position.into();
        if position.x >= self.size || position.y >= self.size {
            Err(PiecePlacementErr::PlacedOutsideBoard)
        } else if !self.players.contains(&player) {
            Err(PiecePlacementErr::PlayerNotInGame)
        } else {
            self.board[position.y*self.size + position.x] = Some(Stone::new(player, PlayState::Placed));
            Ok(())
        }
    }

    pub fn get(&self, x: usize, y: usize) -> Option<&Stone<'a>> {
        let stone = self.board.get(y*self.size + x);
        if let Some(&Some( ref owner )) = stone {
            Some(owner)
        } else {
            None
        }
    }

    pub fn get_mut(&mut self, x: usize, y: usize) -> Option<&mut Stone<'a>> {
        let stone = self.board.get_mut(y*self.size + x);
        if let Some(&mut Some( ref mut owner )) = stone {
            Some(owner)
        } else {
            None
        }
    }

    pub fn get_direct_opt(&self, x: usize, y: usize) -> Option<&Option<Stone<'a>>> {
        self.board.get(y*self.size + x)
    }

    pub fn get_mut_direct_opt(&mut self, x: usize, y: usize) -> Option<&mut Option<Stone<'a>>> {
        self.board.get_mut(y*self.size + x)
    }

    pub fn get_row(&self, row: usize) -> Vec<&Option<Stone<'a>>> {
        self.board.iter().skip(row*self.size).take(self.size).collect()
    }


    pub fn get_column(&self, column: usize) -> Vec<&Option<Stone<'a>>> {
        self.board.iter().enumerate().filter_map(|(i, cell)| {
            if i >= column && (i - column) % self.size == 0 {
                Some(cell)
            } else {
                None
            }
        }).collect()
    }

    pub fn get_harmonies(&self) -> Vec<Harmony> {
        let mut harmonies = Vec::new();
        for (y, row) in (0..self.size).map(|n| (n, self.get_row(n))) {
            for player in self.players.iter() {
                for (start, end) in (0..self.size).filter_map(|n| {
                    let stone = row[n];
                    if let &Some(ref stone) = stone {
                        if **player == **stone {
                            Some((n, y, stone))
                        } else { 
                            None
                        }
                    } else {
                        None
                    }
                }).collect::<Vec<_>>().iter().combinations() {
                    harmonies.push(Harmony::new((start.0, start.1), (end.0, end.1), start.2));
                }
            }
        }

        for (x, column) in (0..self.size).map(|n| (n, self.get_column(n))) {
            for player in self.players.iter() {
                for (start, end) in (0..self.size).filter_map(|n| {
                    let stone = column[n];
                    if let &Some(ref stone) = stone {
                        if **player == **stone {
                            Some((x, n, stone))
                        } else { 
                            None
                        }
                    } else {
                        None
                    }
                }).collect::<Vec<_>>().iter().combinations() {
                    harmonies.push(Harmony::new((start.0, start.1), (end.0, end.1), start.2));
                }
            }
        }



        {
            let mut offset = 0;
            for (i, harmony) in harmonies.clone().iter().enumerate() {
                if harmony.get_length() == 0 {
                    harmonies.remove(i-offset);
                    offset += 1;
                }
            }
        }

        let mut harmonies_map = {
            let mut buffer = HashMap::new();
            for harmony in harmonies.iter() {
                buffer.insert(harmony, true);
            }
            buffer
        };

        for (A, B) in harmonies.iter().combinations() {
            if A.owner != B.owner {
                match (A.start.x == A.end.x, B.start.x == B.end.x) {
                    (true, false) => {
                        // Perpendicular, A vertical, B horizontal
                        let A_lower = std::cmp::min(A.start.y, A.end.y);
                        let A_upper = std::cmp::max(A.start.y, A.end.y);
                        let B_lower = std::cmp::min(B.start.x, B.end.x);
                        let B_upper = std::cmp::max(B.start.x, B.end.x);
                        if (B_lower < A.start.x && A.start.x < B_upper) 
                            && (A_lower < B.start.y && B.start.y < A_upper)
                        {
                            *harmonies_map.get_mut(&A).unwrap() = false;
                            *harmonies_map.get_mut(&B).unwrap() = false;
                        }
                    },
                    (false, true) => {
                        // Perpendicular, A horizontal, B vertical
                        let A_lower = std::cmp::min(A.start.x, A.end.x);
                        let A_upper = std::cmp::max(A.start.x, A.end.x);
                        let B_lower = std::cmp::min(B.start.y, B.end.y);
                        let B_upper = std::cmp::max(B.start.y, B.end.y);
                        if (B_lower < A.start.y && A.start.y < B_upper) 
                            && (A_lower < B.start.x && B.start.x < A_upper)
                        {
                            *harmonies_map.get_mut(&A).unwrap() = false;
                            *harmonies_map.get_mut(&B).unwrap() = false;
                        }
                    },
                    (true, true) => {
                        // Parallel, both vertical
                        if A.start.x == B.start.x {
                            let A_lower = std::cmp::min(A.start.y, A.end.y);
                            let A_upper = std::cmp::max(A.start.y, A.end.y);
                            let B_lower = std::cmp::min(B.start.y, B.end.y);
                            let B_upper = std::cmp::max(B.start.y, B.end.y);
                            // If A is contained inside B
                            if B_lower < A_lower && A_upper < B_upper {
                                *harmonies_map.get_mut(&B).unwrap() = false;
                            } else if A_lower < B_lower && B_upper < A_upper {
                                *harmonies_map.get_mut(&A).unwrap() = false;
                            }
                        }
                    },
                    (false, false) => {
                        // Parallel, both horizontal
                        if A.start.y == B.start.y {
                            let A_lower = std::cmp::min(A.start.x, A.end.x);
                            let A_upper = std::cmp::max(A.start.x, A.end.x);
                            let B_lower = std::cmp::min(B.start.x, B.end.x);
                            let B_upper = std::cmp::max(B.start.x, B.end.x);
                            // If A is contained inside B
                            if B_lower < A_lower && A_upper < B_upper {
                                *harmonies_map.get_mut(&B).unwrap() = false;
                            } else if A_lower < B_lower && B_upper < A_upper {
                                *harmonies_map.get_mut(&A).unwrap() = false;
                            }
                        }
                    }
                }
            }
        }


        let harmonies = harmonies_map.iter().filter_map(|(&key, &value)| {
            if value {
                Some(*key)
            } else {
                None
            }
        }).collect();

        return harmonies;
    }

    pub fn get_move_dir_for_stone(&self, x: usize, y: usize) -> MoveDir {
        let mut move_dir = MoveDir::NoDir;

        for harmony in self.get_harmonies().iter().filter(|n| {
            (n.start.x, n.start.y) == (x, y) || (n.end.x, n.end.y) == (x, y)
        }) {
            if harmony.start.x == harmony.end.x {
                move_dir.allow_vert()
            } else {
                move_dir.allow_horiz()
            }
        }

        if let Some(source) = self.get(x, y) {
            if let Some(target) = self.get(x+1, y) {
                if source.owner == target.owner {
                    move_dir.allow_vert();
                }
            } else if let Some(target) = self.get((x as i64 -1).abs() as usize, y) {
                if source.owner == target.owner {
                    move_dir.allow_vert();
                }
            } else if let Some(target) = self.get(x, y+1) {
                if source.owner == target.owner {
                    move_dir.allow_horiz()
                }
            } else if let Some(target) = self.get(x, (y as i64-1).abs() as usize) {
                if source.owner == target.owner {
                    move_dir.allow_horiz()
                }
            }
        }

        return move_dir;
    }

    pub fn move_stone<S, D>(&mut self, source: S, destination: D) -> Result<(), MoveErr> 
        where S: Into<Coord>, D: Into<Coord>
    {
        let source = source.into();
        let destination = destination.into();

        if destination.x >= self.size || destination.y >= self.size {
            Err(MoveErr::DestinationNotInRange)
        } else if source.x == destination.x || source.y == destination.y {
            if self.get(source.x, source.y).is_some() {
                let move_dir = self.get_move_dir_for_stone(source.x, source.y);
                if source.x == destination.x && move_dir.is_vert() {
                    let lower = std::cmp::min(source.y, destination.y);
                    let upper = std::cmp::max(source.y, destination.y);
                    if self.get_column(source.x).iter().skip(lower).take(upper - lower)
                        .fold(0, |a, b| if b.is_some() {a+1} else {a}) == 0 
                    {
                        let mut move_stone = self.get(source.x, source.y).unwrap().clone();
                        move_stone.state = PlayState::Moved;
                        *self.get_mut_direct_opt(destination.x, 
                                                 destination.y).unwrap() = Some(move_stone);
                        *self.get_mut_direct_opt(source.x, source.y).unwrap() = None;
                        Ok(())
                    } else {
                        Err(MoveErr::MovesThroughPiece)
                    }
                } else if source.y == destination.y && move_dir.is_horiz() {
                    let lower = std::cmp::min(source.x, destination.x);
                    let upper = std::cmp::max(source.x, destination.x);
                    if self.get_row(source.y).iter().skip(lower).take(upper - lower - 1)
                        .fold(0, |a, b| if b.is_some() {a+1} else {a}) == 0 
                    {
                        let mut move_stone = self.get(source.x, source.y).unwrap().clone();
                        move_stone.state = PlayState::Moved;
                        *self.get_mut_direct_opt(destination.x, 
                                                 destination.y).unwrap() = Some(move_stone);
                        *self.get_mut_direct_opt(source.x, source.y).unwrap() = None;
                        Ok(())
                    } else {
                        Err(MoveErr::MovesThroughPiece)
                    }
                } else {
                    Err(MoveErr::NoHarmonicLine)
                }
            } else {
                Err(MoveErr::NoPieceAtOrigin)
            }
        } else {
            Err(MoveErr::DestinationNotOrthogonal)
        }
    }

    pub fn update_life(&mut self) -> usize {
        let mut stages = [PlayState::Placed, PlayState::Static, PlayState::Moved];
        let mut deaths = 0;

        let mut new_deaths = 1;
        while new_deaths > 0 {
            new_deaths = 0;
            for stage in stages.iter() {
                for x in 0..self.size {
                    for y in 0..self.size {
                        if self.get(x, y).is_some() {
                            if self.get(x, y).unwrap().state == *stage {
                                for harmony in self.clone().get_harmonies() {
                                    if harmony.owner != self.get(x, y).unwrap().owner {
                                        if harmony.start.x == harmony.end.x && harmony.start.x == x {
                                            let lower = std::cmp::min(harmony.start.y, harmony.end.y);
                                            let upper = std::cmp::max(harmony.start.y, harmony.end.y);

                                            if lower < y && y < upper {
                                                *self.get_mut_direct_opt(x, y).unwrap() = None;
                                                new_deaths += 1;
                                            }
                                        } else if harmony.start.y == harmony.end.y && harmony.start.y == y {
                                            let lower = std::cmp::min(harmony.start.x, harmony.end.x);
                                            let upper = std::cmp::max(harmony.start.x, harmony.end.x);

                                            if lower < x && x < upper {
                                                *self.get_mut_direct_opt(x, y).unwrap() = None;                                
                                                new_deaths += 1;
                                            }
                                        }
                                    }
                                }

                            }
                        }
                    }
                }
            }
            deaths += new_deaths;
        }


        for stone in self.board.iter_mut() {
            if let &mut Some(ref mut stone) = stone {
                stone.state = PlayState::Placed;
            }
        }

        return deaths;
    }
}

#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum MoveDir {
    Horiz,
    Vert,
    HorizVert,
    NoDir
}
impl MoveDir {
    fn allow_horiz(&mut self) {
        *self = match *self {
            MoveDir::Horiz | MoveDir::NoDir => MoveDir::Horiz,
            MoveDir::Vert | MoveDir::HorizVert => MoveDir::HorizVert,
        }
    }

    fn allow_vert(&mut self) {
        *self = match *self {
            MoveDir::Horiz | MoveDir::HorizVert => MoveDir::HorizVert,
            MoveDir::Vert | MoveDir::NoDir => MoveDir::Vert
        }
    }
    fn is_horiz(&self) -> bool {
        match *self {
            MoveDir::Horiz | MoveDir::HorizVert => true,
            _ => false
        }
    }
    fn is_vert(&self) -> bool {
        match *self {
            MoveDir::Vert | MoveDir::HorizVert => true,
            _ => false
        }
    }
}

#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum MoveErr {
    NoPieceAtOrigin,
    DestinationNotOrthogonal,
    NoHarmonicLine,
    MovesThroughPiece,
    DestinationNotInRange
}

#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum PiecePlacementErr {
    PlacedOutsideBoard,
    PlayerNotInGame,
}

#[derive(Debug, Clone, Eq, PartialEq, Hash)]
pub struct Player {
    pub name: String,
}
impl Player {
    pub fn new<S: Into<String>>(name: S) -> Player {
        Player {
            name: name.into()
        }
    }
}


#[derive(Debug, Clone, Eq, PartialEq, Hash)]
pub struct Stone<'a> {
    pub owner: &'a Player,
    pub state: PlayState
}
impl<'a> std::ops::Deref for Stone<'a> {
    type Target = Player;
    fn deref(&self) -> &Self::Target {
        self.owner
    }
}
impl<'a> Stone<'a> {
    fn new(player: &'a Player, state: PlayState) -> Stone<'a> {
        Stone {
            owner: player,
            state: state
        }
    }
}

#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
pub enum PlayState {
    Placed,
    Static,
    Moved
}