use crate::solver::Solver;
use crate::structs::GapHeights;

/// Solve for a given N and return the resulting wall
pub struct NormalSolver<T: num::PrimInt> {
    pub n: u32,
    /// calculated height [might not be correct!]
    pub h: u32,
    /// width
    pub w: u32,
    /// Use to store already used blocks as a bitmask
    solve_stack: Vec<SaveState<T>>,
    permutations: Vec<Vec<u32>>,
}

// used during row creation, will get deprecated
static mut COUNT: u32 = 0;
static mut TRIES: u32 = 0;
static mut SOLUTIONS: u32 = 0;

/// Save the current state for each row
#[derive(Clone, Copy)]
pub struct SaveState<T: num::PrimInt> {
    /// Mask of all currently used stones
    pub bitmask: T,
    /// sum of all placed stones
    pub sum: u32,
    /// the row index
    pub row: u32,
}

impl<T: num::PrimInt> SaveState<T> {
    pub fn new() -> Self {
        Self {
            bitmask: T::zero(),
            sum: 0,
            row: unsafe {
                COUNT += 1;
                COUNT
            },
        }
    }

    #[allow(dead_code)]
    pub fn set_bit(&mut self, stone: u32) {
        self.bitmask =
            self.bitmask | T::from(1 << stone).expect("Stone placing index out of bounds");
    }

    #[allow(dead_code)]
    pub fn get_bit(&self, stone: u32) -> T {
        self.bitmask & T::from(1 << stone).expect("Requested stone index out of bounds")
    }

    #[allow(dead_code)]
    pub fn bridges_gap(&self, gap: u32) -> bool {
        self.get_bit(gap - self.sum) == T::zero()
    }

    #[allow(dead_code)]
    pub fn bridge_gap(mut self, gap: u32) -> Self {
        self.set_bit(gap - self.sum);
        self.sum = gap;
        self
    }
}

impl<T: num::PrimInt> NormalSolver<T> {
    pub fn new(n: u32) -> Self {
        let h = n / 2 + 1;
        let w = h * (n - 1);
        let mut heap = (1..=n).collect::<Vec<u32>>();
        let heap = permutohedron::Heap::new(&mut heap);
        let n_f = permutohedron::factorial(n as usize);
        let mut permutations = Vec::with_capacity(n_f);
        println!("Generating permutations");
        for data in heap {
            permutations.push(data.clone());
        }
        Self {
            n,
            h,
            w,
            solve_stack: vec![SaveState::new(); h as usize],
            permutations,
        }
    }

    pub fn solve(&mut self) {
        //for (n, i) in self.permutations.iter().enumerate() {
        //    println!("perm {}: {:?}", n, i);
        //}
        println!("calculate results");
        self.permute(
            permutohedron::factorial(self.n as usize),
            0,
            ((0..self.h).collect::<Vec<u32>>()).as_ref(),
        );
        unsafe { println!("tries: {}\nsolutions: {}", TRIES, SOLUTIONS) }
    }

    fn permute(&mut self, up: usize, index: usize, numbers: &[u32]) {
        let chunk = self.permutations.len() / self.h as usize;
        if index as usize == numbers.len() {
            //println!("checking {:?}", numbers);
            if self.check_perm(&numbers) {
                println!("success");
            }
            return;
        }
        let mut new_num = Vec::from(numbers);
        for i in numbers[index as usize] as usize..((index + 1) * chunk) {
            for n in (index + 1)..numbers.len() {
                new_num[n] = (n * chunk) as u32;
            }
            self.permute(up, index + 1, &new_num);
            new_num[index] += 1;
        }
    }

    fn check_perm(&mut self, nums: &[u32]) -> bool {
        unsafe {
            TRIES += 1;
        }
        let mut sums = vec![self.w; self.w as usize];
        for (i, num) in nums.iter().enumerate() {
            let mut sum = 0;
            for n in self.permutations[*num as usize][..(self.n - 1 - (self.n & 1)) as usize].iter()
            {
                sum += *n as usize;
                if sums[sum - 1] != self.w {
                    return false;
                }
                sums[sum - 1] = i as u32;
            }
        }
        unsafe {
            SOLUTIONS += 1;
        }
        //println!("{:?}", sums);
        GapHeights::from_heights(sums.iter().map(|x| *x as u32).collect()).output(self.n, self.h);
        //.as_stone_wall(self.n)
        //.output();
        true
    }

    #[allow(dead_code)]
    fn check_gaps(&mut self, wall: &GapHeights) -> bool {
        for (i, r) in wall.iter().enumerate() {
            let stone = (i + 1) as u32 - self.solve_stack[r as usize].sum;
            self.solve_stack[r as usize].set_bit(stone);
        }
        for state in self.solve_stack.as_ref() as &[SaveState<T>] {
            if state.bitmask != T::from(1 << self.n).unwrap() {
                return false;
            }
        }
        true
    }
}