# BitFixed
`BitFixed` is a fixed-size bitset data structure in the FastBit library, providing efficient storage and manipulation of a fixed number of bits.
## Overview
`BitFixed<W>` is a memory-efficient, fixed-capacity bit array that stores a sequence of bits using word-sized integers as the underlying storage. Unlike `BitVec`, `BitFixed` does not support dynamic resizing beyond its initial allocation (though it does have a `resize` method that reallocates).
The type parameter `W` represents the word type used for storage and must implement the `BitWord` trait. Common word types include `u8`, `u16`, `u32`, `u64`, `u128`, and `usize`.
## Memory Layout
`BitFixed` uses a raw pointer to a contiguous array of word-sized integers, where each bit in the words represents a bit in the bitset. The structure contains:
- `ptr`: A non-null pointer to the allocated memory
- `len`: The number of bits in the bitset
The memory is automatically deallocated when the `BitFixed` instance is dropped.
## Usage
### Creating a BitFixed
```rust
use fastbit::{BitFixed, BitRead, BitWrite};
// Create a new BitFixed with 32 bits
let mut bf: BitFixed<u16> = BitFixed::new(32);
// Create an uninitialized BitFixed (faster but contains garbage values)
let mut bf_uninit: BitFixed<u32> = BitFixed::new_uninit(64);
```
### Basic Operations
```rust
use fastbit::{BitFixed, BitRead, BitWrite};
let mut bf: BitFixed<usize> = BitFixed::new(100);
// Set bits
bf.set(10);
bf.set(20);
bf.set(30);
// Test bits
assert!(bf.test(10));
assert!(!bf.test(11));
// Reset (clear) bits
bf.reset(10);
assert!(!bf.test(10));
// Flip bits
bf.flip(20);
assert!(!bf.test(20));
bf.flip(20);
assert!(bf.test(20));
// Test and set (returns previous value)
assert!(!bf.test_and_set(40));
assert!(bf.test_and_set(40));
// Fill all bits
bf.fill();
assert!(bf.all());
// Clear all bits
bf.clear();
assert!(bf.none());
```
### Querying
```rust
use fastbit::{BitFixed, BitRead, BitWrite};
let mut bf: BitFixed<u64> = BitFixed::new(128);
bf.set(10);
bf.set(64);
bf.set(127);
// Count set bits
assert_eq!(bf.count_ones(), 3);
// Check if any bits are set
assert!(bf.any());
// Check if all bits are set
assert!(!bf.all());
// Check if no bits are set
assert!(!bf.none());
// Get the length in bits
assert_eq!(bf.len(), 128);
// Check if empty (zero length)
assert!(!bf.is_empty());
```
### Iteration
```rust
use fastbit::{BitFixed, BitRead};
let mut bf: BitFixed<u8> = BitFixed::new(16);
bf.set(3);
bf.set(7);
bf.set(11);
// Iterate over set bits
let set_bits: Vec<usize> = bf.iter().collect();
assert_eq!(set_bits, vec![3, 7, 11]);
```
### Bitwise Operations
```rust
use fastbit::{BitFixed, BitRead, BitWrite};
use std::ops::{BitAnd, BitOr, BitXor, Not};
let mut bf1: BitFixed<usize> = BitFixed::new(8);
let mut bf2: BitFixed<usize> = BitFixed::new(8);
bf1.set(1);
bf1.set(3);
bf1.set(5);
bf2.set(3);
bf2.set(4);
bf2.set(5);
// Bitwise AND
let bf_and = &bf1 & &bf2;
assert!(bf_and.test(3));
assert!(bf_and.test(5));
assert!(!bf_and.test(1));
assert!(!bf_and.test(4));
// Bitwise OR
let bf_or = &bf1 | &bf2;
assert!(bf_or.test(1));
assert!(bf_or.test(3));
assert!(bf_or.test(4));
assert!(bf_or.test(5));
// Bitwise XOR
let bf_xor = bf1.bitxor(&bf2);
assert!(bf_xor.test(1));
assert!(!bf_xor.test(3));
assert!(bf_xor.test(4));
assert!(!bf_xor.test(5));
// Bitwise NOT
let bf_not = !&bf1;
assert!(!bf_not.test(1));
assert!(!bf_not.test(3));
assert!(!bf_not.test(5));
assert!(bf_not.test(0));
assert!(bf_not.test(2));
assert!(bf_not.test(4));
assert!(bf_not.test(6));
assert!(bf_not.test(7));
// In-place operations
bf1 &= &bf2; // AND assign
```
### Set Operations
```rust
use fastbit::{BitFixed, BitRead, BitWrite};
let mut bf1: BitFixed<u32> = BitFixed::new(16);
let mut bf2: BitFixed<u32> = BitFixed::new(16);
bf1.set(1);
bf1.set(3);
bf1.set(5);
bf2.set(3);
bf2.set(7);
bf2.set(9);
// Check if two bitsets are disjoint (no bits in common)
assert!(!bf1.is_disjoint(&bf2));
// Count the number of bits in the intersection
assert_eq!(bf1.intersection_count(&bf2), 1);
// Copy from another bitset
bf1.copy_from(&bf2);
assert!(bf1.test(3));
assert!(bf1.test(7));
assert!(bf1.test(9));
```
### Views and Conversions
```rust
use fastbit::{BitFixed, BitView, BitViewMut};
let mut bf: BitFixed<usize> = BitFixed::new(64);
bf.set(10);
bf.set(20);
// Get a read-only view
let view: BitView<usize> = bf.as_view();
assert!(view.test(10));
// Get a mutable view
let mut view_mut: BitViewMut<usize> = bf.as_view_mut();
view_mut.set(30);
assert!(bf.test(30));
// Convert from references
let view_from_ref: BitView<usize> = (&bf).into();
let view_mut_from_ref: BitViewMut<usize> = (&mut bf).into();
```
## API Reference
### Constructors
- `new(bit_len: usize) -> Self`: Creates a new, zero-initialized bitset with the specified number of bits.
- `new_uninit(bit_len: usize) -> Self`: Creates a new, uninitialized bitset with the specified number of bits.
### Capacity
- `len(&self) -> usize`: Returns the number of bits in the bitset.
- `is_empty(&self) -> bool`: Returns true if the bitset has zero length.
- `capacity(&self) -> usize`: Returns the capacity in bits (rounded up to the nearest word boundary).
- `resize(&mut self, new_bit_len: usize)`: Resizes the bitset to the new length.
### Bit Operations
- `test(&self, idx: usize) -> bool`: Returns true if the bit at position `idx` is set.
- `set(&mut self, idx: usize)`: Sets the bit at position `idx`.
- `reset(&mut self, idx: usize)`: Clears the bit at position `idx`.
- `flip(&mut self, idx: usize)`: Flips the bit at position `idx`.
- `test_and_set(&mut self, idx: usize) -> bool`: Sets the bit at position `idx` and returns the previous value.
- `fill(&mut self)`: Sets all bits to 1.
- `clear(&mut self)`: Clears all bits to 0.
### Queries
- `count_ones(&self) -> usize`: Returns the number of set bits.
- `all(&self) -> bool`: Returns true if all bits are set.
- `any(&self) -> bool`: Returns true if any bit is set.
- `none(&self) -> bool`: Returns true if no bits are set.
### Set Operations
- `is_disjoint(&self, other: &Self) -> bool`: Returns true if the two bitsets have no bits in common.
- `intersection_count(&self, other: &Self) -> usize`: Returns the number of bits set in both bitsets.
- `copy_from(&mut self, other: &Self)`: Copies all bits from `other` to `self`.
### Views and Iteration
- `iter(&self) -> Iter<W>`: Returns an iterator over the set bits.
- `as_view(&self) -> BitView<'_, W>`: Returns a read-only view of the bitset.
- `as_view_mut(&self) -> BitViewMut<'_, W>`: Returns a mutable view of the bitset.
### Bitwise Operations
- `&`: Bitwise AND
- `|`: Bitwise OR
- `^`: Bitwise XOR
- `!`: Bitwise NOT
- `&=`: Bitwise AND assign
- `|=`: Bitwise OR assign
- `^=`: Bitwise XOR assign
## Implementation Details
`BitFixed` uses raw pointers and unsafe Rust to manage memory efficiently. The implementation:
1. Allocates memory for the bitset using `std::alloc::alloc`
2. Manages the memory with `NonNull<W>` to ensure the pointer is never null
3. Deallocates memory in the `Drop` implementation
4. Uses word-level operations for efficiency
5. Implements standard traits like `Clone`, `PartialEq`, `Eq`, and `Hash`
## Performance Considerations
- `BitFixed` is more memory-efficient than `Vec<bool>` as it uses one bit per boolean value
- Operations like `set`, `reset`, and `test` are constant time O(1)
- Bitwise operations operate on words, making them very efficient
- The `resize` operation requires reallocation and copying, which is O(n)
- `BitFixed` has less overhead than `BitVec` since it doesn't track capacity separately
## Differences from BitVec
While `BitVec` and `BitFixed` share many similarities, there are key differences:
1. `BitFixed` has a fixed capacity after creation (though it can be resized with reallocation)
2. `BitVec` tracks capacity separately from length, allowing for more efficient growth
3. `BitFixed` has slightly less memory overhead (no capacity field)
4. `BitVec` is more suitable for cases where the size may change frequently
5. `BitFixed` is more suitable for cases where the size is known in advance
## Thread Safety
`BitFixed` does not implement `Send` or `Sync` automatically. Care should be taken when sharing instances between threads.