vec_collections/
vec_map.rs

1#![allow(clippy::clone_on_copy)]
2#[cfg(feature = "total")]
3use crate::iterators::SliceIterator;
4use crate::{
5    dedup::{sort_dedup_by_key, Keep},
6    merge_state::{InPlaceSmallVecMergeStateRef, MergeStateMut, NoConverter, SmallVecMergeState},
7    VecSet,
8};
9use crate::{iterators::VecMapIter, merge_state::InPlaceMergeState};
10use binary_merge::MergeOperation;
11#[cfg(feature = "rkyv_validated")]
12use bytecheck::CheckBytes;
13use core::{borrow::Borrow, cmp::Ordering, fmt, fmt::Debug, hash, hash::Hash, iter::FromIterator};
14#[cfg(feature = "rkyv")]
15use rkyv::{validation::ArchiveContext, Archive};
16use smallvec::{Array, SmallVec};
17use std::collections::BTreeMap;
18#[cfg(feature = "serde")]
19use {
20    core::marker::PhantomData,
21    serde::{
22        de::{Deserialize, Deserializer, MapAccess, Visitor},
23        ser::{Serialize, SerializeMap, Serializer},
24    },
25};
26
27/// An abstract vec map
28///
29/// this is implemented by VecMap and ArchivedVecMap, so they are interoperable.
30pub trait AbstractVecMap<K, V> {
31    fn as_slice(&self) -> &[(K, V)];
32
33    fn is_empty(&self) -> bool {
34        self.as_slice().is_empty()
35    }
36
37    fn iter(&self) -> VecMapIter<core::slice::Iter<(K, V)>> {
38        VecMapIter::new(self.as_slice().iter())
39    }
40
41    /// lookup of a mapping. Time complexity is O(log N). Binary search.
42    fn get<Q>(&self, key: &Q) -> Option<&V>
43    where
44        K: Borrow<Q> + 'static,
45        Q: Ord + ?Sized,
46    {
47        let elements = self.as_slice();
48        elements
49            .binary_search_by(|p| p.0.borrow().cmp(key))
50            .map(|index| &elements[index].1)
51            .ok()
52    }
53
54    /// Perform an outer join with another VecMap, producing a new result
55    ///
56    ///
57    fn outer_join<W, R, F, A>(&self, that: &impl AbstractVecMap<K, W>, f: F) -> VecMap<A>
58    where
59        K: Ord + Clone,
60        A: Array<Item = (K, R)>,
61        F: Fn(OuterJoinArg<&K, &V, &W>) -> Option<R>,
62    {
63        VecMap::<A>::new(SmallVecMergeState::merge(
64            self.as_slice(),
65            that.as_slice(),
66            OuterJoinOp(f),
67            NoConverter,
68        ))
69    }
70
71    fn left_join<W, R, F, A>(&self, that: &impl AbstractVecMap<K, W>, f: F) -> VecMap<A>
72    where
73        K: Ord + Clone,
74        F: Fn(&K, &V, Option<&W>) -> Option<R>,
75        A: Array<Item = (K, R)>,
76    {
77        VecMap::new(SmallVecMergeState::merge(
78            self.as_slice(),
79            that.as_slice(),
80            LeftJoinOp(f),
81            NoConverter,
82        ))
83    }
84
85    fn right_join<W, R, F, A>(&self, that: &impl AbstractVecMap<K, W>, f: F) -> VecMap<A>
86    where
87        K: Ord + Clone,
88        F: Fn(&K, Option<&V>, &W) -> Option<R>,
89        A: Array<Item = (K, R)>,
90    {
91        VecMap::new(SmallVecMergeState::merge(
92            self.as_slice(),
93            that.as_slice(),
94            RightJoinOp(f),
95            NoConverter,
96        ))
97    }
98
99    fn inner_join<W, R, F, A>(&self, that: &impl AbstractVecMap<K, W>, f: F) -> VecMap<A>
100    where
101        K: Ord + Clone,
102        F: Fn(&K, &V, &W) -> Option<R>,
103        A: Array<Item = (K, R)>,
104    {
105        VecMap::new(SmallVecMergeState::merge(
106            self.as_slice(),
107            that.as_slice(),
108            InnerJoinOp(f),
109            NoConverter,
110        ))
111    }
112}
113
114impl<K, V, A: Array<Item = (K, V)>> AbstractVecMap<K, V> for VecMap<A> {
115    fn as_slice(&self) -> &[A::Item] {
116        self.0.as_slice()
117    }
118}
119
120#[cfg(feature = "rkyv")]
121impl<K, V> AbstractVecMap<K, V> for ArchivedVecMap<K, V> {
122    fn as_slice(&self) -> &[(K, V)] {
123        self.0.as_slice()
124    }
125}
126
127/// A map backed by a [SmallVec] of key value pairs.
128///
129/// [SmallVec]: https://docs.rs/smallvec/1.4.1/smallvec/struct.SmallVec.html
130pub struct VecMap<A: Array>(SmallVec<A>);
131
132/// Type alias for a [VecMap](struct.VecMap) with up to 1 mapping with inline storage.
133///
134/// This is a good default, since for usize sized keys and values, 1 mapping is the max you can fit in without making the struct larger.
135pub type VecMap1<K, V> = VecMap<[(K, V); 1]>;
136
137impl<T: Debug, A: Array<Item = T>> Debug for VecMap<A> {
138    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
139        f.debug_set().entries(self.as_slice().iter()).finish()
140    }
141}
142
143impl<T: Clone, A: Array<Item = T>> Clone for VecMap<A> {
144    fn clone(&self) -> Self {
145        Self(self.0.clone())
146    }
147}
148
149impl<T: Hash, A: Array<Item = T>> Hash for VecMap<A> {
150    fn hash<H: hash::Hasher>(&self, state: &mut H) {
151        self.0.hash(state)
152    }
153}
154
155impl<T: PartialEq, A: Array<Item = T>> PartialEq for VecMap<A> {
156    fn eq(&self, other: &Self) -> bool {
157        self.0 == other.0
158    }
159}
160
161impl<T: Eq, A: Array<Item = T>> Eq for VecMap<A> {}
162
163impl<T: PartialOrd, A: Array<Item = T>> PartialOrd for VecMap<A> {
164    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
165        self.0.partial_cmp(&other.0)
166    }
167}
168
169impl<T: Ord, A: Array<Item = T>> Ord for VecMap<A> {
170    fn cmp(&self, other: &Self) -> Ordering {
171        self.0.cmp(&other.0)
172    }
173}
174
175impl<'a, K: 'a, V: 'a, A: Array<Item = (K, V)>> IntoIterator for &'a VecMap<A> {
176    type Item = &'a A::Item;
177    type IntoIter = VecMapIter<core::slice::Iter<'a, A::Item>>;
178    fn into_iter(self) -> Self::IntoIter {
179        self.iter()
180    }
181}
182
183impl<A: Array> IntoIterator for VecMap<A> {
184    type Item = A::Item;
185    type IntoIter = VecMapIter<smallvec::IntoIter<A>>;
186    fn into_iter(self) -> Self::IntoIter {
187        VecMapIter::new(self.0.into_iter())
188    }
189}
190
191impl<A: Array> Default for VecMap<A> {
192    fn default() -> Self {
193        VecMap(SmallVec::default())
194    }
195}
196
197impl<A: Array> From<VecMap<A>> for VecSet<A> {
198    fn from(value: VecMap<A>) -> Self {
199        // entries are sorted by unique first elemnt, so they are also a valid set
200        VecSet::new_unsafe(value.0)
201    }
202}
203
204struct CombineOp<F, K>(F, std::marker::PhantomData<K>);
205
206impl<'a, K: Ord, V, A: Array<Item = (K, V)>, B: Array<Item = (K, V)>, F: Fn(V, V) -> V>
207    MergeOperation<InPlaceMergeState<'a, A, B>> for CombineOp<F, K>
208{
209    fn cmp(&self, a: &(K, V), b: &(K, V)) -> Ordering {
210        a.0.cmp(&b.0)
211    }
212    fn from_a(&self, m: &mut InPlaceMergeState<A, B>, n: usize) -> bool {
213        m.advance_a(n, true)
214    }
215    fn from_b(&self, m: &mut InPlaceMergeState<A, B>, n: usize) -> bool {
216        m.advance_b(n, true)
217    }
218    fn collision(&self, m: &mut InPlaceMergeState<A, B>) -> bool {
219        if let (Some((ak, av)), Some((_, bv))) = (m.a.pop_front(), m.b.next()) {
220            let r = (self.0)(av, bv);
221            m.a.push((ak, r));
222        }
223        true
224    }
225}
226
227pub enum OuterJoinArg<K, A, B> {
228    Left(K, A),
229    Right(K, B),
230    Both(K, A, B),
231}
232
233struct OuterJoinOp<F>(F);
234struct LeftJoinOp<F>(F);
235struct RightJoinOp<F>(F);
236struct InnerJoinOp<F>(F);
237
238impl<K: Ord, V, A: Array<Item = (K, V)>> FromIterator<(K, V)> for VecMap<A> {
239    fn from_iter<I: IntoIterator<Item = A::Item>>(iter: I) -> Self {
240        VecMap(sort_dedup_by_key(iter.into_iter(), Keep::Last, |(k, _)| k))
241    }
242}
243
244impl<K, V, A: Array<Item = (K, V)>> From<BTreeMap<K, V>> for VecMap<A> {
245    fn from(value: BTreeMap<K, V>) -> Self {
246        Self::new(value.into_iter().collect())
247    }
248}
249
250impl<K: Ord + 'static, V, A: Array<Item = (K, V)>> Extend<A::Item> for VecMap<A> {
251    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
252        self.merge_with::<A>(iter.into_iter().collect());
253    }
254}
255
256impl<A: Array> AsRef<[A::Item]> for VecMap<A> {
257    fn as_ref(&self) -> &[A::Item] {
258        self.as_slice()
259    }
260}
261
262impl<A: Array> From<VecMap<A>> for SmallVec<A> {
263    fn from(value: VecMap<A>) -> Self {
264        value.0
265    }
266}
267
268impl<'a, K, V, W, R, A, F> MergeOperation<SmallVecMergeState<'a, (K, V), (K, W), A>>
269    for OuterJoinOp<F>
270where
271    K: Ord + Clone,
272    A: Array<Item = (K, R)>,
273    F: Fn(OuterJoinArg<&K, &V, &W>) -> Option<R>,
274{
275    fn cmp(&self, a: &(K, V), b: &(K, W)) -> Ordering {
276        a.0.cmp(&b.0)
277    }
278    fn from_a(&self, m: &mut SmallVecMergeState<'a, (K, V), (K, W), A>, n: usize) -> bool {
279        for _ in 0..n {
280            if let Some((k, a)) = m.a.next() {
281                let arg = OuterJoinArg::Left(k, a);
282                if let Some(res) = (self.0)(arg) {
283                    m.r.push((k.clone(), res));
284                }
285            }
286        }
287        true
288    }
289    fn from_b(&self, m: &mut SmallVecMergeState<'a, (K, V), (K, W), A>, n: usize) -> bool {
290        for _ in 0..n {
291            if let Some((k, b)) = m.b.next() {
292                let arg = OuterJoinArg::Right(k, b);
293                if let Some(res) = (self.0)(arg) {
294                    m.r.push((k.clone(), res));
295                }
296            }
297        }
298        true
299    }
300    fn collision(&self, m: &mut SmallVecMergeState<'a, (K, V), (K, W), A>) -> bool {
301        if let Some((k, a)) = m.a.next() {
302            if let Some((_, b)) = m.b.next() {
303                let arg = OuterJoinArg::Both(k, a, b);
304                if let Some(res) = (self.0)(arg) {
305                    m.r.push((k.clone(), res));
306                }
307            }
308        }
309        true
310    }
311}
312
313impl<'a, K, V, W, F, A> MergeOperation<InPlaceSmallVecMergeStateRef<'a, A, (K, W)>>
314    for OuterJoinOp<F>
315where
316    A: Array<Item = (K, V)>,
317    K: Ord + Clone,
318    F: Fn(OuterJoinArg<&K, V, &W>) -> Option<V>,
319{
320    fn cmp(&self, a: &(K, V), b: &(K, W)) -> Ordering {
321        a.0.cmp(&b.0)
322    }
323    fn from_a(&self, m: &mut InPlaceSmallVecMergeStateRef<'a, A, (K, W)>, n: usize) -> bool {
324        for _ in 0..n {
325            if let Some((k, v)) = m.a.pop_front() {
326                if let Some(v) = (self.0)(OuterJoinArg::Left(&k, v)) {
327                    m.a.push((k, v));
328                }
329            }
330        }
331        true
332    }
333    fn from_b(&self, m: &mut InPlaceSmallVecMergeStateRef<'a, A, (K, W)>, n: usize) -> bool {
334        for _ in 0..n {
335            if let Some((k, b)) = m.b.next() {
336                if let Some(v) = (self.0)(OuterJoinArg::Right(k, b)) {
337                    m.a.push((k.clone(), v));
338                }
339            }
340        }
341        true
342    }
343    fn collision(&self, m: &mut InPlaceSmallVecMergeStateRef<'a, A, (K, W)>) -> bool {
344        if let Some((k, v)) = m.a.pop_front() {
345            if let Some((_, w)) = m.b.next() {
346                if let Some(v) = (self.0)(OuterJoinArg::Both(&k, v, w)) {
347                    m.a.push((k, v));
348                }
349            }
350        }
351        true
352    }
353}
354
355impl<'a, K, V, W, F, A, B> MergeOperation<InPlaceMergeState<'a, A, B>> for OuterJoinOp<F>
356where
357    A: Array<Item = (K, V)>,
358    B: Array<Item = (K, W)>,
359    K: Ord,
360    F: Fn(OuterJoinArg<&K, V, W>) -> Option<V>,
361{
362    fn cmp(&self, a: &(K, V), b: &(K, W)) -> Ordering {
363        a.0.cmp(&b.0)
364    }
365    fn from_a(&self, m: &mut InPlaceMergeState<'a, A, B>, n: usize) -> bool {
366        for _ in 0..n {
367            if let Some((k, v)) = m.a.pop_front() {
368                if let Some(v) = (self.0)(OuterJoinArg::Left(&k, v)) {
369                    m.a.push((k, v));
370                }
371            }
372        }
373        true
374    }
375    fn from_b(&self, m: &mut InPlaceMergeState<'a, A, B>, n: usize) -> bool {
376        for _ in 0..n {
377            if let Some((k, b)) = m.b.next() {
378                if let Some(v) = (self.0)(OuterJoinArg::Right(&k, b)) {
379                    m.a.push((k, v));
380                }
381            }
382        }
383        true
384    }
385    fn collision(&self, m: &mut InPlaceMergeState<'a, A, B>) -> bool {
386        if let Some((k, v)) = m.a.pop_front() {
387            if let Some((_, w)) = m.b.next() {
388                if let Some(v) = (self.0)(OuterJoinArg::Both(&k, v, w)) {
389                    m.a.push((k, v));
390                }
391            }
392        }
393        true
394    }
395}
396
397impl<'a, K, V, W, R, F, A> MergeOperation<SmallVecMergeState<'a, (K, V), (K, W), A>>
398    for LeftJoinOp<F>
399where
400    K: Ord + Clone,
401    A: Array<Item = (K, R)>,
402    F: Fn(&K, &V, Option<&W>) -> Option<R>,
403{
404    fn cmp(&self, a: &(K, V), b: &(K, W)) -> Ordering {
405        a.0.cmp(&b.0)
406    }
407    fn from_a(&self, m: &mut SmallVecMergeState<'a, (K, V), (K, W), A>, n: usize) -> bool {
408        for _ in 0..n {
409            if let Some((k, a)) = m.a.next() {
410                if let Some(res) = (self.0)(k, a, None) {
411                    m.r.push((k.clone(), res));
412                }
413            }
414        }
415        true
416    }
417    fn from_b(&self, m: &mut SmallVecMergeState<'a, (K, V), (K, W), A>, n: usize) -> bool {
418        m.b.drop_front(n);
419        true
420    }
421    fn collision(&self, m: &mut SmallVecMergeState<'a, (K, V), (K, W), A>) -> bool {
422        if let Some((k, a)) = m.a.next() {
423            if let Some((_, b)) = m.b.next() {
424                if let Some(res) = (self.0)(k, a, Some(b)) {
425                    m.r.push((k.clone(), res));
426                }
427            }
428        }
429        true
430    }
431}
432
433impl<'a, K, V, W, F, A> MergeOperation<InPlaceSmallVecMergeStateRef<'a, A, (K, W)>>
434    for LeftJoinOp<F>
435where
436    A: Array<Item = (K, V)>,
437    K: Ord + Clone,
438    F: Fn(&K, V, Option<&W>) -> Option<V>,
439{
440    fn cmp(&self, a: &(K, V), b: &(K, W)) -> Ordering {
441        a.0.cmp(&b.0)
442    }
443    fn from_a(&self, m: &mut InPlaceSmallVecMergeStateRef<'a, A, (K, W)>, n: usize) -> bool {
444        for _ in 0..n {
445            if let Some((k, v)) = m.a.pop_front() {
446                if let Some(v) = (self.0)(&k, v, None) {
447                    m.a.push((k, v))
448                }
449            }
450        }
451        true
452    }
453    fn from_b(&self, m: &mut InPlaceSmallVecMergeStateRef<'a, A, (K, W)>, n: usize) -> bool {
454        m.b.drop_front(n);
455        true
456    }
457    fn collision(&self, m: &mut InPlaceSmallVecMergeStateRef<'a, A, (K, W)>) -> bool {
458        if let Some((k, v)) = m.a.pop_front() {
459            if let Some((_, w)) = m.b.next() {
460                if let Some(v) = (self.0)(&k, v, Some(w)) {
461                    m.a.push((k, v))
462                }
463            }
464        }
465        true
466    }
467}
468
469impl<'a, K, V, W, R, F, A> MergeOperation<SmallVecMergeState<'a, (K, V), (K, W), A>>
470    for RightJoinOp<F>
471where
472    K: Ord + Clone,
473    A: Array<Item = (K, R)>,
474    F: Fn(&K, Option<&V>, &W) -> Option<R>,
475{
476    fn cmp(&self, a: &(K, V), b: &(K, W)) -> Ordering {
477        a.0.cmp(&b.0)
478    }
479    fn from_a(&self, m: &mut SmallVecMergeState<'a, (K, V), (K, W), A>, n: usize) -> bool {
480        m.a.drop_front(n);
481        true
482    }
483    fn from_b(&self, m: &mut SmallVecMergeState<'a, (K, V), (K, W), A>, n: usize) -> bool {
484        for _ in 0..n {
485            if let Some((k, b)) = m.b.next() {
486                if let Some(res) = (self.0)(k, None, b) {
487                    m.r.push((k.clone(), res));
488                }
489            }
490        }
491        true
492    }
493    fn collision(&self, m: &mut SmallVecMergeState<'a, (K, V), (K, W), A>) -> bool {
494        if let Some((k, a)) = m.a.next() {
495            if let Some((_, b)) = m.b.next() {
496                if let Some(res) = (self.0)(k, Some(a), b) {
497                    m.r.push((k.clone(), res));
498                }
499            }
500        }
501        true
502    }
503}
504
505impl<'a, K, V, W, F, A> MergeOperation<InPlaceSmallVecMergeStateRef<'a, A, (K, W)>>
506    for RightJoinOp<F>
507where
508    A: Array<Item = (K, V)>,
509    K: Ord + Clone,
510    F: Fn(&K, Option<V>, &W) -> Option<V>,
511{
512    fn cmp(&self, a: &(K, V), b: &(K, W)) -> Ordering {
513        a.0.cmp(&b.0)
514    }
515    fn from_a(&self, m: &mut InPlaceSmallVecMergeStateRef<'a, A, (K, W)>, n: usize) -> bool {
516        m.a.consume(n, false);
517        true
518    }
519    fn from_b(&self, m: &mut InPlaceSmallVecMergeStateRef<'a, A, (K, W)>, n: usize) -> bool {
520        for _ in 0..n {
521            if let Some((k, w)) = m.b.next() {
522                if let Some(v) = (self.0)(k, None, w) {
523                    m.a.push((k.clone(), v))
524                }
525            }
526        }
527        true
528    }
529    fn collision(&self, m: &mut InPlaceSmallVecMergeStateRef<'a, A, (K, W)>) -> bool {
530        if let Some((k, v)) = m.a.pop_front() {
531            if let Some((_, w)) = m.b.next() {
532                if let Some(res) = (self.0)(&k, Some(v), w) {
533                    m.a.push((k, res));
534                }
535            }
536        }
537        true
538    }
539}
540
541impl<'a, K, V, W, R, F, A> MergeOperation<SmallVecMergeState<'a, (K, V), (K, W), A>>
542    for InnerJoinOp<F>
543where
544    K: Ord + Clone,
545    A: Array<Item = (K, R)>,
546    F: Fn(&K, &V, &W) -> Option<R>,
547{
548    fn cmp(&self, a: &(K, V), b: &(K, W)) -> Ordering {
549        a.0.cmp(&b.0)
550    }
551    fn from_a(&self, m: &mut SmallVecMergeState<'a, (K, V), (K, W), A>, n: usize) -> bool {
552        m.a.drop_front(n);
553        true
554    }
555    fn from_b(&self, m: &mut SmallVecMergeState<'a, (K, V), (K, W), A>, n: usize) -> bool {
556        m.b.drop_front(n);
557        true
558    }
559    fn collision(&self, m: &mut SmallVecMergeState<'a, (K, V), (K, W), A>) -> bool {
560        if let Some((k, a)) = m.a.next() {
561            if let Some((_, b)) = m.b.next() {
562                if let Some(res) = (self.0)(k, a, b) {
563                    m.r.push((k.clone(), res));
564                }
565            }
566        }
567        true
568    }
569}
570
571impl<'a, K, V, W, F, A> MergeOperation<InPlaceSmallVecMergeStateRef<'a, A, (K, W)>>
572    for InnerJoinOp<F>
573where
574    A: Array<Item = (K, V)>,
575    K: Ord + Clone,
576    F: Fn(&K, V, &W) -> Option<V>,
577{
578    fn cmp(&self, a: &(K, V), b: &(K, W)) -> Ordering {
579        a.0.cmp(&b.0)
580    }
581    fn from_a(&self, m: &mut InPlaceSmallVecMergeStateRef<'a, A, (K, W)>, n: usize) -> bool {
582        m.a.consume(n, false);
583        true
584    }
585    fn from_b(&self, m: &mut InPlaceSmallVecMergeStateRef<'a, A, (K, W)>, n: usize) -> bool {
586        m.b.drop_front(n);
587        true
588    }
589    fn collision(&self, m: &mut InPlaceSmallVecMergeStateRef<'a, A, (K, W)>) -> bool {
590        if let Some((k, v)) = m.a.pop_front() {
591            if let Some((_, w)) = m.b.next() {
592                if let Some(v) = (self.0)(&k, v, w) {
593                    m.a.push((k, v))
594                }
595            }
596        }
597        true
598    }
599}
600
601impl<K, V, A: Array<Item = (K, V)>> VecMap<A> {
602    /// map values while keeping keys
603    pub fn map_values<R, B: Array<Item = (K, R)>, F: FnMut(V) -> R>(self, mut f: F) -> VecMap<B> {
604        VecMap::new(
605            self.0
606                .into_iter()
607                .map(|entry| (entry.0, f(entry.1)))
608                .collect(),
609        )
610    }
611}
612
613impl<A: Array> VecMap<A> {
614    /// private because it does not check invariants
615    pub(crate) fn new(value: SmallVec<A>) -> Self {
616        Self(value)
617    }
618
619    pub fn is_empty(&self) -> bool {
620        self.0.is_empty()
621    }
622
623    pub fn empty() -> Self {
624        Self(SmallVec::new())
625    }
626
627    /// number of mappings
628    pub fn len(&self) -> usize {
629        self.0.len()
630    }
631
632    /// the underlying memory as a slice of key value pairs
633    fn as_slice(&self) -> &[A::Item] {
634        self.0.as_ref()
635    }
636
637    /// retain all pairs matching a predicate
638    pub fn retain<F: FnMut(&A::Item) -> bool>(&mut self, mut f: F) {
639        self.0.retain(|entry| f(entry))
640    }
641
642    #[cfg(feature = "total")]
643    pub(crate) fn slice_iter(&self) -> SliceIterator<A::Item> {
644        SliceIterator(self.0.as_slice())
645    }
646
647    pub fn into_inner(self) -> SmallVec<A> {
648        self.0
649    }
650
651    /// Creates a vecmap with a single item
652    pub fn single(item: A::Item) -> Self {
653        Self(smallvec::smallvec![item])
654    }
655}
656
657impl<K: Ord + 'static, V, A: Array<Item = (K, V)>> VecMap<A> {
658    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
659        match self.0.binary_search_by(|(k, _)| k.cmp(&key)) {
660            Ok(index) => {
661                let mut elem = (key, value);
662                std::mem::swap(&mut elem, &mut self.0[index]);
663                Some(elem.1)
664            }
665            Err(ip) => {
666                self.0.insert(ip, (key, value));
667                None
668            }
669        }
670    }
671
672    pub fn inner_join_with<W, F>(&mut self, that: &impl AbstractVecMap<K, W>, f: F)
673    where
674        K: Ord + Clone,
675        F: Fn(&K, V, &W) -> Option<V>,
676    {
677        InPlaceSmallVecMergeStateRef::merge(
678            &mut self.0,
679            &that.as_slice(),
680            InnerJoinOp(f),
681            NoConverter,
682        )
683    }
684
685    pub fn left_join_with<W, F>(&mut self, that: &impl AbstractVecMap<K, W>, f: F)
686    where
687        K: Ord + Clone,
688        F: Fn(&K, V, Option<&W>) -> Option<V>,
689    {
690        InPlaceSmallVecMergeStateRef::merge(
691            &mut self.0,
692            &that.as_slice(),
693            LeftJoinOp(f),
694            NoConverter,
695        )
696    }
697
698    pub fn right_join_with<W, F>(&mut self, that: &impl AbstractVecMap<K, W>, f: F)
699    where
700        K: Ord + Clone,
701        F: Fn(&K, Option<V>, &W) -> Option<V>,
702    {
703        InPlaceSmallVecMergeStateRef::merge(
704            &mut self.0,
705            &that.as_slice(),
706            RightJoinOp(f),
707            NoConverter,
708        )
709    }
710
711    pub fn outer_join_with<W, F>(&mut self, that: &impl AbstractVecMap<K, W>, f: F)
712    where
713        K: Ord + Clone,
714        F: Fn(OuterJoinArg<&K, V, &W>) -> Option<V>,
715    {
716        InPlaceSmallVecMergeStateRef::merge(
717            &mut self.0,
718            &that.as_slice(),
719            OuterJoinOp(f),
720            NoConverter,
721        )
722    }
723
724    /// in-place merge with another map of the same type. The merge is right-biased, so on collisions the values
725    /// from the rhs will win.
726    pub fn merge_with<B: Array<Item = (K, V)>>(&mut self, that: VecMap<B>) {
727        self.combine_with(that, |_, r| r)
728    }
729
730    /// in-place combine with another map of the same type. The given function allows to select the value in case
731    /// of collisions.
732    pub fn combine_with<B: Array<Item = A::Item>, F: Fn(V, V) -> V>(
733        &mut self,
734        that: VecMap<B>,
735        f: F,
736    ) {
737        InPlaceMergeState::merge(
738            &mut self.0,
739            that.0,
740            OuterJoinOp(move |arg: OuterJoinArg<&K, V, V>| {
741                Some(match arg {
742                    OuterJoinArg::Left(_, v) => v,
743                    OuterJoinArg::Right(_, v) => v,
744                    OuterJoinArg::Both(_, v, w) => f(v, w),
745                })
746            }),
747            NoConverter,
748        );
749    }
750}
751
752impl<K: Ord + 'static, V, A: Array<Item = (K, V)>> VecMap<A> {
753    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
754    where
755        K: Borrow<Q>,
756        Q: Ord + ?Sized,
757    {
758        let elements = self.0.as_mut_slice();
759        match elements.binary_search_by(|p| p.0.borrow().cmp(key)) {
760            Ok(index) => Some(&mut elements[index].1),
761            Err(_) => None,
762        }
763    }
764}
765
766#[cfg(feature = "serde")]
767impl<K, V, A: Array<Item = (K, V)>> Serialize for VecMap<A>
768where
769    K: Serialize,
770    V: Serialize,
771{
772    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
773        let mut state = serializer.serialize_map(Some(self.len()))?;
774        for (k, v) in self.0.iter() {
775            state.serialize_entry(&k, &v)?;
776        }
777        state.end()
778    }
779}
780
781#[cfg(feature = "serde")]
782impl<'de, K, V, A: Array<Item = (K, V)>> Deserialize<'de> for VecMap<A>
783where
784    K: Deserialize<'de> + Ord + PartialEq + Clone,
785    V: Deserialize<'de>,
786{
787    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
788        deserializer.deserialize_map(VecMapVisitor {
789            phantom: PhantomData,
790        })
791    }
792}
793
794#[cfg(feature = "serde")]
795struct VecMapVisitor<K, V, A> {
796    phantom: PhantomData<(K, V, A)>,
797}
798
799#[cfg(feature = "serde")]
800impl<'de, K, V, A> Visitor<'de> for VecMapVisitor<K, V, A>
801where
802    A: Array<Item = (K, V)>,
803    K: Deserialize<'de> + Ord + PartialEq + Clone,
804    V: Deserialize<'de>,
805{
806    type Value = VecMap<A>;
807
808    fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
809        formatter.write_str("a map")
810    }
811
812    fn visit_map<M: MapAccess<'de>>(self, mut map: M) -> Result<Self::Value, M::Error> {
813        let len = map.size_hint().unwrap_or(0);
814        let mut values: SmallVec<A> = SmallVec::with_capacity(len);
815
816        while let Some(value) = map.next_entry::<K, V>()? {
817            values.push(value);
818        }
819        values.sort_by_key(|x: &(K, V)| x.0.clone());
820        values.dedup_by_key(|x: &mut (K, V)| x.0.clone());
821        Ok(VecMap(values))
822    }
823}
824
825#[cfg(feature = "rkyv")]
826#[repr(transparent)]
827pub struct ArchivedVecMap<K, V>(rkyv::vec::ArchivedVec<(K, V)>);
828
829#[cfg(feature = "rkyv")]
830impl<K, V, A> rkyv::Archive for VecMap<A>
831where
832    A: Array<Item = (K, V)>,
833    K: rkyv::Archive,
834    V: rkyv::Archive,
835{
836    type Archived = ArchivedVecMap<K::Archived, V::Archived>;
837
838    type Resolver = rkyv::vec::VecResolver;
839
840    unsafe fn resolve(&self, pos: usize, resolver: Self::Resolver, out: *mut Self::Archived) {
841        rkyv::vec::ArchivedVec::resolve_from_slice(self.0.as_slice(), pos, resolver, &mut (*out).0);
842    }
843}
844
845#[cfg(feature = "rkyv")]
846impl<S, K, V, A> rkyv::Serialize<S> for VecMap<A>
847where
848    A: Array<Item = (K, V)>,
849    K: rkyv::Archive + rkyv::Serialize<S>,
850    V: rkyv::Archive + rkyv::Serialize<S>,
851    S: rkyv::ser::ScratchSpace + rkyv::ser::Serializer,
852{
853    fn serialize(&self, serializer: &mut S) -> Result<Self::Resolver, S::Error> {
854        rkyv::vec::ArchivedVec::serialize_from_slice(self.0.as_ref(), serializer)
855    }
856}
857
858#[cfg(feature = "rkyv")]
859impl<D, K, V, A> rkyv::Deserialize<VecMap<A>, D> for ArchivedVecMap<K::Archived, V::Archived>
860where
861    A: Array<Item = (K, V)>,
862    K: rkyv::Archive,
863    V: rkyv::Archive,
864    D: rkyv::Fallible + ?Sized,
865    [<<A as Array>::Item as rkyv::Archive>::Archived]:
866        rkyv::DeserializeUnsized<[<A as Array>::Item], D>,
867{
868    fn deserialize(&self, deserializer: &mut D) -> Result<VecMap<A>, D::Error> {
869        // todo: replace this with SmallVec once smallvec support for rkyv lands on crates.io
870        let items: Vec<(K, V)> = self.0.deserialize(deserializer)?;
871        Ok(VecMap(items.into()))
872    }
873}
874
875/// Validation error for a vec map
876#[cfg(feature = "rkyv_validated")]
877#[derive(Debug)]
878pub enum ArchivedVecMapError {
879    /// error with the individual elements of the VecSet
880    ValueCheckError,
881    /// elements were not properly ordered
882    OrderCheckError,
883}
884
885#[cfg(feature = "rkyv_validated")]
886impl std::error::Error for ArchivedVecMapError {}
887
888#[cfg(feature = "rkyv_validated")]
889impl std::fmt::Display for ArchivedVecMapError {
890    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
891        write!(f, "{:?}", self)
892    }
893}
894
895#[cfg(feature = "rkyv_validated")]
896impl<C: ?Sized, K, V> bytecheck::CheckBytes<C> for ArchivedVecMap<K, V>
897where
898    C: ArchiveContext,
899    C::Error: std::error::Error,
900    K: Ord + Archive + CheckBytes<C>,
901    V: Archive + CheckBytes<C>,
902    bool: bytecheck::CheckBytes<C>,
903{
904    type Error = ArchivedVecMapError;
905    unsafe fn check_bytes<'a>(
906        value: *const Self,
907        context: &mut C,
908    ) -> Result<&'a Self, Self::Error> {
909        let values = &(*value).0;
910        CheckBytes::check_bytes(values, context)
911            .map_err(|_| ArchivedVecMapError::ValueCheckError)?;
912        if !values
913            .iter()
914            .zip(values.iter().skip(1))
915            .all(|((ak, _), (bk, _))| ak < bk)
916        {
917            return Err(ArchivedVecMapError::OrderCheckError);
918        };
919        Ok(&*value)
920    }
921}
922
923#[cfg(test)]
924mod tests {
925    use super::*;
926    use maplit::btreemap;
927    use quickcheck::*;
928    use std::collections::BTreeMap;
929    use OuterJoinArg::*;
930
931    type Test = VecMap1<i32, i32>;
932    type Ref = BTreeMap<i32, i32>;
933
934    impl<K: Arbitrary + Ord, V: Arbitrary> Arbitrary for VecMap1<K, V> {
935        fn arbitrary<G: Gen>(g: &mut G) -> Self {
936            let t: BTreeMap<K, V> = Arbitrary::arbitrary(g);
937            t.into()
938        }
939    }
940
941    fn outer_join_reference(a: &Ref, b: &Ref) -> Ref {
942        let mut r = a.clone();
943        for (k, v) in b.clone().into_iter() {
944            r.insert(k, v);
945        }
946        r
947    }
948
949    fn inner_join_reference(a: &Ref, b: &Ref) -> Ref {
950        let mut r: Ref = BTreeMap::new();
951        for (k, v) in a.clone().into_iter() {
952            if b.contains_key(&k) {
953                r.insert(k, v);
954            }
955        }
956        r
957    }
958
959    quickcheck! {
960
961        #[cfg(feature = "serde")]
962        fn serde_roundtrip(reference: Test) -> bool {
963            let bytes = serde_json::to_vec(&reference).unwrap();
964            let deser = serde_json::from_slice(&bytes).unwrap();
965            reference == deser
966        }
967
968        #[cfg(feature = "rkyv")]
969        fn rkyv_roundtrip_unvalidated(a: Test) -> bool {
970            use rkyv::*;
971            use ser::Serializer;
972            let mut serializer = ser::serializers::AllocSerializer::<256>::default();
973            serializer.serialize_value(&a).unwrap();
974            let bytes = serializer.into_serializer().into_inner();
975            let archived = unsafe { rkyv::archived_root::<Test>(&bytes) };
976            let deserialized: Test = archived.deserialize(&mut Infallible).unwrap();
977            a == deserialized
978        }
979
980        #[cfg(feature = "rkyv_validated")]
981        #[quickcheck]
982        fn rkyv_roundtrip_validated(a: Test) -> bool {
983            use rkyv::*;
984            use ser::Serializer;
985            let mut serializer = ser::serializers::AllocSerializer::<256>::default();
986            serializer.serialize_value(&a).unwrap();
987            let bytes = serializer.into_serializer().into_inner();
988            let archived = rkyv::check_archived_root::<Test>(&bytes).unwrap();
989            let deserialized: Test = archived.deserialize(&mut Infallible).unwrap();
990            a == deserialized
991        }
992
993        fn outer_join(a: Ref, b: Ref) -> bool {
994            let expected: Test = outer_join_reference(&a, &b).into();
995            let a: Test = a.into();
996            let b: Test = b.into();
997            let actual = a.outer_join(&b, |arg| Some(match arg {
998                Left(_, a) => *a,
999                Right(_, b) => *b,
1000                Both(_, _, b) => *b,
1001            }));
1002            expected == actual
1003        }
1004
1005        fn inner_join(a: Ref, b: Ref) -> bool {
1006            let expected: Test = inner_join_reference(&a, &b).into();
1007            let a: Test = a.into();
1008            let b: Test = b.into();
1009            let actual = a.inner_join(&b, |_, a,_| Some(*a));
1010            expected == actual
1011        }
1012    }
1013
1014    #[test]
1015    fn smoke_test() {
1016        let a = btreemap! {
1017            1 => 1,
1018            2 => 3,
1019        };
1020        let b = btreemap! {
1021            1 => 2,
1022            3 => 4,
1023        };
1024        let r = outer_join_reference(&a, &b);
1025        let a: Test = a.into();
1026        let b: Test = b.into();
1027        let expected: Test = r.into();
1028        let actual = a.outer_join(&b, |arg| {
1029            Some(match arg {
1030                Left(_, a) => a.clone(),
1031                Right(_, b) => b.clone(),
1032                Both(_, _, b) => b.clone(),
1033            })
1034        });
1035        assert_eq!(actual, expected);
1036        println!("{:?}", actual);
1037    }
1038}
vec_collections/vec_map.rs

vec_collections/
vec_map.rs
