use super::{Solver, FirstSolver};

#[derive(Clone, Debug)]
struct Row {
    n: u32,
    b: u32,
    palette: Vec<bool>,
    max_stone: u32,
    width: u32,
    stones: Vec<u32>,
    max_reachable: u32,
}

impl Row {
    fn new(n: u32, b: u32) -> Row {
        Self {
            n,
            b,
            palette: vec![true; n as usize],
            max_stone: n,
            width: 0,
            stones: Vec::with_capacity(n as usize),
            max_reachable: n,
        }
    }

    fn with_stone(n: u32, b: u32, s: u32) -> Row {
        let mut stones = Vec::with_capacity(n as usize);
        stones.push(s);
        let max_stone = n - if s == n { 1 } else { 0 };
        Self {
            n,
            b,
            palette: (1..=n).map(|i| i != s).collect(),
            max_stone,
            width: s,
            stones,
            max_reachable: s + max_stone,
        }
    }

    fn update(&mut self, x: u32) -> Option<u32> {
        let stone_len = x - self.width;
        if stone_len > self.n || !self.palette[(stone_len - 1) as usize] {
            return None;
        }
        self.width = x;
        self.palette[(stone_len - 1) as usize] = false;
        self.stones.push(stone_len);
        if self.max_stone == stone_len {
            while !self.palette[(self.max_stone - 1) as usize] {
                self.max_stone -= 1;
            }
            self.max_reachable = x + self.max_stone
        } else {
            self.max_reachable += stone_len
        }
        Some(stone_len)
    }

    fn undo_update(&mut self) {
        let stone_len = self.stones.pop().unwrap();
        self.width -= stone_len;
        self.palette[(stone_len - 1) as usize] = true;
        if stone_len > self.max_stone {
            self.max_stone = stone_len;
            self.max_reachable = self.width + stone_len
        } else {
            self.max_reachable -= stone_len
        }
    }

    fn complete(&mut self) {
        self.stones.push(self.b - self.width);
    }

    fn output_repeat(&self) {
        for (i, &stone) in self.stones.iter().enumerate() {
            for _ in 0..stone {
                print!("{}", ['-', '*'][i & 1]);
            }
        }
        println!();
    }

    fn output_numbers(&self) {
        for stone in self.stones.iter() {
            print!("{:2} ", stone);
        }
        println!();
    }
}

#[derive(Clone, Debug)]
pub struct BwinfSolver {
    n: u32,
    h: u32,
    b: u32,
    rows: Vec<Row>,
    x: u32,
    min_max_reachable: u32,
    max_reached: u32,
    steps: u64,
    stone_counts: Vec<u64>,
}

impl Solver for BwinfSolver {
    fn new(n: u32) -> Self {
        let (h, b) = ((n >> 1) + 1, (n * n + n ) >> 1);
        Self {
            n,
            h,
            b,
            rows: vec![Row::new(n, b); h as usize],
            x: 1,
            min_max_reachable: n,
            max_reached: 0,
            steps: 0,
            stone_counts: vec![0; n as usize]
        }
    }

    fn n(&self) -> u32 {
        self.n
    }

    fn h(&self) -> u32 {
        self.h
    }

    fn w(&self) -> u32 {
        self.b
    }
}

impl BwinfSolver {
    pub fn solve(&mut self) {
        self.solve_recursive();
    }

    fn new_linear(n: u32) -> Self {
        let (h, b) = ((n >> 1) + 1, (n * n + n) >> 1);
        let rows = (1..=h).map(|i| Row::with_stone(n, b, i)).collect();
        let x = h + 1;
        let mut stone_counts = vec![1; h as usize];
        stone_counts.append(&mut vec![0; (n - h) as usize]);
        Self {
            n,
            h,
            b,
            rows,
            x,
            min_max_reachable: 1 + n,
            max_reached: n,
            steps: 0,
            stone_counts
        }
    }

    fn complete(&mut self) {
        for row in self.rows.iter_mut() {
            row.complete()
        }
    }

    fn order_key(&self, index: u32) -> (u64, usize, i32) {
        let row = self.rows.get(index as usize).unwrap();
        (self.stone_counts[(self.x - row.width - 1) as usize] as u64,
         row.stones.len() as usize,
         -(row.width as i32))
    }

    fn order(&self) -> Vec<u32> {
        //(0..self.h).collect()
        let mut v: Vec<u32> = (0..self.h).collect();
        v.sort_unstable_by_key(|&row| self.order_key(row));
        v
    }

    fn solve_recursive(&mut self) -> bool {
        self.steps += 1;
        // complete if already nearly complete
        if self.x == self.b {
            self.complete();
            return true;
        }
        let mut row_empty = false;
        let min_max_reachable = self.min_max_reachable;
        for row_index in self.order() {
            if self.rows[row_index as usize].stones.is_empty() {
                if row_empty {
                    break;
                }
                row_empty = true;
            }
            let max_reachable = self.rows[row_index as usize].max_reachable;
            if let Some(stone) = self.rows[row_index as usize].update(self.x) {
                self.stone_counts[stone as usize - 1] += 1;
                if max_reachable == self.min_max_reachable {
                    self.min_max_reachable =
                        self.rows.iter().map(|v| v.max_reachable).min().unwrap();
                }
                if self.min_max_reachable > self.x {
                    self.x += 1;
                    if self.solve_recursive() {
                        return true;
                    }
                    self.x -= 1;
                }
                self.min_max_reachable = min_max_reachable;
                self.rows[row_index as usize].undo_update();
                self.stone_counts[stone as usize - 1] -= 1;
            }
        }
        false
    }

    pub fn output(&self) {
        for row in self.rows.iter() {
            row.output_numbers();
        }
    }

    pub fn get_steps(&self) -> u64 {
        self.steps
    }
}