use actions::*;
use ships::*;
use state::*;
use math::*;

use std::collections::HashMap;
use std::cmp::Ordering;

#[derive(Serialize, Deserialize, Clone, Debug)]
pub struct Knowledge {
    pub last_action: Action,
    pub opponent_map: OpponentMapKnowledge,
    pub map_size: u16,
    pub available_weapons: Vec<Weapon>,
    pub shootable_weapons: Vec<Weapon>,
    pub charging_weapons: HashMap<Weapon, u16>
}

impl Knowledge {
    pub fn new(map_size: u16, action: Action) -> Knowledge {
        Knowledge {
            last_action: action,
            opponent_map: OpponentMapKnowledge::new(map_size),
            map_size: map_size,
            available_weapons: Vec::new(),
            shootable_weapons: Vec::new(),
            charging_weapons: HashMap::new()
        }
    }

    pub fn with_action(&self, action: Action) -> Knowledge {
        Knowledge {
            last_action: action,
            ..self.clone()
        }
    }

    pub fn resolve_last_action(&self, state: &State) -> Knowledge {
        let mut new_knowledge = self.clone();

        let energy = state.player_map.energy;
        let mut available_weapons: Vec<_> = state.player_map.ships.iter()
            .filter(|&(_, ship_data)| !ship_data.destroyed)
            .flat_map(|(ship, _)| ship.weapons())
            .collect();
        
        available_weapons.sort_by_key(|weapon| format!("{}",weapon));
        available_weapons.dedup();
        new_knowledge.available_weapons = available_weapons;
        
        new_knowledge.shootable_weapons = new_knowledge.available_weapons.iter()
            .filter(|weapon| weapon.energy_cost(state.map_size) <= energy)
            .cloned()
            .collect();
        
        new_knowledge.charging_weapons = new_knowledge.available_weapons.iter()
            .filter(|weapon| weapon.energy_cost(state.map_size) > energy)
            .map(|weapon| (weapon.clone(), weapon.single_shot_rounds_to_ready(energy, state.map_size)))
            .collect();
            
        let (hits, misses, _) = match self.last_action {
            Action::PlaceShips(_) => {
                (vec!(), vec!(), vec!())
            },
            Action::Shoot(Weapon::SeekerMissle, p) => {
                Knowledge::seeker_hits_and_misses(p, &state)
            }
            
            Action::Shoot(w, p) => {
                Knowledge::to_hits_and_misses(w.affected_cells(p, state.map_size), &state)
            }
        };
        
        let sunk_ships = new_knowledge.opponent_map.update_sunk_ships(&state);
        
        new_knowledge.opponent_map.update_from_shot(hits, misses, sunk_ships);
        
        new_knowledge
    }

    fn to_hits_and_misses(points: Vec<Point>, state: &State) -> (Vec<Point>, Vec<Point>, Vec<Point>) {
        let hits = points.iter().filter(|p| state.opponent_map.cells[p.x as usize][p.y as usize].damaged).cloned().collect();
        let misses = points.iter().filter(|p| state.opponent_map.cells[p.x as usize][p.y as usize].missed).cloned().collect();
        let unknown = points.iter().filter(|p| !state.opponent_map.cells[p.x as usize][p.y as usize].missed && !state.opponent_map.cells[p.x as usize][p.y as usize].damaged).cloned().collect();

        (hits, misses, unknown)
    }

    fn seeker_hits_and_misses(p: Point, state: &State) -> (Vec<Point>, Vec<Point>, Vec<Point>) {
        let mut misses: Vec<Point> = Vec::new();
        let mut hits: Vec<Point> = Vec::new();

        let rings = vec!(
            vec!(
                //0
                Some(p)
            ),
            vec!(
                //1
                p.move_point(Direction::North, 1, state.map_size),
                p.move_point(Direction::East, 1, state.map_size),
                p.move_point(Direction::South, 1, state.map_size),
                p.move_point(Direction::West, 1, state.map_size),
            ),
            vec!(
                //1.44
                p.move_point(Direction::NorthEast, 1, state.map_size),
                p.move_point(Direction::SouthEast, 1, state.map_size),
                p.move_point(Direction::NorthWest, 1, state.map_size),
                p.move_point(Direction::SouthWest, 1, state.map_size)
            ),
            vec!(
                //2
                p.move_point(Direction::North, 2, state.map_size),
                p.move_point(Direction::East, 2, state.map_size),
                p.move_point(Direction::South, 2, state.map_size),
                p.move_point(Direction::West, 2, state.map_size),
            )
        );

        //start in the center. Add rings, until I find a hit
        //don't add more after a hit is found
        for ring in rings {
            if hits.is_empty() {
                let (mut new_hits, mut new_misses, mut unknown) = Knowledge::to_hits_and_misses(ring.iter().filter_map(|&p| p).collect::<Vec<_>>(), &state);
                misses.append(&mut new_misses);
                if !new_hits.is_empty() {
                    hits.append(&mut new_hits);
                } else {
                    misses.append(&mut unknown);
                }
            }
        }
        
        (hits, misses, vec!())
    }

    pub fn has_unknown_hits(&self) -> bool {
        self.opponent_map.cells.iter().fold(false, |acc, x| {
            x.iter().fold(acc, |acc, y| acc || y.unknown_hit())
        })
    }

    pub fn get_best_adjacent_shots(&self) -> Vec<Point> {
        let unknown_hits = self.opponent_map.cells_with_unknown_hits();
        let adjacent_cells = self.opponent_map.adjacent_unshot_cells(&unknown_hits);
      
        let possible_placements = self.opponent_map.possible_placements();

        let mut max_score = 1;
        let mut best_cells = Vec::new();
            
        for placement in possible_placements {
            for &cell in &adjacent_cells {
                let score = placement.count_hit_cells(cell, &unknown_hits);
                if score > max_score {
                    max_score = score;
                    best_cells = vec!(cell);
                }
                else if score == max_score {
                    best_cells.push(cell);
                }
            }
        }

        best_cells
    }

    pub fn get_best_seek_shots(&self) -> (Weapon, Vec<Point>) {
        let possible_placements = self.opponent_map.possible_placements();
        // let lattice = self.lattice_size(); //TODO use the lattice still?

        let guaranteed_hits = self.get_points_that_touch_all_possibilities_on_unsunk_ship();
        if !guaranteed_hits.is_empty() {
            return (Weapon::SingleShot, guaranteed_hits);
        }

        let mut best_shots: HashMap<Weapon, (Vec<Point>, usize)> = HashMap::new();
        
        for &weapon in self.available_weapons.iter() {
            let mut current_best_score = 1;
            let mut best_cells = Vec::new();

            for target in self.opponent_map.flat_cell_position_list() {
                let cells = if weapon == Weapon::SeekerMissle {
                    let full_range = weapon.affected_cells(target, self.map_size);
                    let has_hits = full_range.iter().any(|p| self.opponent_map.cells[p.x as usize][p.y as usize].hit);
                    if has_hits {
                        vec!()
                    }
                    else {
                        full_range
                    }
                }
                else {
                    weapon.affected_cells(target, self.map_size)
                        .iter()
                        .filter(|p| !self.opponent_map.cells[p.x as usize][p.y as usize].hit)
                        .cloned()
                        .collect()
                };
                
                let possibilities = possible_placements.iter()
                    .filter(|placement| placement.touches_any_point(&cells))
                    .count();
                
                if possibilities > current_best_score {
                    current_best_score = possibilities;
                    best_cells = vec!(target);
                }
                else if possibilities == current_best_score {
                    best_cells.push(target);
                }
            }

            best_shots.insert(weapon, (best_cells, current_best_score));
        }

        let best_single: Option<(Weapon, (Vec<Point>, usize))> =
            best_shots.get(&Weapon::SingleShot).map(|x| (Weapon::SingleShot, x.clone()));
        
        let best: (Weapon, (Vec<Point>, usize)) =
            best_shots.iter()
            .max_by(|&(weapon_a, &(_, score_a)), &(weapon_b, &(_, score_b))| {
                let score = score_a.cmp(&score_b);
                let cost = weapon_a.energy_cost(self.map_size).cmp(&weapon_b.energy_cost(self.map_size));
                if score == Ordering::Equal { cost } else { score }
            })
            .and_then(|(&weapon, x)| {
                if self.shootable_weapons.contains(&weapon) {
                    Some((weapon, x.clone()))
                } else {
                    best_single
                }
            })
            .unwrap_or((Weapon::SingleShot, (vec!(), 0)));

        
        (best.0.clone(), (best.1).0)
    }

    fn get_points_that_touch_all_possibilities_on_unsunk_ship(&self) -> Vec<Point> {
        self.opponent_map.flat_cell_position_list().iter().cloned().filter(|&point| {
            self.opponent_map.ships.values()
                .any(|ref ship| !ship.destroyed &&
                     ship.possible_placements.iter().all(|placement| {
                         placement.touches_point(point)
                     }))
        }).collect()
    }

    fn lattice_size(&self) -> u16 {
        let any_long_ships = self.opponent_map.ships.iter()
            .any(|(ship, knowledge)| ship.length() >= 4 && !knowledge.destroyed);
        if any_long_ships {
            4
        }
        else {
            2
        }
    }
}

#[derive(Serialize, Deserialize, Clone, Debug)]
pub struct OpponentMapKnowledge {
    pub ships: HashMap<Ship, OpponentShipKnowledge>,
    pub cells: Vec<Vec<KnowledgeCell>>
}

impl OpponentMapKnowledge {
    fn new(map_size: u16) -> OpponentMapKnowledge {
        let mut cells = Vec::with_capacity(map_size as usize);
        for x in 0..map_size {
            cells.push(Vec::with_capacity(map_size as usize));
            for y in 0..map_size {
                cells[x as usize].push(KnowledgeCell::new(x, y));
            }
        }

        let ships = Ship::all_types().iter()
            .map(|s| (s.clone(), OpponentShipKnowledge::new(s.clone(), map_size)))
            .collect::<HashMap<_, _>>();
            
        OpponentMapKnowledge {
            ships: ships,
            cells: cells
        }
    }

    fn update_sunk_ships(&mut self, state: &State) -> Vec<Ship> {
        let sunk_ships = self.ships.iter()
            .filter(|&(_, x)| !x.destroyed)
            .filter(|&(s, _)| state.opponent_map.ships.get(s).map(|x| x.destroyed) == Some(true))
            .map(|(s, _)| s.clone())
            .collect();

        for &ship in &sunk_ships {
            self.ships.get_mut(&ship).map(|ref mut ship_knowledge| ship_knowledge.destroyed = true);
        }

        sunk_ships
    }
    
    fn update_from_shot(&mut self, hit_cells: Vec<Point>, missed_cells: Vec<Point>, sunk_ships: Vec<Ship>) {
        for &missed in &missed_cells {
            self.cells[missed.x as usize][missed.y as usize].missed = true;
        }
        for &hit in &hit_cells {
            self.cells[hit.x as usize][hit.y as usize].hit = true;
        }

        self.clear_sunk_ship_impossible_placements(&sunk_ships, &hit_cells);

        let mut more_changes = true;
        while more_changes {
            more_changes = self.derive_ship_positions() || self.clear_impossible_placements();
        }
    }

    fn derive_ship_positions(&mut self) -> bool {
        let mut any_changes = false;
        for knowledge in self.ships.values() {
            if knowledge.possible_placements.len() == 1 {
                let ref true_placement = knowledge.possible_placements[0];
                for p in true_placement.points_on_ship() {
                    if self.cells[p.x as usize][p.y as usize].known_ship == None {
                        self.cells[p.x as usize][p.y as usize].known_ship = Some(true_placement.ship);
                        any_changes = true;
                    }
                }
            }
        }
        any_changes
    }

    fn clear_impossible_placements(&mut self) -> bool {
        let mut any_changes = false;
        let ref cells = self.cells;
        for knowledge in self.ships.values_mut() {
            let before = knowledge.possible_placements.len();
            knowledge.possible_placements.retain(|x| x.all_could_be_hits(&cells));
            let after = knowledge.possible_placements.len();
            if before != after {
                any_changes = true;
            }
        }
        any_changes
    }

    fn clear_sunk_ship_impossible_placements(&mut self, sunk_ships: &Vec<Ship>, must_touch_any: &Vec<Point>) {
        let cells_copy = self.cells.clone();
        
        for knowledge in self.ships.values_mut() {
            knowledge.possible_placements.retain(|x| !sunk_ships.contains(&x.ship) || (x.touches_any_point(&must_touch_any) && x.all_are_hits(&cells_copy)));
        }
    }

    fn cells_with_unknown_hits(&self) -> Vec<Point> {
        self.cells.iter().flat_map(|x| {
            x.iter().filter(|y| y.unknown_hit()).map(|y| y.position)
        }).collect()
    }

    fn adjacent_unshot_cells(&self, cells: &Vec<Point>) -> Vec<Point> {
        self.cells.iter().flat_map(|x| {
            x.iter()
                .filter(|y| !y.shot_attempted())
                .map(|y| y.position)
                .filter(|&y| cells.iter().any(|z| z.is_adjacent(y)))
        }).collect()
    }

    fn flat_cell_position_list(&self) -> Vec<Point> {
        self.cells.iter().flat_map(|x| {
            x.iter().map(|y| y.position)
        }).collect()
    }

    fn cells_on_lattice(&self, lattice_size: u16) -> Vec<Point> {
        self.cells.iter().flat_map(|x| {
            x.iter()
                .filter(|y| !y.shot_attempted() && y.position.is_on_lattice(lattice_size))
                .map(|y| y.position)
        }).collect()
    }

    fn possible_placements(&self) -> Vec<PossibleShipPlacement> {
        self.ships
            .values()
            .flat_map(|knowledge| knowledge.possible_placements.clone())
            .collect()
    }
}

#[derive(Serialize, Deserialize, Clone, Debug)]
pub struct OpponentShipKnowledge {
    pub ship: Ship,
    pub destroyed: bool,
    pub possible_placements: Vec<PossibleShipPlacement>
}

impl OpponentShipKnowledge {
    fn new(ship: Ship, map_size: u16) -> OpponentShipKnowledge {
        OpponentShipKnowledge {
            ship: ship,
            destroyed: false,
            possible_placements: PossibleShipPlacement::enumerate(ship, map_size)
        }
    }
}

#[derive(Serialize, Deserialize, Clone, Debug)]
pub struct PossibleShipPlacement {
    pub ship: Ship,
    pub direction: Direction,
    pub position: Point
}

impl PossibleShipPlacement {
    fn enumerate(ship: Ship, map_size: u16) -> Vec<PossibleShipPlacement> {
        (0..(map_size-ship.length()+1)).flat_map(move |par| {
            (0..map_size).flat_map(move |per| {
                vec!(
                    PossibleShipPlacement {
                        ship: ship,
                        direction: Direction::East,
                        position: Point::new(par, per)
                    },
                    PossibleShipPlacement {
                        ship: ship,
                        direction: Direction::North,
                        position: Point::new(per, par)
                    }
                )
            })
        }).collect()
    }

    pub fn touches_point(&self, p: Point) -> bool {
        p.check_for_ship_collision(self.position, self.direction, self.ship.length())
    }
    pub fn touches_any_point(&self, ps: &Vec<Point>) -> bool {
        ps.iter().any(|&p| self.touches_point(p))
    }

    pub fn points_on_ship(&self) -> Vec<Point> {
        (0..self.ship.length() as i32).map(|i| {
            self.position.move_point_no_bounds_check(self.direction, i)
        }).collect()
    }

    fn all_are_hits(&self, cells: &Vec<Vec<KnowledgeCell>>) -> bool {
        self.points_on_ship()
            .iter()
            .fold(true, |acc, p| acc && cells[p.x as usize][p.y as usize].hit)
    }

    fn all_could_be_hits(&self, cells: &Vec<Vec<KnowledgeCell>>) -> bool {
        self.points_on_ship()
            .iter()
            .all(|p| {
                let ref cell = cells[p.x as usize][p.y as usize];
                !cell.missed && cell.known_ship.map(|ship| ship == self.ship).unwrap_or(true)
            })
    }

    fn count_hit_cells(&self, required: Point, wanted: &Vec<Point>) -> u16 {
        if !self.touches_point(required) {
            return 0;
        }

        wanted.iter().filter(|&&x| self.touches_point(x)).count() as u16
    }
}

#[derive(Serialize, Deserialize, Clone, Debug)]
pub struct KnowledgeCell {
    pub missed: bool,
    pub hit: bool,
    pub known_ship: Option<Ship>,
    pub position: Point
}

impl KnowledgeCell {
    fn new(x: u16, y: u16) -> KnowledgeCell {
        KnowledgeCell {
            missed: false,
            hit: false,
            position: Point::new(x, y),
            known_ship: None
        }
    }

    pub fn shot_attempted(&self) -> bool {
        self.missed || self.hit
    }

    pub fn unknown_hit(&self) -> bool {
        self.hit && self.known_ship.is_none()
    }

}