use std::collections::HashSet;
use std::fmt;

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct Position {
    pub x: u8,
    pub y: u8,
}

impl fmt::Display for Position {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:x}{}", 10 + self.x, self.y + 1)
    }
}

#[derive(PartialEq, Clone, Copy)]
pub enum Player {
    Black,
    White,
}

impl fmt::Display for Player {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "{}",
            match self {
                Player::Black => "B",
                Player::White => "W",
            }
        )
    }
}

#[derive(PartialEq, Clone, Copy)]
pub enum Stone {
    Flat,
    Standing,
    Capstone,
}

impl fmt::Display for Stone {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "{}",
            match self {
                Stone::Flat => "",
                Stone::Standing => "S",
                Stone::Capstone => "C",
            }
        )
    }
}

#[derive(Clone, Copy)]
pub enum Direction {
    Up,
    Down,
    Left,
    Right,
}

impl fmt::Display for Direction {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "{}",
            match self {
                Direction::Up => "+",
                Direction::Down => "-",
                Direction::Left => "<",
                Direction::Right => ">",
            }
        )
    }
}

pub enum Action {
    Place(Player, Position, Stone),
    Move(Position, Direction, u8, Vec<u8>),
}

impl fmt::Display for Action {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Action::Place(_, pos, stone) => write!(f, "{}{}", stone, pos),
            Action::Move(pos, direction, picked_up, drops) => {
                match (*picked_up > 1, drops.len() > 1) {
                    (true, true) => write!(
                        f,
                        "{}{}{}{}",
                        picked_up,
                        pos,
                        direction,
                        drops.into_iter().map(|q| q.to_string()).collect::<String>(),
                    ),
                    (true, false) => write!(f, "{}{}{}", picked_up, pos, direction),
                    // (false, true) should be impossible
                    _ => write!(f, "{}{}", pos, direction),
                }
            }
        }
    }
}

#[derive(Clone, Copy)]
pub struct Piece {
    pub player: Player,
    pub stone: Stone,
}

#[derive(Clone, Copy)]
pub enum WinType {
    RoadWin(Player),
    FlatWin(Player),
    Draw,
}

impl fmt::Display for WinType {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "{}",
            match self {
                WinType::RoadWin(Player::Black) => "0-R",
                WinType::RoadWin(Player::White) => "R-0",
                WinType::FlatWin(Player::Black) => "0-F",
                WinType::FlatWin(Player::White) => "F-0",
                WinType::Draw => "1/2-1/2",
            }
        )
    }
}

pub type Stack = Vec<Piece>;

struct GameState {
    size: u8,
    black_flats: u8,
    white_flats: u8,
    black_capstones: u8,
    white_capstones: u8,
    board: Vec<Stack>,
}

// TODO: Generate all legal actions for a given player

impl GameState {
    fn copy(&self) -> GameState {
        let mut copy = GameState {
            size: self.size,
            black_flats: self.black_flats,
            white_flats: self.white_flats,
            black_capstones: self.black_capstones,
            white_capstones: self.white_capstones,
            board: Vec::new(),
        };
        for i in 0..self.board.len() {
            copy.board.push(Vec::new());
            for j in 0..self.board[i].len() {
                copy.board[i].push(self.board[i][j]);
            }
        }
        copy
    }

    // Defaults to 5x5 if requested things are out of range
    fn new(size: u8) -> GameState {
        let (flats, caps) = match size {
            3 => (10, 0),
            4 => (15, 0),
            6 => (30, 1),
            7 => (40, 2),
            8 => (50, 2),
            _ => (21, 1),
        };
        GameState {
            size: size,
            black_flats: flats,
            white_flats: flats,
            black_capstones: caps,
            white_capstones: caps,
            board: {
                let mut v: Vec<Stack> = Vec::new();
                for _i in 0..size * size {
                    v.push(Vec::new());
                }
                v
            },
        }
    }

    fn remaining_pieces(&self, player: Player, stone: Stone) -> u8 {
        match player {
            Player::Black => {
                if stone == Stone::Capstone {
                    self.black_capstones
                } else {
                    self.black_flats
                }
            }
            Player::White => {
                if stone == Stone::Capstone {
                    self.white_capstones
                } else {
                    self.white_flats
                }
            }
        }
    }

    fn within_bounds(&self, pos: &Position) -> bool {
        if (pos.x < self.size) && (pos.y < self.size) {
            true
        } else {
            false
        }
    }

    fn pos_to_idx(&self, pos: &Position) -> usize {
        let y: usize = pos.y as usize;
        let x: usize = pos.x as usize;
        x + y * (self.size as usize)
    }

    fn query_pos(&self, pos: &Position) -> Option<&Stack> {
        self.board.get(self.pos_to_idx(pos))
    }

    fn is_legal_place(&self, player: Player, pos: &Position, stone: Stone) -> Result<(), String> {
        /* In order to legally place a piece:
        1. The desired square must be empty
        2. The player must have sufficient pieces
         */
        if self.within_bounds(pos) {
            if let Some(stack) = &self.board.get(self.pos_to_idx(pos)) {
                if stack.len() > 0 {
                    return Err(format!("{} is already occupied.", pos));
                } else if self.remaining_pieces(player, stone) == 0 {
                    return Err(format!(
                        "{} has no more remaining {} pieces.",
                        player, stone
                    ));
                } else {
                    return Ok(());
                }
            } else {
                return Err(format!(
                    "Internal error: lookup for {} failed in is_legal_place.",
                    pos
                ));
            }
        } else {
            return Err(format!("Position {} is not within bounds.", pos));
        }
    }

    fn place_stone(
        &self,
        player: Player,
        pos: &Position,
        stone: Stone,
    ) -> Result<(Vec<Position>, GameState), String> {
        self.is_legal_place(player, pos, stone)?;

        // Place stone
        let mut copy = self.copy();
        let idx = self.pos_to_idx(&pos);
        copy.board[idx].push(Piece {
            player: player,
            stone: stone,
        });

        // Decrease count
        match player {
            Player::Black => {
                if stone == Stone::Capstone {
                    copy.black_capstones -= 1;
                } else {
                    copy.black_flats -= 1;
                }
            }
            Player::White => {
                if stone == Stone::Capstone {
                    copy.white_capstones -= 1;
                } else {
                    copy.white_flats -= 1;
                }
            }
        }
        Ok((vec![pos.clone()], copy))
    }

    fn is_legal_move(
        &self,
        player: Player,
        pos: &Position,
        direction: Direction,
        picked_up: u8,
        drops: &Vec<u8>,
    ) -> Result<(), String> {
        if self.within_bounds(pos) {
            /* Rules for moving a stack:
            - There are stones
            - Drops have been specified
            - Must actually move at least one stone
            - Top stone belongs to player
            - One or more on each subsequent square
            - Total number of stones picked up does not exceed the carry capacity
            - Direction does not contain a capstone
            - Wall may only appear on last spot if it's capstone alone that covers
            - All stones are used up before then end of the board is met
             */
            if let Some(stack) = &self.board.get(self.pos_to_idx(pos)) {
                let stack_len = stack.len();
                let drops_len = drops.len();

                if stack_len == 0 {
                    return Err(format!("{} has no stones to move.", pos));
                };

                if drops_len == 0 {
                    return Err(String::from(
                        "A drop sequence for must be specified for a move.",
                    ));
                };

                if picked_up == 0 {
                    return Err(String::from(
                        "A valid move must change the position of at least a single stone.",
                    ));
                }

                if stack[stack_len - 1].player != player {
                    return Err(format!(
                        "{} may not move the stack at {} as it belongs to {}.",
                        player,
                        pos,
                        stack[stack_len - 1].player
                    ));
                };

                for i in 0..drops_len {
                    if drops[i] == 0 {
                        return Err(String::from(
                            "A move may not drop 0 stones on subsequent squares.",
                        ));
                    }
                }

                let picked_up = picked_up as usize;
                let sum_dropped = drops.iter().map(|&d| d as usize).sum::<usize>();
                if sum_dropped != picked_up {
                    return Err(format!(
                        "Move intended to pick up {} stones but drop {}.",
                        picked_up, sum_dropped
                    ));
                }

                let carry_capacity = self.size as usize;
                if picked_up > carry_capacity {
                    return Err(format!(
                        "A move may not pick up more than the carry capacity of {} stones.",
                        self.size
                    ));
                }

                let mut steps: usize = drops.len();
                let cap: bool = stack[0].stone == Stone::Capstone;
                let mut pos_new = Position { x: pos.x, y: pos.y };

                while steps > 0 {
                    if {
                        match direction {
                            Direction::Up => pos_new.y + 1 >= self.size,
                            Direction::Down => pos_new.y == 0,
                            Direction::Left => pos_new.x == 0,
                            Direction::Right => pos_new.x + 1 >= self.size,
                        }
                    } {
                        return Err(String::from("A move may not extend past the board."));
                    } else {
                        match direction {
                            Direction::Up => pos_new.y += 1,
                            Direction::Down => pos_new.y -= 1,
                            Direction::Left => pos_new.x -= 1,
                            Direction::Right => pos_new.x += 1,
                        }
                        if let Some(stack) = &self.board.get(self.pos_to_idx(&pos_new)) {
                            if stack.len() > 0 {
                                match stack[stack.len() - 1].stone {
                                    Stone::Capstone => {
                                        return Err(String::from(
                                            "A move may not cover a capstone.",
                                        ));
                                    }
                                    Stone::Standing => {
                                        if (steps > 1) || (!cap) {
                                            return Err(String::from(
                                                "A move may not cover a standing stone.",
                                            ));
                                        }
                                    }
                                    Stone::Flat => (),
                                }
                            }
                        } else {
                            return Err(format!(
                                "Internal error: lookup for {} failed in is_legal_move (1).",
                                pos_new
                            ));
                        }
                    }
                    steps -= 1;
                }
                return Ok(());
            } else {
                return Err(format!(
                    "Internal error: lookup for {} failed in is_legal_move (2).",
                    pos
                ));
            }
        } else {
            return Err(format!("Position {} is not within bounds.", pos));
        }
    }

    fn move_stack(
        &self,
        player: Player,
        pos: &Position,
        direction: Direction,
        picked_up: u8,
        drops: &Vec<u8>,
    ) -> Result<(Vec<Position>, GameState), String> {
        self.is_legal_move(player, pos, direction, picked_up, drops)?;

        let mut copy = self.copy();
        let mut pos_vec: Vec<Position> = vec![pos.clone()];

        let idx = copy.pos_to_idx(&pos);
        let stack: &Stack = &self.board[self.pos_to_idx(pos)];

        let stack_height = copy.board[idx].len();

        let mut offset = stack_height - (picked_up as usize);

        for _i in offset..stack_height {
            copy.board[idx].pop();
        }

        for drop_idx in 0..drops.len() {
            let new_pos = pos_vec[pos_vec.len() - 1];
            pos_vec.push(match direction {
                Direction::Up => Position {
                    x: new_pos.x,
                    y: new_pos.y + 1,
                },
                Direction::Down => Position {
                    x: new_pos.x,
                    y: new_pos.y - 1,
                },
                Direction::Left => Position {
                    x: new_pos.x - 1,
                    y: new_pos.y,
                },
                Direction::Right => Position {
                    x: new_pos.x + 1,
                    y: new_pos.y,
                },
            });

            let new_pos = pos_vec[pos_vec.len() - 1];
            let idx = copy.pos_to_idx(&new_pos);
            let num = drops[drop_idx] as usize;

            for i in 0..num {
                // Are we flattening?
                if stack[offset + i].stone == Stone::Capstone {
                    if let Some(top_piece) = copy.board[idx].last() {
                        if top_piece.stone == Stone::Standing {
                            let top_stone_idx = copy.board[idx].len() - 1;
                            copy.board[idx][top_stone_idx].stone = Stone::Flat;
                        }
                    }
                }
                copy.board[idx].push(stack[offset + i]);
            }
            offset += num;
        }
        Ok((pos_vec, copy))
    }

    // Either up or right
    fn dfs(&self, player: Player, up: bool, mut todo: Vec<Position>) -> bool {
        let mut seen: HashSet<Position> = HashSet::new();
        for i in 0..todo.len() {
            seen.insert(todo[i].clone());
        }
        loop {
            let more = todo.pop();
            if let Some(p) = more {
                if p.y + 1 < self.size {
                    let p_up = Position { x: p.x, y: p.y + 1 };
                    let i_up = self.pos_to_idx(&p_up);
                    if !seen.contains(&p_up) && self.within_bounds(&p_up) {
                        let l = self.board[i_up].len();
                        if l > 0 {
                            let piece = self.board[i_up][l - 1];
                            if (piece.player == player) && (piece.stone != Stone::Standing) {
                                if up && (p_up.y + 1 == self.size) {
                                    return true;
                                } else {
                                    seen.insert(p_up);
                                    todo.push(p_up);
                                }
                            }
                        }
                    }
                }

                if p.x + 1 < self.size {
                    let p_right = Position { x: p.x + 1, y: p.y };
                    let i_right = self.pos_to_idx(&p_right);
                    if !seen.contains(&p_right) && self.within_bounds(&p_right) {
                        let l = self.board[i_right].len();
                        if l > 0 {
                            let piece = self.board[i_right][l - 1];
                            if (piece.player == player) && (piece.stone != Stone::Standing) {
                                if !up && (p_right.x + 1 == self.size) {
                                    return true;
                                } else {
                                    seen.insert(p_right);
                                    todo.push(p_right);
                                }
                            }
                        }
                    }
                }

                if p.y > 0 {
                    let p_down = Position { x: p.x, y: p.y - 1 };
                    let i_down = self.pos_to_idx(&p_down);
                    if !seen.contains(&p_down) && self.within_bounds(&p_down) {
                        let l = self.board[i_down].len();
                        if l > 0 {
                            let piece = self.board[i_down][l - 1];
                            if (piece.player == player) && (piece.stone != Stone::Standing) {
                                seen.insert(p_down);
                                todo.push(p_down);
                            }
                        }
                    }
                }

                if p.x > 0 {
                    let p_left = Position { x: p.x - 1, y: p.y };
                    let i_left = self.pos_to_idx(&p_left);
                    if !seen.contains(&p_left) && self.within_bounds(&p_left) {
                        let l = self.board[i_left].len();
                        if l > 0 {
                            let piece = self.board[i_left][l - 1];
                            if (piece.player == player) && (piece.stone != Stone::Standing) {
                                seen.insert(p_left);
                                todo.push(p_left);
                            }
                        }
                    }
                }

                seen.insert(p);
            } else {
                break;
            }
        }
        return false;
    }

    fn check_road_win(&self) -> Option<WinType> {
        // Depth first search from bottom edge and left edge

        let mut todo_black_up: Vec<Position> = Vec::new();
        let mut todo_white_up: Vec<Position> = Vec::new();
        let mut todo_black_right: Vec<Position> = Vec::new();
        let mut todo_white_right: Vec<Position> = Vec::new();

        for i in 0..self.size {
            let pos_up = Position { x: i, y: 0 };
            let pos_right = Position { x: 0, y: i };
            let stack_up = &self.board[self.pos_to_idx(&pos_up)];
            let stack_right = &self.board[self.pos_to_idx(&pos_right)];

            if !stack_up.is_empty() {
                match stack_up[stack_up.len() - 1].player {
                    Player::Black => todo_black_up.push(pos_up),
                    Player::White => todo_white_up.push(pos_up),
                }
            }

            if !stack_right.is_empty() {
                match stack_right[stack_right.len() - 1].player {
                    Player::Black => todo_black_right.push(pos_right),
                    Player::White => todo_white_right.push(pos_right),
                }
            }
        }

        if self.dfs(Player::Black, true, todo_black_up)
            || self.dfs(Player::Black, false, todo_black_right)
        {
            return Some(WinType::RoadWin(Player::Black));
        }

        if self.dfs(Player::White, true, todo_white_up)
            || self.dfs(Player::White, false, todo_white_right)
        {
            return Some(WinType::RoadWin(Player::White));
        }

        return None;
    }

    fn check_flat_win(&self) -> Option<WinType> {
        let full_board = self.board.iter().all(|s| s.len() > 0);
        let finished_flats = (self.black_flats == 0) || (self.white_flats == 0);

        if full_board || finished_flats {
            let count = self.board.iter().fold(0, |c, s| match s.last() {
                None => c,
                Some(piece) => {
                    if piece.stone == Stone::Flat {
                        match piece.player {
                            Player::Black => c + 1,
                            Player::White => c - 1,
                        }
                    } else {
                        c
                    }
                }
            });
            // Trichotomy of reals ...
            if count > 0 {
                return Some(WinType::FlatWin(Player::Black));
            } else if count == 0 {
                return Some(WinType::Draw);
            } else {
                return Some(WinType::FlatWin(Player::White));
            }
        }
        return None;
    }

    // TODO: this does not handle the case dragon edge case
    fn check_win(&self) -> Option<WinType> {
        if let Some(w) = self.check_road_win() {
            return Some(w);
        } else {
            return self.check_flat_win();
        }
    }
}

enum TurnOrder {
    WhitePlacesBlack,
    BlackPlacesWhite,
    Normal,
}

pub struct Game {
    size: u8,
    current_player: Player,
    turn_order: TurnOrder,
    actions: Vec<Action>,
    states: Vec<GameState>,
    white_player_name: String,
    black_player_name: String,
    date_string: String,
    win_type: Option<WinType>,
}

impl Game {
    pub fn new(
        size: u8,
        white_player_name: &str,
        black_player_name: &str,
        date_str: &str,
    ) -> (Game, String) {
        let (size, warning) = if (size <= 3) || (size >= 8) {
            (5, format!("Warning: the requested game size of {}x{} is not supported, defaulting to 5x5.",
                    size, size))
        } else {
            (size, String::new())
        };

        (
            Game {
                size: size,
                states: vec![GameState::new(size)],
                actions: Vec::new(),
                current_player: Player::White,
                turn_order: TurnOrder::WhitePlacesBlack,
                white_player_name: white_player_name.to_string(),
                black_player_name: black_player_name.to_string(),
                date_string: date_str.to_string(),
                win_type: None,
            },
            warning,
        )
    }

    // Relying on only ::new(...) being used to make instances

    fn last_state(&self) -> &GameState {
        &self.states[self.states.len() - 1]
    }

    pub fn query_square(&self, pos: &Position) -> Option<&Stack> {
        self.last_state().query_pos(pos)
    }

    pub fn query_current_player_name(&self) -> &str {
        match self.current_player {
            Player::Black => &self.black_player_name,
            Player::White => &self.white_player_name,
        }
    }

    pub fn query_pieces(&self, player: Player, stone: Stone) -> u8 {
        self.last_state().remaining_pieces(player, stone)
    }

    pub fn query_current_player(&self) -> Player {
        self.current_player
    }

    pub fn query_stone_owner(&self) -> Player {
        match self.turn_order {
            TurnOrder::WhitePlacesBlack => Player::Black,
            TurnOrder::BlackPlacesWhite => Player::White,
            TurnOrder::Normal => self.current_player,
        }
    }

    pub fn get_size(&self) -> u8 {
        self.size
    }

    pub fn query_action_lines(&self) -> Vec<String> {
        let mut result = Vec::new();
        let mut newline = true;
        let num_actions = self.actions.len();
        if num_actions > 0 {
            let mut line = String::new();
            line += "1. ";
            for i in 0..num_actions {
                if i > 1 && newline {
                    // TODO: Is placing the opponent's first stone the zeroeth action?
                    line += &format!("{}. ", i / 2 + 1);
                }
                line += &format!("{}  ", self.actions[i].to_string());
                if i > 0 && !newline {
                    result.push(line);
                    line = String::new();
                }
                newline = !newline;
            }
            if !line.is_empty() {
                result.push(line);
            }
        }
        if self.win_type.is_some() {
            result.push(self.win_type.unwrap().to_string());
        }
        result
    }

    pub fn perform_action(
        &mut self,
        act: Action,
    ) -> Result<(Vec<Position>, Option<WinType>), String> {
        let maybe_state = self.states.last();
        if maybe_state.is_none() {
            return Err(String::from("Internal error: cannot find last game state"));
        }
        let state = maybe_state.unwrap();
        let new_state_either = match &act {
            Action::Place(player, pos, stone) => match self.turn_order {
                TurnOrder::WhitePlacesBlack => {
                    if (self.current_player == Player::White)
                        && (*player == Player::Black)
                        && (*stone == Stone::Flat)
                    {
                        state.place_stone(*player, pos, *stone)
                    } else {
                        Err(String::from(
                            "At the start of the game, W must place a B flat.",
                        ))
                    }
                }
                TurnOrder::BlackPlacesWhite => {
                    if (self.current_player == Player::Black)
                        && (*player == Player::White)
                        && (*stone == Stone::Flat)
                    {
                        state.place_stone(*player, pos, *stone)
                    } else {
                        Err(String::from(
                            "At the start of the game, B must place a W flat.",
                        ))
                    }
                }
                TurnOrder::Normal => state.place_stone(*player, pos, *stone),
            },
            Action::Move(pos, direction, picked_up, drops) => match self.turn_order {
                TurnOrder::Normal => {
                    state.move_stack(self.current_player, pos, *direction, *picked_up, drops)
                }
                _ => Err(String::from(
                    "At the start of the game only placing flats is allowed.",
                )),
            },
        };

        match new_state_either {
            Err(e) => return Err(e),
            Ok((pos_vec, new_state)) => {
                self.states.push(new_state);
                self.actions.push(act);
                self.current_player = match self.turn_order {
                    TurnOrder::WhitePlacesBlack => Player::Black,
                    TurnOrder::BlackPlacesWhite => Player::White,
                    TurnOrder::Normal => match self.current_player {
                        Player::Black => Player::White,
                        Player::White => Player::Black,
                    },
                };

                self.turn_order = match self.turn_order {
                    TurnOrder::WhitePlacesBlack => TurnOrder::BlackPlacesWhite,
                    TurnOrder::BlackPlacesWhite => TurnOrder::Normal,
                    TurnOrder::Normal => TurnOrder::Normal,
                };
                self.win_type = self.last_state().check_win();
                return Ok((pos_vec, self.win_type));
            }
        }
    }

    pub fn undo(&mut self) -> Result<Vec<Position>, String> {
        if self.actions.len() > 0 {
            self.actions.pop();
            self.states.pop();
            self.turn_order = match self.actions.len() {
                0 => TurnOrder::WhitePlacesBlack,
                1 => TurnOrder::BlackPlacesWhite,
                _ => TurnOrder::Normal,
            };
            self.current_player = match self.current_player {
                Player::Black => Player::White,
                Player::White => Player::Black,
            };
            // I'm too lazy to work out exactly which squares must be
            // redrawn when an action is undone
            let mut redraw_all: Vec<Position> = Vec::new();
            for x in 0..self.size {
                for y in 0..self.size {
                    redraw_all.push(Position { x, y });
                }
            }
            Ok(redraw_all)
        } else {
            Err(String::from("Cannot undo in an empty game!"))
        }
    }
}

impl fmt::Display for Game {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "[Date \"{}\"]\n[Player1 \"{}\"]\n[Player2 \"{}\"]\n[Size \"{}\"]\n{}",
            self.date_string,
            self.white_player_name,
            self.black_player_name,
            self.size,
            self.query_action_lines().join("\n"),
        )
    }
}