use std::mem::swap;
use std::collections::VecDeque;

#[derive(PartialEq, Clone)]
struct Board {
    arr: Vec<Vec<u32>>,
    zero: (usize, usize),
}

impl Board {
    fn find_zero(board: &Vec<Vec<u32>>) -> (usize, usize) {
        for i in 0..board.len() {
            for j in 0..board[i].len() {
                if board[i][j] == 0 {
                    return (i, j);
                }
            }
        }
        panic!("Couldn't find a zero inside {:?}", board);
    }

    fn new(board: Vec<Vec<u32>>) -> Board {
        Board {
            zero: Self::find_zero(&board),
            arr: board,
        }
    }

    fn can_move_zero(&self, direction: u32) -> bool {
        match direction {
            0 => self.zero.1 > 0,
            1 => self.zero.1 < self.arr[self.zero.0].len() - 1,
            2 => self.zero.0 > 0,
            3 => self.zero.0 < self.arr.len() - 1,
            _ => panic!("Unknown direction {}", direction),
        }
    }

    fn dir_to_str(direction: u32) -> String {
        match direction {
            0 => "left".to_string(),
            1 => "right".to_string(),
            2 => "up".to_string(),
            3 => "down".to_string(),
            _ => panic!("Unknown direction {}", direction),
        }
    }

    fn move_zero(&mut self, direction: u32) {
        match direction {
            0 => {
                let (left, right) = self.arr[self.zero.0].split_at_mut(self.zero.1);
                swap(&mut left[self.zero.1 - 1], &mut right[0]);
                self.zero.1 -= 1;
            },
            1 => {
                let (left, right) = self.arr[self.zero.0].split_at_mut(self.zero.1 + 1);
                swap(&mut left[self.zero.1 - 1], &mut right[0]);
                self.zero.1 += 1;
            },
            2 => {
                let (top, bottom) = self.arr.split_at_mut(self.zero.0);
                swap(&mut top[self.zero.0 - 1][self.zero.1], &mut bottom[0][self.zero.1]);
                self.zero.0 -= 1;
            },
            3 => {
                let (top, bottom) = self.arr.split_at_mut(self.zero.0 + 1);
                swap(&mut top[self.zero.0 - 1][self.zero.1], &mut bottom[0][self.zero.1]);
                self.zero.0 += 1;
            },
            _ => panic!("Unknown direction {}", direction),
        }
    }
}

#[derive(Clone)]
struct GraphNode {
    board: Board,
    adj: Vec<GraphNode>,
    dist: u32,
    path: Vec<String>,
}

impl PartialEq for GraphNode {
    fn eq(&self, other: &Self) -> bool {
        self.board == other.board
    }
}
impl Eq for GraphNode {}

impl GraphNode {
    fn new(board: Vec<Vec<u32>>, dist: u32, path: Vec<String>) -> GraphNode {
        GraphNode {
            board: Board::new(board),
            adj: Vec::new(),
            dist: dist,
            path: path
        }
    }
}

pub struct Graph {
    root: GraphNode,
}

impl Graph {
    pub fn new(root_board: Vec<Vec<u32>>, goal: u32) -> Graph {
        let mut G = Graph { root: GraphNode::new(root_board, 0, Vec::new()) };
        let mut queue: VecDeque<&mut GraphNode> = VecDeque::new();
        queue.push_back(&mut G.root);

        let mut all_nodes: Vec<&GraphNode> = Vec::new();

        while !queue.is_empty() {
            let curr: &mut GraphNode = queue.pop_front().unwrap();
            for direction in 0..4 {
                if ! curr.board.can_move_zero(direction) { continue; }

                let mut newnode: GraphNode = curr.clone().to_owned();
                newnode.board.move_zero(direction);
                newnode.path.push(Board::dir_to_str(direction));
                // TODO: update distance

                if all_nodes.iter().any(|&x| *x == newnode) { continue; }
                curr.adj.push(newnode);

                queue.push_back(curr.adj.last_mut().unwrap());
                // all_nodes.push(curr.adj.last().unwrap());
            }
        }

        G
    }
}