Line data Source code
1 : use std::alloc::Layout;
2 : use std::cmp::Ordering;
3 : use std::ops::RangeBounds;
4 :
5 : #[derive(Clone, Copy, Debug, PartialEq, Eq)]
6 : pub enum VecMapOrdering {
7 : Greater,
8 : GreaterOrEqual,
9 : }
10 :
11 : /// Ordered map datastructure implemented in a Vec.
12 : ///
13 : /// Append only - can only add keys that are larger than the
14 : /// current max key.
15 : /// Ordering can be adjusted using [`VecMapOrdering`]
16 : /// during `VecMap` construction.
17 : #[derive(Clone, Debug)]
18 : pub struct VecMap<K, V> {
19 : data: Vec<(K, V)>,
20 : ordering: VecMapOrdering,
21 : }
22 :
23 : impl<K, V> Default for VecMap<K, V> {
24 9515732 : fn default() -> Self {
25 9515732 : VecMap {
26 9515732 : data: Default::default(),
27 9515732 : ordering: VecMapOrdering::Greater,
28 9515732 : }
29 9515732 : }
30 : }
31 :
32 : #[derive(thiserror::Error, Debug)]
33 : pub enum VecMapError {
34 : #[error("Key violates ordering constraint")]
35 : InvalidKey,
36 : #[error("Mismatched ordering constraints")]
37 : ExtendOrderingError,
38 : }
39 :
40 : impl<K: Ord, V> VecMap<K, V> {
41 4 : pub fn new(ordering: VecMapOrdering) -> Self {
42 4 : Self {
43 4 : data: Vec::new(),
44 4 : ordering,
45 4 : }
46 4 : }
47 :
48 4 : pub fn with_capacity(capacity: usize, ordering: VecMapOrdering) -> Self {
49 4 : Self {
50 4 : data: Vec::with_capacity(capacity),
51 4 : ordering,
52 4 : }
53 4 : }
54 :
55 0 : pub fn is_empty(&self) -> bool {
56 0 : self.data.is_empty()
57 0 : }
58 :
59 17775454 : pub fn as_slice(&self) -> &[(K, V)] {
60 17775454 : self.data.as_slice()
61 17775454 : }
62 :
63 : /// This function may panic if given a range where the lower bound is
64 : /// greater than the upper bound.
65 998832 : pub fn slice_range<R: RangeBounds<K>>(&self, range: R) -> &[(K, V)] {
66 : use std::ops::Bound::*;
67 :
68 1997618 : let binary_search = |k: &K| self.data.binary_search_by_key(&k, extract_key);
69 :
70 998832 : let start_idx = match range.start_bound() {
71 27 : Unbounded => 0,
72 998722 : Included(k) => binary_search(k).unwrap_or_else(std::convert::identity),
73 83 : Excluded(k) => match binary_search(k) {
74 36 : Ok(idx) => idx + 1,
75 47 : Err(idx) => idx,
76 : },
77 : };
78 :
79 998832 : let end_idx = match range.end_bound() {
80 19 : Unbounded => self.data.len(),
81 99 : Included(k) => match binary_search(k) {
82 44 : Ok(idx) => idx + 1,
83 55 : Err(idx) => idx,
84 : },
85 998714 : Excluded(k) => binary_search(k).unwrap_or_else(std::convert::identity),
86 : };
87 :
88 998832 : &self.data[start_idx..end_idx]
89 998832 : }
90 :
91 : /// Add a key value pair to the map.
92 : /// If `key` is not respective of the `self` ordering the
93 : /// pair will not be added and `InvalidKey` error will be returned.
94 5387109 : pub fn append(&mut self, key: K, value: V) -> Result<usize, VecMapError> {
95 5387109 : self.validate_key_order(&key)?;
96 :
97 5387107 : let delta_size = self.instrument_vec_op(|vec| vec.push((key, value)));
98 5387107 : Ok(delta_size)
99 37 : }
100 :
101 : /// Update the maximum key value pair or add a new key value pair to the map.
102 : /// If `key` is not respective of the `self` ordering no updates or additions
103 : /// will occur and `InvalidKey` error will be returned.
104 10181496 : pub fn append_or_update_last(
105 10181496 : &mut self,
106 10181496 : key: K,
107 10181496 : mut value: V,
108 10181496 : ) -> Result<(Option<V>, usize), VecMapError> {
109 10181496 : if let Some((last_key, last_value)) = self.data.last_mut() {
110 1107034 : match key.cmp(last_key) {
111 0 : Ordering::Less => return Err(VecMapError::InvalidKey),
112 : Ordering::Equal => {
113 0 : std::mem::swap(last_value, &mut value);
114 : const DELTA_SIZE: usize = 0;
115 0 : return Ok((Some(value), DELTA_SIZE));
116 : }
117 1107034 : Ordering::Greater => {}
118 : }
119 0 : }
120 :
121 10181496 : let delta_size = self.instrument_vec_op(|vec| vec.push((key, value)));
122 10181496 : Ok((None, delta_size))
123 0 : }
124 :
125 : /// Move items from `other` to the end of `self`, leaving `other` empty.
126 : /// If the `other` ordering is different from `self` ordering
127 : /// `ExtendOrderingError` error will be returned.
128 : /// If any keys in `other` is not respective of the ordering defined in
129 : /// `self`, `InvalidKey` error will be returned and no mutation will occur.
130 7 : pub fn extend(&mut self, other: &mut Self) -> Result<usize, VecMapError> {
131 7 : if self.ordering != other.ordering {
132 2 : return Err(VecMapError::ExtendOrderingError);
133 5 : }
134 5 :
135 5 : let other_first_opt = other.data.last().map(extract_key);
136 5 : if let Some(other_first) = other_first_opt {
137 4 : self.validate_key_order(other_first)?;
138 1 : }
139 :
140 3 : let delta_size = self.instrument_vec_op(|vec| vec.append(&mut other.data));
141 3 : Ok(delta_size)
142 7 : }
143 :
144 : /// Validate the current last key in `self` and key being
145 : /// inserted against the order defined in `self`.
146 5387113 : fn validate_key_order(&self, key: &K) -> Result<(), VecMapError> {
147 5387113 : if let Some(last_key) = self.data.last().map(extract_key) {
148 4945836 : match (&self.ordering, &key.cmp(last_key)) {
149 : (VecMapOrdering::Greater, Ordering::Less | Ordering::Equal) => {
150 3 : return Err(VecMapError::InvalidKey);
151 : }
152 4945821 : (VecMapOrdering::Greater, Ordering::Greater) => {}
153 : (VecMapOrdering::GreaterOrEqual, Ordering::Less) => {
154 1 : return Err(VecMapError::InvalidKey);
155 : }
156 11 : (VecMapOrdering::GreaterOrEqual, Ordering::Equal | Ordering::Greater) => {}
157 : }
158 16 : }
159 :
160 5387109 : Ok(())
161 41 : }
162 :
163 : /// Instrument an operation on the underlying [`Vec`].
164 : /// Will panic if the operation decreases capacity.
165 : /// Returns the increase in memory usage caused by the op.
166 15568606 : fn instrument_vec_op(&mut self, op: impl FnOnce(&mut Vec<(K, V)>)) -> usize {
167 15568606 : let old_cap = self.data.capacity();
168 15568606 : op(&mut self.data);
169 15568606 : let new_cap = self.data.capacity();
170 15568606 :
171 15568606 : match old_cap.cmp(&new_cap) {
172 : Ordering::Less => {
173 9590016 : let old_size = Layout::array::<(K, V)>(old_cap).unwrap().size();
174 9590016 : let new_size = Layout::array::<(K, V)>(new_cap).unwrap().size();
175 9590016 : new_size - old_size
176 : }
177 5978590 : Ordering::Equal => 0,
178 0 : Ordering::Greater => panic!("VecMap capacity shouldn't ever decrease"),
179 : }
180 38 : }
181 :
182 : /// Similar to `from_iter` defined in `FromIter` trait except
183 : /// that it accepts an [`VecMapOrdering`]
184 4 : pub fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I, ordering: VecMapOrdering) -> Self {
185 4 : let iter = iter.into_iter();
186 4 : let initial_capacity = {
187 4 : match iter.size_hint() {
188 0 : (lower_bound, None) => lower_bound,
189 4 : (_, Some(upper_bound)) => upper_bound,
190 : }
191 : };
192 :
193 4 : let mut vec_map = VecMap::with_capacity(initial_capacity, ordering);
194 22 : for (key, value) in iter {
195 18 : vec_map
196 18 : .append(key, value)
197 18 : .expect("The passed collection needs to be sorted!");
198 18 : }
199 :
200 4 : vec_map
201 4 : }
202 : }
203 :
204 : impl<K: Ord, V> IntoIterator for VecMap<K, V> {
205 : type Item = (K, V);
206 : type IntoIter = std::vec::IntoIter<(K, V)>;
207 :
208 0 : fn into_iter(self) -> Self::IntoIter {
209 0 : self.data.into_iter()
210 0 : }
211 : }
212 :
213 24724286 : fn extract_key<K, V>(entry: &(K, V)) -> &K {
214 24724286 : &entry.0
215 24724286 : }
216 :
217 : #[cfg(test)]
218 : mod tests {
219 : use std::collections::BTreeMap;
220 : use std::ops::Bound;
221 :
222 : use super::{VecMap, VecMapOrdering};
223 :
224 : #[test]
225 1 : fn unbounded_range() {
226 1 : let mut vec = VecMap::default();
227 1 : vec.append(0, ()).unwrap();
228 1 :
229 1 : assert_eq!(vec.slice_range(0..0), &[]);
230 1 : }
231 :
232 : #[test]
233 : #[should_panic]
234 1 : fn invalid_ordering_range() {
235 1 : let mut vec = VecMap::default();
236 1 : vec.append(0, ()).unwrap();
237 1 :
238 1 : #[allow(clippy::reversed_empty_ranges)]
239 1 : vec.slice_range(1..0);
240 1 : }
241 :
242 : #[test]
243 1 : fn range_tests() {
244 1 : let mut vec = VecMap::default();
245 1 : vec.append(0, ()).unwrap();
246 1 : vec.append(2, ()).unwrap();
247 1 : vec.append(4, ()).unwrap();
248 1 :
249 1 : assert_eq!(vec.slice_range(0..0), &[]);
250 1 : assert_eq!(vec.slice_range(0..1), &[(0, ())]);
251 1 : assert_eq!(vec.slice_range(0..2), &[(0, ())]);
252 1 : assert_eq!(vec.slice_range(0..3), &[(0, ()), (2, ())]);
253 :
254 1 : assert_eq!(vec.slice_range(..0), &[]);
255 1 : assert_eq!(vec.slice_range(..1), &[(0, ())]);
256 :
257 1 : assert_eq!(vec.slice_range(..3), &[(0, ()), (2, ())]);
258 1 : assert_eq!(vec.slice_range(..3), &[(0, ()), (2, ())]);
259 :
260 1 : assert_eq!(vec.slice_range(0..=0), &[(0, ())]);
261 1 : assert_eq!(vec.slice_range(0..=1), &[(0, ())]);
262 1 : assert_eq!(vec.slice_range(0..=2), &[(0, ()), (2, ())]);
263 1 : assert_eq!(vec.slice_range(0..=3), &[(0, ()), (2, ())]);
264 :
265 1 : assert_eq!(vec.slice_range(..=0), &[(0, ())]);
266 1 : assert_eq!(vec.slice_range(..=1), &[(0, ())]);
267 1 : assert_eq!(vec.slice_range(..=2), &[(0, ()), (2, ())]);
268 1 : assert_eq!(vec.slice_range(..=3), &[(0, ()), (2, ())]);
269 1 : }
270 :
271 : struct BoundIter {
272 : min: i32,
273 : max: i32,
274 :
275 : next: Option<Bound<i32>>,
276 : }
277 :
278 : impl BoundIter {
279 20 : fn new(min: i32, max: i32) -> Self {
280 20 : Self {
281 20 : min,
282 20 : max,
283 20 :
284 20 : next: Some(Bound::Unbounded),
285 20 : }
286 20 : }
287 : }
288 :
289 : impl Iterator for BoundIter {
290 : type Item = Bound<i32>;
291 :
292 240 : fn next(&mut self) -> Option<Self::Item> {
293 240 : let cur = self.next?;
294 :
295 220 : self.next = match &cur {
296 20 : Bound::Unbounded => Some(Bound::Included(self.min)),
297 100 : Bound::Included(x) => {
298 100 : if *x >= self.max {
299 20 : Some(Bound::Excluded(self.min))
300 : } else {
301 80 : Some(Bound::Included(x + 1))
302 : }
303 : }
304 100 : Bound::Excluded(x) => {
305 100 : if *x >= self.max {
306 20 : None
307 : } else {
308 80 : Some(Bound::Excluded(x + 1))
309 : }
310 : }
311 : };
312 :
313 220 : Some(cur)
314 240 : }
315 : }
316 :
317 : #[test]
318 1 : fn range_exhaustive() {
319 4 : let map: BTreeMap<i32, ()> = (1..=7).step_by(2).map(|x| (x, ())).collect();
320 1 : let mut vec = VecMap::default();
321 4 : for &key in map.keys() {
322 4 : vec.append(key, ()).unwrap();
323 4 : }
324 :
325 : const RANGE_MIN: i32 = 0;
326 : const RANGE_MAX: i32 = 8;
327 20 : for lower_bound in BoundIter::new(RANGE_MIN, RANGE_MAX) {
328 19 : let ub_min = match lower_bound {
329 1 : Bound::Unbounded => RANGE_MIN,
330 9 : Bound::Included(x) => x,
331 9 : Bound::Excluded(x) => x + 1,
332 : };
333 201 : for upper_bound in BoundIter::new(ub_min, RANGE_MAX) {
334 201 : let map_range: Vec<(i32, ())> = map
335 201 : .range((lower_bound, upper_bound))
336 320 : .map(|(&x, _)| (x, ()))
337 201 : .collect();
338 201 : let vec_slice = vec.slice_range((lower_bound, upper_bound));
339 201 :
340 201 : assert_eq!(map_range, vec_slice);
341 : }
342 : }
343 1 : }
344 :
345 : #[test]
346 1 : fn extend() {
347 1 : let mut left = VecMap::default();
348 1 : left.append(0, ()).unwrap();
349 1 : assert_eq!(left.as_slice(), &[(0, ())]);
350 :
351 1 : let mut empty = VecMap::default();
352 1 : left.extend(&mut empty).unwrap();
353 1 : assert_eq!(left.as_slice(), &[(0, ())]);
354 1 : assert_eq!(empty.as_slice(), &[]);
355 :
356 1 : let mut right = VecMap::default();
357 1 : right.append(1, ()).unwrap();
358 1 :
359 1 : left.extend(&mut right).unwrap();
360 1 :
361 1 : assert_eq!(left.as_slice(), &[(0, ()), (1, ())]);
362 1 : assert_eq!(right.as_slice(), &[]);
363 :
364 1 : let mut zero_map = VecMap::default();
365 1 : zero_map.append(0, ()).unwrap();
366 1 :
367 1 : left.extend(&mut zero_map).unwrap_err();
368 1 : assert_eq!(left.as_slice(), &[(0, ()), (1, ())]);
369 1 : assert_eq!(zero_map.as_slice(), &[(0, ())]);
370 :
371 1 : let mut one_map = VecMap::default();
372 1 : one_map.append(1, ()).unwrap();
373 1 :
374 1 : left.extend(&mut one_map).unwrap_err();
375 1 : assert_eq!(left.as_slice(), &[(0, ()), (1, ())]);
376 1 : assert_eq!(one_map.as_slice(), &[(1, ())]);
377 :
378 1 : let mut map_greater_or_equal = VecMap::new(VecMapOrdering::GreaterOrEqual);
379 1 : map_greater_or_equal.append(2, ()).unwrap();
380 1 : map_greater_or_equal.append(2, ()).unwrap();
381 1 :
382 1 : left.extend(&mut map_greater_or_equal).unwrap_err();
383 1 : assert_eq!(left.as_slice(), &[(0, ()), (1, ())]);
384 1 : assert_eq!(map_greater_or_equal.as_slice(), &[(2, ()), (2, ())]);
385 1 : }
386 :
387 : #[test]
388 1 : fn extend_with_ordering() {
389 1 : let mut left = VecMap::new(VecMapOrdering::GreaterOrEqual);
390 1 : left.append(0, ()).unwrap();
391 1 : assert_eq!(left.as_slice(), &[(0, ())]);
392 :
393 1 : let mut greater_right = VecMap::new(VecMapOrdering::Greater);
394 1 : greater_right.append(0, ()).unwrap();
395 1 : left.extend(&mut greater_right).unwrap_err();
396 1 : assert_eq!(left.as_slice(), &[(0, ())]);
397 :
398 1 : let mut greater_or_equal_right = VecMap::new(VecMapOrdering::GreaterOrEqual);
399 1 : greater_or_equal_right.append(2, ()).unwrap();
400 1 : greater_or_equal_right.append(2, ()).unwrap();
401 1 : left.extend(&mut greater_or_equal_right).unwrap();
402 1 : assert_eq!(left.as_slice(), &[(0, ()), (2, ()), (2, ())]);
403 1 : }
404 :
405 : #[test]
406 1 : fn vec_map_from_sorted() {
407 1 : let vec = vec![(1, ()), (2, ()), (3, ()), (6, ())];
408 1 : let vec_map = VecMap::from_iter(vec, VecMapOrdering::Greater);
409 1 : assert_eq!(vec_map.as_slice(), &[(1, ()), (2, ()), (3, ()), (6, ())]);
410 :
411 1 : let vec = vec![(1, ()), (2, ()), (3, ()), (3, ()), (6, ()), (6, ())];
412 1 : let vec_map = VecMap::from_iter(vec, VecMapOrdering::GreaterOrEqual);
413 1 : assert_eq!(
414 1 : vec_map.as_slice(),
415 1 : &[(1, ()), (2, ()), (3, ()), (3, ()), (6, ()), (6, ())]
416 1 : );
417 1 : }
418 :
419 : #[test]
420 : #[should_panic]
421 1 : fn vec_map_from_unsorted_greater() {
422 1 : let vec = vec![(1, ()), (2, ()), (2, ()), (3, ()), (6, ())];
423 1 : let _ = VecMap::from_iter(vec, VecMapOrdering::Greater);
424 1 : }
425 :
426 : #[test]
427 : #[should_panic]
428 1 : fn vec_map_from_unsorted_greater_or_equal() {
429 1 : let vec = vec![(1, ()), (2, ()), (3, ()), (6, ()), (5, ())];
430 1 : let _ = VecMap::from_iter(vec, VecMapOrdering::GreaterOrEqual);
431 1 : }
432 : }
|
