oxihuman_core/
bit_set.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5/// A compact bitset for tracking boolean flags by index.
6#[allow(dead_code)]
7#[derive(Debug, Clone)]
8pub struct BitSet {
9    words: Vec<u64>,
10}
11
12#[allow(dead_code)]
13impl BitSet {
14    pub fn new() -> Self {
15        Self { words: Vec::new() }
16    }
17
18    pub fn with_capacity(bits: usize) -> Self {
19        let words = bits.div_ceil(64);
20        Self {
21            words: vec![0u64; words],
22        }
23    }
24
25    pub fn set(&mut self, index: usize) {
26        let word = index / 64;
27        let bit = index % 64;
28        if word >= self.words.len() {
29            self.words.resize(word + 1, 0);
30        }
31        self.words[word] |= 1u64 << bit;
32    }
33
34    pub fn clear_bit(&mut self, index: usize) {
35        let word = index / 64;
36        let bit = index % 64;
37        if word < self.words.len() {
38            self.words[word] &= !(1u64 << bit);
39        }
40    }
41
42    pub fn test(&self, index: usize) -> bool {
43        let word = index / 64;
44        let bit = index % 64;
45        if word >= self.words.len() {
46            return false;
47        }
48        (self.words[word] & (1u64 << bit)) != 0
49    }
50
51    pub fn count_ones(&self) -> usize {
52        self.words.iter().map(|w| w.count_ones() as usize).sum()
53    }
54
55    pub fn is_empty(&self) -> bool {
56        self.words.iter().all(|&w| w == 0)
57    }
58
59    pub fn clear(&mut self) {
60        for w in &mut self.words {
61            *w = 0;
62        }
63    }
64
65    pub fn union(&self, other: &BitSet) -> BitSet {
66        let len = self.words.len().max(other.words.len());
67        let mut result = BitSet::with_capacity(len * 64);
68        for i in 0..len {
69            let a = self.words.get(i).copied().unwrap_or(0);
70            let b = other.words.get(i).copied().unwrap_or(0);
71            result.words[i] = a | b;
72        }
73        result
74    }
75
76    pub fn intersection(&self, other: &BitSet) -> BitSet {
77        let len = self.words.len().min(other.words.len());
78        let mut result = BitSet::with_capacity(len * 64);
79        for i in 0..len {
80            result.words[i] = self.words[i] & other.words[i];
81        }
82        result
83    }
84
85    pub fn capacity_bits(&self) -> usize {
86        self.words.len() * 64
87    }
88}
89
90impl Default for BitSet {
91    fn default() -> Self {
92        Self::new()
93    }
94}
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99
100    #[test]
101    fn test_new_empty() {
102        let bs = BitSet::new();
103        assert!(bs.is_empty());
104        assert_eq!(bs.count_ones(), 0);
105    }
106
107    #[test]
108    fn test_set_and_test() {
109        let mut bs = BitSet::new();
110        bs.set(5);
111        assert!(bs.test(5));
112        assert!(!bs.test(4));
113    }
114
115    #[test]
116    fn test_clear_bit() {
117        let mut bs = BitSet::new();
118        bs.set(10);
119        bs.clear_bit(10);
120        assert!(!bs.test(10));
121    }
122
123    #[test]
124    fn test_count_ones() {
125        let mut bs = BitSet::new();
126        bs.set(0);
127        bs.set(63);
128        bs.set(64);
129        assert_eq!(bs.count_ones(), 3);
130    }
131
132    #[test]
133    fn test_clear() {
134        let mut bs = BitSet::new();
135        bs.set(1);
136        bs.set(100);
137        bs.clear();
138        assert!(bs.is_empty());
139    }
140
141    #[test]
142    fn test_union() {
143        let mut a = BitSet::new();
144        a.set(1);
145        let mut b = BitSet::new();
146        b.set(2);
147        let u = a.union(&b);
148        assert!(u.test(1));
149        assert!(u.test(2));
150    }
151
152    #[test]
153    fn test_intersection() {
154        let mut a = BitSet::new();
155        a.set(1);
156        a.set(2);
157        let mut b = BitSet::new();
158        b.set(2);
159        b.set(3);
160        let inter = a.intersection(&b);
161        assert!(!inter.test(1));
162        assert!(inter.test(2));
163        assert!(!inter.test(3));
164    }
165
166    #[test]
167    fn test_with_capacity() {
168        let bs = BitSet::with_capacity(128);
169        assert_eq!(bs.capacity_bits(), 128);
170    }
171
172    #[test]
173    fn test_large_index() {
174        let mut bs = BitSet::new();
175        bs.set(1000);
176        assert!(bs.test(1000));
177        assert!(!bs.test(999));
178    }
179
180    #[test]
181    fn test_test_out_of_range() {
182        let bs = BitSet::new();
183        assert!(!bs.test(500));
184    }
185}
oxihuman_core/bit_set.rs

oxihuman_core/
bit_set.rs
