csf/fp/
collision_solver.rs

1use bitm::{BitAccess, BitVec, n_lowest_bits};
2
3/// Solves value collisions during construction of BBMap.
4pub trait CollisionSolver {
5    /// Returns true if `index` is under collision and should not be farther processed.
6    fn is_under_collision(&self, index: usize) -> bool;
7
8    /// Try to assign value (`bits_per_fragment` bits of `fragment`) to the given `index` which is not under collision.
9    fn process_fragment(&mut self, index: usize, fragment: u8, bits_per_fragment: u8);
10
11    /// Array that shows indices which have assigned values and are not under collision.
12    fn to_collision_array(self) -> Box<[u64]>;
13
14    fn construct_value_array(number_of_values: usize, bits_per_fragment: u8) -> Box<[u64]> {
15        Box::<[u64]>::with_zeroed_bits(number_of_values*bits_per_fragment as usize)
16    }
17
18    /// Set `index`-th value in final `output` (which is an array of `bits_per_fragment` bits values) to `fragment`.
19    #[inline(always)] fn set_value(output: &mut [u64], index: usize, fragment: u8, bits_per_fragment: u8) {
20        output.init_fragment(index, fragment as u64, bits_per_fragment);
21    }
22}
23
24/// Builds `CollisionSolver`.
25pub trait CollisionSolverBuilder {
26    /// Type of collision solver that is build by `self`.
27    type CollisionSolver: CollisionSolver;
28
29    /// Constructs `CollisionSolver` for given number of values (64*`level_size_segments`) and `bits_per_fragment`.
30    /// The solver supports indices in range [0, 64*`level_size_segments`) and values of the size of `bits_per_fragment` bits.
31    fn new(&self, level_size_segments: usize, bits_per_fragment: u8) -> Self::CollisionSolver;
32
33    /// Gets whether the `new` method, with the current parameters, returns the collision solver that is lossless.
34    fn is_lossless(&self) -> bool;
35}
36
37/// Shows that the builder always produces the collision solver that is lossless and thus can be used with compressed BBmap.
38pub trait IsLossless: CollisionSolverBuilder {} // TODO: maybe check only in runtime by is_lossless method
39
40
41/// BBMap collision solver that permits assigning only one value (few equal values) to each index.
42pub struct LoMemAcceptEqualsSolver {
43    /// Which indices are under collision.
44    collided: Box<[u64]>,
45    /// Fragments assigned to indices.
46    fragments: Box<[u64]>,
47    /// Which indices have assigned values and are not under collision.
48    current_array: Box<[u64]>
49}
50
51impl LoMemAcceptEqualsSolver {
52    pub(crate) fn new(level_size_segments: usize, bits_per_fragment: u8) -> Self {
53        Self {
54            collided: Box::<[u64]>::with_zeroed_64bit_segments(level_size_segments),
55            fragments: Box::<[u64]>::with_zeroed_64bit_segments(level_size_segments * bits_per_fragment as usize),
56            current_array: Box::<[u64]>::with_zeroed_64bit_segments(level_size_segments)
57        }
58    }
59}
60
61impl CollisionSolver for LoMemAcceptEqualsSolver {
62    #[inline(always)] fn is_under_collision(&self, index: usize) -> bool {
63        self.collided.get_bit(index)
64    }
65
66    fn process_fragment(&mut self, index: usize, fragment: u8, bits_per_fragment: u8) {
67        if !self.current_array.get_bit(index) { // empty:
68            self.current_array.set_bit(index);
69            self.fragments.init_fragment(index, fragment as _, bits_per_fragment);
70        } else if /*fragments[a_index]*/ self.fragments.get_fragment(index, bits_per_fragment) as u8 != fragment {
71            self.collided.set_bit(index);
72            self.current_array.clear_bit(index);
73        }
74    }
75
76    fn to_collision_array(self) -> Box<[u64]> {
77        self.current_array
78    }
79}
80
81#[derive(Default, Copy, Clone)]
82pub struct LoMemAcceptEquals;
83
84impl CollisionSolverBuilder for LoMemAcceptEquals {
85    type CollisionSolver = LoMemAcceptEqualsSolver;
86
87    #[inline(always)] fn new(&self, level_size_segments: usize, bits_per_fragment: u8) -> Self::CollisionSolver {
88        Self::CollisionSolver::new(level_size_segments, bits_per_fragment)
89    }
90
91    #[inline(always)] fn is_lossless(&self) -> bool { true }
92}
93
94impl IsLossless for LoMemAcceptEquals {}
95
96
97/// BBMap collision solver that permits assigning only one value (few equal values) to each index.
98pub struct AcceptEqualsSolver {
99    /// Which indices are under collision.
100    collided: Box<[u64]>,
101    /// Fragments assigned to indices (uses 1 byte / value).
102    fragments: Box<[u8]>,
103    /// Which indices have assigned values and are not under collision.
104    current_array: Box<[u64]>
105}
106
107impl AcceptEqualsSolver {
108    fn new(level_size_segments: usize, _bits_per_fragment: u8) -> Self {
109        Self {
110            collided: Box::<[u64]>::with_zeroed_64bit_segments(level_size_segments as usize),
111            fragments: vec![0u8; level_size_segments as usize * 64].into_boxed_slice(),
112            current_array: Box::<[u64]>::with_zeroed_64bit_segments(level_size_segments as usize)
113        }
114    }
115}
116
117impl CollisionSolver for AcceptEqualsSolver {
118    #[inline(always)] fn is_under_collision(&self, index: usize) -> bool {
119        self.collided.get_bit(index)
120    }
121
122    fn process_fragment(&mut self, index: usize, fragment: u8, _bits_per_fragment: u8) {
123        if !self.current_array.get_bit(index) { // empty:
124            self.current_array.set_bit(index);
125            self.fragments[index] = fragment;
126        } else if self.fragments[index] != fragment {
127            self.collided.set_bit(index);
128            self.current_array.clear_bit(index);
129        }
130    }
131
132    fn to_collision_array(self) -> Box<[u64]> {
133        self.current_array
134    }
135}
136
137#[derive(Default, Copy, Clone)]
138pub struct AcceptEquals;
139
140impl CollisionSolverBuilder for AcceptEquals {
141    type CollisionSolver = AcceptEqualsSolver;
142
143    #[inline(always)] fn new(&self, level_size_segments: usize, bits_per_fragment: u8) -> Self::CollisionSolver {
144        Self::CollisionSolver::new(level_size_segments, bits_per_fragment)
145    }
146
147    #[inline(always)] fn is_lossless(&self) -> bool { true }
148}
149
150impl IsLossless for AcceptEquals {}
151
152#[derive(Copy, Clone)]
153struct LimitedDifferenceCell {
154    /// total difference of added values over minimal value
155    total_difference: u16,
156    /// minimal value (lowest bit) and number of fragments
157    minimum_and_count: u16
158}
159
160impl LimitedDifferenceCell {
161    /// total_difference=0, minimum=value_mask, count=0
162    #[inline(always)] fn new(value_mask: u16) -> Self {
163        Self { total_difference: 0, minimum_and_count: value_mask }
164    }
165
166    #[inline(always)] fn minimum(&self, value_mask: u16) -> u8 {
167        (self.minimum_and_count & value_mask) as u8
168    }
169
170    #[inline(always)] fn set_minimum(&mut self, new_value: u8, value_mask: u16) {
171        self.minimum_and_count &= !value_mask;
172        self.minimum_and_count |= new_value as u16;
173    }
174
175    #[inline(always)] fn inc_count(&mut self, bits_per_value: u8) {
176        self.minimum_and_count = self.minimum_and_count.checked_add(1 << bits_per_value).unwrap();
177    }
178
179    #[inline(always)] fn get_count(&self, bits_per_value: u8) -> u16 {
180        self.minimum_and_count >> bits_per_value
181    }
182}
183
184pub struct AcceptLimitedAverageDifferenceSolver {
185    cells: Box<[LimitedDifferenceCell]>,
186    bits_per_value: u8,
187    value_mask: u16,
188    max_difference_per_value: u8
189}
190
191impl AcceptLimitedAverageDifferenceSolver {
192    pub fn new(level_size_segments: usize, bits_per_value: u8, max_difference_per_value: u8) -> Self {
193        let value_mask = n_lowest_bits(bits_per_value as _) as u16;
194        Self {
195            cells: vec![LimitedDifferenceCell::new(value_mask); level_size_segments as usize*64].into_boxed_slice(),
196            bits_per_value,
197            value_mask,
198            max_difference_per_value
199        }
200    }
201}
202
203impl CollisionSolver for AcceptLimitedAverageDifferenceSolver {
204    #[inline(always)] fn is_under_collision(&self, _index: usize) -> bool { false }
205
206    fn process_fragment(&mut self, index: usize, fragment: u8, _bits_per_fragment: u8) {
207        let c = &mut self.cells[index];
208        let m = c.minimum(self.value_mask);
209        if fragment < m {
210            c.total_difference = c.total_difference.checked_add(c.get_count(self.bits_per_value) * (m - fragment) as u16).unwrap();
211            c.set_minimum(fragment, self.value_mask);
212        } else {
213            c.total_difference = c.total_difference.checked_add((fragment - m) as u16).unwrap(); // (fragment - m) can be 0 here
214        }
215        c.inc_count(self.bits_per_value);
216    }
217
218    fn to_collision_array(self) -> Box<[u64]> {
219        let mut result = Box::<[u64]>::with_zeroed_64bit_segments(self.cells.len() / 64);
220        for (index, cell) in self.cells.into_iter().enumerate() {
221            let d = cell.get_count(self.bits_per_value);
222            if d != 0 && cell.total_difference as u32 <= d as u32 * self.max_difference_per_value as u32 {
223                result.set_bit(index);
224            }
225        }
226        result
227    }
228
229    fn construct_value_array(number_of_values: usize, bits_per_fragment: u8) -> Box<[u64]> {
230        Box::<[u64]>::with_filled_bits(number_of_values*bits_per_fragment as usize)
231    }
232
233    fn set_value(output: &mut [u64], index: usize, fragment: u8, bits_per_fragment: u8) {
234        let fragment = fragment as u64;
235        output.conditionally_change_fragment(| old| if fragment < old { Some(fragment) } else {None}, index, bits_per_fragment);
236    }
237}
238
239/// Collision solver that uses minimal value in the set and accepts limited average difference
240/// between values of the set members and this minimum.
241#[derive(Copy, Clone)]
242pub struct AcceptLimitedAverageDifference {
243    /// Maximal average difference accepted.
244    max_difference_per_value: u8
245}
246
247impl AcceptLimitedAverageDifference {
248    pub fn new(max_difference_per_value: u8) -> Self {
249        Self { max_difference_per_value }
250    }
251}
252
253impl CollisionSolverBuilder for AcceptLimitedAverageDifference {
254    type CollisionSolver = AcceptLimitedAverageDifferenceSolver;
255
256    #[inline(always)] fn new(&self, level_size_segments: usize, bits_per_fragment: u8) -> Self::CollisionSolver {
257        Self::CollisionSolver::new(level_size_segments, bits_per_fragment, self.max_difference_per_value)
258    }
259
260    #[inline(always)] fn is_lossless(&self) -> bool { self.max_difference_per_value == 0 }
261}
262
263
264pub struct CountPositiveCollisions {
265    count_and_fragments: Box<[u16]>
266}
267
268impl CountPositiveCollisions {
269    pub fn new(level_size: usize) -> Self {
270        CountPositiveCollisions {
271            count_and_fragments: vec![0; level_size].into_boxed_slice()
272        }
273    }
274
275    pub fn consider(count_and_fragment: &mut u16, fragment: u16, bits_per_fragment: u8) {
276        if *count_and_fragment == 0 {  // empty?
277            *count_and_fragment = (1u16 << bits_per_fragment) | fragment;
278        } else if *count_and_fragment & ((1u16 << bits_per_fragment) - 1) == fragment {   // the same fragment again
279            if let Some(v) = count_and_fragment.checked_add(1 << bits_per_fragment) {
280                *count_and_fragment = v;
281            }
282        } else {    // collision:
283            *count_and_fragment = u16::MAX;
284        }
285    }
286
287    /// Returns number of positive collision in given `entry`.
288    #[inline] pub fn positive_collisions_in_entry(entry: u16, bits_per_fragment: u8) -> u16 {
289        if entry == u16::MAX {  // collision
290            0
291        } else {
292            entry >> bits_per_fragment
293        }
294    }
295
296    /// Returns number of positive collision at given `index`.
297    #[inline] pub fn count(&self, index: usize, bits_per_fragment: u8) -> u16 {
298        Self::positive_collisions_in_entry(self.count_and_fragments[index], bits_per_fragment)
299    }
300
301    pub fn len(&self) -> usize { self.count_and_fragments.len() }
302
303    /// Counts total number of positive collision in each group (chunk) of successive `values_per_group` indices.
304    pub fn positive_collisions_of_groups(&self, values_per_group: u8, bits_per_fragment: u8) -> Box<[u8]> {
305        self.count_and_fragments
306            .chunks(values_per_group as usize)
307            .map(|v|
308                v.iter()
309                    .map(|e| Self::positive_collisions_in_entry(*e, bits_per_fragment))
310                    .fold(0u8, |sum, x| sum.saturating_add(x.min(u8::MAX as _) as u8))
311            ).collect()
312    }
313}
314
315impl CollisionSolver for CountPositiveCollisions {
316    fn is_under_collision(&self, index: usize) -> bool {
317        self.count_and_fragments[index] == u16::MAX
318    }
319
320    fn process_fragment(&mut self, index: usize, fragment: u8, bits_per_fragment: u8) {
321        Self::consider(&mut self.count_and_fragments[index], fragment as u16, bits_per_fragment);
322    }
323
324    fn to_collision_array(self) -> Box<[u64]> {
325        todo!()
326    }
327}
csf/fp/collision_solver.rs

csf/fp/
collision_solver.rs
