oxihuman_core/
bitmap_index.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5//! Bitmap-based index for fast set membership and intersection queries.
6
7/// A bitmap index storing up to `capacity` bits.
8#[allow(dead_code)]
9#[derive(Debug, Clone)]
10pub struct BitmapIndex {
11    words: Vec<u64>,
12    capacity: usize,
13}
14
15#[allow(dead_code)]
16impl BitmapIndex {
17    pub fn new(capacity: usize) -> Self {
18        let word_count = capacity.div_ceil(64);
19        Self {
20            words: vec![0u64; word_count],
21            capacity,
22        }
23    }
24
25    pub fn set(&mut self, bit: usize) {
26        if bit < self.capacity {
27            self.words[bit / 64] |= 1u64 << (bit % 64);
28        }
29    }
30
31    pub fn clear_bit(&mut self, bit: usize) {
32        if bit < self.capacity {
33            self.words[bit / 64] &= !(1u64 << (bit % 64));
34        }
35    }
36
37    pub fn get(&self, bit: usize) -> bool {
38        if bit < self.capacity {
39            (self.words[bit / 64] >> (bit % 64)) & 1 == 1
40        } else {
41            false
42        }
43    }
44
45    pub fn count_ones(&self) -> usize {
46        self.words.iter().map(|w| w.count_ones() as usize).sum()
47    }
48
49    pub fn capacity(&self) -> usize {
50        self.capacity
51    }
52
53    pub fn intersect(&self, other: &Self) -> Self {
54        let cap = self.capacity.min(other.capacity);
55        let wc = self.words.len().min(other.words.len());
56        let mut result = Self::new(cap);
57        #[allow(clippy::needless_range_loop)]
58        for i in 0..wc {
59            result.words[i] = self.words[i] & other.words[i];
60        }
61        result
62    }
63
64    pub fn union(&self, other: &Self) -> Self {
65        let cap = self.capacity.max(other.capacity);
66        let mut result = Self::new(cap);
67        #[allow(clippy::needless_range_loop)]
68        for i in 0..self.words.len().max(other.words.len()) {
69            let a = if i < self.words.len() {
70                self.words[i]
71            } else {
72                0
73            };
74            let b = if i < other.words.len() {
75                other.words[i]
76            } else {
77                0
78            };
79            result.words[i] = a | b;
80        }
81        result
82    }
83
84    pub fn clear_all(&mut self) {
85        for w in &mut self.words {
86            *w = 0;
87        }
88    }
89
90    pub fn is_empty(&self) -> bool {
91        self.words.iter().all(|&w| w == 0)
92    }
93
94    pub fn first_set(&self) -> Option<usize> {
95        for (i, &w) in self.words.iter().enumerate() {
96            if w != 0 {
97                let bit = i * 64 + w.trailing_zeros() as usize;
98                if bit < self.capacity {
99                    return Some(bit);
100                }
101            }
102        }
103        None
104    }
105}
106
107#[cfg(test)]
108mod tests {
109    use super::*;
110
111    #[test]
112    fn new_bitmap_is_empty() {
113        let b = BitmapIndex::new(128);
114        assert!(b.is_empty());
115        assert_eq!(b.count_ones(), 0);
116    }
117
118    #[test]
119    fn set_and_get() {
120        let mut b = BitmapIndex::new(100);
121        b.set(42);
122        assert!(b.get(42));
123        assert!(!b.get(43));
124    }
125
126    #[test]
127    fn clear_bit() {
128        let mut b = BitmapIndex::new(64);
129        b.set(10);
130        b.clear_bit(10);
131        assert!(!b.get(10));
132    }
133
134    #[test]
135    fn count_ones_accurate() {
136        let mut b = BitmapIndex::new(200);
137        b.set(0);
138        b.set(63);
139        b.set(64);
140        b.set(199);
141        assert_eq!(b.count_ones(), 4);
142    }
143
144    #[test]
145    fn intersect_works() {
146        let mut a = BitmapIndex::new(128);
147        let mut b = BitmapIndex::new(128);
148        a.set(5);
149        a.set(10);
150        b.set(10);
151        b.set(20);
152        let c = a.intersect(&b);
153        assert!(c.get(10));
154        assert!(!c.get(5));
155        assert!(!c.get(20));
156    }
157
158    #[test]
159    fn union_works() {
160        let mut a = BitmapIndex::new(128);
161        let mut b = BitmapIndex::new(128);
162        a.set(3);
163        b.set(7);
164        let c = a.union(&b);
165        assert!(c.get(3));
166        assert!(c.get(7));
167    }
168
169    #[test]
170    fn clear_all_resets() {
171        let mut b = BitmapIndex::new(64);
172        b.set(0);
173        b.set(63);
174        b.clear_all();
175        assert!(b.is_empty());
176    }
177
178    #[test]
179    fn first_set_finds_lowest() {
180        let mut b = BitmapIndex::new(128);
181        b.set(70);
182        b.set(30);
183        assert_eq!(b.first_set(), Some(30));
184    }
185
186    #[test]
187    fn out_of_bounds_ignored() {
188        let mut b = BitmapIndex::new(10);
189        b.set(100); // no panic
190        assert!(!b.get(100));
191    }
192
193    #[test]
194    fn capacity_returns_max() {
195        let b = BitmapIndex::new(256);
196        assert_eq!(b.capacity(), 256);
197    }
198}
oxihuman_core/bitmap_index.rs

oxihuman_core/
bitmap_index.rs
