Line data Source code
1 : use std::{alloc::Layout, cmp::Ordering, ops::RangeBounds};
2 :
3 : /// Ordered map datastructure implemented in a Vec.
4 : /// Append only - can only add keys that are larger than the
5 : /// current max key.
6 0 : #[derive(Clone, Debug)]
7 : pub struct VecMap<K, V>(Vec<(K, V)>);
8 :
9 : impl<K, V> Default for VecMap<K, V> {
10 5891901 : fn default() -> Self {
11 5891901 : VecMap(Default::default())
12 5891901 : }
13 : }
14 :
15 0 : #[derive(Debug)]
16 : pub struct InvalidKey;
17 :
18 : impl<K: Ord, V> VecMap<K, V> {
19 0 : pub fn is_empty(&self) -> bool {
20 0 : self.0.is_empty()
21 0 : }
22 :
23 10457491 : pub fn as_slice(&self) -> &[(K, V)] {
24 10457491 : self.0.as_slice()
25 10457491 : }
26 :
27 : /// This function may panic if given a range where the lower bound is
28 : /// greater than the upper bound.
29 4203684 : pub fn slice_range<R: RangeBounds<K>>(&self, range: R) -> &[(K, V)] {
30 4203684 : use std::ops::Bound::*;
31 4203684 :
32 8407276 : let binary_search = |k: &K| self.0.binary_search_by_key(&k, extract_key);
33 :
34 4203684 : let start_idx = match range.start_bound() {
35 54 : Unbounded => 0,
36 4203464 : Included(k) => binary_search(k).unwrap_or_else(std::convert::identity),
37 166 : Excluded(k) => match binary_search(k) {
38 72 : Ok(idx) => idx + 1,
39 94 : Err(idx) => idx,
40 : },
41 : };
42 :
43 4203684 : let end_idx = match range.end_bound() {
44 38 : Unbounded => self.0.len(),
45 198 : Included(k) => match binary_search(k) {
46 88 : Ok(idx) => idx + 1,
47 110 : Err(idx) => idx,
48 : },
49 4203448 : Excluded(k) => binary_search(k).unwrap_or_else(std::convert::identity),
50 : };
51 :
52 4203684 : &self.0[start_idx..end_idx]
53 4203684 : }
54 :
55 : /// Add a key value pair to the map.
56 : /// If `key` is less than or equal to the current maximum key
57 : /// the pair will not be added and InvalidKey error will be returned.
58 26 : pub fn append(&mut self, key: K, value: V) -> Result<usize, InvalidKey> {
59 26 : if let Some((last_key, _last_value)) = self.0.last() {
60 10 : if &key <= last_key {
61 0 : return Err(InvalidKey);
62 10 : }
63 16 : }
64 :
65 26 : let delta_size = self.instrument_vec_op(|vec| vec.push((key, value)));
66 26 : Ok(delta_size)
67 26 : }
68 :
69 : /// Update the maximum key value pair or add a new key value pair to the map.
70 : /// If `key` is less than the current maximum key no updates or additions
71 : /// will occur and InvalidKey error will be returned.
72 65308100 : pub fn append_or_update_last(
73 65308100 : &mut self,
74 65308100 : key: K,
75 65308100 : mut value: V,
76 65308100 : ) -> Result<(Option<V>, usize), InvalidKey> {
77 65308100 : if let Some((last_key, last_value)) = self.0.last_mut() {
78 59416217 : match key.cmp(last_key) {
79 0 : Ordering::Less => return Err(InvalidKey),
80 : Ordering::Equal => {
81 0 : std::mem::swap(last_value, &mut value);
82 0 : const DELTA_SIZE: usize = 0;
83 0 : return Ok((Some(value), DELTA_SIZE));
84 : }
85 59416217 : Ordering::Greater => {}
86 : }
87 5891883 : }
88 :
89 65308100 : let delta_size = self.instrument_vec_op(|vec| vec.push((key, value)));
90 65308100 : Ok((None, delta_size))
91 65308100 : }
92 :
93 : /// Split the map into two.
94 : ///
95 : /// The left map contains everything before `cutoff` (exclusive).
96 : /// Right map contains `cutoff` and everything after (inclusive).
97 0 : pub fn split_at(&self, cutoff: &K) -> (Self, Self)
98 0 : where
99 0 : K: Clone,
100 0 : V: Clone,
101 0 : {
102 0 : let split_idx = self
103 0 : .0
104 0 : .binary_search_by_key(&cutoff, extract_key)
105 0 : .unwrap_or_else(std::convert::identity);
106 0 :
107 0 : (
108 0 : VecMap(self.0[..split_idx].to_vec()),
109 0 : VecMap(self.0[split_idx..].to_vec()),
110 0 : )
111 0 : }
112 :
113 : /// Move items from `other` to the end of `self`, leaving `other` empty.
114 : /// If any keys in `other` is less than or equal to any key in `self`,
115 : /// `InvalidKey` error will be returned and no mutation will occur.
116 8 : pub fn extend(&mut self, other: &mut Self) -> Result<usize, InvalidKey> {
117 8 : let self_last_opt = self.0.last().map(extract_key);
118 8 : let other_first_opt = other.0.last().map(extract_key);
119 :
120 8 : if let (Some(self_last), Some(other_first)) = (self_last_opt, other_first_opt) {
121 6 : if self_last >= other_first {
122 4 : return Err(InvalidKey);
123 2 : }
124 2 : }
125 :
126 4 : let delta_size = self.instrument_vec_op(|vec| vec.append(&mut other.0));
127 4 : Ok(delta_size)
128 8 : }
129 :
130 : /// Instrument an operation on the underlying [`Vec`].
131 : /// Will panic if the operation decreases capacity.
132 : /// Returns the increase in memory usage caused by the op.
133 65308130 : fn instrument_vec_op(&mut self, op: impl FnOnce(&mut Vec<(K, V)>)) -> usize {
134 65308130 : let old_cap = self.0.capacity();
135 65308130 : op(&mut self.0);
136 65308130 : let new_cap = self.0.capacity();
137 65308130 :
138 65308130 : match old_cap.cmp(&new_cap) {
139 : Ordering::Less => {
140 7796396 : let old_size = Layout::array::<(K, V)>(old_cap).unwrap().size();
141 7796396 : let new_size = Layout::array::<(K, V)>(new_cap).unwrap().size();
142 7796396 : new_size - old_size
143 : }
144 57511734 : Ordering::Equal => 0,
145 0 : Ordering::Greater => panic!("VecMap capacity shouldn't ever decrease"),
146 : }
147 65308130 : }
148 : }
149 :
150 37668066 : fn extract_key<K, V>(entry: &(K, V)) -> &K {
151 37668066 : &entry.0
152 37668066 : }
153 :
154 : #[cfg(test)]
155 : mod tests {
156 : use std::{collections::BTreeMap, ops::Bound};
157 :
158 : use super::VecMap;
159 :
160 2 : #[test]
161 2 : fn unbounded_range() {
162 2 : let mut vec = VecMap::default();
163 2 : vec.append(0, ()).unwrap();
164 2 :
165 2 : assert_eq!(vec.slice_range(0..0), &[]);
166 2 : }
167 :
168 2 : #[test]
169 : #[should_panic]
170 2 : fn invalid_ordering_range() {
171 2 : let mut vec = VecMap::default();
172 2 : vec.append(0, ()).unwrap();
173 2 :
174 2 : #[allow(clippy::reversed_empty_ranges)]
175 2 : vec.slice_range(1..0);
176 2 : }
177 :
178 2 : #[test]
179 2 : fn range_tests() {
180 2 : let mut vec = VecMap::default();
181 2 : vec.append(0, ()).unwrap();
182 2 : vec.append(2, ()).unwrap();
183 2 : vec.append(4, ()).unwrap();
184 2 :
185 2 : assert_eq!(vec.slice_range(0..0), &[]);
186 2 : assert_eq!(vec.slice_range(0..1), &[(0, ())]);
187 2 : assert_eq!(vec.slice_range(0..2), &[(0, ())]);
188 2 : assert_eq!(vec.slice_range(0..3), &[(0, ()), (2, ())]);
189 :
190 2 : assert_eq!(vec.slice_range(..0), &[]);
191 2 : assert_eq!(vec.slice_range(..1), &[(0, ())]);
192 :
193 2 : assert_eq!(vec.slice_range(..3), &[(0, ()), (2, ())]);
194 2 : assert_eq!(vec.slice_range(..3), &[(0, ()), (2, ())]);
195 :
196 2 : assert_eq!(vec.slice_range(0..=0), &[(0, ())]);
197 2 : assert_eq!(vec.slice_range(0..=1), &[(0, ())]);
198 2 : assert_eq!(vec.slice_range(0..=2), &[(0, ()), (2, ())]);
199 2 : assert_eq!(vec.slice_range(0..=3), &[(0, ()), (2, ())]);
200 :
201 2 : assert_eq!(vec.slice_range(..=0), &[(0, ())]);
202 2 : assert_eq!(vec.slice_range(..=1), &[(0, ())]);
203 2 : assert_eq!(vec.slice_range(..=2), &[(0, ()), (2, ())]);
204 2 : assert_eq!(vec.slice_range(..=3), &[(0, ()), (2, ())]);
205 2 : }
206 :
207 : struct BoundIter {
208 : min: i32,
209 : max: i32,
210 :
211 : next: Option<Bound<i32>>,
212 : }
213 :
214 : impl BoundIter {
215 40 : fn new(min: i32, max: i32) -> Self {
216 40 : Self {
217 40 : min,
218 40 : max,
219 40 :
220 40 : next: Some(Bound::Unbounded),
221 40 : }
222 40 : }
223 : }
224 :
225 : impl Iterator for BoundIter {
226 : type Item = Bound<i32>;
227 :
228 480 : fn next(&mut self) -> Option<Self::Item> {
229 480 : let cur = self.next?;
230 :
231 440 : self.next = match &cur {
232 40 : Bound::Unbounded => Some(Bound::Included(self.min)),
233 200 : Bound::Included(x) => {
234 200 : if *x >= self.max {
235 40 : Some(Bound::Excluded(self.min))
236 : } else {
237 160 : Some(Bound::Included(x + 1))
238 : }
239 : }
240 200 : Bound::Excluded(x) => {
241 200 : if *x >= self.max {
242 40 : None
243 : } else {
244 160 : Some(Bound::Excluded(x + 1))
245 : }
246 : }
247 : };
248 :
249 440 : Some(cur)
250 480 : }
251 : }
252 :
253 2 : #[test]
254 2 : fn range_exhaustive() {
255 8 : let map: BTreeMap<i32, ()> = (1..=7).step_by(2).map(|x| (x, ())).collect();
256 2 : let mut vec = VecMap::default();
257 8 : for &key in map.keys() {
258 8 : vec.append(key, ()).unwrap();
259 8 : }
260 :
261 : const RANGE_MIN: i32 = 0;
262 : const RANGE_MAX: i32 = 8;
263 40 : for lower_bound in BoundIter::new(RANGE_MIN, RANGE_MAX) {
264 38 : let ub_min = match lower_bound {
265 2 : Bound::Unbounded => RANGE_MIN,
266 18 : Bound::Included(x) => x,
267 18 : Bound::Excluded(x) => x + 1,
268 : };
269 402 : for upper_bound in BoundIter::new(ub_min, RANGE_MAX) {
270 402 : let map_range: Vec<(i32, ())> = map
271 402 : .range((lower_bound, upper_bound))
272 640 : .map(|(&x, _)| (x, ()))
273 402 : .collect();
274 402 : let vec_slice = vec.slice_range((lower_bound, upper_bound));
275 402 :
276 402 : assert_eq!(map_range, vec_slice);
277 : }
278 : }
279 2 : }
280 :
281 2 : #[test]
282 2 : fn extend() {
283 2 : let mut left = VecMap::default();
284 2 : left.append(0, ()).unwrap();
285 2 : assert_eq!(left.as_slice(), &[(0, ())]);
286 :
287 2 : let mut empty = VecMap::default();
288 2 : left.extend(&mut empty).unwrap();
289 2 : assert_eq!(left.as_slice(), &[(0, ())]);
290 2 : assert_eq!(empty.as_slice(), &[]);
291 :
292 2 : let mut right = VecMap::default();
293 2 : right.append(1, ()).unwrap();
294 2 :
295 2 : left.extend(&mut right).unwrap();
296 2 :
297 2 : assert_eq!(left.as_slice(), &[(0, ()), (1, ())]);
298 2 : assert_eq!(right.as_slice(), &[]);
299 :
300 2 : let mut zero_map = VecMap::default();
301 2 : zero_map.append(0, ()).unwrap();
302 2 :
303 2 : left.extend(&mut zero_map).unwrap_err();
304 2 : assert_eq!(left.as_slice(), &[(0, ()), (1, ())]);
305 2 : assert_eq!(zero_map.as_slice(), &[(0, ())]);
306 :
307 2 : let mut one_map = VecMap::default();
308 2 : one_map.append(1, ()).unwrap();
309 2 :
310 2 : left.extend(&mut one_map).unwrap_err();
311 2 : assert_eq!(left.as_slice(), &[(0, ()), (1, ())]);
312 2 : assert_eq!(one_map.as_slice(), &[(1, ())]);
313 2 : }
314 : }
|
