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 | |
5 | use alloc::vec; |
6 | use alloc::vec::Vec; |
7 | use core::fmt; |
8 | use core::iter::FromIterator; |
9 | use core::ops::Deref; |
10 | |
11 | use super::FlexZeroSlice; |
12 | use 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)] |
17 | pub struct FlexZeroVecOwned(Vec<u8>); |
18 | |
19 | impl 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 | |
220 | impl Deref for FlexZeroVecOwned { |
221 | type Target = FlexZeroSlice; |
222 | fn deref(&self) -> &Self::Target { |
223 | self.as_slice() |
224 | } |
225 | } |
226 | |
227 | impl fmt::Debug for FlexZeroVecOwned { |
228 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
229 | write!(f, " {:?}" , self.to_vec()) |
230 | } |
231 | } |
232 | |
233 | impl From<&FlexZeroSlice> for FlexZeroVecOwned { |
234 | fn from(other: &FlexZeroSlice) -> Self { |
235 | Self::from_slice(other) |
236 | } |
237 | } |
238 | |
239 | impl 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)] |
254 | mod 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 | |