1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
//! # Compressed bit masks
/// A single compressed “word” in our run‐length encoding.
///
/// - `ZeroRun(n)`: represents `n` consecutive words of all‐zeros (`0x0000…`)
/// - `OneRun(n)`: represents `n` consecutive words of all‐ones (`0xFFFF…`)
/// - `Literal(w)`: represents exactly one word with arbitrary bits
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Segment {
/// Repeat `0x0000...`.
ZeroRun(usize),
/// Repeat `0x1111...`.
OneRun(usize),
/// Non-uniform `u64` bit mask.
Literal(u64),
}
/// A sequence of `u64` masks, compressed by run‐length encoding.
#[derive(Debug, Clone)]
pub struct CompressedMasks {
segments: Vec<Segment>,
// Total number of words represented (kept in sync with pushes).
len_words: usize,
}
impl CompressedMasks {
/// Create an empty sequence.
pub fn new() -> Self {
CompressedMasks {
segments: Vec::new(),
len_words: 0,
}
}
/// Clearn the content.
pub fn clear(&mut self) {
// Usually, should use `self.segments.clear()`,
// however, since `Segment` is `Copy` and has no destructor,
// it is less work for the compiler to optimize.
unsafe {self.segments.set_len(0)};
self.len_words = 0;
}
/// Push a number of ones.
pub fn push_ones(&mut self, ones: u64) {
let n = ones / 64;
let k = ones % 64;
for _ in 0..n {self.push(0xffffffffffffffff)}
self.push((1_u64 << k) - 1)
}
/// Push a new 64‐bit mask on the end, merging into the last run if possible.
pub fn push(&mut self, word: u64) {
use Segment::*;
self.len_words += 1;
match self.segments.last_mut() {
// extend an existing zero‐run
Some(ZeroRun(n)) if word == 0 => *n += 1,
// extend an existing one‐run
Some(OneRun(n)) if word == !0 => *n += 1,
// otherwise, we need a new segment
_ => self.segments.push(match word {
0 => ZeroRun(1),
0xffffffffffffffff => OneRun(1),
_ => Literal(word),
})
}
}
/// Get the uncompressed length (number of `u64` words).
pub fn len(&self) -> usize {
self.len_words
}
/// Counts the total number of ones.
pub fn count_ones(&self) -> u64 {
let mut sum: u64 = 0;
for seg in &self.segments {
match *seg {
Segment::ZeroRun(_) => {}
Segment::OneRun(count) => sum += (64 * count) as u64,
Segment::Literal(w) => sum += w.count_ones() as u64,
}
}
sum
}
/// Returns the word at position `i`, decompressing on the fly.
pub fn get(&self, mut i: usize) -> Option<u64> {
if i >= self.len_words {
return None;
}
for seg in &self.segments {
match *seg {
Segment::ZeroRun(count) if i < count => return Some(0),
Segment::ZeroRun(count) => { i -= count; }
Segment::OneRun(count) if i < count => return Some(!0),
Segment::OneRun(count) => { i -= count; }
Segment::Literal(w) if i == 0 => return Some(w),
Segment::Literal(_) => { i -= 1; }
}
}
// should never reach here if len_words is correct
None
}
/// Iterate through decompressed words, skipping zero runs.
pub fn iter(&self) -> impl Iterator<Item = (usize, u64)> + Clone {
self.segments.iter()
.scan(0usize, |offset, seg| {
let start = *offset;
let count = match *seg {
Segment::ZeroRun(c) => c,
Segment::OneRun(c) => c,
Segment::Literal(_) => 1,
};
*offset += count;
Some((start, seg))
})
.filter(|(_, seg)| if let Segment::ZeroRun(_) = *seg {false} else {true})
.flat_map(|(i, seg)| match *seg {
Segment::ZeroRun(count) => std::iter::repeat(0).take(count),
Segment::OneRun(count) => std::iter::repeat(0xffffffffffffffff).take(count),
Segment::Literal(w) => std::iter::repeat(w).take(1),
}.enumerate().map(move |(j, m)| (i + j, m)))
}
}