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, n: u32) -> bool {
        if gap - self.sum > n {
            //println!("{}", gap - self.sum);
            return false;
        }
        self.get_bit(gap - self.sum) == T::zero()
    }

    #[allow(dead_code)]
    pub unsafe 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());
        }
        /*use permutohedron::LexicalPermutation;
        loop {
            permutations.push(heap.to_vec());
            if !heap.next_permutation() {
                break;
            }
        }*/

        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() {
            let tmp: Vec<u32> = i.iter().map(|x| *x).collect();
            //println!("perm {}: {:?}", n, tmp);
        }
        //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() - 2 {
            let mut new_num = Vec::from(numbers);
            if self.n == 6 {
                new_num[2] = 675;
            }
            if self.n == 8 {
                //new_num[3] = 38728;
                new_num[3] = 36719;
            }

            if self.check_perm(&new_num[..(new_num.len() - 1)]) {
                for i in new_num {
                    println!("{}\t{}", numbers[0], i);
                }
            }
            return;
        }
        if index as usize == numbers.len() {
            //println!("checking {:?}", numbers);
            if self.check_perm(&numbers) {
                //println!("success");
                for i in numbers {
                    println!("{},{}", numbers[0], i);
                }
            }
            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;
            }
        }
        //for i in 0..sums.len() {
        //    let test = SaveState::<u64>::new();
        //    if sums[i] == self.w {
        //        if !test.bridges_gap(i as u32, self.n) {
        //            //return false;
        //        }
        //        unsafe {
        //            test.bridge_gap(i as u32);
        //        }
        //    }
        //}
        unsafe {
            SOLUTIONS += 1;
        }
        //println!("{:?}", sums);
        let vec = sums
            .iter()
            .map(|x| if *x != self.w { *x as u32 } else { self.h - 1 })
            .collect();
        //println!("{:?}", vec);
        let vec = GapHeights::from_heights(vec); //.output(self.n, self.h);

        if !self.check_gaps(&vec) {
            return false;
        }
        println!("success");
        vec.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;
            if stone > self.n {
                return false;
            }
            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
    }
}