use std::marker::PhantomData;
use super::{Engine, Curve, PrimeField};

/// Represents the scratch space for a wNAF form scalar.
pub struct WNAFTable {
    window: usize,
    wnaf: Vec<i64>
}

impl WNAFTable {
    pub fn new() -> WNAFTable {
        WNAFTable {
            window: 0,
            wnaf: vec![]
        }
    }

    /// Convert the scalar into wNAF form.
    pub fn set_scalar<E: Engine, G: Curve<E>>(&mut self, table: &WindowTable<E, G>, mut c: <E::Fr as PrimeField<E>>::Repr) {
        self.window = table.window;
        self.wnaf.truncate(0);

        while !E::Fr::repr_is_zero(&c) {
            let mut u;
            if E::Fr::repr_is_odd(&c) {
                u = (E::Fr::repr_least_significant_limb(&c) % (1 << (self.window+1))) as i64;

                if u > (1 << self.window) {
                    u -= 1 << (self.window+1);
                }

                if u > 0 {
                    E::Fr::repr_sub_noborrow(&mut c, &E::Fr::repr_from_u64(u as u64));
                } else {
                    E::Fr::repr_add_nocarry(&mut c, &E::Fr::repr_from_u64((-u) as u64));
                }
            } else {
                u = 0;
            }

            self.wnaf.push(u);

            E::Fr::repr_div2(&mut c);
        }
    }
}

/// Represents a window table for a base curve point.
pub struct WindowTable<E: Engine, G: Curve<E>>{
    window: usize,
    table: Vec<G>,
    _marker: PhantomData<E>
}

impl<E: Engine, G: Curve<E>> WindowTable<E, G> {
    /// Construct a new window table for a given base.
    pub fn new(e: &E, base: G, window: usize) -> Self {
        let mut tmp = WindowTable {
            window: 0,
            table: vec![],
            _marker: PhantomData
        };

        tmp.set_base(e, base, window);

        tmp
    }

    /// Replace this window table with a new one generated by a different base.
    pub fn set_base(&mut self, e: &E, mut base: G, window: usize) {
        assert!(window < 23);
        assert!(window > 1);

        self.window = window;
        self.table.truncate(0);
        self.table.reserve(1 << (window-1));

        let mut dbl = base;
        dbl.double(e);

        for _ in 0..(1 << (window-1)) {
            self.table.push(base);
            base.add_assign(e, &dbl);
        }
    }

    pub fn exp(&self, e: &E, wnaf: &WNAFTable) -> G {
        assert_eq!(wnaf.window, self.window);

        let mut result = G::zero(e);

        for n in wnaf.wnaf.iter().rev() {
            result.double(e);

            if *n != 0 {
                if *n > 0 {
                    result.add_assign(e, &self.table[(n/2) as usize]);
                } else {
                    result.sub_assign(e, &self.table[((-n)/2) as usize]);
                }
            }
        }

        result
    }

    pub fn current_window(&self) -> usize {
        self.window
    }
}
