16994f6b1SLoGin use core::{intrinsics::unlikely, marker::PhantomData}; 26994f6b1SLoGin 36994f6b1SLoGin use crate::traits::BitOps; 46994f6b1SLoGin 5*b2ca6800SLoGin pub(crate) struct BitMapCore<T: BitOps> { 66994f6b1SLoGin phantom: PhantomData<T>, 76994f6b1SLoGin } 86994f6b1SLoGin 9*b2ca6800SLoGin impl<T: BitOps> BitMapCore<T> { 106994f6b1SLoGin pub const fn new() -> Self { 116994f6b1SLoGin Self { 126994f6b1SLoGin phantom: PhantomData, 136994f6b1SLoGin } 146994f6b1SLoGin } 156994f6b1SLoGin 166994f6b1SLoGin /// 获取位图中的某一位 17*b2ca6800SLoGin pub(crate) fn get(&self, n: usize, data: &[T], index: usize) -> Option<bool> { 18*b2ca6800SLoGin if unlikely(index >= n) { 196994f6b1SLoGin return None; 206994f6b1SLoGin } 216994f6b1SLoGin 226994f6b1SLoGin let element_index = index / T::bit_size(); 236994f6b1SLoGin let bit_index = index % T::bit_size(); 246994f6b1SLoGin 256994f6b1SLoGin let element = data.get(element_index)?; 266994f6b1SLoGin let bit = <T as BitOps>::get(element, bit_index); 276994f6b1SLoGin 286994f6b1SLoGin Some(bit) 296994f6b1SLoGin } 306994f6b1SLoGin 316994f6b1SLoGin /// 设置位图中的某一位 32*b2ca6800SLoGin pub(crate) fn set(&self, n: usize, data: &mut [T], index: usize, value: bool) -> Option<bool> { 33*b2ca6800SLoGin if unlikely(index >= n) { 346994f6b1SLoGin return None; 356994f6b1SLoGin } 366994f6b1SLoGin let element_index = index / T::bit_size(); 376994f6b1SLoGin let bit_index = index % T::bit_size(); 386994f6b1SLoGin 396994f6b1SLoGin let element = data.get_mut(element_index)?; 406994f6b1SLoGin let bit = <T as BitOps>::set(element, bit_index, value); 416994f6b1SLoGin 426994f6b1SLoGin Some(bit) 436994f6b1SLoGin } 446994f6b1SLoGin 45*b2ca6800SLoGin pub(crate) fn set_all(&self, n: usize, data: &mut [T], value: bool) { 466994f6b1SLoGin let val = if value { T::max() } else { T::zero() }; 476994f6b1SLoGin for element in data.iter_mut() { 486994f6b1SLoGin *element = val; 496994f6b1SLoGin } 506994f6b1SLoGin 516994f6b1SLoGin // 特殊处理最后一个元素 526994f6b1SLoGin let last_element = data.last_mut().unwrap(); 53*b2ca6800SLoGin let mask = T::make_mask(n % T::bit_size()); 546994f6b1SLoGin if mask != T::zero() { 556994f6b1SLoGin *last_element &= mask; 566994f6b1SLoGin } 576994f6b1SLoGin } 586994f6b1SLoGin 596994f6b1SLoGin /// 获取位图中第一个为1的位 606994f6b1SLoGin pub(crate) fn first_index(&self, data: &[T]) -> Option<usize> { 616994f6b1SLoGin for (i, element) in data.iter().enumerate() { 626994f6b1SLoGin let bit = <T as BitOps>::first_index(element); 636994f6b1SLoGin if bit.is_some() { 646994f6b1SLoGin return Some(i * T::bit_size() + bit.unwrap()); 656994f6b1SLoGin } 666994f6b1SLoGin } 676994f6b1SLoGin 686994f6b1SLoGin None 696994f6b1SLoGin } 706994f6b1SLoGin 716994f6b1SLoGin /// 获取位图中第一个为0的位 72*b2ca6800SLoGin pub(crate) fn first_false_index(&self, n: usize, data: &[T]) -> Option<usize> { 736994f6b1SLoGin for (i, element) in data.iter().enumerate() { 746994f6b1SLoGin if let Some(bit) = <T as BitOps>::first_false_index(element) { 75*b2ca6800SLoGin return self.make_index(n, i * T::bit_size() + bit); 766994f6b1SLoGin } 776994f6b1SLoGin } 786994f6b1SLoGin 796994f6b1SLoGin None 806994f6b1SLoGin } 816994f6b1SLoGin 826994f6b1SLoGin /// 获取位图中最后一个为1的位 83*b2ca6800SLoGin pub(crate) fn last_index(&self, n: usize, data: &[T]) -> Option<usize> { 846994f6b1SLoGin for (i, element) in data.iter().enumerate().rev() { 856994f6b1SLoGin if let Some(bit) = <T as BitOps>::last_index(element) { 86*b2ca6800SLoGin return self.make_index(n, i * T::bit_size() + bit); 876994f6b1SLoGin } 886994f6b1SLoGin } 896994f6b1SLoGin 906994f6b1SLoGin None 916994f6b1SLoGin } 926994f6b1SLoGin 936994f6b1SLoGin /// 获取位图中最后一个为0的位 946994f6b1SLoGin /// 956994f6b1SLoGin /// ## 参数 966994f6b1SLoGin /// 976994f6b1SLoGin /// - `data`:位图数据 986994f6b1SLoGin /// - `n`:位图有效位数 99*b2ca6800SLoGin pub(crate) fn last_false_index(&self, n: usize, data: &[T]) -> Option<usize> { 1006994f6b1SLoGin let mut iter = data.iter().rev(); 1016994f6b1SLoGin let mut last_element = *iter.next()?; 1026994f6b1SLoGin 1036994f6b1SLoGin // 对最后一个元素进行特殊处理,因为最后一个元素可能不是满的 104*b2ca6800SLoGin let mut mask = T::make_mask(n % T::bit_size()); 1056994f6b1SLoGin if mask != T::zero() { 1066994f6b1SLoGin <T as BitOps>::invert(&mut mask); 1076994f6b1SLoGin 1086994f6b1SLoGin last_element |= mask; 1096994f6b1SLoGin } 1106994f6b1SLoGin 1116994f6b1SLoGin if let Some(bit) = <T as BitOps>::last_false_index(&last_element) { 112*b2ca6800SLoGin return self.make_index(n, (data.len() - 1) * T::bit_size() + bit); 1136994f6b1SLoGin } 1146994f6b1SLoGin 1156994f6b1SLoGin for element in iter { 1166994f6b1SLoGin if let Some(bit) = <T as BitOps>::last_false_index(element) { 117*b2ca6800SLoGin return self.make_index(n, (data.len() - 1) * T::bit_size() + bit); 1186994f6b1SLoGin } 1196994f6b1SLoGin } 1206994f6b1SLoGin 1216994f6b1SLoGin None 1226994f6b1SLoGin } 1236994f6b1SLoGin 1246994f6b1SLoGin /// 获取位图中下一个为1的位 125*b2ca6800SLoGin pub(crate) fn next_index(&self, n: usize, data: &[T], index: usize) -> Option<usize> { 126*b2ca6800SLoGin if unlikely(index >= n) { 1276994f6b1SLoGin return None; 1286994f6b1SLoGin } 1296994f6b1SLoGin 1306994f6b1SLoGin let element_index = index / T::bit_size(); 1316994f6b1SLoGin let bit_index = index % T::bit_size(); 1326994f6b1SLoGin 1336994f6b1SLoGin let element = data.get(element_index)?; 1346994f6b1SLoGin if let Some(bit) = <T as BitOps>::next_index(element, bit_index) { 135*b2ca6800SLoGin return self.make_index(n, element_index * T::bit_size() + bit); 1366994f6b1SLoGin } 1376994f6b1SLoGin 1386994f6b1SLoGin for (i, element) in data.iter().enumerate().skip(element_index + 1) { 1396994f6b1SLoGin if let Some(bit) = <T as BitOps>::first_index(element) { 140*b2ca6800SLoGin return self.make_index(n, i * T::bit_size() + bit); 1416994f6b1SLoGin } 1426994f6b1SLoGin } 1436994f6b1SLoGin 1446994f6b1SLoGin None 1456994f6b1SLoGin } 1466994f6b1SLoGin 1476994f6b1SLoGin /// 获取位图中下一个为0的位 148*b2ca6800SLoGin pub(crate) fn next_false_index(&self, n: usize, data: &[T], index: usize) -> Option<usize> { 149*b2ca6800SLoGin if unlikely(index >= n) { 1506994f6b1SLoGin return None; 1516994f6b1SLoGin } 1526994f6b1SLoGin 1536994f6b1SLoGin let element_index = index / T::bit_size(); 1546994f6b1SLoGin let bit_index = index % T::bit_size(); 1556994f6b1SLoGin 1566994f6b1SLoGin let element = data.get(element_index)?; 1576994f6b1SLoGin if let Some(bit) = <T as BitOps>::next_false_index(element, bit_index) { 158*b2ca6800SLoGin return self.make_index(n, element_index * T::bit_size() + bit); 1596994f6b1SLoGin } 1606994f6b1SLoGin 1616994f6b1SLoGin for (i, element) in data.iter().enumerate().skip(element_index + 1) { 1626994f6b1SLoGin if let Some(bit) = <T as BitOps>::first_false_index(element) { 163*b2ca6800SLoGin return self.make_index(n, i * T::bit_size() + bit); 1646994f6b1SLoGin } 1656994f6b1SLoGin } 1666994f6b1SLoGin 1676994f6b1SLoGin None 1686994f6b1SLoGin } 1696994f6b1SLoGin 1706994f6b1SLoGin /// 获取位图中上一个为1的位 171*b2ca6800SLoGin pub(crate) fn prev_index(&self, n: usize, data: &[T], index: usize) -> Option<usize> { 172*b2ca6800SLoGin if unlikely(index >= n) { 1736994f6b1SLoGin return None; 1746994f6b1SLoGin } 1756994f6b1SLoGin let element_index = index / T::bit_size(); 1766994f6b1SLoGin let bit_index = index % T::bit_size(); 1776994f6b1SLoGin 1786994f6b1SLoGin let element = data.get(element_index)?; 1796994f6b1SLoGin if let Some(bit) = <T as BitOps>::prev_index(element, bit_index) { 180*b2ca6800SLoGin return self.make_index(n, element_index * T::bit_size() + bit); 1816994f6b1SLoGin } 1826994f6b1SLoGin 1836994f6b1SLoGin for (i, element) in data.iter().enumerate().take(element_index).rev() { 1846994f6b1SLoGin if let Some(bit) = <T as BitOps>::last_index(element) { 185*b2ca6800SLoGin return self.make_index(n, i * T::bit_size() + bit); 1866994f6b1SLoGin } 1876994f6b1SLoGin } 1886994f6b1SLoGin 1896994f6b1SLoGin None 1906994f6b1SLoGin } 1916994f6b1SLoGin 192*b2ca6800SLoGin pub(crate) fn prev_false_index(&self, n: usize, data: &[T], index: usize) -> Option<usize> { 1936994f6b1SLoGin let element_index = index / T::bit_size(); 1946994f6b1SLoGin let bit_index = index % T::bit_size(); 1956994f6b1SLoGin 1966994f6b1SLoGin let element = data.get(element_index)?; 1976994f6b1SLoGin if let Some(bit) = <T as BitOps>::prev_false_index(element, bit_index) { 198*b2ca6800SLoGin return self.make_index(n, element_index * T::bit_size() + bit); 1996994f6b1SLoGin } 2006994f6b1SLoGin 2016994f6b1SLoGin for (i, element) in data.iter().enumerate().take(element_index).rev() { 2026994f6b1SLoGin if let Some(bit) = <T as BitOps>::last_false_index(element) { 203*b2ca6800SLoGin return self.make_index(n, i * T::bit_size() + bit); 2046994f6b1SLoGin } 2056994f6b1SLoGin } 2066994f6b1SLoGin 2076994f6b1SLoGin None 2086994f6b1SLoGin } 2096994f6b1SLoGin 210*b2ca6800SLoGin pub(crate) fn invert(&self, n: usize, data: &mut [T]) { 2116994f6b1SLoGin for element in data.iter_mut() { 2126994f6b1SLoGin <T as BitOps>::invert(element); 2136994f6b1SLoGin } 2146994f6b1SLoGin 2156994f6b1SLoGin // 特殊处理最后一个元素 2166994f6b1SLoGin 2176994f6b1SLoGin let last_element = data.last_mut().unwrap(); 218*b2ca6800SLoGin let mask = T::make_mask(n % T::bit_size()); 2196994f6b1SLoGin if mask != T::zero() { 2206994f6b1SLoGin *last_element &= mask; 2216994f6b1SLoGin } 2226994f6b1SLoGin } 2236994f6b1SLoGin 224*b2ca6800SLoGin pub(crate) fn is_full(&self, n: usize, data: &[T]) -> bool { 2256994f6b1SLoGin let mut iter = data.iter().peekable(); 2266994f6b1SLoGin while let Some(element) = iter.next() { 2276994f6b1SLoGin if iter.peek().is_none() { 2286994f6b1SLoGin // 这是最后一个元素,进行特殊处理 2296994f6b1SLoGin let mut element = *element; 230*b2ca6800SLoGin let mut mask = T::make_mask(n % T::bit_size()); 2316994f6b1SLoGin if mask == T::zero() { 2326994f6b1SLoGin mask = T::max(); 2336994f6b1SLoGin } 2346994f6b1SLoGin 2356994f6b1SLoGin T::bit_and(&mut element, &mask); 2366994f6b1SLoGin if element == mask { 2376994f6b1SLoGin return true; 2386994f6b1SLoGin } 2396994f6b1SLoGin } else { 2406994f6b1SLoGin if element != &T::make_mask(T::bit_size()) { 2416994f6b1SLoGin return false; 2426994f6b1SLoGin } 2436994f6b1SLoGin } 2446994f6b1SLoGin } 2456994f6b1SLoGin 2466994f6b1SLoGin return false; 2476994f6b1SLoGin } 2486994f6b1SLoGin 2496994f6b1SLoGin pub(crate) fn is_empty(&self, data: &[T]) -> bool { 2506994f6b1SLoGin for element in data.iter() { 2516994f6b1SLoGin if element != &T::zero() { 2526994f6b1SLoGin return false; 2536994f6b1SLoGin } 2546994f6b1SLoGin } 2556994f6b1SLoGin 2566994f6b1SLoGin return true; 2576994f6b1SLoGin } 2586994f6b1SLoGin 259*b2ca6800SLoGin fn make_index(&self, n: usize, index: usize) -> Option<usize> { 260*b2ca6800SLoGin if unlikely(index >= n) { 2616994f6b1SLoGin return None; 2626994f6b1SLoGin } 2636994f6b1SLoGin 2646994f6b1SLoGin Some(index) 2656994f6b1SLoGin } 2666994f6b1SLoGin } 267