1/// A boolean hypercube structure to create an ergonomic evaluation domain
 2use crate::utils::virtual_polynomial::bit_decompose;
 3use ark_ff::PrimeField;
 4
 5use std::marker::PhantomData;
 6
 7/// A boolean hypercube that returns its points as an iterator
 8/// If you iterate on it for 3 variables you will get points in little-endian order:
 9/// 000 -> 100 -> 010 -> 110 -> 001 -> 101 -> 011 -> 111
10#[derive(Debug, Clone)]
11pub struct BooleanHypercube<F: PrimeField> {
12    _f: PhantomData<F>,
13    n_vars: usize,
14    current: u64,
15    max: u64,
16}
17
18impl<F: PrimeField> BooleanHypercube<F> {
19    pub fn new(n_vars: usize) -> Self {
20        BooleanHypercube::<F> {
21            _f: PhantomData::<F>,
22            n_vars,
23            current: 0,
24            max: 2_u32.pow(n_vars as u32) as u64,
25        }
26    }
27
28    /// returns the entry at given i (which is the little-endian bit representation of i)
29    pub fn at_i(&self, i: usize) -> Vec<F> {
30        assert!(i < self.max as usize);
31        let bits = bit_decompose((i) as u64, self.n_vars);
32        bits.iter().map(|&x| F::from(x)).collect()
33    }
34}
35
36impl<F: PrimeField> Iterator for BooleanHypercube<F> {
37    type Item = Vec<F>;
38
39    fn next(&mut self) -> Option<Self::Item> {
40        let bits = bit_decompose(self.current, self.n_vars);
41        let result: Vec<F> = bits.iter().map(|&x| F::from(x)).collect();
42        self.current += 1;
43
44        if self.current > self.max {
45            return None;
46        }
47
48        Some(result)
49    }
50}
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55    use crate::utils::vec::tests::to_F_dense_matrix;
56    use ark_pallas::Fr;
57
58    #[test]
59    fn test_hypercube() {
60        let expected_results = to_F_dense_matrix(vec![
61            vec![0, 0, 0],
62            vec![1, 0, 0],
63            vec![0, 1, 0],
64            vec![1, 1, 0],
65            vec![0, 0, 1],
66            vec![1, 0, 1],
67            vec![0, 1, 1],
68            vec![1, 1, 1],
69        ]);
70
71        let bhc = BooleanHypercube::<Fr>::new(3);
72        for (i, point) in bhc.clone().enumerate() {
73            assert_eq!(point, expected_results[i]);
74            assert_eq!(point, bhc.at_i(i));
75        }
76    }
77}