# Description
A multilinear polynomial is stored by a list of its evaluations.

__Example__ $f(x_1, x_2) = 3x_1x_2 + 2x_2$ is stored as $[0,2,0,5]$ whose evaluations are

0, 0 |-> 0
0, 1 |-> 2
1, 0 |-> 0
1, 1 |-> 5

We have a multilinear extension $eq(\vec x, \vec r)$ for $\vec x = \left<x_1,\dots,x_n\right>$ and a point $\vec r = \left<r_1,\dots,r_n\right>$.

__Task__: Evaluate
$$eq(\vec x,\vec r) = \prod_{i=1}^n (x_i \times r_i + (1-x_i)\times(1-r_i))$$
We build $eq(\vec x, \vec r)$ for $\vec x = \left<x_1,\dots,x_n\right>$ and a point $\vec r = \left<r_1,\dots,r_n\right>$ from its evaluations. To build $eq(\vec x, \vec r)$, we want to evaluate $eq(\vec x, \vec r)$ over $\vec x \in \{0, 1\}^n$.

__Example__. With n = 4, x is a binary vector of 4, then $eq(\vec x,\vec r)$ with $\vec r = [1,2,3,4]$

x1, x2, x3, x4
0, 0, 0, 0 |-> (1-r0) * (1-r1) * (1-r2) * (1-r3) = 0
1, 0, 0, 0 |-> r0 * (1-r1) * (1-r2) * (1-r3) = -6
0, 1, 0, 0 |-> (1-r0) * r1 * (1-r2) * (1-r3) = 0
1, 1, 0, 0 |-> r0 * r1 * (1-r2) * (1-r3) = 12
....
1, 1, 1, 1 |-> r0 * r1 * r2 * r3 = 24

# Code

/// Stores a multilinear polynomial in dense evaluation form.
#[derive(Clone, PartialEq, Eq, Hash, Default, CanonicalSerialize, CanonicalDeserialize)]
pub struct DenseMultilinearExtension<F: Field> {
    /// The evaluation over {0,1}^`num_vars`
    pub evaluations: Vec<F>,
    /// Number of variables
    pub num_vars: usize,
}

/// This function build the eq(x, r) polynomial for any given r.
///
/// Evaluate
///      eq(x,y) = \prod_i=1^num_var (x_i * y_i + (1-x_i)*(1-y_i))
/// over r, which is
///      eq(x,r) = \prod_i=1^num_var (x_i * r_i + (1-x_i)*(1-r_i))
pub fn build_eq_x_r<F: PrimeField>(r: &[F]) -> DenseMultilinearExtension {
    // num_var = r.len()
    // eq(x,r) with r = [1,2]
    // 0,  0, |-> (1-r0)   * (1-r1)     = 0
    // 1,  0, |-> r0       * (1-r1)     = 1
    // 0,  1, |-> (1-r0)   * r1         = 0
    // 1,  1, |-> r0       * r1         = 2
    // your code here

    let mut extensions: DenseMultilinearExtension {
        evaluations: vec![],
        num_vars: r.len()
    }
    let index = 0;
    while index <= 2^(r.len()) {  
        let decomposition: Vec<Bool> = decompose(index);
        let mut accumulator;
        for (i,item) in decomposition.iter().enumerate() {
            if item == false {
                accumulator *= eval(r[i], 0)
            } else {
                accumulator *= eval(r[i], 1)
            }
        }
        extensions.evaluations.append(accumulator)
        }
    }
    
// O(2^(r.len()) * r.len()), Super linear in terms of number of constraints

// O(N*log(N)) where N = 2^(r.len()) is # variable in CS
// O(N) 

pub fn eval(r: &F, x_1: usize) -> F {
    (x_1 * r) + ( 1 - x_1 ) * ( 1 - r)
}

// index loop though 0.. 2^num_vars
// decompose(0) -> (0, 0)
// decompose(1) -> (1, 0)
// decompose(2) -> (0, 1)
// decompose(3) -> (1, 1)
pub fn decompose(index: u8)-> Vec<bool>{}

// for each loop with index 
// vec x = decompose(index)
// vec r = r
// compute \prod_i=1^num_var (x_i * r_i + (1-x_i)*(1-r_i))