dynamization/
strategy.rs

1//! Different dynamization strategies.
2//!
3//! Currently only [`Binary`] is supported.
4
5use crate::*;
6
7
8/// A dynamization strategy.
9///
10/// Can be simply a ZST. Also can contain some internal bookkeeping machinery.
11pub trait Strategy where Self: Sized {
12    /// A default strategy with a default initial unit count.
13    fn new_unit_count() -> (Self, usize);
14
15    /// A strategy with a specified initial unit count.
16    fn with_unit_count(unit_count: usize) -> Self;
17
18    /// An algorithm for adding a new unit.
19    ///
20    /// Can modify an internal state of the strategy.
21    fn add<Container: Static>(
22        &mut self, units: &mut Vec<Option<Container>>, container: Container
23    );
24}
25
26
27/// Binary dynamization.
28///
29/// A nonempty unit with the index `k>0` has size between `2^{k-1}+1` and `2^k`.
30///
31/// A new unit is added to the most appropriate index: if this index 
32/// is occupied, the added unit is merged with
33/// the occupying one and moved to the index corresponding to the resulting size.
34///
35/// Sometimes this strategy can provoke a long chain of merges (but not 
36/// longer than a logarithm of the total size). For a more 
37/// predictable performance see the [`SkewBinary`] strategy.
38#[derive(Clone, Debug)]
39pub struct Binary;
40
41
42impl Strategy for Binary {
43    fn new_unit_count() -> (Self, usize) {
44        (Binary, 8)
45    }
46
47    fn with_unit_count(_unit_count: usize) -> Self {
48        Binary
49    }
50
51    fn add<Container: Static>(
52        &mut self, 
53        units: &mut Vec<Option<Container>>, 
54        mut container: Container)
55    {
56        let len = container.len();
57
58        let mut unit_size = 1;
59        let mut index = 0;
60
61        while unit_size < len {
62            index += 1;
63            unit_size *= 2;
64        }
65
66        while units.len() <= index {
67            units.push(None);
68        }
69
70        for unit in &mut units[index..] {
71            let content = core::mem::replace(unit, None);
72            
73            match content {
74                None => {
75                    *unit = Some(container);
76                    return;
77                }
78
79                Some(other) => {
80                    container = container.merge_with(other);
81
82                    if container.len() <= unit_size {
83                        *unit = Some(container);
84                        return;
85                    }
86                }
87            }
88        }
89         
90        units.push(Some(container));
91    }
92}
93
94
95/// Simple binary dynamization.
96///
97/// Much like [`Binary`] but doesn't account for unit sizes: every new unit 
98/// is added to the index 0.
99///
100/// Nevertheless has the same average asymptotics: each stored item `X` participates 
101/// in at most `log N` merges where `N` is the count of items added after the 
102/// item `X` was inserted.
103#[derive(Clone, Debug)]
104pub struct SimpleBinary;
105
106
107impl Strategy for SimpleBinary {
108    fn new_unit_count() -> (Self, usize) {
109        (SimpleBinary, 8)
110    }
111
112    fn with_unit_count(_unit_count: usize) -> Self {
113        SimpleBinary
114    }
115
116    fn add<Container: Static>(
117        &mut self, 
118        units: &mut Vec<Option<Container>>, 
119        mut container: Container)
120    {
121        for unit in &mut *units {
122            let content = core::mem::replace(unit, None);
123            
124            match content {
125                None => {
126                    *unit = Some(container);
127                    return;
128                }
129
130                Some(other) => {
131                    container = container.merge_with(other);
132                }
133            }
134        }
135         
136        units.push(Some(container));
137    }
138}
139
140
141/// Skew-binary dynamization.
142///
143/// Ensures that each unit addition makes not more than two merges.
144///
145/// Useful when there is a large overhead for each merge and predictable 
146/// performance is needed.
147///
148/// But in other cases [`Binary`] and [`SimpleBinary`] are much more preferable.
149#[derive(Clone, Debug)]
150pub struct SkewBinary {
151    last_merge: usize
152}
153
154impl Strategy for SkewBinary {
155    fn new_unit_count() -> (Self, usize) {
156        (SkewBinary { last_merge: 0 }, 8)
157    }
158
159    fn with_unit_count(unit_count: usize) -> Self {
160        assert!(unit_count > 0);
161
162        SkewBinary {
163            last_merge: 0,
164        }
165    }
166
167    fn add<Container: Static>(
168        &mut self, 
169        units: &mut Vec<Option<Container>>, 
170        mut container: Container)
171    {
172        if units.len() == 0 {
173            units.push(Some(container));
174            return;
175        }
176
177        let unit = &mut units[self.last_merge];
178        let content = core::mem::replace(unit, None);
179            
180        match content {
181            None => {
182                *unit = Some(container);
183                return;
184            }
185
186            Some(other) => {
187                container = container.merge_with(other);
188            }
189        }
190
191        let new_index = self.last_merge + 1;
192        
193        if units.len() == new_index {
194            units.push(Some(container));
195            self.last_merge = 0;
196            return;
197        }
198
199        let unit = &mut units[new_index];
200        let content = core::mem::replace(unit, None);
201            
202        match content {
203            None => {
204                *unit = Some(container);
205                self.last_merge = 0;
206            }
207
208            Some(other) => {
209                *unit = Some(container.merge_with(other));
210                self.last_merge = new_index;
211            }
212        }
213    }
214}
215
dynamization/strategy.rs

dynamization/
strategy.rs
