use rayon::prelude::*;

/// Solve for a given N and return the resulting wall
#[derive(Clone)]
pub struct NormalSolver {
    pub n: u32,
    /// calculated height [might not be correct!]
    pub h: u32,
    /// width
    pub w: u32,
    pub chunk: u32,
    pub mask: u64,
    /// Use to store already used blocks as a bitmask
    permutations: Vec<Vec<u32>>,
    masks: Vec<u64>,
}

static mut TRIES: u32 = 0;
static mut SOLUTIONS: u32 = 0;

impl NormalSolver {
    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 chunk = n_f as u32 / n;
        let mut permutations = Vec::with_capacity(n_f);
        let mut masks: Vec<u64> = vec![0; n_f];
        println!("Generating permutations");
        for (j, data) in heap.enumerate() {
            permutations.push(data.clone());
            let mut sum = 0;
            for stone in permutations[j].iter().take(n as usize - 1) {
                //.take(n as usize - 1) {
                sum += stone;
                masks[j] |= 1 << sum;
            }
        }
        Self {
            n,
            h,
            w,
            chunk,
            mask: (1 << w) - 2,
            permutations,
            masks,
        }
    }

    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!("perm {}: {:b}", n, self.masks[n]);
        }
        println!("calculate results");
        self.permute(
            permutohedron::factorial(self.n as usize),
            0,
            0,
            ((0..(self.h - 1))
                .map(|x| x * self.chunk)
                .collect::<Vec<u32>>())
            .as_ref(),
        );
        unsafe { println!("tries: {}\nsolutions: {}", TRIES, SOLUTIONS) }
    }

    fn permute(&self, up: usize, index: usize, curr_mask: u64, numbers: &[u32]) {
        if index as usize == numbers.len() {
            //println!("checking {:?}", numbers);
            unsafe {
                TRIES += 1;
            }
            let mut tmask: u64 = 0;
            let mut sum = 0;
            let mut stones = 0;
            for i in 1..=(self.w + 1) {
                if curr_mask & (1 << i) == 0 {
                    stones += 1;
                    tmask |= 1 << (i - sum);
                    sum = i;
                }
            }
            if tmask == (1 << (self.n + 1)) - 2 && stones == self.n {
                println!("tmask: {:b}", tmask);
                println!("curr: {:b}", curr_mask);
                //println!("success");
                unsafe {
                    SOLUTIONS += 1;
                }
                for i in numbers {
                    println!("{}\t{}", numbers[0], i);
                }
            }
            return;
        }
        let mut new_num = Vec::from(numbers);
        let start = numbers[index as usize] / self.chunk;
        if index as usize == numbers.len() - 1 {
            #[cfg(feature = "gpu")]
            {
                crate::solvers::opencl::check(
                    self.masks.as_ref(),
                    self.w,
                    self.n,
                    curr_mask,
                    (start * self.chunk) as usize,
                )
                .unwrap();
                return;
            }
        }
        for i in start..self.n - (self.h - 1 - index as u32) {
            for n in 1..(numbers.len() - index) {
                new_num[n + index] = (n as u32 + i) * self.chunk;
            }
            if index == 0 && false {
                (0..self.chunk).into_par_iter().for_each(|j| {
                    let mut new_num = new_num.clone();
                    let tmp = i * self.chunk + j;
                    new_num[index] = tmp;
                    self.permute(
                        up,
                        index + 1,
                        curr_mask | self.masks[tmp as usize],
                        &new_num,
                    );
                });
            } else {
                for j in 0..self.chunk {
                    new_num[index] = i * self.chunk + j;
                    self.permute(
                        up,
                        index + 1,
                        curr_mask | self.masks[new_num[index] as usize],
                        &new_num,
                    );
                }
            }
        }
    }
}