rust-dense-bitset 0.1.1

use crate::bitset::BitSet;

use std::fmt;
use std::hash::{Hash, Hasher};

/// Overload of &, &=, |, |=, ^, ^=, !, <<, <<=, >>, >>=
use std::ops::{
    BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not, Shl, ShlAssign, Shr,
    ShrAssign,
};

/// Provides an efficient and compact `BitSet` implementation for up to 64 bits.
///
/// This structure implements `BitSet, Clone, Copy, Default, Debug, Hash, PartialEq, Eq` and bit operations.
#[derive(Copy, Clone, Default)]
pub struct DenseBitSet {
    state: u64,
}

impl DenseBitSet {
    /// Returns a new empty `DenseBitSet`.
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    ///
    /// let mut bs = DenseBitSet::new();
    /// ```
    pub fn new() -> Self {
        Self { state: 0 }
    }

    /// Generates a bitset from an integer (little endian convention).
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    ///
    /// let bs = DenseBitSet::from_integer(1234567890);
    /// ```
    pub fn from_integer(i: u64) -> Self {
        Self { state: i }
    }

    /// Generates a bitset from a string and a base (little endian convention).
    ///
    /// The `base` must be an integer between 2 and 32.
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    ///
    /// let mut bs1 = DenseBitSet::from_string("101010", 2);
    /// let mut bs2 = DenseBitSet::from_string("2a", 16);
    ///
    /// assert_eq!(bs1,bs2);
    /// ```
    ///
    /// # Panics
    ///  
    /// This function will panic if an incorrect `base` is provided or if invalid
    /// characters are found when parsing.
    pub fn from_string(s: &str, base: u32) -> Self {
        assert!(2 <= base && base <= 32, "Only supports base from 2 to 32");
        let val = u64::from_str_radix(s, base);
        let res: u64 = val.expect("Failed to parse string");
        Self { state: res }
    }

    /// Returns an integer representing the bitset (little endian convention).
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    ///
    /// let bs = DenseBitSet::from_integer(1234);
    ///
    /// assert_eq!(bs.to_integer(), 1234);
    /// ```
    pub fn to_integer(self) -> u64 {
        self.state
    }

    /// Returns an integer representation of the bitset starting at the given `position` with given `length` (little endian convention).
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    ///
    /// let bs = DenseBitSet::from_integer(0b11110101010010);
    /// let value = bs.extract(5,6);
    ///
    /// assert_eq!(value, 42);
    /// ```
    ///
    /// # Panics
    /// This function will panic if `length` is zero or if one tries to
    /// access a bit beyond the 64 bit limit (i.e., `position + length > 64`).
    pub fn extract(self, position: usize, length: usize) -> u64 {
        assert!(
            position + length <= 64,
            "This implementation is currently limited to 64 bit bitsets."
        );
        assert!(length > 0, "Cannot extract a zero-width slice.");
        if length < 64 {
            (self.state >> position) & ((1 << length) - 1)
        } else {
            // This special branch is to avoid overflowing when masking
            (self.state >> position)
        }
    }

    /// Returns nothing, mutates the `DenseBitSet` to insert `value` at the given `position`.
    ///
    /// Note that `value` is treated as a `length`-bit integer (little endian convention);
    /// if necessary, `value` is padded with zeros (or truncated) to be of the correct length.
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    ///
    /// let mut bs = DenseBitSet::new();
    /// bs.insert(10, 8, 0b10101011);
    /// bs.insert(3,1,1);
    ///
    /// assert_eq!(bs.to_integer(), 0b101010110000001000)
    /// ```
    ///
    /// # Panics
    /// This function will panic if `length` is zero, or if one tries to
    /// insert a bit beyond the 64 bit limit (i.e. `position + length > 64`)
    pub fn insert(&mut self, position: usize, length: usize, value: u64) {
        assert!(
            position + length <= 64,
            "This implementation is currently limited to 64 bit bitsets."
        );
        assert!(length > 0, "Cannot insert zero-width slice");
        if length < 64 {
            let mut u = u64::max_value();
            u ^= ((1 << length) - 1) << position;
            self.state &= u;
            self.state |= value << position;
        } else {
            self.state = value;
        }
    }

    /// Returns `true` if and only if all bits are set to `true`.
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    /// use rust_dense_bitset::BitSet;
    ///
    /// let mut bs = DenseBitSet::from_integer(u64::max_value());
    ///
    /// assert!(bs.all());
    ///
    /// bs.set_bit(28,false);
    /// bs.all(); // -> false
    /// ```
    pub fn all(self) -> bool {
        self.state == u64::max_value()
    }

    /// Returns `true` if at least one of the bits is set to `true`.
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    /// use rust_dense_bitset::BitSet;
    ///
    /// let mut bs = DenseBitSet::from_integer(2048);
    ///
    /// assert!(bs.any());
    ///
    /// bs.set_bit(11,false);
    /// bs.any(); // -> false
    /// ```
    pub fn any(self) -> bool {
        self.state > 0
    }

    /// Returns `true` if all the bits are set to `false`.
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    /// use rust_dense_bitset::BitSet;
    ///
    /// let mut bs = DenseBitSet::from_integer(2048);
    /// bs.set_bit(11,false);
    ///
    /// assert!(bs.none());
    /// ```
    pub fn none(self) -> bool {
        !self.any()
    }

    /// Returns a bit-reversed `DenseBitSet`.
    ///
    /// This method is using a constant time bit reversal algorithm for 64 bits integers.
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    ///
    /// let bs = DenseBitSet::from_integer(0b11110001);
    /// let bs2 = bs.reverse();
    ///
    /// assert_eq!(bs2.to_integer(), 0b1000111100000000000000000000000000000000000000000000000000000000);
    /// ```
    pub fn reverse(self) -> Self {
        let mut v = self.state;
        v = ((v >> 1) & (0x5555555555555555 as u64)) | ((v & (0x5555555555555555 as u64)) << 1);
        v = ((v >> 2) & (0x3333333333333333 as u64)) | ((v & (0x3333333333333333 as u64)) << 2);
        v = ((v >> 4) & (0x0F0F0F0F0F0F0F0F as u64)) | ((v & (0x0F0F0F0F0F0F0F0F as u64)) << 4);

        Self {
            state: v.swap_bytes(),
        }
    }

    /// Right rotation of `shift` bits.
    ///
    /// Shifts the bits to the right, wrapping the truncated bits to the end of the bitset.
    ///
    /// The rotation is done in-place, so the bitset needs to be mutable.
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    ///
    /// let mut bs = DenseBitSet::from_integer(0b111000111000111000111);
    /// bs.rotr(10);
    ///
    /// assert_eq!(bs.to_integer(), 0b111000111000000000000000000000000000000000000000000011100011100 );
    /// ```
    pub fn rotr(&mut self, shift: u32) {
        self.state = self.state.rotate_right(shift);
    }

    /// Left rotation of `shift` bits.
    ///
    /// Shifts the bits to the left, wrapping the truncated bits to the beginning of the bitset.
    ///  
    /// The rotation is done in place, so the bitset needs to be mutable.
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    ///
    /// let mut bs = DenseBitSet::from_integer(0b111000111000111000111);
    /// bs.rotl(10);
    ///
    /// assert_eq!(bs.to_integer(), 0b1110001110001110001110000000000 );
    /// ```
    pub fn rotl(&mut self, shift: u32) {
        self.state = self.state.rotate_left(shift);
    }

    /// Returns the position of the first set bit (little endian convention)
    ///
    /// # Example
    /// ```
    /// # use rust_dense_bitset::DenseBitSet;
    /// let dbs = DenseBitSet::from_integer(256);
    /// println!("{}", dbs.first_set());
    /// ```
    pub fn first_set(self) -> u32 {
        self.state.trailing_zeros()
    }
}

/// This is a compact implementation of the `BitSet` trait over a 64-bit word (which is the native
/// word size for many architectures), allowing for efficient operations and compact memory usage.
///
/// Modifiers and accessors are boundary checked to ensure that operations remain within that 64 bit range.
///
/// Note: The `BitSet` trait must be in scope in order to use methods from this trait.
impl BitSet for DenseBitSet {
    /// Sets the bit at index `position` to `value`.
    /// The bitset needs to be mutable for this operation to succeed.
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    /// use rust_dense_bitset::BitSet;
    ///
    /// let mut bs = DenseBitSet::new();
    /// bs.set_bit(25, true); // This sets the bit at index 25 , hence the 26th bit -> 2^25
    ///
    /// assert_eq!(bs.to_integer(), 33554432);
    /// ```
    fn set_bit(&mut self, position: usize, value: bool) {
        assert!(
            position < 64,
            "This implementation is currently limited to 64 bit bitsets."
        );
        if value {
            self.state |= 1 << position
        } else {
            self.state &= !(1 << position)
        }
    }

    /// Get the bit at index `position`.
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    /// use rust_dense_bitset::BitSet;
    ///
    /// let bs = DenseBitSet::from_integer(65536);
    ///
    /// assert!(bs.get_bit(16));
    /// ```
    fn get_bit(&self, position: usize) -> bool {
        assert!(
            position < 64,
            "This implementation is currently limited to 64 bit bitsets."
        );

        (self.state >> position) & 1 == 1
    }

    /// Returns the bitset's Hamming weight (in other words, the number of bits set to true).
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    /// use rust_dense_bitset::BitSet;
    ///
    /// let bs = DenseBitSet::from_integer(0b01100100111010);
    ///
    /// println!("{}", bs.get_weight()); // -> 7
    /// ```
    fn get_weight(&self) -> u32 {
        self.state.count_ones()
    }

    /// This resets the bitset to its empty state.
    /// (The bitset must be mutable for this operation).
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    /// use rust_dense_bitset::BitSet;
    ///
    /// let mut bs = DenseBitSet::from_integer(1234567890);
    /// bs.reset();
    ///
    /// assert!(bs.none());
    /// ```
    fn reset(&mut self) {
        self.state = 0
    }

    /// Returns a representation of the bitset as a `String`.
    ///
    /// # Example
    /// ```
    /// use rust_dense_bitset::DenseBitSet;
    /// use rust_dense_bitset::BitSet;
    ///
    /// let bs = DenseBitSet::from_integer(68719481088);
    ///
    /// println!("{}", bs.to_string()) // -> "0000000000000000000000000001000000000000000000000001000100000000"
    /// ```
    fn to_string(self) -> String {
        format!("{:064b}", self.state)
    }
}

impl fmt::Debug for DenseBitSet {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:064b}", self.to_integer())
    }
}

impl PartialEq for DenseBitSet {
    fn eq(&self, other: &Self) -> bool {
        self.state == other.to_integer()
    }
}

impl Eq for DenseBitSet {}

impl Hash for DenseBitSet {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.state.hash(state);
    }
}

impl BitAnd for DenseBitSet {
    type Output = Self;
    fn bitand(self, rhs: Self) -> Self {
        Self {
            state: self.state & rhs.state,
        }
    }
}

impl BitAndAssign for DenseBitSet {
    fn bitand_assign(&mut self, rhs: Self) {
        self.state &= rhs.state;
    }
}

impl BitOr for DenseBitSet {
    type Output = Self;
    fn bitor(self, rhs: Self) -> Self {
        Self {
            state: self.state | rhs.state,
        }
    }
}

impl BitOrAssign for DenseBitSet {
    fn bitor_assign(&mut self, rhs: Self) {
        self.state |= rhs.state;
    }
}

impl BitXor for DenseBitSet {
    type Output = Self;
    fn bitxor(self, rhs: Self) -> Self {
        Self {
            state: self.state ^ rhs.state,
        }
    }
}

impl BitXorAssign for DenseBitSet {
    fn bitxor_assign(&mut self, rhs: Self) {
        self.state ^= rhs.state;
    }
}

impl Not for DenseBitSet {
    type Output = Self;
    fn not(self) -> Self {
        Self { state: !self.state }
    }
}

impl Shl<usize> for DenseBitSet {
    type Output = Self;
    fn shl(self, rhs: usize) -> Self {
        if rhs >= 64 {
            Self { state: 0 }
        } else {
            Self {
                state: self.state << rhs,
            }
        }
    }
}

impl ShlAssign<usize> for DenseBitSet {
    fn shl_assign(&mut self, rhs: usize) {
        if rhs >= 64 {
            self.reset();
        } else {
            self.state <<= rhs;
        }
    }
}

impl Shr<usize> for DenseBitSet {
    type Output = Self;
    fn shr(self, rhs: usize) -> Self {
        if rhs >= 64 {
            Self { state: 0 }
        } else {
            Self {
                state: self.state >> rhs,
            }
        }
    }
}

impl ShrAssign<usize> for DenseBitSet {
    fn shr_assign(&mut self, rhs: usize) {
        if rhs >= 64 {
            self.reset();
        } else {
            self.state >>= rhs;
        }
    }
}