typed_index_collections/
vec.rs

1use alloc::borrow::Cow;
2use alloc::boxed::Box;
3use alloc::collections::TryReserveError;
4use alloc::ffi::CString;
5use alloc::string::String;
6use alloc::vec::{self, Drain, Splice, Vec};
7use core::borrow::{Borrow, BorrowMut};
8use core::cmp::Ordering;
9use core::hash::{Hash, Hasher};
10use core::iter::FromIterator;
11use core::marker::PhantomData;
12use core::mem::MaybeUninit;
13use core::ops::{Deref, DerefMut, Index, IndexMut, RangeBounds};
14use core::{fmt, slice};
15#[cfg(feature = "std")]
16use std::io::{IoSlice, Result as IoResult, Write};
17
18#[cfg(feature = "bincode")]
19use bincode::de::{BorrowDecode, BorrowDecoder, Decode, Decoder};
20#[cfg(feature = "bincode")]
21use bincode::enc::{Encode, Encoder};
22#[cfg(feature = "bincode")]
23use bincode::error::{DecodeError, EncodeError};
24#[cfg(all(feature = "alloc", feature = "serde"))]
25use serde::de::{Deserialize, Deserializer};
26#[cfg(feature = "serde")]
27use serde::ser::{Serialize, Serializer};
28
29use crate::{TiEnumerated, TiRangeBounds, TiSlice, TiSliceIndex};
30
31/// A contiguous growable array type
32/// that only accepts keys of the type `K`.
33///
34/// `TiVec<K, V>` is a wrapper around Rust container type [`std::vec::Vec`].
35/// The struct mirrors the stable API of Rust [`std::vec::Vec`]
36/// and forwards to it as much as possible.
37///
38/// `TiVec<K, V>` uses `K` instead of `usize` for element indices and
39/// require the index to implement
40/// [`From<usize>`][`From`] and [`Into<usize>`][`Into`] traits.
41/// Their implementation can be easily done
42/// with [`derive_more`] crate and `#[derive(From, Into)]`.
43///
44/// `TiVec<K, V>` can be converted to [`std::vec::Vec<V>`][`std::vec::Vec`] and
45/// back using [`From`] and [`Into`].
46///
47/// There are also zero-cost conversions available between references:
48/// - [`&std::vec::Vec<V>`][`std::vec::Vec`] and `&TiVec<K, V>` with [`AsRef`],
49/// - [`&mut std::vec::Vec<V>`][`std::vec::Vec`] and `&mut TiVec<K, V>` with
50///   [`AsMut`],
51///
52/// Added methods:
53/// - [`from_ref`] - Converts a [`&std::vec::Vec<V>`][`std::vec::Vec`] into a
54///   `&TiVec<K, V>`.
55/// - [`from_mut`] - Converts a [`&mut std::vec::Vec<V>`][`std::vec::Vec`] into
56///   a `&mut TiVec<K, V>`.
57/// - [`push_and_get_key`] - Appends an element to the back of a collection and
58///   returns its index of type `K`.
59/// - [`pop_key_value`] - Removes the last element from a vector and returns it
60///   with its index of type `K`, or [`None`] if the vector is empty.
61/// - [`pop_key_value_if`] - Removes the last element from a vector and returns
62///   it with its index of type `K`, or [`None`] if the predicate returns false
63///   or the vector is empty.
64/// - [`drain_enumerated`] - Creates a draining iterator that removes the
65///   specified range in the vector and yields the current count and the removed
66///   items. It acts like `self.drain(range).enumerate()`, but instead of
67///   `usize` it returns index of type `K`.
68/// - [`into_iter_enumerated`] - Converts the vector into iterator over all
69///   key-value pairs with `K` used for iteration indices. It acts like
70///   `self.into_iter().enumerate()`, but use `K` instead of `usize` for
71///   iteration indices.
72///
73/// # Example
74///
75/// ```
76/// use derive_more::{From, Into};
77/// use typed_index_collections::TiVec;
78///
79/// #[derive(From, Into)]
80/// struct FooId(usize);
81///
82/// let mut foos: TiVec<FooId, usize> = std::vec![10, 11, 13].into();
83/// foos.insert(FooId(2), 12);
84/// assert_eq!(foos[FooId(2)], 12);
85/// ```
86///
87/// [`from_ref`]: #method.from_ref
88/// [`from_mut`]: #method.from_mut
89/// [`push_and_get_key`]: #method.push_and_get_key
90/// [`pop_key_value`]: #method.pop_key_value
91/// [`pop_key_value_if`]: #method.pop_key_value_if
92/// [`drain_enumerated`]: #method.drain_enumerated
93/// [`into_iter_enumerated`]: #method.into_iter_enumerated
94/// [`std::vec::Vec`]: https://doc.rust-lang.org/std/vec/struct.Vec.html
95/// [`From`]: https://doc.rust-lang.org/std/convert/trait.From.html
96/// [`Into`]: https://doc.rust-lang.org/std/convert/trait.Into.html
97/// [`AsRef`]: https://doc.rust-lang.org/std/convert/trait.AsRef.html
98/// [`AsMut`]: https://doc.rust-lang.org/std/convert/trait.AsMut.html
99/// [`derive_more`]: https://crates.io/crates/derive_more
100#[repr(transparent)]
101pub struct TiVec<K, V> {
102    /// Raw slice property
103    pub raw: Vec<V>,
104
105    /// Tied slice index type
106    ///
107    /// `fn(T) -> T` is *[PhantomData pattern][phantomdata patterns]*
108    /// used to relax auto trait implementations bounds for
109    /// [`Send`], [`Sync`], [`Unpin`], [`UnwindSafe`] and [`RefUnwindSafe`].
110    ///
111    /// Derive attribute is not used for trait implementations because it also
112    /// requires the same trait implemented for K that is an unnecessary
113    /// requirement.
114    ///
115    /// [phantomdata patterns]: https://doc.rust-lang.org/nomicon/phantom-data.html#table-of-phantomdata-patterns
116    /// [`Send`]: https://doc.rust-lang.org/core/marker/trait.Send.html
117    /// [`Sync`]: https://doc.rust-lang.org/core/marker/trait.Sync.html
118    /// [`Unpin`]: https://doc.rust-lang.org/core/marker/trait.Unpin.html
119    /// [`UnwindSafe`]: https://doc.rust-lang.org/core/std/panic/trait.UnwindSafe.html
120    /// [`RefUnwindSafe`]: https://doc.rust-lang.org/core/std/panic/trait.RefUnwindSafe.html
121    _marker: PhantomData<fn(K) -> K>,
122}
123
124impl<K, V> TiVec<K, V> {
125    /// Constructs a new, empty `TiVec<K, V>`.
126    ///
127    /// See [`Vec::new`] for more details.
128    ///
129    /// [`Vec::new`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.new
130    #[inline]
131    #[must_use]
132    pub const fn new() -> Self {
133        Self {
134            raw: Vec::new(),
135            _marker: PhantomData,
136        }
137    }
138
139    /// Constructs a new, empty `TiVec<K, V>` with the specified capacity.
140    ///
141    /// See [`Vec::with_capacity`] for more details.
142    ///
143    /// [`Vec::with_capacity`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.with_capacity
144    #[inline]
145    #[must_use]
146    pub fn with_capacity(capacity: usize) -> Self {
147        Self {
148            raw: Vec::with_capacity(capacity),
149            _marker: PhantomData,
150        }
151    }
152
153    /// Creates a `TiVec<K, V>` directly from the raw components of another
154    /// vector.
155    ///
156    /// See [`Vec::from_raw_parts`] for more details.
157    ///
158    /// # Safety
159    ///
160    /// This is highly unsafe, due to the number of invariants that aren't
161    /// checked.
162    /// See [`Vec::from_raw_parts`] for more details.
163    ///
164    /// [`Vec::from_raw_parts`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.from_raw_parts
165    #[inline]
166    pub unsafe fn from_raw_parts(ptr: *mut V, length: usize, capacity: usize) -> Self {
167        Self {
168            // SAFETY: Guaranteed by the caller.
169            raw: unsafe { Vec::from_raw_parts(ptr, length, capacity) },
170            _marker: PhantomData,
171        }
172    }
173
174    /// Converts a [`&std::vec::Vec<V>`] into a `&TiVec<K, V>`.
175    ///
176    /// Vector reference is intentionally used in the argument
177    /// instead of slice reference for conversion with no-op.
178    ///
179    /// # Example
180    ///
181    /// ```
182    /// # use typed_index_collections::TiVec;
183    /// pub struct Id(usize);
184    /// let vec: &TiVec<Id, usize> = TiVec::from_ref(&vec![1, 2, 4]);
185    /// ```
186    ///
187    /// [`&std::vec::Vec<V>`]: https://doc.rust-lang.org/std/vec/struct.Vec.html
188    #[inline]
189    #[must_use]
190    pub const fn from_ref(raw: &Vec<V>) -> &Self {
191        // SAFETY: `TiVec<K, V>` is `repr(transparent)` over a `Vec<V>` type.
192        unsafe { &*core::ptr::from_ref::<Vec<V>>(raw).cast::<Self>() }
193    }
194
195    /// Converts a [`&mut std::vec::Vec<V>`] into a `&mut TiVec<K, V>`.
196    ///
197    /// # Example
198    ///
199    /// ```
200    /// # use typed_index_collections::TiVec;
201    /// pub struct Id(usize);
202    /// let vec: &mut TiVec<Id, usize> = TiVec::from_mut(&mut vec![1, 2, 4]);
203    /// ```
204    ///
205    /// [`&mut std::vec::Vec<V>`]: https://doc.rust-lang.org/std/vec/struct.Vec.html
206    #[inline]
207    pub const fn from_mut(raw: &mut Vec<V>) -> &mut Self {
208        // SAFETY: `TiVec<K, V>` is `repr(transparent)` over a `Vec<V>` type.
209        unsafe { &mut *core::ptr::from_mut::<Vec<V>>(raw).cast::<Self>() }
210    }
211
212    /// Returns the number of elements the vector can hold without
213    /// reallocating.
214    ///
215    /// See [`Vec::capacity`] for more details.
216    ///
217    /// [`Vec::capacity`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.capacity
218    #[inline]
219    #[must_use]
220    pub const fn capacity(&self) -> usize {
221        self.raw.capacity()
222    }
223
224    /// Reserves capacity for at least `additional` more elements to be inserted
225    /// in the given `TiVec<K, V>`. The collection may reserve more space to
226    /// avoid frequent reallocations. After calling `reserve`, capacity will
227    /// be greater than or equal to `self.len() + additional`. Does nothing
228    /// if capacity is already sufficient.
229    ///
230    /// See [`Vec::reserve`] for more details.
231    ///
232    /// [`Vec::reserve`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.reserve
233    #[inline]
234    pub fn reserve(&mut self, additional: usize) {
235        self.raw.reserve(additional);
236    }
237
238    /// Reserves the minimum capacity for exactly `additional` more elements to
239    /// be inserted in the given `TiVec<K, V>`. After calling `reserve_exact`,
240    /// capacity will be greater than or equal to `self.len() + additional`.
241    /// Does nothing if the capacity is already sufficient.
242    ///
243    /// See [`Vec::reserve_exact`] for more details.
244    ///
245    /// [`Vec::reserve_exact`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.reserve_exact
246    #[inline]
247    pub fn reserve_exact(&mut self, additional: usize) {
248        self.raw.reserve_exact(additional);
249    }
250
251    /// Tries to reserve capacity for at least `additional` more elements to be
252    /// inserted in the given `Vec<T>`.
253    ///
254    /// See [`Vec::try_reserve`] for more details.
255    ///
256    /// # Errors
257    ///
258    /// If the capacity overflows, or the allocator reports a failure, then an
259    /// error is returned.
260    ///
261    /// [`Vec::try_reserve`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.try_reserve
262    #[inline]
263    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
264        self.raw.try_reserve(additional)
265    }
266
267    /// Tries to reserve the minimum capacity for at least `additional`
268    /// elements to be inserted in the given `Vec<T>`.
269    ///
270    /// See [`Vec::try_reserve_exact`] for more details.
271    ///
272    /// # Errors
273    ///
274    /// If the capacity overflows, or the allocator reports a failure, then an
275    /// error is returned.
276    ///
277    /// [`Vec::try_reserve_exact`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.try_reserve_exact
278    #[inline]
279    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
280        self.raw.try_reserve_exact(additional)
281    }
282
283    /// Shrinks the capacity of the vector as much as possible.
284    ///
285    /// See [`Vec::shrink_to_fit`] for more details.
286    ///
287    /// [`Vec::shrink_to_fit`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.shrink_to_fit
288    #[inline]
289    pub fn shrink_to_fit(&mut self) {
290        self.raw.shrink_to_fit();
291    }
292
293    /// Shrinks the capacity of the vector with a lower bound.
294    ///
295    /// See [`Vec::shrink_to`] for more details.
296    ///
297    /// [`Vec::shrink_to`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.shrink_to
298    #[inline]
299    pub fn shrink_to(&mut self, min_capacity: usize) {
300        self.raw.shrink_to(min_capacity);
301    }
302    /// Converts the vector into [`Box<TiSlice<K, V>>`][`Box`].
303    ///
304    /// See [`Vec::into_boxed_slice`] for more details.
305    ///
306    /// [`Vec::into_boxed_slice`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.into_boxed_slice
307    /// [`Box`]: https://doc.rust-lang.org/std/boxed/struct.Box.html
308    #[inline]
309    #[must_use]
310    pub fn into_boxed_slice(self) -> Box<TiSlice<K, V>> {
311        self.raw.into_boxed_slice().into()
312    }
313
314    /// Shortens the vector, keeping the first `len` elements and dropping
315    /// the rest.
316    ///
317    /// See [`Vec::truncate`] for more details.
318    ///
319    /// [`Vec::truncate`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.truncate
320    #[inline]
321    pub fn truncate(&mut self, len: usize) {
322        self.raw.truncate(len);
323    }
324
325    /// Extracts a slice containing the entire vector.
326    ///
327    /// See [`Vec::as_slice`] for more details.
328    ///
329    /// [`Vec::as_slice`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.as_slice
330    #[inline]
331    #[must_use]
332    pub const fn as_slice(&self) -> &TiSlice<K, V> {
333        TiSlice::from_ref(self.raw.as_slice())
334    }
335
336    /// Extracts a mutable slice of the entire vector.
337    ///
338    /// See [`Vec::as_mut_slice`] for more details.
339    ///
340    /// [`Vec::as_mut_slice`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.as_mut_slice
341    #[inline]
342    pub const fn as_mut_slice(&mut self) -> &mut TiSlice<K, V> {
343        TiSlice::from_mut(self.raw.as_mut_slice())
344    }
345
346    /// Returns a raw pointer to the vector's buffer.
347    ///
348    /// See [`Vec::as_ptr`] for more details.
349    ///
350    /// [`Vec::as_ptr`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.as_ptr
351    #[inline]
352    #[must_use]
353    pub const fn as_ptr(&self) -> *const V {
354        self.raw.as_ptr()
355    }
356
357    /// Returns an unsafe mutable pointer to the vector's buffer.
358    ///
359    /// See [`Vec::as_mut_ptr`] for more details.
360    ///
361    /// [`Vec::as_mut_ptr`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.as_mut_ptr
362    #[inline]
363    pub const fn as_mut_ptr(&mut self) -> *mut V {
364        self.raw.as_mut_ptr()
365    }
366
367    /// Forces the length of the vector to `new_len`.
368    ///
369    /// See [`Vec::set_len`] for more details.
370    ///
371    /// # Safety
372    ///
373    /// - `new_len` must be less than or equal to [`capacity()`].
374    /// - The elements at `old_len..new_len` must be initialized.
375    ///
376    /// [`Vec::set_len`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.set_len
377    /// [`capacity()`]: #method.capacity
378    #[inline]
379    pub unsafe fn set_len(&mut self, new_len: usize) {
380        // SAFETY: Guaranteed by the caller.
381        unsafe { self.raw.set_len(new_len) };
382    }
383
384    /// Removes an element from the vector and returns it.
385    ///
386    /// The removed element is replaced by the last element of the vector.
387    ///
388    /// See [`Vec::swap_remove`] for more details.
389    ///
390    /// [`Vec::swap_remove`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.swap_remove
391    #[inline]
392    pub fn swap_remove(&mut self, index: K) -> V
393    where
394        K: Into<usize>,
395    {
396        self.raw.swap_remove(index.into())
397    }
398
399    /// Inserts an element at position `index` within the vector, shifting all
400    /// elements after it to the right.
401    ///
402    /// See [`Vec::insert`] for more details.
403    ///
404    /// [`Vec::insert`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.insert
405    #[inline]
406    pub fn insert(&mut self, index: K, element: V)
407    where
408        K: Into<usize>,
409    {
410        self.raw.insert(index.into(), element);
411    }
412
413    /// Removes and returns the element at position `index` within the vector,
414    /// shifting all elements after it to the left.
415    ///
416    /// See [`Vec::remove`] for more details.
417    ///
418    /// [`Vec::remove`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.remove
419    #[inline]
420    pub fn remove(&mut self, index: K) -> V
421    where
422        K: Into<usize>,
423    {
424        self.raw.remove(index.into())
425    }
426
427    /// Retains only the elements specified by the predicate.
428    ///
429    /// See [`Vec::retain`] for more details.
430    ///
431    /// [`Vec::retain`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.retain
432    #[inline]
433    pub fn retain<F>(&mut self, f: F)
434    where
435        F: FnMut(&V) -> bool,
436    {
437        self.raw.retain(f);
438    }
439
440    /// Retains only the elements specified by the predicate, passing a mutable
441    /// reference to it.
442    ///
443    /// See [`Vec::retain_mut`] for more details.
444    ///
445    /// [`Vec::retain_mut`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.retain_mut
446    #[inline]
447    pub fn retain_mut<F>(&mut self, f: F)
448    where
449        F: FnMut(&mut V) -> bool,
450    {
451        self.raw.retain_mut(f);
452    }
453
454    /// Removes all but the first of consecutive elements in the vector that
455    /// resolve to the same key.
456    ///
457    /// See [`Vec::dedup_by_key`] for more details.
458    ///
459    /// [`Vec::dedup_by_key`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.dedup_by_key
460    #[inline]
461    pub fn dedup_by_key<F, K2>(&mut self, key: F)
462    where
463        F: FnMut(&mut V) -> K2,
464        K2: PartialEq,
465    {
466        self.raw.dedup_by_key(key);
467    }
468
469    /// Removes all but the first of consecutive elements in the vector
470    /// satisfying a given equality relation.
471    ///
472    /// See [`Vec::dedup_by`] for more details.
473    ///
474    /// [`Vec::dedup_by`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.dedup_by
475    #[inline]
476    pub fn dedup_by<F>(&mut self, same_bucket: F)
477    where
478        F: FnMut(&mut V, &mut V) -> bool,
479    {
480        self.raw.dedup_by(same_bucket);
481    }
482
483    /// Appends an element to the back of a collection.
484    ///
485    /// See [`Vec::push`] for more details.
486    ///
487    /// [`Vec::push`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.push
488    #[inline]
489    pub fn push(&mut self, value: V) {
490        self.raw.push(value);
491    }
492
493    /// Appends an element to the back of a collection and returns its index of
494    /// type `K`.
495    ///
496    /// It acts like `{ vec.push(...); vec.last_key().unwrap() }`,
497    /// but is optimized better.
498    ///
499    /// See [`Vec::push`] for more details.
500    ///
501    /// # Example
502    ///
503    /// ```
504    /// # use derive_more::{From, Into};
505    /// # use typed_index_collections::TiVec;
506    /// #[derive(Eq, Debug, From, Into, PartialEq)]
507    /// pub struct Id(usize);
508    /// let mut vec: TiVec<Id, usize> = vec![1, 2, 4].into();
509    /// assert_eq!(vec.push_and_get_key(8), Id(3));
510    /// assert_eq!(vec.push_and_get_key(16), Id(4));
511    /// assert_eq!(vec.push_and_get_key(32), Id(5));
512    /// ```
513    ///
514    /// [`Vec::push`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.push
515    #[inline]
516    pub fn push_and_get_key(&mut self, value: V) -> K
517    where
518        usize: Into<K>,
519    {
520        let key = self.next_key();
521        self.raw.push(value);
522        key
523    }
524
525    /// Removes the last element from a vector and returns it, or [`None`] if it
526    /// is empty.
527    ///
528    /// See [`Vec::pop`] for more details.
529    ///
530    /// [`Vec::pop`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.pop
531    #[inline]
532    pub fn pop(&mut self) -> Option<V> {
533        self.raw.pop()
534    }
535
536    /// Removes the last element from a vector and returns it with
537    /// its index of type `K`, or [`None`] if the vector is empty.
538    ///
539    /// See [`Vec::pop`] for more details.
540    ///
541    /// # Example
542    ///
543    /// ```
544    /// # use derive_more::{From, Into};
545    /// # use typed_index_collections::TiVec;
546    /// #[derive(Eq, Debug, From, Into, PartialEq)]
547    /// pub struct Id(usize);
548    /// let mut vec: TiVec<Id, usize> = vec![1, 2, 4].into();
549    /// assert_eq!(vec.pop_key_value(), Some((Id(2), 4)));
550    /// assert_eq!(vec.pop_key_value(), Some((Id(1), 2)));
551    /// assert_eq!(vec.pop_key_value(), Some((Id(0), 1)));
552    /// assert_eq!(vec.pop_key_value(), None);
553    /// ```
554    ///
555    /// [`Vec::pop`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.pop
556    #[inline]
557    pub fn pop_key_value(&mut self) -> Option<(K, V)>
558    where
559        usize: Into<K>,
560    {
561        self.raw.pop().map(|value| (self.raw.len().into(), value))
562    }
563
564    /// Removes and returns the last element from a vector if the predicate
565    /// returns `true`, or [`None`] if the predicate returns false or the vector
566    /// is empty (the predicate will not be called in that case).
567    ///
568    /// See [`Vec::pop_if`] for more details.
569    ///
570    /// [`Vec::pop_if`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.pop_if
571    #[inline]
572    pub fn pop_if(&mut self, predicate: impl FnOnce(&mut V) -> bool) -> Option<V> {
573        self.raw.pop_if(predicate)
574    }
575
576    /// Removes and returns the last element from a vector if the predicate
577    /// returns `true` with its index of type `K`, or [`None`] if the predicate
578    /// returns false or the vector is empty (the predicate will not be called
579    /// in that case).
580    ///
581    /// See [`Vec::pop_if`] for more details.
582    ///
583    /// # Example
584    ///
585    /// ```
586    /// # use derive_more::{From, Into};
587    /// # use typed_index_collections::TiVec;
588    /// #[derive(Eq, Debug, From, Into, PartialEq)]
589    /// pub struct Id(usize);
590    /// let mut vec: TiVec<Id, i32> = vec![-2, 4].into();
591    /// assert_eq!(vec.pop_key_value_if(|v| *v > 0), Some((Id(1), 4)));
592    /// assert_eq!(vec.pop_key_value_if(|v| *v > 0), None);
593    /// assert_eq!(vec.pop_key_value_if(|v| *v < 0), Some((Id(0), -2)));
594    /// assert_eq!(vec.pop_key_value_if(|v| *v < 0), None);
595    /// assert_eq!(vec.pop_key_value_if(|v| *v > 0), None);
596    /// ```
597    ///
598    /// [`Vec::pop_if`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.pop_if
599    #[inline]
600    pub fn pop_key_value_if(&mut self, predicate: impl FnOnce(&mut V) -> bool) -> Option<(K, V)>
601    where
602        usize: Into<K>,
603    {
604        self.raw
605            .pop_if(predicate)
606            .map(|value| (self.raw.len().into(), value))
607    }
608
609    /// Moves all the elements of `other` into `Self`, leaving `other` empty.
610    ///
611    /// See [`Vec::append`] for more details.
612    ///
613    /// [`Vec::append`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.append
614    #[inline]
615    pub fn append(&mut self, other: &mut Self) {
616        self.raw.append(&mut other.raw);
617    }
618
619    /// Creates a draining iterator that removes the specified range in the
620    /// vector and yields the removed items.
621    ///
622    /// See [`Vec::drain`] for more details.
623    ///
624    /// [`Vec::drain`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.drain
625    #[inline]
626    pub fn drain<R>(&mut self, range: R) -> Drain<'_, V>
627    where
628        R: TiRangeBounds<K>,
629    {
630        self.raw.drain(range.into_range())
631    }
632
633    /// Creates a draining iterator that removes the specified
634    /// range in the vector and yields the current count and the removed items.
635    ///
636    /// It acts like `self.drain(range).enumerate()`,
637    /// but instead of `usize` it returns index of type `K`.
638    ///
639    /// Note that the indices started from `K::from_usize(0)`,
640    /// regardless of the range starting point.
641    ///
642    /// See [`Vec::drain`] for more details.
643    ///
644    /// # Example
645    ///
646    /// ```
647    /// # use derive_more::{From, Into};
648    /// # use typed_index_collections::{TiSlice, TiVec};
649    /// #[derive(Eq, Debug, From, Into, PartialEq)]
650    /// pub struct Id(usize);
651    /// let mut vec: TiVec<Id, usize> = vec![1, 2, 4].into();
652    /// {
653    ///     let mut iterator = vec.drain_enumerated(Id(1)..);
654    ///     assert_eq!(iterator.next(), Some((Id(0), 2)));
655    ///     assert_eq!(iterator.next(), Some((Id(1), 4)));
656    ///     assert_eq!(iterator.next(), None);
657    /// }
658    /// assert_eq!(vec.as_slice(), TiSlice::from_ref(&[1]));
659    /// ```
660    ///
661    /// [`Vec::drain`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.drain
662    #[inline]
663    pub fn drain_enumerated<R>(&mut self, range: R) -> TiEnumerated<Drain<'_, V>, K, V>
664    where
665        usize: Into<K>,
666        R: TiRangeBounds<K>,
667    {
668        self.raw
669            .drain(range.into_range())
670            .enumerate()
671            .map(|(key, value)| (key.into(), value))
672    }
673
674    /// Clears the vector, removing all values.
675    ///
676    /// See [`Vec::clear`] for more details.
677    ///
678    /// [`Vec::clear`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.clear
679    #[inline]
680    pub fn clear(&mut self) {
681        self.raw.clear();
682    }
683
684    /// Returns the number of elements in the vector, also referred to
685    /// as its 'length'.
686    ///
687    /// See [`Vec::len`] for more details.
688    ///
689    /// [`Vec::len`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.len
690    #[inline]
691    #[must_use]
692    pub const fn len(&self) -> usize {
693        self.raw.len()
694    }
695
696    /// Returns `true` if the vector contains no elements.
697    ///
698    /// See [`Vec::is_empty`] for more details.
699    ///
700    /// [`Vec::is_empty`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.is_empty
701    #[inline]
702    #[must_use]
703    pub const fn is_empty(&self) -> bool {
704        self.raw.is_empty()
705    }
706
707    /// Splits the collection into two at the given index.
708    ///
709    /// See [`Vec::split_off`] for more details.
710    ///
711    /// [`Vec::split_off`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.split_off
712    #[inline]
713    #[must_use = "use `.truncate()` if you don't need the other half"]
714    pub fn split_off(&mut self, at: K) -> Self
715    where
716        K: Into<usize>,
717    {
718        self.raw.split_off(at.into()).into()
719    }
720
721    /// Resizes the `TiVec` in-place so that `len` is equal to `new_len`.
722    ///
723    /// See [`Vec::resize_with`] for more details.
724    ///
725    /// [`Vec::resize_with`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.resize_with
726    #[inline]
727    pub fn resize_with<F>(&mut self, new_len: usize, f: F)
728    where
729        F: FnMut() -> V,
730    {
731        self.raw.resize_with(new_len, f);
732    }
733
734    /// Resizes the `TiVec` in-place so that `len` is equal to `new_len`.
735    ///
736    /// See [`Vec::resize`] for more details.
737    ///
738    /// [`Vec::resize`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.resize
739    #[inline]
740    pub fn resize(&mut self, new_len: usize, value: V)
741    where
742        V: Clone,
743    {
744        self.raw.resize(new_len, value);
745    }
746
747    /// Consumes and leaks the `Vec`, returning a mutable reference to the
748    /// contents, `&'a mut [T]`. Note that the type `T` must outlive the
749    /// chosen lifetime `'a`. If the type has only static references, or
750    /// none at all, then this may be chosen to be `'static`.
751    ///
752    /// See [`Vec::leak`] for more details.
753    ///
754    /// [`Vec::leak`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.leak
755    #[expect(clippy::must_use_candidate, reason = "not used in `Vec::leak`")]
756    #[inline]
757    pub fn leak<'a>(self) -> &'a mut TiSlice<K, V> {
758        self.raw.leak().as_mut()
759    }
760
761    /// Returns the remaining spare capacity of the vector as a slice of
762    /// `MaybeUninit<T>`.
763    ///
764    /// See [`Vec::spare_capacity_mut`] for more details.
765    ///
766    /// [`Vec::spare_capacity_mut`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.spare_capacity_mut
767    #[inline]
768    pub fn spare_capacity_mut(&mut self) -> &mut TiSlice<K, MaybeUninit<V>> {
769        self.raw.spare_capacity_mut().as_mut()
770    }
771
772    /// Clones and appends all elements in a slice to the `TiVec`.
773    ///
774    /// See [`Vec::extend_from_slice`] for more details.
775    ///
776    /// [`Vec::extend_from_slice`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.extend_from_slice
777    #[inline]
778    pub fn extend_from_slice(&mut self, other: &TiSlice<K, V>)
779    where
780        V: Clone,
781    {
782        self.raw.extend_from_slice(&other.raw);
783    }
784
785    /// Copies elements from `src` range to the end of the vector.
786    ///
787    /// See [`Vec::extend_from_within`] for more details.
788    ///
789    /// # Panics
790    ///
791    /// Panics if the starting point is greater than the end point or if
792    /// the end point is greater than the length of the vector.
793    ///
794    /// [`Vec::extend_from_within`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.extend_from_within
795    #[inline]
796    pub fn extend_from_within<R>(&mut self, src: R)
797    where
798        V: Clone,
799        R: RangeBounds<usize>,
800    {
801        self.raw.extend_from_within(src);
802    }
803
804    /// Removes consecutive repeated elements in the vector according to the
805    /// [`PartialEq`] trait implementation.
806    ///
807    /// See [`Vec::dedup`] for more details.
808    ///
809    /// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
810    /// [`Vec::dedup`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.dedup
811    #[inline]
812    pub fn dedup(&mut self)
813    where
814        V: PartialEq,
815    {
816        self.raw.dedup();
817    }
818
819    /// Creates a splicing iterator that replaces the specified range in the
820    /// vector with the given `replace_with` iterator and yields the removed
821    /// items. `replace_with` does not need to be the same length as
822    /// `range`.
823    ///
824    /// See [`Vec::splice`] for more details.
825    ///
826    /// [`Vec::splice`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.splice
827    #[inline]
828    pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter>
829    where
830        R: TiRangeBounds<K>,
831        I: IntoIterator<Item = V>,
832    {
833        self.raw.splice(range.into_range(), replace_with)
834    }
835
836    /// Converts the vector into iterator over all key-value pairs
837    /// with `K` used for iteration indices.
838    ///
839    /// It acts like `self.into_iter().enumerate()`,
840    /// but use `K` instead of `usize` for iteration indices.
841    ///
842    /// # Example
843    ///
844    /// ```
845    /// # use derive_more::{From, Into};
846    /// # use typed_index_collections::TiVec;
847    /// #[derive(Eq, Debug, From, Into, PartialEq)]
848    /// pub struct Id(usize);
849    /// let vec: TiVec<Id, usize> = vec![1, 2, 4].into();
850    /// let mut iterator = vec.into_iter_enumerated();
851    /// assert_eq!(iterator.next(), Some((Id(0), 1)));
852    /// assert_eq!(iterator.next(), Some((Id(1), 2)));
853    /// assert_eq!(iterator.next(), Some((Id(2), 4)));
854    /// assert_eq!(iterator.next(), None);
855    /// ```
856    #[inline]
857    pub fn into_iter_enumerated(self) -> TiEnumerated<vec::IntoIter<V>, K, V>
858    where
859        usize: Into<K>,
860    {
861        self.raw
862            .into_iter()
863            .enumerate()
864            .map(|(key, value)| (key.into(), value))
865    }
866}
867
868impl<K, V> fmt::Debug for TiVec<K, V>
869where
870    K: fmt::Debug,
871    V: fmt::Debug,
872    usize: Into<K>,
873{
874    #[allow(clippy::allow_attributes, reason = "rust-lang/rust#130021")]
875    #[allow(
876        clippy::missing_inline_in_public_items,
877        reason = "use default inlining behavior"
878    )]
879    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
880        f.debug_map().entries(self.iter_enumerated()).finish()
881    }
882}
883
884impl<K, V> AsRef<Self> for TiVec<K, V> {
885    #[inline]
886    fn as_ref(&self) -> &Self {
887        self
888    }
889}
890
891impl<K, V> AsMut<Self> for TiVec<K, V> {
892    #[inline]
893    fn as_mut(&mut self) -> &mut Self {
894        self
895    }
896}
897
898impl<K, V> AsRef<TiSlice<K, V>> for TiVec<K, V> {
899    #[inline]
900    fn as_ref(&self) -> &TiSlice<K, V> {
901        self
902    }
903}
904
905impl<K, V> AsMut<TiSlice<K, V>> for TiVec<K, V> {
906    #[inline]
907    fn as_mut(&mut self) -> &mut TiSlice<K, V> {
908        self
909    }
910}
911
912impl<K, V> AsRef<Vec<V>> for TiVec<K, V> {
913    #[inline]
914    fn as_ref(&self) -> &Vec<V> {
915        &self.raw
916    }
917}
918
919impl<K, V> AsMut<Vec<V>> for TiVec<K, V> {
920    #[inline]
921    fn as_mut(&mut self) -> &mut Vec<V> {
922        &mut self.raw
923    }
924}
925
926impl<K, V> AsRef<[V]> for TiVec<K, V> {
927    #[inline]
928    fn as_ref(&self) -> &[V] {
929        &self.raw
930    }
931}
932
933impl<K, V> AsMut<[V]> for TiVec<K, V> {
934    #[inline]
935    fn as_mut(&mut self) -> &mut [V] {
936        &mut self.raw
937    }
938}
939
940impl<K, V> AsRef<TiVec<K, V>> for Vec<V> {
941    #[inline]
942    fn as_ref(&self) -> &TiVec<K, V> {
943        TiVec::from_ref(self)
944    }
945}
946
947impl<K, V> AsMut<TiVec<K, V>> for Vec<V> {
948    #[inline]
949    fn as_mut(&mut self) -> &mut TiVec<K, V> {
950        TiVec::from_mut(self)
951    }
952}
953
954impl<K, V> Borrow<TiSlice<K, V>> for TiVec<K, V> {
955    #[inline]
956    fn borrow(&self) -> &TiSlice<K, V> {
957        self.as_slice()
958    }
959}
960
961impl<K, V> BorrowMut<TiSlice<K, V>> for TiVec<K, V> {
962    #[inline]
963    fn borrow_mut(&mut self) -> &mut TiSlice<K, V> {
964        self.as_mut_slice()
965    }
966}
967
968impl<K, V> Deref for TiVec<K, V> {
969    type Target = TiSlice<K, V>;
970
971    #[inline]
972    fn deref(&self) -> &TiSlice<K, V> {
973        Self::Target::from_ref(&self.raw)
974    }
975}
976
977impl<K, V> DerefMut for TiVec<K, V> {
978    #[inline]
979    fn deref_mut(&mut self) -> &mut TiSlice<K, V> {
980        Self::Target::from_mut(&mut self.raw)
981    }
982}
983
984impl<K, V> From<Vec<V>> for TiVec<K, V> {
985    #[inline]
986    fn from(vec: Vec<V>) -> Self {
987        Self {
988            raw: vec,
989            _marker: PhantomData,
990        }
991    }
992}
993
994impl<K, V> From<TiVec<K, V>> for Vec<V> {
995    #[inline]
996    fn from(vec: TiVec<K, V>) -> Self {
997        vec.raw
998    }
999}
1000
1001impl<K, V> From<&TiSlice<K, V>> for TiVec<K, V>
1002where
1003    V: Clone,
1004{
1005    #[inline]
1006    fn from(slice: &TiSlice<K, V>) -> Self {
1007        slice.to_vec()
1008    }
1009}
1010
1011impl<K, V> From<&mut TiSlice<K, V>> for TiVec<K, V>
1012where
1013    V: Clone,
1014{
1015    #[inline]
1016    fn from(slice: &mut TiSlice<K, V>) -> Self {
1017        slice.to_vec()
1018    }
1019}
1020
1021impl<K, V> From<Cow<'_, TiSlice<K, V>>> for TiVec<K, V>
1022where
1023    V: Clone,
1024{
1025    #[inline]
1026    fn from(slice: Cow<'_, TiSlice<K, V>>) -> Self {
1027        slice.into_owned()
1028    }
1029}
1030
1031impl<K, V> From<TiVec<K, V>> for Cow<'_, TiSlice<K, V>>
1032where
1033    V: Clone,
1034{
1035    #[inline]
1036    fn from(vec: TiVec<K, V>) -> Self {
1037        Cow::Owned(vec)
1038    }
1039}
1040
1041impl<K> From<&str> for TiVec<K, u8> {
1042    #[inline]
1043    fn from(s: &str) -> Self {
1044        s.as_bytes().to_vec().into()
1045    }
1046}
1047
1048impl<K> From<String> for TiVec<K, u8> {
1049    #[inline]
1050    fn from(s: String) -> Self {
1051        s.into_bytes().into()
1052    }
1053}
1054
1055impl<K> From<CString> for TiVec<K, u8> {
1056    #[inline]
1057    fn from(s: CString) -> Self {
1058        s.into_bytes().into()
1059    }
1060}
1061
1062impl<K, V> Clone for TiVec<K, V>
1063where
1064    V: Clone,
1065{
1066    #[inline]
1067    fn clone(&self) -> Self {
1068        self.raw.clone().into()
1069    }
1070}
1071
1072impl<K, V> Eq for TiVec<K, V> where V: Eq {}
1073
1074impl<K, A, B> PartialEq<TiVec<K, B>> for TiVec<K, A>
1075where
1076    A: PartialEq<B>,
1077{
1078    #[inline]
1079    fn eq(&self, other: &TiVec<K, B>) -> bool {
1080        self.raw == other.raw
1081    }
1082}
1083
1084impl<K, A, B> PartialEq<TiSlice<K, B>> for TiVec<K, A>
1085where
1086    A: PartialEq<B>,
1087{
1088    #[inline]
1089    fn eq(&self, other: &TiSlice<K, B>) -> bool {
1090        *self.raw == other.raw
1091    }
1092}
1093
1094impl<K, A, B> PartialEq<TiVec<K, B>> for TiSlice<K, A>
1095where
1096    A: PartialEq<B>,
1097{
1098    #[inline]
1099    fn eq(&self, other: &TiVec<K, B>) -> bool {
1100        self.raw == *other.raw
1101    }
1102}
1103
1104impl<'a, K, A, B> PartialEq<&'a TiSlice<K, B>> for TiVec<K, A>
1105where
1106    A: PartialEq<B>,
1107{
1108    #[inline]
1109    fn eq(&self, other: &&'a TiSlice<K, B>) -> bool {
1110        *self.raw == other.raw
1111    }
1112}
1113
1114impl<K, A, B> PartialEq<TiVec<K, B>> for &TiSlice<K, A>
1115where
1116    A: PartialEq<B>,
1117{
1118    #[inline]
1119    fn eq(&self, other: &TiVec<K, B>) -> bool {
1120        self.raw == *other.raw
1121    }
1122}
1123
1124impl<'a, K, A, B> PartialEq<&'a mut TiSlice<K, B>> for TiVec<K, A>
1125where
1126    A: PartialEq<B>,
1127{
1128    #[inline]
1129    fn eq(&self, other: &&'a mut TiSlice<K, B>) -> bool {
1130        *self.raw == other.raw
1131    }
1132}
1133
1134impl<K, A, B> PartialEq<TiVec<K, B>> for &mut TiSlice<K, A>
1135where
1136    A: PartialEq<B>,
1137{
1138    #[inline]
1139    fn eq(&self, other: &TiVec<K, B>) -> bool {
1140        self.raw == *other.raw
1141    }
1142}
1143
1144impl<K, V> Ord for TiVec<K, V>
1145where
1146    V: Ord,
1147{
1148    #[inline]
1149    fn cmp(&self, other: &Self) -> Ordering {
1150        self.raw.cmp(&other.raw)
1151    }
1152}
1153
1154impl<K, V> PartialOrd<Self> for TiVec<K, V>
1155where
1156    V: PartialOrd<V>,
1157{
1158    #[inline]
1159    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1160        self.raw.partial_cmp(&other.raw)
1161    }
1162}
1163
1164impl<K, V> Hash for TiVec<K, V>
1165where
1166    V: Hash,
1167{
1168    #[inline]
1169    fn hash<H: Hasher>(&self, state: &mut H) {
1170        self.raw.hash(state);
1171    }
1172}
1173
1174impl<K, V> Default for TiVec<K, V> {
1175    #[inline]
1176    fn default() -> Self {
1177        Vec::default().into()
1178    }
1179}
1180
1181impl<I, K, V> Index<I> for TiVec<K, V>
1182where
1183    I: TiSliceIndex<K, V>,
1184{
1185    type Output = I::Output;
1186
1187    #[inline]
1188    fn index(&self, index: I) -> &Self::Output {
1189        index.index(self)
1190    }
1191}
1192
1193impl<I, K, V> IndexMut<I> for TiVec<K, V>
1194where
1195    I: TiSliceIndex<K, V>,
1196{
1197    #[inline]
1198    fn index_mut(&mut self, index: I) -> &mut Self::Output {
1199        index.index_mut(self)
1200    }
1201}
1202
1203impl<K, V> Extend<V> for TiVec<K, V> {
1204    #[inline]
1205    fn extend<I: IntoIterator<Item = V>>(&mut self, iter: I) {
1206        self.raw.extend(iter);
1207    }
1208}
1209
1210impl<'a, K, V: 'a + Copy> Extend<&'a V> for TiVec<K, V> {
1211    #[inline]
1212    fn extend<I: IntoIterator<Item = &'a V>>(&mut self, iter: I) {
1213        self.raw.extend(iter);
1214    }
1215}
1216
1217impl<K, V> FromIterator<V> for TiVec<K, V> {
1218    #[inline]
1219    fn from_iter<I: IntoIterator<Item = V>>(iter: I) -> Self {
1220        Self {
1221            raw: Vec::from_iter(iter),
1222            _marker: PhantomData,
1223        }
1224    }
1225}
1226
1227impl<K, V> IntoIterator for TiVec<K, V> {
1228    type Item = V;
1229    type IntoIter = vec::IntoIter<V>;
1230
1231    #[inline]
1232    fn into_iter(self) -> vec::IntoIter<V> {
1233        self.raw.into_iter()
1234    }
1235}
1236
1237impl<'a, K, V> IntoIterator for &'a TiVec<K, V> {
1238    type Item = &'a V;
1239    type IntoIter = slice::Iter<'a, V>;
1240
1241    #[inline]
1242    fn into_iter(self) -> slice::Iter<'a, V> {
1243        self.raw.iter()
1244    }
1245}
1246
1247impl<'a, K, V> IntoIterator for &'a mut TiVec<K, V> {
1248    type Item = &'a mut V;
1249    type IntoIter = slice::IterMut<'a, V>;
1250
1251    #[inline]
1252    fn into_iter(self) -> slice::IterMut<'a, V> {
1253        self.raw.iter_mut()
1254    }
1255}
1256
1257/// Write is implemented for `Vec<u8>` by appending to the vector.
1258/// The vector will grow as needed.
1259#[cfg(feature = "std")]
1260#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
1261impl<K> Write for TiVec<K, u8> {
1262    #[inline]
1263    fn write(&mut self, buf: &[u8]) -> IoResult<usize> {
1264        self.raw.write(buf)
1265    }
1266
1267    #[inline]
1268    fn write_vectored(&mut self, bufs: &[IoSlice<'_>]) -> IoResult<usize> {
1269        self.raw.write_vectored(bufs)
1270    }
1271
1272    #[inline]
1273    fn write_all(&mut self, buf: &[u8]) -> IoResult<()> {
1274        self.raw.write_all(buf)
1275    }
1276
1277    #[inline]
1278    fn flush(&mut self) -> IoResult<()> {
1279        self.raw.flush()
1280    }
1281}
1282
1283#[cfg(feature = "serde")]
1284#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
1285impl<K, V> Serialize for TiVec<K, V>
1286where
1287    V: Serialize,
1288{
1289    #[inline]
1290    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1291    where
1292        S: Serializer,
1293    {
1294        self.raw.as_slice().serialize(serializer)
1295    }
1296}
1297
1298#[cfg(feature = "serde")]
1299#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
1300impl<'de, K, V> Deserialize<'de> for TiVec<K, V>
1301where
1302    V: Deserialize<'de>,
1303{
1304    #[inline]
1305    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
1306    where
1307        D: Deserializer<'de>,
1308    {
1309        Vec::deserialize(deserializer).map(Into::into)
1310    }
1311}
1312
1313#[cfg(feature = "bincode")]
1314#[cfg_attr(docsrs, doc(cfg(feature = "bincode")))]
1315impl<K, V> Encode for TiVec<K, V>
1316where
1317    V: Encode,
1318{
1319    #[inline]
1320    fn encode<E>(&self, encoder: &mut E) -> Result<(), EncodeError>
1321    where
1322        E: Encoder,
1323    {
1324        self.raw.encode(encoder)
1325    }
1326}
1327
1328#[cfg(feature = "bincode")]
1329#[cfg_attr(docsrs, doc(cfg(feature = "bincode")))]
1330impl<K, V, Context> Decode<Context> for TiVec<K, V>
1331where
1332    V: Decode<Context>,
1333{
1334    #[inline]
1335    fn decode<D>(decoder: &mut D) -> Result<Self, DecodeError>
1336    where
1337        D: Decoder<Context = Context>,
1338    {
1339        Vec::decode(decoder).map(Into::into)
1340    }
1341}
1342
1343#[cfg(feature = "bincode")]
1344#[cfg_attr(docsrs, doc(cfg(feature = "bincode")))]
1345impl<'de, K, V, Context> BorrowDecode<'de, Context> for TiVec<K, V>
1346where
1347    V: BorrowDecode<'de, Context>,
1348{
1349    #[inline]
1350    fn borrow_decode<D>(decoder: &mut D) -> Result<Self, DecodeError>
1351    where
1352        D: BorrowDecoder<'de, Context = Context>,
1353    {
1354        Vec::borrow_decode(decoder).map(Into::into)
1355    }
1356}
1357
1358#[expect(
1359    dead_code,
1360    unused_imports,
1361    unused_mut,
1362    clippy::into_iter_on_ref,
1363    clippy::op_ref,
1364    clippy::too_many_lines,
1365    clippy::undocumented_unsafe_blocks,
1366    clippy::unwrap_used,
1367    reason = "okay in tests"
1368)]
1369#[cfg(test)]
1370mod test {
1371    use alloc::borrow::{Cow, ToOwned};
1372    use alloc::boxed::Box;
1373    use alloc::ffi::CString;
1374    use alloc::string::ToString;
1375    use alloc::vec::Vec;
1376    use core::borrow::{Borrow, BorrowMut};
1377    use core::hash::{Hash, Hasher};
1378    use core::ops::Bound;
1379    #[cfg(feature = "std")]
1380    use std::hash::DefaultHasher;
1381    #[cfg(feature = "std")]
1382    use std::io::{IoSlice, Write};
1383
1384    use crate::test_util::{AsSliceAndCapacity, Id};
1385    use crate::{TiSlice, TiVec};
1386
1387    #[test]
1388    fn test_vec_read_api_compatibility() {
1389        assert_eq!(
1390            TiVec::<Id, u32>::new().as_slice_and_capacity(),
1391            Vec::<u32>::new().as_slice_and_capacity(),
1392        );
1393        for c in [0, 1, 2, 4] {
1394            assert_eq!(
1395                TiVec::<Id, u32>::with_capacity(c).as_slice_and_capacity(),
1396                Vec::<u32>::with_capacity(c).as_slice_and_capacity(),
1397            );
1398        }
1399
1400        for v in [
1401            &[0_u32; 0][..],
1402            &[1],
1403            &[1, 1234],
1404            &[1, 2, 4],
1405            &[1, 5, 3, 2],
1406            &[1, 1, 9, 2, 4, 1, 12345, 12],
1407        ] {
1408            let cv = (v.to_vec(), TiVec::<Id, _>::from(v.to_vec()));
1409            let mut cv = (&cv.0, &cv.1);
1410
1411            let mut mv = (v.to_vec(), TiVec::<Id, _>::from(v.to_vec()));
1412            let mut mv = (&mut mv.0, &mut mv.1);
1413
1414            assert_eq_api!(cv, v => AsRef::<[_]>::as_ref(v));
1415            assert_eq_api!(mv, v => AsMut::<[_]>::as_mut(v));
1416            assert_eq_api!(cv, v => AsRef::<Vec<_>>::as_ref(v));
1417            assert_eq_api!(mv, v => AsMut::<Vec<_>>::as_mut(v));
1418            assert_eq_api!(cv, v => AsRef::<TiVec<_, _>>::as_ref(v));
1419            assert_eq_api!(mv, v => AsMut::<TiVec<_, _>>::as_mut(v));
1420            assert_eq!(
1421                AsRef::<[_]>::as_ref(cv.0),
1422                AsRef::<[_]>::as_ref(AsRef::<TiSlice<_, _>>::as_ref(cv.1))
1423            );
1424            assert_eq!(
1425                AsMut::<[_]>::as_mut(mv.0),
1426                AsMut::<[_]>::as_mut(AsMut::<TiSlice<_, _>>::as_mut(mv.1))
1427            );
1428            assert_eq!(
1429                Borrow::<[_]>::borrow(cv.0),
1430                AsRef::<[_]>::as_ref(Borrow::<TiSlice<_, _>>::borrow(cv.1))
1431            );
1432            assert_eq!(
1433                BorrowMut::<[_]>::borrow_mut(mv.0),
1434                AsMut::<[_]>::as_mut(BorrowMut::<TiSlice<_, _>>::borrow_mut(mv.1))
1435            );
1436
1437            assert_eq_api!(cv, v => v.len());
1438            assert_eq_api!(cv, v => v.is_empty());
1439            assert_eq_api!(cv, v => v.capacity());
1440            assert_eq_api!(cv, v => v.as_slice().into_std());
1441            assert_eq_api!(mv, v => v.as_mut_slice().into_std());
1442            assert_eq_api!(cv, v => TheVec::from(v.as_slice()).into_std());
1443            assert_eq_api!(mv, v => TheVec::from(v.as_mut_slice()).into_std());
1444            assert_eq_api!(cv, v => TheVec::from(Cow::Borrowed(v.as_slice())).into_std());
1445            assert_eq_api!(mv, v => Cow::from(v.clone()).into_std());
1446
1447            if !v.is_empty() {
1448                assert_ne!(cv.0.as_ptr(), cv.1.as_ptr());
1449                assert_ne!(cv.0.as_ptr_range(), cv.1.as_ptr_range());
1450                assert_ne!(mv.0.as_mut_ptr(), mv.1.as_mut_ptr());
1451                assert_ne!(mv.0.as_mut_ptr_range(), mv.1.as_mut_ptr_range());
1452            }
1453
1454            assert_eq_api!(cv, v => *v == TheVec::<u32>::default());
1455            assert_eq_api!(cv, v => v == v.as_slice());
1456            assert_eq_api!(cv, v => v.as_slice() == v);
1457            assert_eq_api!(cv, v => v == &v.as_slice());
1458            assert_eq_api!(cv, v => &v.as_slice() == v);
1459            assert_eq_api!(mv, v => v == &(&mut [1_u32, 1234][..]).into_tic());
1460            assert_eq_api!(mv, v => &(&mut [1_u32, 1234][..]).into_tic() == v);
1461            assert_eq_api!(cv, v => v.cmp(&alloc::vec![1, 1234].into_tic()));
1462            assert_eq_api!(cv, v => v.partial_cmp(&alloc::vec![1, 1234].into_tic()));
1463
1464            for i in 0..v.len() {
1465                assert_eq_api!(cv, v => v[i.into_tic()]);
1466                assert_eq_api!(mv, v => v[i.into_tic()] = v[i.into_tic()]);
1467            }
1468
1469            unsafe {
1470                assert_eq_api!(cv, v => {
1471                    let mut v = core::mem::ManuallyDrop::new(v.clone());
1472                    TheVec::from_raw_parts(v.as_mut_ptr(), v.len(), v.capacity()).into_std()
1473                });
1474            }
1475        }
1476    }
1477
1478    #[test]
1479    fn test_vec_write_api_compatibility() {
1480        for v in [
1481            &[0_u32; 0][..],
1482            &[1],
1483            &[1, 1234],
1484            &[1, 2, 4],
1485            &[1, 5, 3, 2],
1486            &[1, 1, 9, 2, 4, 1, 12345, 12],
1487        ] {
1488            let mut mv = (v.to_vec(), TiVec::<Id, _>::from(v.to_vec()));
1489            let mut mv = (&mut mv.0, &mut mv.1);
1490
1491            let restore = |mv: &mut (&mut Vec<u32>, &mut TiVec<Id, u32>)| {
1492                *mv.0 = v.to_vec();
1493                *mv.1 = TiVec::from(v.to_vec());
1494            };
1495
1496            restore(&mut mv);
1497            assert_eq_api!(mv, v => v.try_reserve(usize::MAX));
1498            restore(&mut mv);
1499            assert_eq_api!(mv, v => v.try_reserve_exact(usize::MAX));
1500
1501            for i in 0..8 {
1502                restore(&mut mv);
1503                assert_eq_api!(mv, v => v.resize(i, 123));
1504                restore(&mut mv);
1505                assert_eq_api!(mv, v => { let mut a = 1; v.resize_with(i, || { a *= 2; a }) });
1506                restore(&mut mv);
1507                assert_eq_api!(mv, v => v.reserve(i));
1508                assert_eq_api!(mv, v => v.spare_capacity_mut().len());
1509                restore(&mut mv);
1510                assert_eq_api!(mv, v => v.try_reserve(i));
1511                restore(&mut mv);
1512                assert_eq_api!(mv, v => v.reserve_exact(i));
1513                restore(&mut mv);
1514                assert_eq_api!(mv, v => v.try_reserve_exact(i));
1515                restore(&mut mv);
1516                assert_eq_api!(mv, v => v.reserve_exact(i));
1517                assert_eq_api!(mv, v => v.shrink_to_fit());
1518                restore(&mut mv);
1519                assert_eq_api!(mv, v => v.reserve_exact(i * 2));
1520                assert_eq_api!(mv, v => v.shrink_to(i));
1521                restore(&mut mv);
1522                assert_eq_api!(mv, v => v.truncate(i));
1523            }
1524
1525            let l1: Vec<_> = mv.0.clone();
1526            let l1c = l1.capacity();
1527            let l1 = l1.leak();
1528            let l2: TiVec<_, _> = mv.1.clone();
1529            let l2c = l2.capacity();
1530            let l2 = l2.leak();
1531            assert_eq!(l1, &l2.raw);
1532            drop(unsafe { Vec::from_raw_parts(l1.as_mut_ptr(), l1.len(), l1c) });
1533            drop(unsafe { TiVec::<Id, _>::from_raw_parts(l2.as_mut_ptr(), l2.len(), l2c) });
1534
1535            restore(&mut mv);
1536            assert_eq_api!(mv, v => (&*v).into_iter().copied().collect::<Vec<_>>());
1537            assert_eq_api!(mv, v => v.iter_mut().collect::<Vec<_>>());
1538            assert_eq_api!(mv, v => v.clone().into_iter().collect::<Vec<_>>());
1539
1540            restore(&mut mv);
1541            assert_eq_api!(mv, v => v.pop());
1542            assert_eq_api!(mv, v => v.push(123));
1543            assert_eq_api!(mv, v => v.pop());
1544
1545            restore(&mut mv);
1546            assert_eq_api!(mv, v => v.pop_if(|v| *v < 10));
1547            assert_eq_api!(mv, v => v.push(234));
1548
1549            restore(&mut mv);
1550            assert_eq_api!(mv, v => v.append(&mut v.clone()));
1551            restore(&mut mv);
1552            assert_eq_api!(mv, v => v.extend(v.clone().as_slice()));
1553            restore(&mut mv);
1554            assert_eq_api!(mv, v => v.extend(v.clone().iter().copied()));
1555            restore(&mut mv);
1556            assert_eq_api!(mv, v => v.extend_from_slice(&v.clone()));
1557            restore(&mut mv);
1558            assert_eq_api!(mv, v => v.into_iter().collect::<TheVec<_>>().into_std());
1559
1560            restore(&mut mv);
1561            assert_eq_api!(mv, v => v.retain(|value| value % 3 == 0 || value % 4 == 0));
1562
1563            restore(&mut mv);
1564            assert_eq_api!(mv, v => v.retain_mut(|value| {
1565                *value += 1;
1566                *value % 3 == 0 || *value % 4 == 0
1567            }));
1568
1569            restore(&mut mv);
1570            assert_eq_api!(mv, v => v.dedup());
1571
1572            restore(&mut mv);
1573            assert_eq_api!(mv, v => v.dedup_by(|lhs, rhs| lhs < rhs));
1574
1575            restore(&mut mv);
1576            assert_eq_api!(mv, v => v.dedup_by_key(|value| *value % 3));
1577
1578            for i in 0..v.len() {
1579                restore(&mut mv);
1580                assert_eq_api!(mv, v => v.swap_remove(i.into_tic()));
1581                restore(&mut mv);
1582                assert_eq_api!(mv, v => v.insert(i.into_tic(), 123));
1583                restore(&mut mv);
1584                assert_eq_api!(mv, v => v.remove(i.into_tic()));
1585                restore(&mut mv);
1586                unsafe { assert_eq_api!(mv, v => v.set_len(i)) };
1587                restore(&mut mv);
1588                assert_eq_api!(mv, v => v.split_off(i.into_tic()).into_std());
1589            }
1590
1591            for a in 0..v.len() {
1592                for b in a..v.len() {
1593                    restore(&mut mv);
1594                    assert_eq_api!(mv, v => v.drain((a..b).into_tic()).collect::<Vec<_>>());
1595                    restore(&mut mv);
1596                    assert_eq_api!(mv, v => v.extend_from_within(a..b));
1597                    restore(&mut mv);
1598                    assert_eq_api!(
1599                        mv, v => v.splice((a..b).into_tic(), [1, 2, 3]).collect::<Vec<_>>()
1600                    );
1601                }
1602            }
1603            restore(&mut mv);
1604            assert_eq_api!(mv, v => v.splice(.., [1, 2, 3]).collect::<Vec<_>>());
1605
1606            restore(&mut mv);
1607            assert_eq_api!(mv, v => v.clear());
1608        }
1609    }
1610
1611    #[cfg(feature = "std")]
1612    #[test]
1613    fn test_vec_hash_compatibility() {
1614        for v in [
1615            &[0_u32; 0][..],
1616            &[1],
1617            &[1, 1234],
1618            &[1, 2, 4],
1619            &[1, 5, 3, 2],
1620            &[1, 1, 9, 2, 4, 1, 12345, 12],
1621        ] {
1622            let cv = (v.to_vec(), TiVec::<Id, _>::from(v.to_vec()));
1623            let mut cv = (&cv.0, &cv.1);
1624            assert_eq_api!(cv, v => {
1625                let mut hasher = DefaultHasher::new();
1626                v.hash(&mut hasher);
1627                hasher.finish()
1628            });
1629        }
1630    }
1631
1632    #[test]
1633    fn test_u8_vec_api_compatibility() {
1634        assert_eq!(
1635            Vec::from(TiVec::<Id, u8>::from("abc")),
1636            Vec::<u8>::from("abc"),
1637        );
1638        assert_eq!(
1639            Vec::from(TiVec::<Id, u8>::from("abc".to_owned())),
1640            Vec::<u8>::from("abc".to_owned()),
1641        );
1642        assert_eq!(
1643            Vec::from(TiVec::<Id, u8>::from(CString::new("abc").unwrap())),
1644            Vec::<u8>::from(CString::new("abc").unwrap()),
1645        );
1646
1647        for v in [&b"abc"[..], b"aBc", b"ABC", b"abd", b"a\x80\x81b"] {
1648            let cv = (v.to_vec(), TiVec::<Id, _>::from(v.to_vec()));
1649            let mut cv = (&cv.0, &cv.1);
1650
1651            assert_eq_api!(cv, v => TheVec::from(v.as_slice()).into_std());
1652        }
1653    }
1654
1655    #[test]
1656    fn test_vec_debug() {
1657        let s0: TiVec<Id, u32> = TiVec::from(alloc::vec![]);
1658        let s1: TiVec<Id, u32> = TiVec::from(alloc::vec![12]);
1659        let s2: TiVec<Id, u32> = TiVec::from(alloc::vec![23, 34]);
1660        assert_eq!(&alloc::format!("{s0:?}"), "{}");
1661        assert_eq!(&alloc::format!("{s1:?}"), "{Id(0): 12}");
1662        assert_eq!(&alloc::format!("{s2:?}"), "{Id(0): 23, Id(1): 34}");
1663    }
1664
1665    #[cfg(feature = "std")]
1666    #[test]
1667    fn test_vec_write() {
1668        let mut mv = (Vec::<u8>::new(), TiVec::<Id, u8>::new());
1669        let mut mv = (&mut mv.0, &mut mv.1);
1670
1671        assert_eq_api!(mv, v => v.write(&[1, 2, 3]).unwrap());
1672        assert_eq_api!(mv, v => v.write_vectored(
1673            &[IoSlice::new(&[1, 2, 3]), IoSlice::new(&[4, 5])]
1674        ).unwrap());
1675        assert_eq_api!(mv, v => v.write_all(&[1, 2, 3]).unwrap());
1676        assert_eq_api!(mv, v => v.flush().unwrap());
1677    }
1678
1679    #[cfg(feature = "serde")]
1680    #[test]
1681    fn test_vec_serialize() {
1682        let s0: TiVec<Id, u32> = TiVec::from(alloc::vec![]);
1683        let s1: TiVec<Id, u32> = TiVec::from(alloc::vec![12]);
1684        let s2: TiVec<Id, u32> = TiVec::from(alloc::vec![23, 34]);
1685        assert_eq!(&serde_json::to_string(&s0).unwrap(), "[]");
1686        assert_eq!(&serde_json::to_string(&s1).unwrap(), "[12]");
1687        assert_eq!(&serde_json::to_string(&s2).unwrap(), "[23,34]");
1688    }
1689
1690    #[cfg(feature = "serde")]
1691    #[test]
1692    fn test_vec_deserialize() {
1693        let s0: TiVec<Id, u32> = serde_json::from_str("[]").unwrap();
1694        let s1: TiVec<Id, u32> = serde_json::from_str("[12]").unwrap();
1695        let s2: TiVec<Id, u32> = serde_json::from_str("[23, 34]").unwrap();
1696        assert_eq!(s0.as_slice().raw, [0; 0][..]);
1697        assert_eq!(s1.as_slice().raw, [12][..]);
1698        assert_eq!(s2.as_slice().raw, [23, 34][..]);
1699    }
1700
1701    #[cfg(feature = "bincode")]
1702    #[test]
1703    fn test_vec_encode() {
1704        let config = bincode::config::standard();
1705        let s0: TiVec<Id, u32> = TiVec::from(alloc::vec![]);
1706        let s1: TiVec<Id, u32> = TiVec::from(alloc::vec![12]);
1707        let s2: TiVec<Id, u32> = TiVec::from(alloc::vec![23, 34]);
1708        let s3: TiVec<Id, u32> = TiVec::from(alloc::vec![0x1234_5678, 0x2345_6789]);
1709        assert_eq!(&bincode::encode_to_vec(s0, config).unwrap(), &[0]);
1710        assert_eq!(&bincode::encode_to_vec(s1, config).unwrap(), &[1, 12]);
1711        assert_eq!(&bincode::encode_to_vec(s2, config).unwrap(), &[2, 23, 34]);
1712        assert_eq!(
1713            &bincode::encode_to_vec(s3, config).unwrap(),
1714            &[2, 252, 0x78, 0x56, 0x34, 0x12, 252, 0x89, 0x67, 0x45, 0x23]
1715        );
1716    }
1717
1718    #[cfg(feature = "bincode")]
1719    #[test]
1720    fn test_vec_decode() {
1721        fn decode_whole(bytes: &[u8]) -> TiVec<Id, u32> {
1722            let config = bincode::config::standard();
1723            let (decoded, len) = bincode::decode_from_slice(bytes, config).unwrap();
1724            assert_eq!(len, bytes.len());
1725            decoded
1726        }
1727
1728        let s0: TiVec<Id, u32> = decode_whole(&[0]);
1729        let s1: TiVec<Id, u32> = decode_whole(&[1, 12]);
1730        let s2: TiVec<Id, u32> = decode_whole(&[2, 23, 34]);
1731        let s3: TiVec<Id, u32> =
1732            decode_whole(&[2, 252, 0x78, 0x56, 0x34, 0x12, 252, 0x89, 0x67, 0x45, 0x23]);
1733        assert_eq!(s0.as_slice().raw, [0; 0][..]);
1734        assert_eq!(s1.as_slice().raw, [12][..]);
1735        assert_eq!(s2.as_slice().raw, [23, 34][..]);
1736        assert_eq!(s3.as_slice().raw, [0x1234_5678, 0x2345_6789][..]);
1737    }
1738
1739    #[cfg(feature = "bincode")]
1740    #[test]
1741    fn test_boxed_slice_borrow_decode() {
1742        fn decode_whole(bytes: &[u8]) -> TiVec<Id, &str> {
1743            let config = bincode::config::standard();
1744            let (decoded, len) = bincode::borrow_decode_from_slice(bytes, config).unwrap();
1745            assert_eq!(len, bytes.len());
1746            decoded
1747        }
1748
1749        let s0: TiVec<Id, &str> = decode_whole(&[0]);
1750        let s1: TiVec<Id, &str> = decode_whole(&[1, 1, b'a']);
1751        let s2: TiVec<Id, &str> = decode_whole(&[2, 2, b'b', b'c', 3, b'd', b'e', b'f']);
1752        assert_eq!(s0.as_slice().raw, [""; 0][..]);
1753        assert_eq!(s1.as_slice().raw, ["a"][..]);
1754        assert_eq!(s2.as_slice().raw, ["bc", "def"][..]);
1755    }
1756}
typed_index_collections/vec.rs

typed_index_collections/
vec.rs
