1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
// This file is part of ICU4X. For terms of use, please see the file
// called LICENSE at the top level of the ICU4X source tree
// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).

use super::FlexZeroSlice;
use super::FlexZeroVecOwned;
use crate::ZeroVecError;
use core::cmp::Ordering;
use core::iter::FromIterator;
use core::ops::Deref;

/// A zero-copy data structure that efficiently stores integer values.
///
/// `FlexZeroVec` automatically increases or decreases its storage capacity based on the largest
/// integer stored in the vector. It therefore results in lower memory usage when smaller numbers
/// are usually stored, but larger values must sometimes also be stored.
///
/// The maximum value that can be stored in `FlexZeroVec` is `usize::MAX` on the current platform.
///
/// `FlexZeroVec` is the data structure for storing `usize` in a `ZeroMap`.
///
/// `FlexZeroVec` derefs to [`FlexZeroSlice`], which contains most of the methods.
///
/// # Examples
///
/// Storing a vec of `usize`s in a zero-copy way:
///
/// ```
/// use zerovec::vecs::FlexZeroVec;
///
/// // Create a FlexZeroVec and add a few numbers to it
/// let mut zv1 = FlexZeroVec::new();
/// zv1.to_mut().push(55);
/// zv1.to_mut().push(33);
/// zv1.to_mut().push(999);
/// assert_eq!(zv1.to_vec(), vec![55, 33, 999]);
///
/// // Convert it to bytes and back
/// let bytes = zv1.as_bytes();
/// let zv2 =
///     FlexZeroVec::parse_byte_slice(bytes).expect("bytes should round-trip");
/// assert_eq!(zv2.to_vec(), vec![55, 33, 999]);
///
/// // Verify the compact storage
/// assert_eq!(7, bytes.len());
/// assert!(matches!(zv2, FlexZeroVec::Borrowed(_)));
/// ```
///
/// Storing a map of `usize` to `usize` in a zero-copy way:
///
/// ```
/// use zerovec::ZeroMap;
///
/// // Append some values to the ZeroMap
/// let mut zm = ZeroMap::<usize, usize>::new();
/// assert!(zm.try_append(&29, &92).is_none());
/// assert!(zm.try_append(&38, &83).is_none());
/// assert!(zm.try_append(&56, &65).is_none());
/// assert_eq!(zm.len(), 3);
///
/// // Insert another value into the middle
/// assert!(zm.try_append(&47, &74).is_some());
/// assert!(zm.insert(&47, &74).is_none());
/// assert_eq!(zm.len(), 4);
///
/// // Verify that the values are correct
/// assert_eq!(zm.get_copied(&0), None);
/// assert_eq!(zm.get_copied(&29), Some(92));
/// assert_eq!(zm.get_copied(&38), Some(83));
/// assert_eq!(zm.get_copied(&47), Some(74));
/// assert_eq!(zm.get_copied(&56), Some(65));
/// assert_eq!(zm.get_copied(&usize::MAX), None);
/// ```
#[derive(Debug)]
#[non_exhaustive]
pub enum FlexZeroVec<'a> {
    Owned(FlexZeroVecOwned),
    Borrowed(&'a FlexZeroSlice),
}

impl<'a> Deref for FlexZeroVec<'a> {
    type Target = FlexZeroSlice;
    fn deref(&self) -> &Self::Target {
        match self {
            FlexZeroVec::Owned(v) => v.deref(),
            FlexZeroVec::Borrowed(v) => v,
        }
    }
}

impl<'a> AsRef<FlexZeroSlice> for FlexZeroVec<'a> {
    fn as_ref(&self) -> &FlexZeroSlice {
        self.deref()
    }
}

impl Eq for FlexZeroVec<'_> {}

impl<'a, 'b> PartialEq<FlexZeroVec<'b>> for FlexZeroVec<'a> {
    #[inline]
    fn eq(&self, other: &FlexZeroVec<'b>) -> bool {
        self.iter().eq(other.iter())
    }
}

impl<'a> Default for FlexZeroVec<'a> {
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}

impl<'a> PartialOrd for FlexZeroVec<'a> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<'a> Ord for FlexZeroVec<'a> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.iter().cmp(other.iter())
    }
}

impl<'a> FlexZeroVec<'a> {
    #[inline]
    /// Creates a new, borrowed, empty `FlexZeroVec`.
    ///
    /// # Examples
    ///
    /// ```
    /// use zerovec::vecs::FlexZeroVec;
    ///
    /// let zv: FlexZeroVec = FlexZeroVec::new();
    /// assert!(zv.is_empty());
    /// ```
    pub const fn new() -> Self {
        Self::Borrowed(FlexZeroSlice::new_empty())
    }

    /// Parses a `&[u8]` buffer into a `FlexZeroVec`.
    ///
    /// The bytes within the byte buffer must remain constant for the life of the FlexZeroVec.
    ///
    /// # Endianness
    ///
    /// The byte buffer must be encoded in little-endian, even if running in a big-endian
    /// environment. This ensures a consistent representation of data across platforms.
    ///
    /// # Max Value
    ///
    /// The bytes will fail to parse if the high value is greater than the capacity of `usize`
    /// on this platform. For example, a `FlexZeroVec` created on a 64-bit platform might fail
    /// to deserialize on a 32-bit platform.
    ///
    /// # Example
    ///
    /// ```
    /// use zerovec::vecs::FlexZeroVec;
    ///
    /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
    /// let zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid slice");
    ///
    /// assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
    /// assert_eq!(zv.get(2), Some(421));
    /// ```
    pub fn parse_byte_slice(bytes: &'a [u8]) -> Result<Self, ZeroVecError> {
        let slice: &'a FlexZeroSlice = FlexZeroSlice::parse_byte_slice(bytes)?;
        Ok(Self::Borrowed(slice))
    }

    /// Converts a borrowed FlexZeroVec to an owned FlexZeroVec. No-op if already owned.
    ///
    /// # Example
    ///
    /// ```
    /// use zerovec::vecs::FlexZeroVec;
    ///
    /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
    /// let zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid bytes");
    /// assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
    ///
    /// let owned = zv.into_owned();
    /// assert!(matches!(owned, FlexZeroVec::Owned(_)));
    /// ```
    pub fn into_owned(self) -> FlexZeroVec<'static> {
        match self {
            Self::Owned(owned) => FlexZeroVec::Owned(owned),
            Self::Borrowed(slice) => FlexZeroVec::Owned(FlexZeroVecOwned::from_slice(slice)),
        }
    }

    /// Allows the FlexZeroVec to be mutated by converting it to an owned variant, and producing
    /// a mutable [`FlexZeroVecOwned`].
    ///
    /// # Example
    ///
    /// ```
    /// use zerovec::vecs::FlexZeroVec;
    ///
    /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
    /// let mut zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid bytes");
    /// assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
    ///
    /// zv.to_mut().push(12);
    /// assert!(matches!(zv, FlexZeroVec::Owned(_)));
    /// assert_eq!(zv.get(4), Some(12));
    /// ```
    pub fn to_mut(&mut self) -> &mut FlexZeroVecOwned {
        match self {
            Self::Owned(ref mut owned) => owned,
            Self::Borrowed(slice) => {
                *self = FlexZeroVec::Owned(FlexZeroVecOwned::from_slice(slice));
                // recursion is limited since we are guaranteed to hit the Owned branch
                self.to_mut()
            }
        }
    }

    /// Remove all elements from this FlexZeroVec and reset it to an empty borrowed state.
    ///
    /// # Examples
    ///
    /// ```
    /// use zerovec::vecs::FlexZeroVec;
    ///
    /// let mut zv: FlexZeroVec = [1, 2, 3].iter().copied().collect();
    /// assert!(!zv.is_empty());
    /// zv.clear();
    /// assert!(zv.is_empty());
    /// ```
    pub fn clear(&mut self) {
        *self = Self::Borrowed(FlexZeroSlice::new_empty())
    }
}

impl FromIterator<usize> for FlexZeroVec<'_> {
    /// Creates a [`FlexZeroVec::Owned`] from an iterator of `usize`.
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = usize>,
    {
        FlexZeroVecOwned::from_iter(iter).into_flexzerovec()
    }
}

#[test]
fn test_zeromap_usize() {
    use crate::ZeroMap;

    let mut zm = ZeroMap::<usize, usize>::new();
    assert!(zm.try_append(&29, &92).is_none());
    assert!(zm.try_append(&38, &83).is_none());
    assert!(zm.try_append(&47, &74).is_none());
    assert!(zm.try_append(&56, &65).is_none());

    assert_eq!(zm.keys.get_width(), 1);
    assert_eq!(zm.values.get_width(), 1);

    assert_eq!(zm.insert(&47, &744), Some(74));
    assert_eq!(zm.values.get_width(), 2);
    assert_eq!(zm.insert(&47, &774), Some(744));
    assert_eq!(zm.values.get_width(), 2);
    assert!(zm.try_append(&1100, &1).is_none());
    assert_eq!(zm.keys.get_width(), 2);
    assert_eq!(zm.remove(&1100), Some(1));
    assert_eq!(zm.keys.get_width(), 1);

    assert_eq!(zm.get_copied(&0), None);
    assert_eq!(zm.get_copied(&29), Some(92));
    assert_eq!(zm.get_copied(&38), Some(83));
    assert_eq!(zm.get_copied(&47), Some(774));
    assert_eq!(zm.get_copied(&56), Some(65));
    assert_eq!(zm.get_copied(&usize::MAX), None);
}