1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5use alloc::vec;
6use alloc::vec::Vec;
7use core::fmt;
8use core::iter::FromIterator;
9use core::ops::Deref;
10
11use super::FlexZeroSlice;
12use super::FlexZeroVec;
13
14/// The fully-owned variant of [`FlexZeroVec`]. Contains all mutation methods.
15// Safety invariant: the inner bytes must deref to a valid `FlexZeroSlice`
16#[derive(Clone, PartialEq, Eq)]
17pub struct FlexZeroVecOwned(Vec<u8>);
18
19impl FlexZeroVecOwned {
20 /// Creates a new [`FlexZeroVecOwned`] with zero elements.
21 pub fn new_empty() -> Self {
22 Self(vec![1])
23 }
24
25 /// Creates a [`FlexZeroVecOwned`] from a [`FlexZeroSlice`].
26 pub fn from_slice(other: &FlexZeroSlice) -> FlexZeroVecOwned {
27 // safety: the bytes originate from a valid FlexZeroSlice
28 Self(other.as_bytes().to_vec())
29 }
30
31 /// Obtains this [`FlexZeroVecOwned`] as a [`FlexZeroSlice`].
32 pub fn as_slice(&self) -> &FlexZeroSlice {
33 let slice: &[u8] = &self.0;
34 unsafe {
35 // safety: the slice is known to come from a valid parsed FlexZeroSlice
36 FlexZeroSlice::from_byte_slice_unchecked(slice)
37 }
38 }
39
40 /// Mutably obtains this `FlexZeroVecOwned` as a [`FlexZeroSlice`].
41 pub(crate) fn as_mut_slice(&mut self) -> &mut FlexZeroSlice {
42 let slice: &mut [u8] = &mut self.0;
43 unsafe {
44 // safety: the slice is known to come from a valid parsed FlexZeroSlice
45 FlexZeroSlice::from_byte_slice_mut_unchecked(slice)
46 }
47 }
48
49 /// Converts this `FlexZeroVecOwned` into a [`FlexZeroVec::Owned`].
50 #[inline]
51 pub fn into_flexzerovec(self) -> FlexZeroVec<'static> {
52 FlexZeroVec::Owned(self)
53 }
54
55 /// Clears all values out of this `FlexZeroVecOwned`.
56 #[inline]
57 pub fn clear(&mut self) {
58 *self = Self::new_empty()
59 }
60
61 /// Appends an item to the end of the vector.
62 ///
63 /// # Panics
64 ///
65 /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
66 ///
67 /// # Examples
68 ///
69 /// ```
70 /// use zerovec::vecs::FlexZeroVec;
71 ///
72 /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
73 /// zv.to_mut().push(33);
74 /// assert_eq!(zv.to_vec(), vec![22, 44, 66, 33]);
75 /// ```
76 pub fn push(&mut self, item: usize) {
77 let insert_info = self.get_insert_info(item);
78 self.0.resize(insert_info.new_bytes_len, 0);
79 let insert_index = insert_info.new_count - 1;
80 self.as_mut_slice().insert_impl(insert_info, insert_index);
81 }
82
83 /// Inserts an element into the middle of the vector.
84 ///
85 /// Caution: Both arguments to this function are of type `usize`. Please be careful to pass
86 /// the index first followed by the value second.
87 ///
88 /// # Panics
89 ///
90 /// Panics if `index > len`.
91 ///
92 /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
93 ///
94 /// # Examples
95 ///
96 /// ```
97 /// use zerovec::vecs::FlexZeroVec;
98 ///
99 /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
100 /// zv.to_mut().insert(2, 33);
101 /// assert_eq!(zv.to_vec(), vec![22, 44, 33, 66]);
102 /// ```
103 pub fn insert(&mut self, index: usize, item: usize) {
104 #[allow(clippy::panic)] // panic is documented in function contract
105 if index > self.len() {
106 panic!("index {} out of range {}", index, self.len());
107 }
108 let insert_info = self.get_insert_info(item);
109 self.0.resize(insert_info.new_bytes_len, 0);
110 self.as_mut_slice().insert_impl(insert_info, index);
111 }
112
113 /// Inserts an element into an ascending sorted vector
114 /// at a position that keeps the vector sorted.
115 ///
116 /// # Panics
117 ///
118 /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
119 ///
120 /// # Examples
121 ///
122 /// ```
123 /// use zerovec::vecs::FlexZeroVecOwned;
124 ///
125 /// let mut fzv = FlexZeroVecOwned::new_empty();
126 /// fzv.insert_sorted(10);
127 /// fzv.insert_sorted(5);
128 /// fzv.insert_sorted(8);
129 ///
130 /// assert!(Iterator::eq(fzv.iter(), [5, 8, 10].iter().copied()));
131 /// ```
132 pub fn insert_sorted(&mut self, item: usize) {
133 let index = match self.binary_search(item) {
134 Ok(i) => i,
135 Err(i) => i,
136 };
137 let insert_info = self.get_insert_info(item);
138 self.0.resize(insert_info.new_bytes_len, 0);
139 self.as_mut_slice().insert_impl(insert_info, index);
140 }
141
142 /// Removes and returns the element at the specified index.
143 ///
144 /// # Panics
145 ///
146 /// Panics if `index >= len`.
147 ///
148 /// # Examples
149 ///
150 /// ```
151 /// use zerovec::vecs::FlexZeroVec;
152 ///
153 /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
154 /// let removed_item = zv.to_mut().remove(1);
155 /// assert_eq!(44, removed_item);
156 /// assert_eq!(zv.to_vec(), vec![22, 66]);
157 /// ```
158 pub fn remove(&mut self, index: usize) -> usize {
159 #[allow(clippy::panic)] // panic is documented in function contract
160 if index >= self.len() {
161 panic!("index {} out of range {}", index, self.len());
162 }
163 let remove_info = self.get_remove_info(index);
164 // Safety: `remove_index` is a valid index
165 let item = unsafe { self.get_unchecked(remove_info.remove_index) };
166 let new_bytes_len = remove_info.new_bytes_len;
167 self.as_mut_slice().remove_impl(remove_info);
168 self.0.truncate(new_bytes_len);
169 item
170 }
171
172 /// Removes and returns the last element from an ascending sorted vector.
173 ///
174 /// If the vector is not sorted, use [`FlexZeroVecOwned::remove()`] instead. Calling this
175 /// function would leave the FlexZeroVec in a safe, well-defined state; however, information
176 /// may be lost and/or the equality invariant might not hold.
177 ///
178 /// # Panics
179 ///
180 /// Panics if `self.is_empty()`.
181 ///
182 /// # Examples
183 ///
184 /// ```
185 /// use zerovec::vecs::FlexZeroVec;
186 ///
187 /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
188 /// let popped_item = zv.to_mut().pop_sorted();
189 /// assert_eq!(66, popped_item);
190 /// assert_eq!(zv.to_vec(), vec![22, 44]);
191 /// ```
192 ///
193 /// Calling this function on a non-ascending vector could cause surprising results:
194 ///
195 /// ```
196 /// use zerovec::vecs::FlexZeroVec;
197 ///
198 /// let mut zv1: FlexZeroVec = [444, 222, 111].iter().copied().collect();
199 /// let popped_item = zv1.to_mut().pop_sorted();
200 /// assert_eq!(111, popped_item);
201 ///
202 /// // Oops!
203 /// assert_eq!(zv1.to_vec(), vec![188, 222]);
204 /// ```
205 pub fn pop_sorted(&mut self) -> usize {
206 #[allow(clippy::panic)] // panic is documented in function contract
207 if self.is_empty() {
208 panic!("cannot pop from an empty vector");
209 }
210 let remove_info = self.get_sorted_pop_info();
211 // Safety: `remove_index` is a valid index
212 let item = unsafe { self.get_unchecked(remove_info.remove_index) };
213 let new_bytes_len = remove_info.new_bytes_len;
214 self.as_mut_slice().remove_impl(remove_info);
215 self.0.truncate(new_bytes_len);
216 item
217 }
218}
219
220impl Deref for FlexZeroVecOwned {
221 type Target = FlexZeroSlice;
222 fn deref(&self) -> &Self::Target {
223 self.as_slice()
224 }
225}
226
227impl fmt::Debug for FlexZeroVecOwned {
228 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
229 write!(f, "{:?}", self.to_vec())
230 }
231}
232
233impl From<&FlexZeroSlice> for FlexZeroVecOwned {
234 fn from(other: &FlexZeroSlice) -> Self {
235 Self::from_slice(other)
236 }
237}
238
239impl FromIterator<usize> for FlexZeroVecOwned {
240 /// Creates a [`FlexZeroVecOwned`] from an iterator of `usize`.
241 fn from_iter<I>(iter: I) -> Self
242 where
243 I: IntoIterator<Item = usize>,
244 {
245 let mut result: FlexZeroVecOwned = FlexZeroVecOwned::new_empty();
246 for item: usize in iter {
247 result.push(item);
248 }
249 result
250 }
251}
252
253#[cfg(test)]
254mod test {
255 use super::*;
256
257 fn check_contents(fzv: &FlexZeroSlice, expected: &[usize]) {
258 assert_eq!(fzv.len(), expected.len(), "len: {fzv:?} != {expected:?}");
259 assert_eq!(
260 fzv.is_empty(),
261 expected.is_empty(),
262 "is_empty: {fzv:?} != {expected:?}"
263 );
264 assert_eq!(
265 fzv.first(),
266 expected.first().copied(),
267 "first: {fzv:?} != {expected:?}"
268 );
269 assert_eq!(
270 fzv.last(),
271 expected.last().copied(),
272 "last: {fzv:?} != {expected:?}"
273 );
274 for i in 0..(expected.len() + 1) {
275 assert_eq!(
276 fzv.get(i),
277 expected.get(i).copied(),
278 "@{i}: {fzv:?} != {expected:?}"
279 );
280 }
281 }
282
283 #[test]
284 fn test_basic() {
285 let mut fzv = FlexZeroVecOwned::new_empty();
286 assert_eq!(fzv.get_width(), 1);
287 check_contents(&fzv, &[]);
288
289 fzv.push(42);
290 assert_eq!(fzv.get_width(), 1);
291 check_contents(&fzv, &[42]);
292
293 fzv.push(77);
294 assert_eq!(fzv.get_width(), 1);
295 check_contents(&fzv, &[42, 77]);
296
297 // Scale up
298 fzv.push(300);
299 assert_eq!(fzv.get_width(), 2);
300 check_contents(&fzv, &[42, 77, 300]);
301
302 // Does not need to be sorted
303 fzv.insert(1, 325);
304 assert_eq!(fzv.get_width(), 2);
305 check_contents(&fzv, &[42, 325, 77, 300]);
306
307 fzv.remove(3);
308 assert_eq!(fzv.get_width(), 2);
309 check_contents(&fzv, &[42, 325, 77]);
310
311 // Scale down
312 fzv.remove(1);
313 assert_eq!(fzv.get_width(), 1);
314 check_contents(&fzv, &[42, 77]);
315 }
316
317 #[test]
318 fn test_build_sorted() {
319 let nums: &[usize] = &[0, 50, 0, 77, 831, 29, 89182, 931, 0, 77, 712381];
320 let mut fzv = FlexZeroVecOwned::new_empty();
321
322 for num in nums {
323 fzv.insert_sorted(*num);
324 }
325 assert_eq!(fzv.get_width(), 3);
326 check_contents(&fzv, &[0, 0, 0, 29, 50, 77, 77, 831, 931, 89182, 712381]);
327
328 for num in nums {
329 let index = fzv.binary_search(*num).unwrap();
330 fzv.remove(index);
331 }
332 assert_eq!(fzv.get_width(), 1);
333 check_contents(&fzv, &[]);
334 }
335}
336