compactly/v2/
maps.rs

1use super::{Encode, EncodingStrategy};
2use crate::{Mapping, Normal, Sorted};
3use std::{
4    collections::{BTreeMap, HashMap},
5    hash::Hash,
6};
7
8pub struct MapContext<K, V, SK: EncodingStrategy<K>, SV: EncodingStrategy<V>> {
9    len: <usize as Encode>::Context,
10    key: SK::Context,
11    value: SV::Context,
12}
13impl<K, V, SK: EncodingStrategy<K>, SV: EncodingStrategy<V>> Default for MapContext<K, V, SK, SV> {
14    fn default() -> Self {
15        Self {
16            len: Default::default(),
17            key: Default::default(),
18            value: Default::default(),
19        }
20    }
21}
22impl<K, V, SK: EncodingStrategy<K>, SV: EncodingStrategy<V>> Clone for MapContext<K, V, SK, SV> {
23    fn clone(&self) -> Self {
24        Self {
25            len: self.len.clone(),
26            key: self.key.clone(),
27            value: self.value.clone(),
28        }
29    }
30}
31
32impl<K: Encode + Hash + Eq, V: Encode> Encode for HashMap<K, V> {
33    type Context = MapContext<K, V, Normal, Normal>;
34    fn encode<E: super::EntropyCoder>(&self, writer: &mut E, ctx: &mut Self::Context) {
35        self.len().encode(writer, &mut ctx.len);
36        for (k, v) in self {
37            k.encode(writer, &mut ctx.key);
38            v.encode(writer, &mut ctx.value);
39        }
40    }
41    fn decode<D: super::EntropyDecoder>(
42        reader: &mut D,
43        ctx: &mut Self::Context,
44    ) -> Result<Self, std::io::Error> {
45        let len = Encode::decode(reader, &mut ctx.len)?;
46        let mut map = Self::with_capacity(len);
47        for _ in 0..len {
48            map.insert(
49                Encode::decode(reader, &mut ctx.key)?,
50                Encode::decode(reader, &mut ctx.value)?,
51            );
52        }
53        Ok(map)
54    }
55}
56
57#[test]
58fn hashmap() {
59    use super::assert_size;
60    assert_size!(HashMap::<usize, usize>::new(), 1);
61    assert_size!(HashMap::from([(0_usize, 0_usize)]), 1);
62    // Sizes of larger hash maps are unpredictable because the values come out
63    // in arbitrary orders.
64}
65
66impl<K: Ord, V: Encode> Encode for BTreeMap<K, V>
67where
68    Sorted: EncodingStrategy<K>,
69{
70    type Context = MapContext<K, V, Sorted, Normal>;
71    #[inline]
72    fn encode<E: super::EntropyCoder>(&self, writer: &mut E, ctx: &mut Self::Context) {
73        Mapping::<Sorted, Normal>::encode(self, writer, ctx)
74    }
75    #[inline]
76    fn decode<D: super::EntropyDecoder>(
77        reader: &mut D,
78        ctx: &mut Self::Context,
79    ) -> Result<Self, std::io::Error> {
80        Mapping::<Sorted, Normal>::decode(reader, ctx)
81    }
82}
83
84#[test]
85fn btreemap() {
86    use super::assert_size;
87    assert_size!(BTreeMap::<usize, usize>::new(), 1);
88    assert_size!(BTreeMap::from([(0_usize, 0_usize)]), 1);
89    assert_size!(BTreeMap::from_iter((0_usize..2).map(|v| (v, v))), 2);
90    assert_size!(BTreeMap::from_iter((0_usize..1_000).map(|v| (v, v))), 934);
91    assert_size!(
92        BTreeMap::from_iter((1_000_usize..2_000).map(|v| (v, v))),
93        975
94    );
95    assert_size!(
96        BTreeMap::from_iter((1_000_000_usize..1_001_000).map(|v| (v, v))),
97        1005
98    );
99}
100
101impl<K: Ord, SK: EncodingStrategy<K>, V, SV: EncodingStrategy<V>> EncodingStrategy<BTreeMap<K, V>>
102    for Mapping<SK, SV>
103{
104    type Context = MapContext<K, V, SK, SV>;
105    #[inline]
106    fn encode<E: super::EntropyCoder>(
107        value: &BTreeMap<K, V>,
108        writer: &mut E,
109        ctx: &mut Self::Context,
110    ) {
111        value.len().encode(writer, &mut ctx.len);
112        for (k, v) in value {
113            SK::encode(k, writer, &mut ctx.key);
114            SV::encode(v, writer, &mut ctx.value);
115        }
116    }
117    #[inline]
118    fn decode<D: super::EntropyDecoder>(
119        reader: &mut D,
120        ctx: &mut Self::Context,
121    ) -> Result<BTreeMap<K, V>, std::io::Error> {
122        let len: usize = Encode::decode(reader, &mut ctx.len)?;
123        let mut map = BTreeMap::new();
124        for _ in 0..len {
125            map.insert(
126                SK::decode(reader, &mut ctx.key)?,
127                SV::decode(reader, &mut ctx.value)?,
128            );
129        }
130        Ok(map)
131    }
132}
133
134impl<K: Hash + Eq, SK: EncodingStrategy<K>, V, SV: EncodingStrategy<V>>
135    EncodingStrategy<HashMap<K, V>> for Mapping<SK, SV>
136{
137    type Context = MapContext<K, V, SK, SV>;
138    #[inline]
139    fn encode<E: super::EntropyCoder>(
140        value: &HashMap<K, V>,
141        writer: &mut E,
142        ctx: &mut Self::Context,
143    ) {
144        value.len().encode(writer, &mut ctx.len);
145        for (k, v) in value {
146            SK::encode(k, writer, &mut ctx.key);
147            SV::encode(v, writer, &mut ctx.value);
148        }
149    }
150    #[inline]
151    fn decode<D: super::EntropyDecoder>(
152        reader: &mut D,
153        ctx: &mut Self::Context,
154    ) -> Result<HashMap<K, V>, std::io::Error> {
155        let len: usize = Encode::decode(reader, &mut ctx.len)?;
156        let mut map = HashMap::with_capacity(len);
157        for _ in 0..len {
158            map.insert(
159                SK::decode(reader, &mut ctx.key)?,
160                SV::decode(reader, &mut ctx.value)?,
161            );
162        }
163        Ok(map)
164    }
165}
compactly/v2/maps.rs

compactly/v2/
maps.rs
