synthphonia/tree_learning/
bits.rs

1use std::u128;
2
3pub type Bits = Box<[u128]>;
4
5/// A trait defining extended operations on box slices, particularly focused on bit manipulation. 
6/// 
7/// 
8/// This trait provides methods to create a new instance from an iterator of boolean values, initialize slices filled with zeros or ones, and count the number of ones in the slice. 
9/// It also includes methods to perform bitwise conjunction, union, and difference operations in place, while offering functionality to check if a slice is a subset of another and to access the boolean value at a specific index. 
10/// These operations facilitate efficient manipulation and querying of boxed slices as bit arrays.
11pub trait BoxSliceExt {
12    fn from_bit_siter(t: impl ExactSizeIterator<Item = bool>) -> Self;
13    fn zeros(len: usize) -> Self;
14    fn ones(len: usize) -> Self;
15    fn count_ones(&self) -> u32;
16    fn conjunction_assign(&mut self, other: &Self);
17    fn union_assign(&mut self, other: &Self);
18    fn difference_assign(&mut self, other: &Self);
19    fn subset(&self, other: &Self) -> bool;
20    fn get(&self, index: usize) -> bool;
21    
22}
23/// Calculates the ceiling of the division of two unsigned integers. 
24/// 
25/// This function takes two parameters, `a` and `b`, both of the type `usize`, and returns the smallest integer greater than or equal to the result of dividing `a` by `b`. 
26/// It utilizes the `div_ceil` method to perform the calculation, which inherently manages any need to round up the result of the division when `a` is not perfectly divisible by `b`. 
27/// This function is useful in scenarios where precise ceiling division is required.
28/// 
29fn ceildiv(a: usize, b: usize) -> usize {
30    a.div_ceil(b)
31}
32
33impl BoxSliceExt for Box<[u128]> {
34    /// Creates a boxed slice of `u128` integers, initializing each value to zero. 
35    /// 
36    /// It achieves this by calculating the necessary length in terms of `u128` blocks to cover the specified `len` in bits and then mapping over this range, collecting zeros into a boxed slice. 
37    /// The process involves using a ceiling division to ensure sufficient space is allocated, corresponding to the bit width of `u128`.
38    /// 
39    fn zeros(len: usize) -> Self {
40        (0..ceildiv(len, u128::BITS as usize)).map(|_| 0u128).collect()
41    }
42    /// Creates a new boxed slice of `u128` integers each filled with the value `u128::MAX`, with partial bit masking applied to the last element if the specified length does not directly align with a multiple of `u128`'s bit size. 
43    /// 
44    /// This function initializes a vector by determining the number of `u128` elements required via ceiling division, fills it with maximum possible 128-bit unsigned integers, and then collects this into a boxed slice. 
45    /// If the intended length in bits leaves a remainder that isn't a full `u128`, the final element is appropriately masked to ensure only the requisite bits are set to one, maintaining the defined length.
46    /// 
47    fn ones(len: usize) -> Self {
48        let mut result: Self = (0..ceildiv(len, u128::BITS as usize)).map(|_| u128::MAX).collect();
49        if len % u128::BITS as usize != 0 {
50            result.last_mut().map(|x| *x &= (1 << (len % u128::BITS as usize)) - 1);
51        }
52        result
53    }
54
55    /// Provides a method that calculates the total number of one-bits in a boxed slice of `u128` integers. 
56    /// 
57    /// It iterates over each `u128` value in the slice, applies the `count_ones` method to obtain the number of one-bits for each element, and sums these counts to return the cumulative total as a `u32`. 
58    /// This operation enables efficient bit counting across potentially large numeric sequences.
59    /// 
60    fn count_ones(&self) -> u32 {
61        self.iter().map(|x| x.count_ones()).sum()
62    }
63    
64    /// Performs an in-place bitwise conjunction between two slices of `u128`. 
65    /// 
66    /// This operation modifies the elements of the caller slice by iterating through it, paired with elements from the `other` slice, applying a bitwise AND operation, and storing the result back into the caller slice elements. 
67    /// Each element in the slice is processed in sequence such that their corresponding positions between the two slices are combined using the AND operation.
68    /// 
69    fn conjunction_assign(&mut self, other: &Self) {
70        self.iter_mut().zip(other.iter()).for_each(|(i, j)| *i &= j);
71    }
72    /// Performs an in-place union operation between two boxed slices. 
73    /// 
74    /// This method iterates over each element of the boxed slice and the corresponding element of another boxed slice, applying the bitwise OR operation. 
75    /// The result of this operation updates the elements of the boxed slice on which the method is called (`self`). 
76    /// This allows for the combination of elements in two slices, storing the union of each pair of elements from the slices into the first slice. 
77    /// This operation assumes both slices have the same length, as it utilizes the `zip` method to combine elements from `self` and `other`.
78    /// 
79    fn union_assign(&mut self, other: &Self) {
80        self.iter_mut().zip(other.iter()).for_each(|(i, j)| *i |= j);
81    }
82    
83    /// Calculates the difference between the current boxed slice of `u128` integers and another slice, assigning the result to the current instance. 
84    /// This method iterates through both slices in parallel, applying a bitwise AND with the negation operation on each corresponding pair of elements, thereby effectively subtracting the bit representation of the elements from `other` out of the current slice's elements.
85    fn difference_assign(&mut self, other: &Self) {
86        self.iter_mut().zip(other.iter()).for_each(|(i, j)| *i &= !j);
87    }
88
89    /// Determines if one boxed slice of `u128` integers is a subset of another. 
90    /// 
91    /// This functionality is executed by comparing each integer in the `other` slice with the corresponding integer in `self` slice. 
92    /// The method utilizes bitwise AND operation to ascertain that every integer in `self` is contained within the same indexed position in `other`. 
93    /// The method returns true only if this condition holds for every pair of integers throughout the slices, indicating that `self` is indeed a subset of `other`.
94    /// 
95    fn subset(&self, other: &Self) -> bool {
96        other.iter().zip(self.iter()).all(|(i, j)| i & j == *j)
97    }
98    
99    /// Constructs a boxed slice of `u128` integers from an iterator of boolean values. 
100    /// 
101    /// The function takes an `ExactSizeIterator` of `bool` items and initializes a `Vec<u128>` large enough to represent each boolean value as a bit within `u128` segments. 
102    /// It calculates the necessary number of `u128` elements using a ceiling division based on the iterator's length divided by 128. 
103    /// As it iterates over the boolean items, it appropriately sets bits in the `u128` segments depending on their indexes. 
104    /// This results in a bit-packed representation of the iterator's boolean sequence, which is then converted into a boxed slice for returned storage efficiency.
105    /// 
106    fn from_bit_siter(t: impl ExactSizeIterator<Item = bool>) -> Self {
107        let mut res = vec![0u128; ceildiv(t.len(), 128)];
108        for (i, b) in t.enumerate() {
109            if b {
110                res[i / 128] |= 1 << (i % 128);
111            }
112        }
113        res.into_boxed_slice()
114    }
115    
116    /// Returns the boolean value of the bit at the given index for a boxed slice of `u128` integers. 
117    /// 
118    /// This function calculates the position of the bit within the slice by dividing the `index` by 128 to locate the correct `u128` integer and then using the modulus operation to determine the bit position within that integer. 
119    /// It then uses bitwise operations to isolate the bit at the specified index and checks whether it is set, returning `true` if the bit is `1` and `false` otherwise.
120    /// 
121    fn get(&self, index: usize) -> bool {
122        self[index / 128] & (1 << (index % 128)) != 0
123    }
124}
125
126/// Creates a boxed slice of `u128` filled with binary ones, with the specified length in bits. 
127/// 
128/// The function calculates the number of `u128` elements needed to represent the given `size` in bits, taking into account the bit width of `u128`. 
129/// It uses a ceiling division to ensure all bits are accommodated. 
130/// Each element of the boxed slice is filled with ones, except for the last element, which is calculated to fit only the remaining bits required. 
131/// The resulting boxed slice represents a sequence of `u128` values with all bits set to one up to the specified bit length.
132/// 
133pub fn boxed_ones(size: usize) -> Box<[u128]> {
134    let l = ceildiv(size, u128::BITS as usize);
135    let rem = size as u32 % u128::BITS;
136    (0..l).map(|i| if i + 1 == l { (1 << rem) - 1 } else { u128::MAX }).collect()
137}
138
139#[cfg(test)]
140mod test {
141    use super::BoxSliceExt;
142
143    #[test]
144    fn test() {
145        for i in 0..=256 {
146            let a = Box::ones(i);
147            assert_eq!(i, a.iter().map(|x| x.count_ones() as usize).sum::<usize>());
148        }
149    }
150}