1///| 容器配置常量
2pub const Int
容器配置常量
ARRAY_CONTAINER_MAX_SIZE : Int
Int = 4096
3
4///|
5pub const Int
BITMAP_CONTAINER_SIZE : Int
Int = 8192 // 2^16 / 8 = 8192 bytes = 1024 UInt64
6
7///|
8pub const Int
RUN_CONTAINER_MAX_SIZE : Int
Int = 2048
9
10///| RoaringBitmap 错误类型
11pub(all) enum RoaringError {
12 (String) -> RoaringError
InvalidInput(String
String)
13 (String) -> RoaringError
OutOfRange(String
String)
14 (String) -> RoaringError
SerializationError(String
String)
15}
16
17///| 容器类型枚举 - Roaring Bitmap 的核心优化策略
18enum Container {
19 // 数组容器：适用于稀疏数据（< 4096 个元素）
20 (Array[UInt16]) -> Container
ArrayContainer(type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[UInt16
UInt16])
21
22 // 位图容器：适用于密集数据（>= 4096 个元素）
23 (FixedArray[UInt64]) -> Container
BitmapContainer(type FixedArray[A]
FixedArray[UInt64
UInt64]) // 1024 个 UInt64，每个64位
24
25 // 运行长度编码容器：适用于连续数据
26 (Array[Run]) -> Container
RunContainer(type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[struct Run {
start: UInt16
length: UInt16
}
运行长度编码的运行段
Run])
27}
28
29///| 运行长度编码的运行段
30pub(all) struct Run {
31 UInt16
start : UInt16
UInt16 // 运行段的起始值
32 UInt16
length : UInt16
UInt16 // 运行长度（实际元素个数 - 1）
33}
34
35///| 高级容器 - 处理 32 位整数的高 16 位
36struct HighContainer {
37 UInt16
key : UInt16
UInt16 // 高 16 位作为键
38 Container
container : enum Container {
ArrayContainer(Array[UInt16])
BitmapContainer(FixedArray[UInt64])
RunContainer(Array[Run])
}
容器类型枚举 - Roaring Bitmap 的核心优化策略
Container // 对应的容器（存储低 16 位）
39 Int
cardinality : Int
Int // 该容器中的元素个数
40}
41
42///| RoaringBitmap 主结构
43pub struct RoaringBitmap {
44 Array[HighContainer]
containers : type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[struct HighContainer {
key: UInt16
container: Container
cardinality: Int
}
高级容器 - 处理 32 位整数的高 16 位
HighContainer] // 按 key 排序的容器数组
45 mut Int
size : Int
Int // 总元素个数
46}
47
48///| 容器操作接口
49pub trait trait ContainerOps {
add(Self, UInt16) -> Self
remove(Self, UInt16) -> Self
contains(Self, UInt16) -> Bool
union(Self, Self) -> Self
intersect(Self, Self) -> Self
difference(Self, Self) -> Self
cardinality(Self) -> Int
is_empty(Self) -> Bool
to_array(Self) -> Array[UInt16]
optimize(Self) -> Container
}
容器操作接口
ContainerOps {
50 // 基本操作
51 (Self, UInt16) -> Self
add(type parameter Self
Self, UInt16
UInt16) -> type parameter Self
Self
52 (Self, UInt16) -> Self
remove(type parameter Self
Self, UInt16
UInt16) -> type parameter Self
Self
53 (Self, UInt16) -> Bool
contains(type parameter Self
Self, UInt16
UInt16) -> Bool
Bool
54
55 // 集合操作
56 (Self, Self) -> Self
union(type parameter Self
Self, type parameter Self
Self) -> type parameter Self
Self
57 (Self, Self) -> Self
intersect(type parameter Self
Self, type parameter Self
Self) -> type parameter Self
Self
58 (Self, Self) -> Self
difference(type parameter Self
Self, type parameter Self
Self) -> type parameter Self
Self
59
60 // 属性查询
61 (Self) -> Int
cardinality(type parameter Self
Self) -> Int
Int
62 (Self) -> Bool
is_empty(type parameter Self
Self) -> Bool
Bool
63
64 // 转换操作
65 (Self) -> Array[UInt16]
to_array(type parameter Self
Self) -> type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[UInt16
UInt16]
66 (Self) -> Container
optimize(type parameter Self
Self) -> enum Container {
ArrayContainer(Array[UInt16])
BitmapContainer(FixedArray[UInt64])
RunContainer(Array[Run])
}
容器类型枚举 - Roaring Bitmap 的核心优化策略
Container // 自动选择最优容器类型
67}
68
69///| 迭代器类型
70pub(all) enum RoaringIterator {
71 (ArrayIteratorState) -> RoaringIterator
ArrayIterator(struct ArrayIteratorState {
values: Array[UInt16]
index: Int
high_bits: UInt
}
数组迭代器状态
ArrayIteratorState)
72 (BitmapIteratorState) -> RoaringIterator
BitmapIterator(struct BitmapIteratorState {
bitmap: FixedArray[UInt64]
word_index: Int
bit_index: Int
high_bits: UInt
}
位图迭代器状态
BitmapIteratorState)
73 (RunIteratorState) -> RoaringIterator
RunIterator(struct RunIteratorState {
runs: Array[Run]
run_index: Int
position_in_run: Int
high_bits: UInt
}
运行迭代器状态
RunIteratorState)
74}
75
76///| 数组迭代器状态
77pub(all) struct ArrayIteratorState {
78 Array[UInt16]
values : type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[UInt16
UInt16]
79 Int
index : Int
Int
80 UInt
high_bits : UInt
UInt // 修正：使用 UInt 而不是 UInt32
81}
82
83///| 位图迭代器状态
84pub(all) struct BitmapIteratorState {
85 FixedArray[UInt64]
bitmap : type FixedArray[A]
FixedArray[UInt64
UInt64]
86 Int
word_index : Int
Int
87 Int
bit_index : Int
Int
88 UInt
high_bits : UInt
UInt // 修正：使用 UInt 而不是 UInt32
89}
90
91///| 运行迭代器状态
92pub(all) struct RunIteratorState {
93 Array[Run]
runs : type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[struct Run {
start: UInt16
length: UInt16
}
运行长度编码的运行段
Run]
94 Int
run_index : Int
Int
95 Int
position_in_run : Int
Int
96 UInt
high_bits : UInt
UInt // 修正：使用 UInt 而不是 UInt32
97}
98
99///| 统计信息结构
100pub struct RoaringStats {
101 Int
total_containers : Int
Int
102 Int
array_containers : Int
Int
103 Int
bitmap_containers : Int
Int
104 Int
run_containers : Int
Int
105 Int
total_bytes : Int
Int
106 Double
compression_ratio : Double
Double
107}
108
109///| 二进制搜索结果
110pub enum SearchResult {
111 (Int) -> SearchResult
Found(Int
Int) // 找到，返回索引
112 (Int) -> SearchResult
NotFound(Int
Int) // 未找到，返回应该插入的位置
113}
114