use core::{
    num::NonZeroUsize,
    ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, Not},
};

mod le;
pub use le::LE;

/// Represents a copyable container of bits (usually an unsigned integer).
/// # Safety
/// - `Self::ZERO` must be `core::mem::zeroed()`.
/// - `2^BITS_LOG2` must be equal to BITS.
/// - The provided methods can only be overridden with equivalent methods.
pub unsafe trait BitBlock:
    Copy
    + Not<Output = Self>
    + BitOr<Output = Self>
    + BitOrAssign
    + BitAndAssign
    + BitAnd<Output = Self>
    + Ord
{
    /// Represents the number of bits in a block. It is generally a good idea for this number to be a power of two.
    const BITS: usize;
    const ZERO: Self;
    /// As of now, this value is not `1` for unsigned integers `UPSTREAM_ONE.wrapping_shift_upstream(1)` should be `0`.
    /// For example, for u8, this value is `0x80` (`0b10000000`).
    const UPSTREAM_ONE: Self;
    /// Shifts `self` `n` bits in the indexing direction.
    fn wrapping_shift_downstream(self, n: usize) -> Self;
    /// Shifts `self` `n` bits against the indexing direction.
    fn wrapping_shift_upstream(self, n: usize) -> Self;
    /// Gets the leading zeros in the indexing direction.
    fn leading_zeros(self) -> usize;
    /// Gets the leading ones in the indexing direction.
    fn leading_ones(self) -> usize;

    /// Returns the index of the block holding the bit at the specified location in a collection (eg. for a `u8`, `get_block_index(9) == 2`).
    fn get_block_index(idx: usize) -> usize {
        idx / Self::BITS
    }

    /// Returns the index of the first bit in the block at `idx`..
    fn bit_index_from_block_index(idx: usize) -> usize {
        idx * Self::BITS
    }

    /// Returns true if the bit at `idx` is `1`.
    #[inline]
    fn wrapping_test_bit(self, idx: usize) -> bool {
        self.wrapping_shift_upstream(idx) & Self::UPSTREAM_ONE != Self::ZERO
    }

    /// Returns `self` with the bit at `idx` set to `1`.
    #[inline]
    fn wrapping_with_bit(self, idx: usize) -> Self {
        self | Self::UPSTREAM_ONE.wrapping_shift_downstream(idx)
    }

    /// Returns `self` with the bit at `idx` set to `0`.
    #[inline]
    fn wrapping_without_bit(self, idx: usize) -> Self {
        self & !Self::UPSTREAM_ONE.wrapping_shift_downstream(idx)
    }

    /// Returns a bit mask of ones at `position` (wrapped) with a length of `length` (saturated).
    /// # Example
    /// ```
    /// # use bitmap32::BitBlock;
    /// # use core::num::NonZeroUsize;
    /// assert_eq!(u8::ones_mask(2, NonZeroUsize::new(3).unwrap()), 0b00111000);
    /// assert_eq!(u8::ones_mask(6, NonZeroUsize::new(10).unwrap()), 0b00000011);
    /// assert_eq!(u8::ones_mask(12, NonZeroUsize::new(2).unwrap()), 0b00001100);
    /// ```
    fn ones_mask(position: usize, length: NonZeroUsize) -> Self {
        let position = position % Self::BITS;

        let mut val = !Self::ZERO;
        let shl_amount = (Self::BITS - position).saturating_sub(length.get());

        val = val.wrapping_shift_downstream(position + shl_amount);
        val = val.wrapping_shift_upstream(shl_amount);

        val
    }
}

macro_rules! impl_bit_block {
    {$type:ty} => {
        unsafe impl BitBlock for $type {
            const ZERO: Self = 0;

            const BITS: usize = Self::BITS as usize;

            const UPSTREAM_ONE: Self = (1 as $type).reverse_bits();

            #[inline(always)]
            fn wrapping_shift_downstream(self, n: usize) -> Self {
                let shr_amnt = n % Self::BITS as usize;
                self.wrapping_shr(shr_amnt as u32)
            }

            #[inline(always)]
            fn wrapping_shift_upstream(self, n: usize) -> Self {
                let shl_amnt = n % Self::BITS as usize;
                self.wrapping_shl(shl_amnt as u32)
            }

            #[inline(always)]
            fn leading_zeros(self) -> usize {
                self.leading_zeros() as usize
            }

            #[inline(always)]
            fn leading_ones(self) -> usize {
                self.leading_ones() as usize
            }
        }
    }
}

impl_bit_block! {u8}
impl_bit_block! {u16}
impl_bit_block! {u32}
impl_bit_block! {u64}
impl_bit_block! {u128}
impl_bit_block! {usize}

#[cfg(test)]
mod tests {
    macro_rules! generate_tests_for {
        {$type:ident} => {
            mod $type {
                use super::super::BitBlock as BB;

                fn rev(n: $type) -> $type {
                    n.reverse_bits()
                }

                #[test]
                fn wrapping_test() {
                    assert_eq!(BB::wrapping_test_bit(rev(0b1), 0), true);
                    assert_eq!(BB::wrapping_test_bit(rev(0b1), 1), false);

                    for i in 0..(5 * <$type as BB>::BITS) {
                        assert_eq!(
                            BB::wrapping_test_bit(rev(0b1000), i),
                            (i % <$type as BB>::BITS) == 3,
                        )
                    }
                }

                #[test]
                fn with_bit() {
                    for _ in 0..100 {
                        let num: $type = rand::random();
                        let idx_wrapping = rand::random::<usize>();
                        let idx = idx_wrapping % <$type as BB>::BITS;

                        let num_modified = num.wrapping_with_bit(idx_wrapping);

                        for i in 0..<$type as BB>::BITS {
                            if i == idx {
                                assert_eq!(num_modified.wrapping_test_bit(idx), true)
                            } else {
                                assert_eq!(
                                    num_modified.wrapping_test_bit(i),
                                    num.wrapping_test_bit(i)
                                )
                            }
                        }
                    }
                }

                #[test]
                fn without_bit() {
                    for _ in 0..100 {
                        let num: $type = rand::random();
                        let idx_wrapping = rand::random::<usize>();
                        let idx = idx_wrapping % <$type as BB>::BITS;

                        let num_modified = num.wrapping_without_bit(idx_wrapping);
                        for i in 0..<$type as BB>::BITS {
                            if i == idx {
                                assert_eq!(num_modified.wrapping_test_bit(idx), false)
                            } else {
                                assert_eq!(
                                    num_modified.wrapping_test_bit(i),
                                    num.wrapping_test_bit(i)
                                )
                            }
                        }
                    }
                }

                #[test]
                fn ones_mask() {
                    use core::num::NonZeroUsize;

                    for _ in 0..100 {
                        let start = rand::random::<usize>() % (<$type as BB>::BITS - 1);
                        let len = NonZeroUsize::MIN.saturating_add(rand::random::<usize>() % (<$type as BB>::BITS - start - 1));

                        let mask_map: crate::BitMap<$type, 1> = [$type::ones_mask(start, len)].into();

                        let mut start_reached = false;
                        let mut current_len: usize = 0;
                        for (i, bit) in mask_map.bits().enumerate() {
                            if i == start as usize {
                                start_reached = true;
                            }

                            if start_reached {
                                if current_len < len.get() {
                                    if bit != true {
                                        panic!("Expected one but got zero: {mask_map:?}; Start: {start}; Len: {len}; Bit: {i}");

                                    }
                                    current_len += 1;
                                } else {
                                    if bit != false {
                                        panic!("Expected zero but got one: {mask_map:?}; Start: {start}; Len: {len}; Bit: {i}");
                                    }
                                }
                            } else {
                                if bit != false {
                                    panic!("Expected zero but got one: {mask_map:?}; Start: {start}; Len: {len}; Bit: {i}");
                                }
                            }

                        }
                    }
                }
            }
        }
    }

    generate_tests_for! {u8}
    generate_tests_for! {u16}
    generate_tests_for! {u32}
    generate_tests_for! {u64}
    generate_tests_for! {u128}
    generate_tests_for! {usize}
}