fastbit 0.11.1

use std::{
    hash::Hash,
    ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not, Shl, Shr, Sub},
    usize,
};

/// A bitset trait support
///

/// TODO: add span related method
/// 1. as_span(&self)
/// 2. as_span_mut(&mut self)
/// 3. span(&self, offset, len)
/// 4. span_mut(&mut self, offset, len)

/// Trait for bitset operations.
pub trait BitRead {
    type Iter<'a>: Iterator<Item = usize>
    where
        Self: 'a;

    /// Returns the number of bits in the bitset.
    fn len(&self) -> usize;

    /// Returns true if the bitset contains no set bits.
    #[inline(always)]
    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns true if the bit at position `idx` is set.
    fn test(&self, idx: usize) -> bool;

    /// Returns the number of set bits.
    fn count_ones(&self) -> usize {
        self.iter().count()
    }

    /// Returns true if all bits are set.
    fn all(&self) -> bool {
        let mut pred = 0;
        for (i, _b) in self.iter().enumerate() {
            if i != pred {
                return false;
            }
            pred = i + 1;
        }
        pred == self.len()
    }

    /// Returns true if any bit is set.
    fn any(&self) -> bool {
        for _b in self.iter() {
            return true;
        }
        false
    }

    #[inline(always)]
    fn none(&self) -> bool {
        !self.any()
    }

    fn iter(&self) -> Self::Iter<'_>;
}

pub trait BitWrite: BitRead {
    /// Sets the bit at position `idx`.
    fn set(&mut self, idx: usize);

    /// Clears the bit at position `idx`.
    fn reset(&mut self, idx: usize);

    /// flit the bit at position `idx`.
    fn flip(&mut self, idx: usize);

    /// return and clear bit at idx.
    fn take(&mut self, idx: usize) -> bool {
        let value = self.test(idx);
        self.reset(idx);
        value
    }

    /// set bit to value, return old.
    fn replace(&mut self, idx: usize, value: bool) -> bool {
        let old = self.test(idx);
        if value {
            self.set(idx);
        }
        old
    }

    /// Sets the bit at position `idx` and returns the previous value.
    fn test_and_set(&mut self, idx: usize) -> bool;

    /// Sets all bits to 1.
    fn fill(&mut self);

    /// Clears all bits to 0.
    fn clear(&mut self);

    // TODO: impl pop_left and pop_right
    // Find and clear the lowest index set bit. Returns `Some(index)`, or `None` if empty.
    // fn pop_left(&mut self) -> Option<usize>;

    // Find and clear the highest index set bit. Returns `Some(index)`, or `None` if empty.
    // fn pop_right(&mut self) -> Option<usize>;
}

pub trait BitResize: BitWrite {
    fn resize(&mut self, len: usize);
}

pub trait BitStack: BitWrite {
    fn push(&mut self, value: bool);
    fn pop(&mut self) -> Option<bool>;
}

/// Iterator over set bits in a BitSet.
pub struct BitSetIter<'a, T: BitRead + ?Sized> {
    pub bitset: &'a T,
    pub current: usize,
}

impl<'a, T: BitRead + ?Sized> Iterator for BitSetIter<'a, T> {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        while self.current < self.bitset.len() {
            let idx = self.current;
            self.current += 1;
            if self.bitset.test(idx) {
                return Some(idx);
            }
        }
        None
    }
}

pub trait BitWord:
    Copy
    + Hash
    + From<u8>
    + BitOr<Output = Self>
    + BitOrAssign
    + BitXor<Output = Self>
    + BitXorAssign
    + BitAnd<Output = Self>
    + BitAndAssign
    + Not<Output = Self>
    + Shr<usize, Output = Self>
    + Shl<usize, Output = Self>
    + Sub<Output = Self>
    + PartialEq
{
    const BITS: usize;
    const MAX: Self;

    fn count_ones(self) -> usize;
    fn trailing_zeros(self) -> usize;
}

macro_rules! impl_bitword {
    ($t:ty) => {
        impl BitWord for $t {
            const BITS: usize = <$t>::BITS as usize;
            const MAX: Self = <$t>::MAX;

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

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

impl_bitword!(u8);
impl_bitword!(u16);
impl_bitword!(u32);
impl_bitword!(u64);
impl_bitword!(u128);
impl_bitword!(usize);