use crate::ids::Id;

pub const NUM_BITS: usize = 256;
const BITS_PER_BYTES: usize = 8;

/// Returns "true" if two Ids are equal for the range [start, end).
/// This does bit-per-bit comparison for the Id type of [u8; ID_LEN].
/// ref. https://pkg.go.dev/github.com/ava-labs/avalanchego/ids#EqualSubset
pub fn equal_subset(start: usize, end: usize, id1: &Id, id2: &Id) -> bool {
    if end == 0 {
        return true;
    }

    let end = end - 1; // -1 for end index
    if start > end {
        return true;
    }
    if end >= NUM_BITS {
        return false;
    }

    let start_index = (start / BITS_PER_BYTES) as usize;
    let end_index = (end / BITS_PER_BYTES) as usize;

    if start_index + 1 < end_index
        && id1.0[(start_index + 1)..end_index] != id2.0[(start_index + 1)..end_index]
    {
        return false;
    }

    let start_bit = (start % BITS_PER_BYTES) as usize; // index in the byte that the first bit is at
    let end_bit = (end % BITS_PER_BYTES) as usize; // index in the byte that the last bit is at

    let start_mask: i32 = -1 << start_bit; // 111...0... The number of 0s is equal to start_bit
    let end_mask: i32 = (1 << (end_bit + 1)) - 1; // 000...1... The number of 1s is equal to end_bit + 1

    if start_index == end_index {
        // if looking at same byte, both masks need to be applied
        let mask = start_mask & end_mask;

        let b1 = mask & id1.0[start_index] as i32;
        let b2 = mask & id2.0[start_index] as i32;

        return b1 == b2;
    }

    let start1 = start_mask & id1.0[start_index] as i32;
    let start2 = start_mask & id2.0[start_index] as i32;

    let end1 = end_mask & id1.0[end_index] as i32;
    let end2 = end_mask & id2.0[end_index] as i32;

    start1 == start2 && end1 == end2
}

/// RUST_LOG=debug cargo test --package avalanche-types --lib -- ids::bits::test_equal_subset --exact --show-output
#[test]
fn test_equal_subset() {
    // ref. TestEqualSubsetEarlyStop
    let id1 = Id::from_slice(&vec![0xf0, 0x0f]);
    let id2 = Id::from_slice(&vec![0xf0, 0x1f]);
    // for c in &id1.0 {
    //     print!("{:b} ", *c);
    // }
    // println!("");
    // for c in &id2.0 {
    //     print!("{:b} ", *c);
    // }
    // 11110000 1111  0 0 0 0 0 0 0 0 ...
    // 11110000 11111 0 0 0 0 0 0 0 0 ...
    assert!(equal_subset(0, 12, &id1, &id2));
    assert!(!equal_subset(0, 13, &id1, &id2));

    // ref. TestEqualSubsetLateStart
    let id1 = Id::from_slice(&vec![0x1f, 0xf8]);
    let id2 = Id::from_slice(&vec![0x10, 0x08]);
    // for c in &id1.0 {
    //     print!("{:b} ", *c);
    // }
    // println!("");
    // for c in &id2.0 {
    //     print!("{:b} ", *c);
    // }
    // 11111 11111000 0 ...
    // 10000 1000 0 0 0 ...
    assert!(equal_subset(4, 12, &id1, &id2));
}

/// Returns the "id1" index of the first different bit in the range [start, end).
/// This does bit-per-bit comparison for the Id type of [u8; ID_LEN].
/// ref. https://pkg.go.dev/github.com/ava-labs/avalanchego/ids#FirstDifferenceSubset
pub fn first_difference_subset(start: usize, end: usize, id1: &Id, id2: &Id) -> (usize, bool) {
    if end == 0 {
        return (0, false);
    }

    let end = end - 1; // -1 for end index
    if start > end {
        return (0, false);
    }
    if end >= NUM_BITS {
        return (0, false);
    }

    let start_index = (start / BITS_PER_BYTES) as usize;
    let end_index = (end / BITS_PER_BYTES) as usize;

    let start_bit = (start % BITS_PER_BYTES) as usize; // index in the byte that the first bit is at
    let end_bit = (end % BITS_PER_BYTES) as usize; // index in the byte that the last bit is at

    let start_mask: i32 = -1 << start_bit; // 111...0... The number of 0s is equal to start_bit
    let end_mask: i32 = (1 << (end_bit + 1)) - 1; // 000...1... The number of 1s is equal to end_bit + 1

    if start_index == end_index {
        // if looking at same byte, both masks need to be applied
        let mask = start_mask & end_mask;

        let b1 = mask & id1.0[start_index] as i32;
        let b2 = mask & id2.0[start_index] as i32;
        if b1 == b2 {
            return (0, false);
        }

        let bd = b1 ^ b2;
        return (
            bd.trailing_zeros() as usize + start_index * BITS_PER_BYTES,
            true,
        );
    }

    let start1 = start_mask & id1.0[start_index] as i32;
    let start2 = start_mask & id2.0[start_index] as i32;
    if start1 != start2 {
        let bd = start1 ^ start2;
        return (
            bd.trailing_zeros() as usize + start_index * BITS_PER_BYTES,
            true,
        );
    }

    // check interior bits
    for idx in (start_index + 1)..end_index {
        let b1 = id1.0[idx];
        let b2 = id2.0[idx];
        if b1 != b2 {
            let bd = b1 ^ b2;
            return (bd.trailing_zeros() as usize + idx * BITS_PER_BYTES, true);
        }
    }

    let end1 = end_mask & id1.0[end_index] as i32;
    let end2 = end_mask & id2.0[end_index] as i32;
    if end1 != end2 {
        let bd = end1 ^ end2;
        return (
            bd.trailing_zeros() as usize + end_index * BITS_PER_BYTES,
            true,
        );
    }

    (0, false) // no difference found
}

/// RUST_LOG=debug cargo test --package avalanche-types --lib -- ids::bits::test_first_difference_subset --exact --show-output
#[test]
fn test_first_difference_subset() {
    // ref. TestFirstDifferenceSubsetEarlyStop
    let id1 = Id::from_slice(&vec![0xf0, 0x0f]);
    let id2 = Id::from_slice(&vec![0xf0, 0x1f]);
    // for c in &id1.0 {
    //     print!("{:b} ", *c);
    // }
    // println!("");
    // for c in &id2.0 {
    //     print!("{:b} ", *c);
    // }
    // 11110000 1111  0 0 0 0 0 ...
    // 11110000 11111 0 0 0 0 0 ...
    assert_eq!(first_difference_subset(0, 12, &id1, &id2), (0, false));
    assert_eq!(first_difference_subset(0, 13, &id1, &id2), (12, true));

    // ref. TestFirstDifferenceEqualByte4
    let id1 = Id::from_slice(&vec![0x10]);
    let id2 = Id::from_slice(&vec![0x00]);
    // for c in &id1.0 {
    //     print!("{:b} ", *c);
    // }
    // println!("");
    // for c in &id2.0 {
    //     print!("{:b} ", *c);
    // }
    // 10000 0 0 0 0 0 0 ...
    // 0 0 0 0 0 0 0 0 0 ...
    assert_eq!(first_difference_subset(0, 4, &id1, &id2), (0, false));
    assert_eq!(first_difference_subset(0, 5, &id1, &id2), (4, true));
}

// TODO: add more tests

#[derive(
    std::clone::Clone,
    std::cmp::Eq,
    std::cmp::Ord,
    std::cmp::PartialEq,
    std::cmp::PartialOrd,
    std::fmt::Debug,
    std::hash::Hash,
)]
pub enum Bit {
    Zero,
    One,
}

impl std::convert::From<usize> for Bit {
    fn from(v: usize) -> Self {
        assert!(v <= 1);
        match v {
            0 => Bit::Zero,
            1 => Bit::One,
            _ => panic!("unexpected bit value {}", v),
        }
    }
}

impl Bit {
    /// Returns the `usize` value of the enum member.
    pub fn as_usize(&self) -> usize {
        match self {
            Bit::Zero => 0,
            Bit::One => 1,
        }
    }
}