pub fn ldd_to_bdd<'id>(

    storage: &mut Storage,

    manager: &<BDDFunction as Function>::Manager<'id>,

    ldd: &LddRef<'_>,

    bits_per_layer: &LddRef<'_>,

    bit_variables: &[VarNo],

) -> Result<BDDFunction, OutOfMemory> {

    if **storage.empty_set() == *ldd {

        return Ok(BDDFunction::f(manager));

    }

    if **storage.empty_vector() == *ldd {

        return Ok(BDDFunction::t(manager));

    }

    let DataRef(value, down, right) = storage.get_ref(ldd);

    let DataRef(bits_value, bits_down, _bits_right) = storage.get_ref(bits_per_layer);

    let right_bdd = ldd_to_bdd(storage, manager, &right, bits_per_layer, bit_variables)?;

    let needed = bits_value as usize;

    if bit_variables.len() < needed {

    }

    let mut down_bdd = ldd_to_bdd(storage, manager, &down, &bits_down, &bit_variables[needed..])?;

    for i in 0..bits_value {

        let bit = bits_value - i - 1; // MSB first

        let var_no = bit_variables[bit as usize];

        if value & (1 << i) != 0 {

            down_bdd = BDDFunction::var(manager, var_no)?.ite(&down_bdd, &BDDFunction::f(manager))?;

            down_bdd = BDDFunction::var(manager, var_no)?.ite(&BDDFunction::f(manager), &down_bdd)?;

    down_bdd.or(&right_bdd)

}

pub fn bdd_to_ldd(

    storage: &mut Storage,

    manager_ref: &BDDManagerRef,

    bdd: &BDDFunction,

    variables: &[VarNo],

    bits_per_layer: &[Value],

    current_bit: Value,

    current_value: Value,

) -> Result<Ldd, OutOfMemory> {

    manager_ref.with_manager_shared(|manager| {

        let edge = bdd.as_edge(manager);

        bdd_to_ldd_edge(storage, manager, edge.borrowed(), variables, bits_per_layer, current_bit, current_value)

    })

}

pub fn bdd_to_ldd_edge<'id>(

    storage: &mut Storage,

    manager: &<BDDFunction as Function>::Manager<'id>,

    bdd: Borrowed<EdgeOfFunc<'id, BDDFunction>>,

    variables: &[VarNo],

    bits_per_layer: &[Value],

    current_bit: Value,

    current_value: Value,

) -> Result<Ldd, OutOfMemory> {

    let bdd_node = match manager.get_node(&bdd) {

        oxidd::Node::Inner(node) => node,

        oxidd::Node::Terminal(terminal) => {

            match terminal {

                    return Ok(storage.empty_set().clone());

                    if !variables.is_empty() {

                        let num_bits = bits_per_layer.first().copied().expect("Missing bits per layer for current layer");

                        if num_bits == current_bit {

                            debug_assert!(current_bit < num_bits, "Current bit exceeds number of bits for layer");        

                            let high = bdd_to_ldd_edge(storage, manager, bdd.borrowed(), &variables[1..], bits_per_layer, current_bit + 1, current_value | (1 << (num_bits - current_bit - 1)))?;

                            let low = bdd_to_ldd_edge(storage, manager, bdd, &variables[1..], bits_per_layer, current_bit + 1, current_value)?;

                            return Ok(union(storage, &high, &low));

                    }

                    return Ok(storage.insert_singleton(current_value));

    let num_bits = bits_per_layer.first().copied().expect("Missing bits per layer for current layer");

    let variable_level = variables.first().expect("Missing variable for current layer");

    if *variable_level < bdd_node.level() { 

        if num_bits == current_bit {

            let down = bdd_to_ldd_edge(storage, manager, bdd, variables, &bits_per_layer[1..], 0, 0)?;

            let right = storage.empty_set().clone();

            return Ok(storage.insert(current_value, &down, &right))

            debug_assert!(current_bit < num_bits, "Current bit exceeds number of bits for layer");

            let high = bdd_to_ldd_edge(storage, manager, bdd.borrowed(), &variables[1..], bits_per_layer, current_bit + 1, current_value | (1 << (num_bits - current_bit - 1)))?;

            let low = bdd_to_ldd_edge(storage, manager, bdd, &variables[1..], bits_per_layer, current_bit + 1, current_value)?;

            return Ok(union(storage, &high, &low));

    }

    debug_assert_eq!(*variable_level, bdd_node.level(), "Levels do not match");

    if num_bits == current_bit {

        let down = bdd_to_ldd_edge(storage, manager, bdd, variables, &bits_per_layer[1..], 0, 0)?;

        let right = storage.empty_set().clone();

        Ok(storage.insert(current_value, &down, &right))

        debug_assert!(current_bit < num_bits, "Current bit exceeds number of bits for layer");  

        let (bdd_high, bdd_low) = collect_children(bdd_node);

        let high = bdd_to_ldd_edge(

            storage,

            manager,

            bdd_high,

            &variables[1..],

            bits_per_layer,

            current_bit + 1,

            current_value | (1 << (num_bits - current_bit - 1)),

        let low = bdd_to_ldd_edge(storage, manager, bdd_low, &variables[1..], bits_per_layer, current_bit + 1, current_value)?;

        Ok(union(storage, &high, &low))

}

pub fn compute_highest(storage: &mut Storage, ldd: &LddRef<'_>) -> Vec<u32> {

    let mut result = vec![0; height(storage, ldd)];

    compute_highest_rec(storage, &mut result, ldd, 0);

    result

}

fn collect_children<E: Edge, N: InnerNode<E>>(node: &N) -> (Borrowed<'_, E>, Borrowed<'_, E>) {

    debug_assert_eq!(N::ARITY, 2);

    let mut it = node.children();

    let f_then = it.next().unwrap();

    let f_else = it.next().unwrap();

    debug_assert!(it.next().is_none());

    (f_then, f_else)

}

fn compute_highest_rec(storage: &mut Storage, result: &mut [u32], set: &LddRef<'_>, depth: usize) {

    if set == storage.empty_set() || set == storage.empty_vector() {

        return;

    }

    let DataRef(value, down, right) = storage.get_ref(set);

    compute_highest_rec(storage, result, &right, depth);

    compute_highest_rec(storage, result, &down, depth + 1);

    result[depth] = result[depth].max(value);

}

pub fn required_bits(value: u32) -> u32 {

    (u32::BITS - value.leading_zeros()).max(1)

}

pub fn required_bits_64(value: u64) -> u32 {

    (u64::BITS - value.leading_zeros()).max(1)

}

pub fn compute_bits(highest: &[u32]) -> Vec<u32> {

    highest.iter().map(|&h| required_bits(h)).collect()

}

    fn test_random_compute_highest() {

        random_test(100, |rng| {

            let set = random_vector_set(rng, 4, 3, 5);

            let mut storage = Storage::new();

            let ldd = from_iter(&mut storage, set.iter());

            println!("LDD: {}", LddDisplay::new(&storage, &ldd));

            let highest = compute_highest(&mut storage, &ldd);

            println!("Highest: {:?}", highest);

            for (i, h) in highest.iter().enumerate() {

                for value in set.iter() {

                    assert!(

                        *h >= value[i],

            let bits = compute_bits(&highest);

            println!("Bits: {:?}", bits);

            for (i, b) in bits.iter().enumerate() {

                let expected_bits = required_bits(highest[i]);

                assert_eq!(

        })

    }

    fn test_random_ldd_to_bdd() {

        random_test(100, |rng| {

            let set = random_vector_set(rng, 50, 3, 5);

            let mut storage = Storage::new();

            let ldd = from_iter(&mut storage, set.iter());

            println!("LDD: {}", LddDisplay::new(&storage, &ldd));

            let highest = compute_highest(&mut storage, &ldd);

            let bits = compute_bits(&highest);

            let bits_dd = singleton(&mut storage, &bits);

            let manager_ref = oxidd::bdd::new_manager(2048, 1024, 1);

            let total_bits: u32 = bits.iter().sum();

            println!("Total bits: {}", total_bits);

            println!("Bits per layer: {:?}", bits);

            let vars = manager_ref.with_manager_exclusive(|manager| manager.add_vars(total_bits).collect::<Vec<_>>());

            let bdd =  manager_ref.with_manager_shared(|manager| ldd_to_bdd(&mut storage, manager, &ldd, &bits_dd, &vars).unwrap() );

            println!("resulting BDD: {}", FormatConfigSet(&bdd));

            let resulting_ldd = bdd_to_ldd(&mut storage, &manager_ref, &bdd, &vars, &bits, 0, 0).unwrap();

            println!("resulting LDD: {}", LddDisplay::new(&storage, &resulting_ldd));

            assert_eq!(ldd, resulting_ldd, "Converted LDD does not match original");

        });

    }