use std::ops;
use std::collections::{HashMap, HashSet};
use std::hash::Hash;
use rand::{Rng, thread_rng};

/// Our indices here are two 32-bit signed values.
type Index = (i32, i32);
/// A `SparseBoard` here is a board that may or may not have every
/// tile filled in, which we represent as a hashmap from indices to
/// cells. When we use a `SparseBoard` as the LHS of a rule, we try to
/// match every cell provided, but don't bother matching the cells
/// which aren't provided; when we use one as the RHS of a rule, we
/// instead overwrite only those cells provided in the board.
///
/// A `SparseBoard` has a conceptual center, which is the cell at
/// index `(0, 0)`. Indices in a `SparseBoard` can be negative.
type SparseBoard<Cell> = HashMap<Index, Cell>;

/// The most important parts of a `Rule` are its LHS and its
/// RHS. These correspond respectively to the patterns which are
/// matched, and the cells that are used to replace those
/// patterns. Note that both of these are sparse boards: a pattern may
/// be an arbitrary shape, and its replacement may replace all, some,
/// or none of the cells matched by the LHS.
pub struct Rule<Cell> {
    pub rule_name: Option<String>,
    pub requires: HashSet<Cell>,
    pub lhs: SparseBoard<Cell>,
    pub rhs: SparseBoard<Cell>,
}

pub struct Board<Cell> {
    pub width: u32,
    pub height: u32,
    pub cells: Vec<Cell>,
    pub contents: HashSet<Cell>,
}

impl<Cell: Clone + Hash + Eq> Board<Cell> {
    pub fn new(width: u32, height: u32, default: Cell) -> Board<Cell> {
        let cells = (0..width*height).map(|_| default.clone()).collect();
        let contents = vec![default].into_iter().collect();
        Board { width, height, cells, contents }
    }

    pub fn get<'a>(&'a self, (w, h): Index) -> Option<&'a Cell> {
        if w > 0 && w < self.width as i32 && h > 0 && h < self.height as i32 {
            Some(&self[(w, h)])
        } else {
            None
        }
    }

    pub fn indices(&self) -> Vec<Index> {
        let mut v = Vec::new();
        for x in 0..self.width {
            for y in 0..self.height {
                v.push((x as i32, y as i32))
            }
        }
        v
    }

    pub fn random_indices(&self) -> Vec<Index> {
        let mut v = self.indices();
        {
            let slice = v.as_mut_slice();
            thread_rng().shuffle(slice);
        }
        v
    }
}

impl Board<char> {
    pub fn print(&self) {
        for x in 0..self.width {
            for y in 0..self.height {
                print!("{} ", self[(x as i32, y as i32)]);
            }
            println!("");
        }
    }
}

impl<Cell> ops::Index<Index> for Board<Cell> {
    type Output = Cell;

    fn index(&self, (w, h): Index) -> &Cell {
        let n: usize = (w + (h * self.width as i32)) as usize;
        &self.cells[n as usize]
    }
}

impl<Cell> ops::IndexMut<Index> for Board<Cell> {
    fn index_mut(&mut self, (w, h): Index) -> &mut Cell {
        let n: usize = (w + (h * self.width as i32)) as usize;
        &mut self.cells[n as usize]
    }
}

impl<Cell: Clone + Hash + Eq> Rule<Cell> {
    /// Create a new `Rule` from two sparse grids of cells,
    /// corresponding respectively to the LHS and the RHS
    pub fn new(
        lhs: SparseBoard<Cell>,
        rhs: SparseBoard<Cell>,
    ) -> Rule<Cell> {
        let rule_name = None;
        let requires = lhs.values().cloned().collect();
        Rule { rule_name, requires, lhs, rhs }
    }

    /// Get mutable access to the LHS of the `Rule`, for modification
    /// later
    pub fn lhs_mut(&mut self) -> &mut SparseBoard<Cell> {
        &mut self.lhs
    }

    /// Get mutable access to the RHS of the `Rule`, for modification
    /// later
    pub fn rhs_mut(&mut self) -> &mut SparseBoard<Cell> {
        &mut self.lhs
    }

    /// Attempt to apply this rule to the provided board at random
    /// (i.e. if there are multiple possible applications of this
    /// rule, then it should choose one of them entirely at random
    pub fn apply_to_board(&self, b: &mut Board<Cell>) -> bool {
        // for each random location in the board
        'outer: for (x, y) in b.random_indices() {
            // find out whether each of our tiles matche
            for (&(i, j), v) in self.lhs.iter() {
                // if a given tile doesn't, then skip ahead
                match b.get((x + i, y + j)) {
                    Some(r) if v == r => (),
                    _ => continue 'outer,
                }
            }

            // if all of them match, then do the rewrites!
            for (&(i, j), r) in self.rhs.iter() {
                b[(x + i, y + j)] = r.clone();
            }

            // and because the rule applied, we can quit now
            return true;
        }
        // if we've tried them all and none of them worked, then we've
        // failed
        false
    }
}


#[cfg(test)]
#[test]
pub fn grammar_test() {
    let rule1: Rule<char> = Rule::new(
        vec![ ((0, 0), 'x') ].into_iter().collect(),
        vec![ ((0, 0), 'y'), ((1, 0), 'y') ].into_iter().collect(),
    );
    let rule2: Rule<char> = Rule::new(
        vec![ ((0, 0), 'y') ].into_iter().collect(),
        vec![ ((0, 0), 'z') ].into_iter().collect(),
    );
    let mut board = Board::new(8, 8, '.');
    board[(2, 2)] = 'x';
    assert!(true, rule1.apply_to_board(&mut board));
    assert!(true, rule2.apply_to_board(&mut board));
    board.print();
}