Merge branch 'master' of kobert:/var/repos/babel

9 files changed, 134 insertions, 11 deletions

diff --git a/src/lib.rs b/src/lib.rs
index 95d8d55..8699cc1 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,7 +1,7 @@
+mod permutations;
 pub mod solver;
 pub mod solvers;
 pub mod structs;
-#[macro_use]
 
 pub static N: u32 = 10;
 pub fn solve(n: u32) {
diff --git a/src/main.rs b/src/main.rs
index 95e3746..fdf3fcd 100755
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,10 +1,16 @@
+mod permutations;
 mod solver;
 mod solvers;
 mod structs;
-#[macro_use]
+use crate::solver::{IteratorSolver, Solver};
 
-pub static N: u32 = 10;
+pub static N: u32 = 8;
 fn main() {
-    let mut solver = solvers::intuitive::NormalSolver::new(N);
-    solver.solve();
+    //let mut solver = solvers::intuitive::NormalSolver::new(N);
+    //solver.solve();
+    let solver = solvers::gpusolver::GpuSolver::new(N);
+    println!("solver: {:?}", solver);
+    for (i, solution) in solver.solve().enumerate() {
+        println!("{}: {:?}", i, solution);
+    }
 }
diff --git a/src/permutations.rs b/src/permutations.rs
new file mode 100644
index 0000000..7b8e4d3
--- /dev/null
+++ b/src/permutations.rs
@@ -0,0 +1,45 @@
+use permutohedron::{Heap, LexicalPermutation};
+
+pub trait PermutationGenerator {
+    fn permutations(n: u32) -> Vec<Vec<u32>>;
+}
+
+pub struct HeapsPermutations;
+
+impl PermutationGenerator for HeapsPermutations {
+    fn permutations(n: u32) -> Vec<Vec<u32>> {
+        Heap::<'_, Vec<u32>, _>::new(&mut (1..=n).collect()).collect()
+    }
+}
+
+pub struct LexicalPermutations {
+    state: Vec<u32>,
+    is_ended: bool,
+}
+
+impl Iterator for LexicalPermutations {
+    type Item = Vec<u32>;
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.is_ended {
+            None
+        } else {
+            self.is_ended = self.state.next_permutation();
+            Some(self.state.clone())
+        }
+    }
+}
+
+impl LexicalPermutations {
+    fn new(n: u32) -> Self {
+        Self {
+            state: (1..=n).collect(),
+            is_ended: false
+        }
+    }
+}
+
+impl PermutationGenerator for LexicalPermutations {
+    fn permutations(n: u32) -> Vec<Vec<u32>> {
+        Self::new(n).collect()
+    }
+}
diff --git a/src/solver.rs b/src/solver.rs
index 809ddb4..db4e732 100755
--- a/src/solver.rs
+++ b/src/solver.rs
@@ -8,10 +8,16 @@ pub fn wall_stats(n: u32) -> (u32, u32) {
 
 pub trait Solver {
     fn new(n: u32) -> Self;
-    fn solve(&mut self) -> StoneWall;
     fn n(&self) -> u32;
-
     fn h(&self) -> u32;
-
     fn w(&self) -> u32;
 }
+
+pub trait FirstSolver {
+    fn solve(self) -> StoneWall;
+}
+
+pub trait IteratorSolver: Solver {
+    type IntoIter: Iterator<Item=StoneWall>;
+    fn solve(self) -> Self::IntoIter;
+}
diff --git a/src/solvers/gpusolver.rs b/src/solvers/gpusolver.rs
new file mode 100644
index 0000000..2b9eb4a
--- /dev/null
+++ b/src/solvers/gpusolver.rs
@@ -0,0 +1,65 @@
+use crate::solver::{wall_stats, Solver, IteratorSolver};
+use crate::structs::StoneWall;
+use crate::permutations::PermutationGenerator;
+
+#[derive(Debug)]
+pub struct GpuSolver {
+    n: u32, h: u32, w: u32,
+    permutations: Vec<Vec<u32>>,
+    masks: Vec<u64>,
+}
+
+impl GpuSolver {
+    fn solve_to_vec(&mut self) -> Vec<StoneWall> {
+        vec![]
+    }
+}
+
+fn generate_permutations(n: u32) -> Vec<Vec<u32>> {
+    crate::permutations::HeapsPermutations::permutations(n)
+}
+
+fn generate_masks(permutations: &[Vec<u32>]) -> Vec<u64> {
+    let mut masks = Vec::with_capacity(permutations.len());
+    for p in permutations {
+        let mut v = 0;
+        let mut x = 0u64;
+        for i in p.iter().take(p.len() - 1).map(|i| {
+                    v += i;
+                    v
+                }) {
+            x |= 1 << i
+        }
+        masks.push(x)
+    }
+    masks
+}
+
+impl Solver for GpuSolver {
+    fn new(n: u32) -> Self {
+        let (h, w) = wall_stats(n);
+        let permutations = generate_permutations(n);
+        let masks = generate_masks(&permutations);
+        Self {
+            n, h, w,
+            permutations,
+            masks,
+        }
+    }
+    fn n(&self) -> u32 {
+        self.n
+    }
+    fn h(&self) -> u32 {
+        self.h
+    }
+    fn w(&self) -> u32 {
+        self.w
+    }
+}
+
+impl IteratorSolver for GpuSolver {
+    type IntoIter = std::vec::IntoIter<StoneWall>;
+    fn solve(mut self) -> Self::IntoIter {
+        self.solve_to_vec().into_iter()
+    }
+}
diff --git a/src/solvers/intuitive.rs b/src/solvers/intuitive.rs
index a5ff935..3db1d33 100755
--- a/src/solvers/intuitive.rs
+++ b/src/solvers/intuitive.rs
@@ -22,7 +22,7 @@ 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 mut heap: Vec<_> = (1..=n).collect();
         let heap = permutohedron::Heap::new(&mut heap);
         let n_f = permutohedron::factorial(n as usize);
         let chunk = n_f as u32 / n;
diff --git a/src/solvers/mod.rs b/src/solvers/mod.rs
index 6eb2ec4..1bdc228 100755
--- a/src/solvers/mod.rs
+++ b/src/solvers/mod.rs
@@ -1,4 +1,5 @@
 //pub mod incremental_block;
 pub mod intuitive;
 //#[cfg(feature = "gpu")]
+pub mod gpusolver;
 pub mod opencl;
diff --git a/src/solvers/opencl.rs b/src/solvers/opencl.rs
index ae5bfa3..676c5cc 100644
--- a/src/solvers/opencl.rs
+++ b/src/solvers/opencl.rs
@@ -1,5 +1,4 @@
-#[macro_use]
-use ocl::{Buffer, Context, Device, Platform, Program, Queue};
+use ocl::{Buffer, Context, Device, Platform, Queue};
 use std::sync::mpsc::{Receiver, Sender};
 
 pub struct Job {
diff --git a/src/structs.rs b/src/structs.rs
index 1d33215..55cff29 100755
--- a/src/structs.rs
+++ b/src/structs.rs
@@ -1,3 +1,4 @@
+#[derive(Clone, Debug)]
 pub struct StoneWall {
     rows: Vec<Vec<u32>>,
 }