use crate::{
    core::{
        actually_used_field::ActuallyUsedField,
        bounds::FieldBounds,
        circuits::{
            boolean::{
                boolean_value::BooleanValue,
                utils::{cpot_circuit, CircuitType},
            },
            traits::arithmetic_circuit::ArithmeticCircuit,
        },
        expressions::expr::EvalFailure,
        global_value::value::FieldValue,
    },
    traits::{FromLeBits, GetBit},
    utils::used_field::UsedField,
};

/// Takes an unsigned integer input n and computes 2^k - 1
/// where k is the smallest integer such that n < 2^k.
#[derive(Debug, Clone)]
pub struct LowestBiggerPowerOfTwoMinusOne;

impl LowestBiggerPowerOfTwoMinusOne {
    /// Takes x as an unsigned integer and computes 2^k - 1
    /// where k is the smallest integer such that x < 2^k.
    pub fn lowest_bigger_power_of_two_minus_one<F: ActuallyUsedField>(
        x: FieldValue<F>,
    ) -> FieldValue<F> {
        let bounds = x.bounds();
        let circuit_size = bounds.unsigned_bin_size();
        let mut bits = (0..circuit_size)
            .map(|i| x.get_bit(i, false))
            .collect::<Vec<BooleanValue>>();
        bits.reverse();
        let (cpot, _) = cpot_circuit(bits, CircuitType::default());
        let mut res_bits = cpot
            .into_iter()
            .scan(BooleanValue::from(false), |acc, bit| {
                let res = *acc ^ bit;
                *acc = res;
                Some(res)
            })
            .collect::<Vec<BooleanValue>>();
        res_bits.reverse();
        FieldValue::<F>::from_le_bits(res_bits, false)
    }
}

impl<F: UsedField> ArithmeticCircuit<F> for LowestBiggerPowerOfTwoMinusOne {
    fn eval(&self, x: Vec<F>) -> Result<Vec<F>, EvalFailure> {
        assert_eq!(x.len(), 1);
        let x = x[0];
        let mut exponent = F::NUM_BITS as usize;
        for i in 0..exponent {
            let pot = F::power_of_two(i);
            if pot > x {
                exponent = i;
                break;
            }
        }
        Ok(vec![F::power_of_two(exponent) - F::ONE])
    }

    fn bounds(&self, bounds: Vec<FieldBounds<F>>) -> Vec<FieldBounds<F>> {
        let max_size = bounds
            .into_iter()
            .map(|bound| bound.bin_size(false))
            .max()
            .unwrap();
        let res = if max_size <= F::CAPACITY as usize {
            FieldBounds::new(F::ZERO, F::power_of_two(max_size) - F::ONE)
        } else {
            FieldBounds::All
        };
        vec![res]
    }

    fn run(&self, vals: Vec<FieldValue<F>>) -> Vec<FieldValue<F>>
    where
        F: ActuallyUsedField,
    {
        vec![LowestBiggerPowerOfTwoMinusOne::lowest_bigger_power_of_two_minus_one(vals[0])]
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{
        core::circuits::traits::arithmetic_circuit::tests::TestedArithmeticCircuit,
        ArcisField,
    };
    use rand::Rng;
    impl TestedArithmeticCircuit<ArcisField> for LowestBiggerPowerOfTwoMinusOne {
        fn gen_desc<R: Rng + ?Sized>(_rng: &mut R) -> Self {
            LowestBiggerPowerOfTwoMinusOne
        }

        fn gen_n_inputs<R: Rng + ?Sized>(&self, _rng: &mut R) -> usize {
            1
        }
    }
    #[test]
    fn tested() {
        LowestBiggerPowerOfTwoMinusOne::test(1, 64)
    }
}
