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    /// # Deprecation
790    ///
791    /// This method is deprecated due to incorrect `src` bounds.
792    /// Use [`extend_from_within_corrected`] instead, which accepts typed
793    /// index ranges.
794    /// See issue [#8] for more details.
795    ///
796    /// # Panics
797    ///
798    /// Panics if the starting point is greater than the end point or if
799    /// the end point is greater than the length of the vector.
800    ///
801    /// [`Vec::extend_from_within`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.extend_from_within
802    /// [`extend_from_within_corrected`]: #method.extend_from_within_corrected
803    /// [#8]: https://github.com/zheland/typed-index-collections/issues/8
804    #[inline]
805    #[deprecated(
806        since = "3.5.0",
807        note = "use `extend_from_within_corrected` instead, will be removed in 4.0.0"
808    )]
809    pub fn extend_from_within<R>(&mut self, src: R)
810    where
811        V: Clone,
812        R: RangeBounds<usize>,
813    {
814        self.raw.extend_from_within(src);
815    }
816
817    /// Copies elements from `src` range to the end of the vector.
818    ///
819    /// See [`Vec::extend_from_within`] for more details.
820    ///
821    /// This is a corrected version of the deprecated
822    /// [`Self::extend_from_within`] that accepts typed index bounds.
823    /// The deprecated method uses incorrect bounds.
824    ///
825    /// # Panics
826    ///
827    /// Panics if the starting point is greater than the end point or if
828    /// the end point is greater than the length of the vector.
829    ///
830    /// [`Vec::extend_from_within`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.extend_from_within
831    /// [`extend_from_within`]: #method.extend_from_within
832    #[inline]
833    pub fn extend_from_within_corrected<R>(&mut self, src: R)
834    where
835        V: Clone,
836        R: TiRangeBounds<K>,
837    {
838        self.raw.extend_from_within(src.into_range());
839    }
840
841    /// Removes consecutive repeated elements in the vector according to the
842    /// [`PartialEq`] trait implementation.
843    ///
844    /// See [`Vec::dedup`] for more details.
845    ///
846    /// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
847    /// [`Vec::dedup`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.dedup
848    #[inline]
849    pub fn dedup(&mut self)
850    where
851        V: PartialEq,
852    {
853        self.raw.dedup();
854    }
855
856    /// Creates a splicing iterator that replaces the specified range in the
857    /// vector with the given `replace_with` iterator and yields the removed
858    /// items. `replace_with` does not need to be the same length as
859    /// `range`.
860    ///
861    /// See [`Vec::splice`] for more details.
862    ///
863    /// [`Vec::splice`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.splice
864    #[inline]
865    pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter>
866    where
867        R: TiRangeBounds<K>,
868        I: IntoIterator<Item = V>,
869    {
870        self.raw.splice(range.into_range(), replace_with)
871    }
872
873    /// Converts the vector into iterator over all key-value pairs
874    /// with `K` used for iteration indices.
875    ///
876    /// It acts like `self.into_iter().enumerate()`,
877    /// but use `K` instead of `usize` for iteration indices.
878    ///
879    /// # Example
880    ///
881    /// ```
882    /// # use derive_more::{From, Into};
883    /// # use typed_index_collections::TiVec;
884    /// #[derive(Eq, Debug, From, Into, PartialEq)]
885    /// pub struct Id(usize);
886    /// let vec: TiVec<Id, usize> = vec![1, 2, 4].into();
887    /// let mut iterator = vec.into_iter_enumerated();
888    /// assert_eq!(iterator.next(), Some((Id(0), 1)));
889    /// assert_eq!(iterator.next(), Some((Id(1), 2)));
890    /// assert_eq!(iterator.next(), Some((Id(2), 4)));
891    /// assert_eq!(iterator.next(), None);
892    /// ```
893    #[inline]
894    pub fn into_iter_enumerated(self) -> TiEnumerated<vec::IntoIter<V>, K, V>
895    where
896        usize: Into<K>,
897    {
898        self.raw
899            .into_iter()
900            .enumerate()
901            .map(|(key, value)| (key.into(), value))
902    }
903}
904
905impl<K, V> fmt::Debug for TiVec<K, V>
906where
907    K: fmt::Debug,
908    V: fmt::Debug,
909    usize: Into<K>,
910{
911    #[allow(clippy::allow_attributes, reason = "rust-lang/rust#130021")]
912    #[allow(
913        clippy::missing_inline_in_public_items,
914        reason = "use default inlining behavior"
915    )]
916    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
917        f.debug_map().entries(self.iter_enumerated()).finish()
918    }
919}
920
921impl<K, V> AsRef<Self> for TiVec<K, V> {
922    #[inline]
923    fn as_ref(&self) -> &Self {
924        self
925    }
926}
927
928impl<K, V> AsMut<Self> for TiVec<K, V> {
929    #[inline]
930    fn as_mut(&mut self) -> &mut Self {
931        self
932    }
933}
934
935impl<K, V> AsRef<TiSlice<K, V>> for TiVec<K, V> {
936    #[inline]
937    fn as_ref(&self) -> &TiSlice<K, V> {
938        self
939    }
940}
941
942impl<K, V> AsMut<TiSlice<K, V>> for TiVec<K, V> {
943    #[inline]
944    fn as_mut(&mut self) -> &mut TiSlice<K, V> {
945        self
946    }
947}
948
949impl<K, V> AsRef<Vec<V>> for TiVec<K, V> {
950    #[inline]
951    fn as_ref(&self) -> &Vec<V> {
952        &self.raw
953    }
954}
955
956impl<K, V> AsMut<Vec<V>> for TiVec<K, V> {
957    #[inline]
958    fn as_mut(&mut self) -> &mut Vec<V> {
959        &mut self.raw
960    }
961}
962
963impl<K, V> AsRef<[V]> for TiVec<K, V> {
964    #[inline]
965    fn as_ref(&self) -> &[V] {
966        &self.raw
967    }
968}
969
970impl<K, V> AsMut<[V]> for TiVec<K, V> {
971    #[inline]
972    fn as_mut(&mut self) -> &mut [V] {
973        &mut self.raw
974    }
975}
976
977impl<K, V> AsRef<TiVec<K, V>> for Vec<V> {
978    #[inline]
979    fn as_ref(&self) -> &TiVec<K, V> {
980        TiVec::from_ref(self)
981    }
982}
983
984impl<K, V> AsMut<TiVec<K, V>> for Vec<V> {
985    #[inline]
986    fn as_mut(&mut self) -> &mut TiVec<K, V> {
987        TiVec::from_mut(self)
988    }
989}
990
991impl<K, V> Borrow<TiSlice<K, V>> for TiVec<K, V> {
992    #[inline]
993    fn borrow(&self) -> &TiSlice<K, V> {
994        self.as_slice()
995    }
996}
997
998impl<K, V> BorrowMut<TiSlice<K, V>> for TiVec<K, V> {
999    #[inline]
1000    fn borrow_mut(&mut self) -> &mut TiSlice<K, V> {
1001        self.as_mut_slice()
1002    }
1003}
1004
1005impl<K, V> Deref for TiVec<K, V> {
1006    type Target = TiSlice<K, V>;
1007
1008    #[inline]
1009    fn deref(&self) -> &TiSlice<K, V> {
1010        Self::Target::from_ref(&self.raw)
1011    }
1012}
1013
1014impl<K, V> DerefMut for TiVec<K, V> {
1015    #[inline]
1016    fn deref_mut(&mut self) -> &mut TiSlice<K, V> {
1017        Self::Target::from_mut(&mut self.raw)
1018    }
1019}
1020
1021impl<K, V> From<Vec<V>> for TiVec<K, V> {
1022    #[inline]
1023    fn from(vec: Vec<V>) -> Self {
1024        Self {
1025            raw: vec,
1026            _marker: PhantomData,
1027        }
1028    }
1029}
1030
1031impl<K, V> From<TiVec<K, V>> for Vec<V> {
1032    #[inline]
1033    fn from(vec: TiVec<K, V>) -> Self {
1034        vec.raw
1035    }
1036}
1037
1038impl<K, V> From<&TiSlice<K, V>> for TiVec<K, V>
1039where
1040    V: Clone,
1041{
1042    #[inline]
1043    fn from(slice: &TiSlice<K, V>) -> Self {
1044        slice.to_vec()
1045    }
1046}
1047
1048impl<K, V> From<&mut TiSlice<K, V>> for TiVec<K, V>
1049where
1050    V: Clone,
1051{
1052    #[inline]
1053    fn from(slice: &mut TiSlice<K, V>) -> Self {
1054        slice.to_vec()
1055    }
1056}
1057
1058impl<K, V> From<Cow<'_, TiSlice<K, V>>> for TiVec<K, V>
1059where
1060    V: Clone,
1061{
1062    #[inline]
1063    fn from(slice: Cow<'_, TiSlice<K, V>>) -> Self {
1064        slice.into_owned()
1065    }
1066}
1067
1068impl<K, V> From<TiVec<K, V>> for Cow<'_, TiSlice<K, V>>
1069where
1070    V: Clone,
1071{
1072    #[inline]
1073    fn from(vec: TiVec<K, V>) -> Self {
1074        Cow::Owned(vec)
1075    }
1076}
1077
1078impl<K> From<&str> for TiVec<K, u8> {
1079    #[inline]
1080    fn from(s: &str) -> Self {
1081        s.as_bytes().to_vec().into()
1082    }
1083}
1084
1085impl<K> From<String> for TiVec<K, u8> {
1086    #[inline]
1087    fn from(s: String) -> Self {
1088        s.into_bytes().into()
1089    }
1090}
1091
1092impl<K> From<CString> for TiVec<K, u8> {
1093    #[inline]
1094    fn from(s: CString) -> Self {
1095        s.into_bytes().into()
1096    }
1097}
1098
1099impl<K, V> Clone for TiVec<K, V>
1100where
1101    V: Clone,
1102{
1103    #[inline]
1104    fn clone(&self) -> Self {
1105        self.raw.clone().into()
1106    }
1107}
1108
1109impl<K, V> Eq for TiVec<K, V> where V: Eq {}
1110
1111impl<K, A, B> PartialEq<TiVec<K, B>> for TiVec<K, A>
1112where
1113    A: PartialEq<B>,
1114{
1115    #[inline]
1116    fn eq(&self, other: &TiVec<K, B>) -> bool {
1117        self.raw == other.raw
1118    }
1119}
1120
1121impl<K, A, B> PartialEq<TiSlice<K, B>> for TiVec<K, A>
1122where
1123    A: PartialEq<B>,
1124{
1125    #[inline]
1126    fn eq(&self, other: &TiSlice<K, B>) -> bool {
1127        *self.raw == other.raw
1128    }
1129}
1130
1131impl<K, A, B> PartialEq<TiVec<K, B>> for TiSlice<K, A>
1132where
1133    A: PartialEq<B>,
1134{
1135    #[inline]
1136    fn eq(&self, other: &TiVec<K, B>) -> bool {
1137        self.raw == *other.raw
1138    }
1139}
1140
1141impl<'a, K, A, B> PartialEq<&'a TiSlice<K, B>> for TiVec<K, A>
1142where
1143    A: PartialEq<B>,
1144{
1145    #[inline]
1146    fn eq(&self, other: &&'a TiSlice<K, B>) -> bool {
1147        *self.raw == other.raw
1148    }
1149}
1150
1151impl<K, A, B> PartialEq<TiVec<K, B>> for &TiSlice<K, A>
1152where
1153    A: PartialEq<B>,
1154{
1155    #[inline]
1156    fn eq(&self, other: &TiVec<K, B>) -> bool {
1157        self.raw == *other.raw
1158    }
1159}
1160
1161impl<'a, K, A, B> PartialEq<&'a mut TiSlice<K, B>> for TiVec<K, A>
1162where
1163    A: PartialEq<B>,
1164{
1165    #[inline]
1166    fn eq(&self, other: &&'a mut TiSlice<K, B>) -> bool {
1167        *self.raw == other.raw
1168    }
1169}
1170
1171impl<K, A, B> PartialEq<TiVec<K, B>> for &mut TiSlice<K, A>
1172where
1173    A: PartialEq<B>,
1174{
1175    #[inline]
1176    fn eq(&self, other: &TiVec<K, B>) -> bool {
1177        self.raw == *other.raw
1178    }
1179}
1180
1181impl<K, V> Ord for TiVec<K, V>
1182where
1183    V: Ord,
1184{
1185    #[inline]
1186    fn cmp(&self, other: &Self) -> Ordering {
1187        self.raw.cmp(&other.raw)
1188    }
1189}
1190
1191impl<K, V> PartialOrd<Self> for TiVec<K, V>
1192where
1193    V: PartialOrd<V>,
1194{
1195    #[inline]
1196    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1197        self.raw.partial_cmp(&other.raw)
1198    }
1199}
1200
1201impl<K, V> Hash for TiVec<K, V>
1202where
1203    V: Hash,
1204{
1205    #[inline]
1206    fn hash<H: Hasher>(&self, state: &mut H) {
1207        self.raw.hash(state);
1208    }
1209}
1210
1211impl<K, V> Default for TiVec<K, V> {
1212    #[inline]
1213    fn default() -> Self {
1214        Vec::default().into()
1215    }
1216}
1217
1218impl<I, K, V> Index<I> for TiVec<K, V>
1219where
1220    I: TiSliceIndex<K, V>,
1221{
1222    type Output = I::Output;
1223
1224    #[inline]
1225    fn index(&self, index: I) -> &Self::Output {
1226        index.index(self)
1227    }
1228}
1229
1230impl<I, K, V> IndexMut<I> for TiVec<K, V>
1231where
1232    I: TiSliceIndex<K, V>,
1233{
1234    #[inline]
1235    fn index_mut(&mut self, index: I) -> &mut Self::Output {
1236        index.index_mut(self)
1237    }
1238}
1239
1240impl<K, V> Extend<V> for TiVec<K, V> {
1241    #[inline]
1242    fn extend<I: IntoIterator<Item = V>>(&mut self, iter: I) {
1243        self.raw.extend(iter);
1244    }
1245}
1246
1247impl<'a, K, V: 'a + Copy> Extend<&'a V> for TiVec<K, V> {
1248    #[inline]
1249    fn extend<I: IntoIterator<Item = &'a V>>(&mut self, iter: I) {
1250        self.raw.extend(iter);
1251    }
1252}
1253
1254impl<K, V> FromIterator<V> for TiVec<K, V> {
1255    #[inline]
1256    fn from_iter<I: IntoIterator<Item = V>>(iter: I) -> Self {
1257        Self {
1258            raw: Vec::from_iter(iter),
1259            _marker: PhantomData,
1260        }
1261    }
1262}
1263
1264impl<K, V> IntoIterator for TiVec<K, V> {
1265    type Item = V;
1266    type IntoIter = vec::IntoIter<V>;
1267
1268    #[inline]
1269    fn into_iter(self) -> vec::IntoIter<V> {
1270        self.raw.into_iter()
1271    }
1272}
1273
1274impl<'a, K, V> IntoIterator for &'a TiVec<K, V> {
1275    type Item = &'a V;
1276    type IntoIter = slice::Iter<'a, V>;
1277
1278    #[inline]
1279    fn into_iter(self) -> slice::Iter<'a, V> {
1280        self.raw.iter()
1281    }
1282}
1283
1284impl<'a, K, V> IntoIterator for &'a mut TiVec<K, V> {
1285    type Item = &'a mut V;
1286    type IntoIter = slice::IterMut<'a, V>;
1287
1288    #[inline]
1289    fn into_iter(self) -> slice::IterMut<'a, V> {
1290        self.raw.iter_mut()
1291    }
1292}
1293
1294/// Write is implemented for `Vec<u8>` by appending to the vector.
1295/// The vector will grow as needed.
1296#[cfg(feature = "std")]
1297#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
1298impl<K> Write for TiVec<K, u8> {
1299    #[inline]
1300    fn write(&mut self, buf: &[u8]) -> IoResult<usize> {
1301        self.raw.write(buf)
1302    }
1303
1304    #[inline]
1305    fn write_vectored(&mut self, bufs: &[IoSlice<'_>]) -> IoResult<usize> {
1306        self.raw.write_vectored(bufs)
1307    }
1308
1309    #[inline]
1310    fn write_all(&mut self, buf: &[u8]) -> IoResult<()> {
1311        self.raw.write_all(buf)
1312    }
1313
1314    #[inline]
1315    fn flush(&mut self) -> IoResult<()> {
1316        self.raw.flush()
1317    }
1318}
1319
1320#[cfg(feature = "serde")]
1321#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
1322impl<K, V> Serialize for TiVec<K, V>
1323where
1324    V: Serialize,
1325{
1326    #[inline]
1327    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1328    where
1329        S: Serializer,
1330    {
1331        self.raw.as_slice().serialize(serializer)
1332    }
1333}
1334
1335#[cfg(feature = "serde")]
1336#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
1337impl<'de, K, V> Deserialize<'de> for TiVec<K, V>
1338where
1339    V: Deserialize<'de>,
1340{
1341    #[inline]
1342    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
1343    where
1344        D: Deserializer<'de>,
1345    {
1346        Vec::deserialize(deserializer).map(Into::into)
1347    }
1348}
1349
1350#[cfg(feature = "bincode")]
1351#[cfg_attr(docsrs, doc(cfg(feature = "bincode")))]
1352impl<K, V> Encode for TiVec<K, V>
1353where
1354    V: Encode,
1355{
1356    #[inline]
1357    fn encode<E>(&self, encoder: &mut E) -> Result<(), EncodeError>
1358    where
1359        E: Encoder,
1360    {
1361        self.raw.encode(encoder)
1362    }
1363}
1364
1365#[cfg(feature = "bincode")]
1366#[cfg_attr(docsrs, doc(cfg(feature = "bincode")))]
1367impl<K, V, Context> Decode<Context> for TiVec<K, V>
1368where
1369    V: Decode<Context>,
1370{
1371    #[inline]
1372    fn decode<D>(decoder: &mut D) -> Result<Self, DecodeError>
1373    where
1374        D: Decoder<Context = Context>,
1375    {
1376        Vec::decode(decoder).map(Into::into)
1377    }
1378}
1379
1380#[cfg(feature = "bincode")]
1381#[cfg_attr(docsrs, doc(cfg(feature = "bincode")))]
1382impl<'de, K, V, Context> BorrowDecode<'de, Context> for TiVec<K, V>
1383where
1384    V: BorrowDecode<'de, Context>,
1385{
1386    #[inline]
1387    fn borrow_decode<D>(decoder: &mut D) -> Result<Self, DecodeError>
1388    where
1389        D: BorrowDecoder<'de, Context = Context>,
1390    {
1391        Vec::borrow_decode(decoder).map(Into::into)
1392    }
1393}
1394
1395#[expect(
1396    dead_code,
1397    unused_imports,
1398    unused_mut,
1399    clippy::into_iter_on_ref,
1400    clippy::op_ref,
1401    clippy::too_many_lines,
1402    clippy::undocumented_unsafe_blocks,
1403    clippy::unwrap_used,
1404    reason = "okay in tests"
1405)]
1406#[cfg(test)]
1407mod test {
1408    use alloc::borrow::{Cow, ToOwned};
1409    use alloc::boxed::Box;
1410    use alloc::ffi::CString;
1411    use alloc::string::ToString;
1412    use alloc::vec::Vec;
1413    use core::borrow::{Borrow, BorrowMut};
1414    use core::hash::{Hash, Hasher};
1415    use core::ops::Bound;
1416    #[cfg(feature = "std")]
1417    use std::hash::DefaultHasher;
1418    #[cfg(feature = "std")]
1419    use std::io::{IoSlice, Write};
1420
1421    use crate::test_util::{AsSliceAndCapacity, Id};
1422    use crate::{TiSlice, TiVec};
1423
1424    #[test]
1425    fn test_vec_read_api_compatibility() {
1426        assert_eq!(
1427            TiVec::<Id, u32>::new().as_slice_and_capacity(),
1428            Vec::<u32>::new().as_slice_and_capacity(),
1429        );
1430        for c in [0, 1, 2, 4] {
1431            assert_eq!(
1432                TiVec::<Id, u32>::with_capacity(c).as_slice_and_capacity(),
1433                Vec::<u32>::with_capacity(c).as_slice_and_capacity(),
1434            );
1435        }
1436
1437        for v in [
1438            &[0_u32; 0][..],
1439            &[1],
1440            &[1, 1234],
1441            &[1, 2, 4],
1442            &[1, 5, 3, 2],
1443            &[1, 1, 9, 2, 4, 1, 12345, 12],
1444        ] {
1445            let cv = (v.to_vec(), TiVec::<Id, _>::from(v.to_vec()));
1446            let mut cv = (&cv.0, &cv.1);
1447
1448            let mut mv = (v.to_vec(), TiVec::<Id, _>::from(v.to_vec()));
1449            let mut mv = (&mut mv.0, &mut mv.1);
1450
1451            assert_eq_api!(cv, v => AsRef::<[_]>::as_ref(v));
1452            assert_eq_api!(mv, v => AsMut::<[_]>::as_mut(v));
1453            assert_eq_api!(cv, v => AsRef::<Vec<_>>::as_ref(v));
1454            assert_eq_api!(mv, v => AsMut::<Vec<_>>::as_mut(v));
1455            assert_eq_api!(cv, v => AsRef::<TiVec<_, _>>::as_ref(v));
1456            assert_eq_api!(mv, v => AsMut::<TiVec<_, _>>::as_mut(v));
1457            assert_eq!(
1458                AsRef::<[_]>::as_ref(cv.0),
1459                AsRef::<[_]>::as_ref(AsRef::<TiSlice<_, _>>::as_ref(cv.1))
1460            );
1461            assert_eq!(
1462                AsMut::<[_]>::as_mut(mv.0),
1463                AsMut::<[_]>::as_mut(AsMut::<TiSlice<_, _>>::as_mut(mv.1))
1464            );
1465            assert_eq!(
1466                Borrow::<[_]>::borrow(cv.0),
1467                AsRef::<[_]>::as_ref(Borrow::<TiSlice<_, _>>::borrow(cv.1))
1468            );
1469            assert_eq!(
1470                BorrowMut::<[_]>::borrow_mut(mv.0),
1471                AsMut::<[_]>::as_mut(BorrowMut::<TiSlice<_, _>>::borrow_mut(mv.1))
1472            );
1473
1474            assert_eq_api!(cv, v => v.len());
1475            assert_eq_api!(cv, v => v.is_empty());
1476            assert_eq_api!(cv, v => v.capacity());
1477            assert_eq_api!(cv, v => v.as_slice().into_std());
1478            assert_eq_api!(mv, v => v.as_mut_slice().into_std());
1479            assert_eq_api!(cv, v => TheVec::from(v.as_slice()).into_std());
1480            assert_eq_api!(mv, v => TheVec::from(v.as_mut_slice()).into_std());
1481            assert_eq_api!(cv, v => TheVec::from(Cow::Borrowed(v.as_slice())).into_std());
1482            assert_eq_api!(mv, v => Cow::from(v.clone()).into_std());
1483
1484            if !v.is_empty() {
1485                assert_ne!(cv.0.as_ptr(), cv.1.as_ptr());
1486                assert_ne!(cv.0.as_ptr_range(), cv.1.as_ptr_range());
1487                assert_ne!(mv.0.as_mut_ptr(), mv.1.as_mut_ptr());
1488                assert_ne!(mv.0.as_mut_ptr_range(), mv.1.as_mut_ptr_range());
1489            }
1490
1491            assert_eq_api!(cv, v => *v == TheVec::<u32>::default());
1492            assert_eq_api!(cv, v => v == v.as_slice());
1493            assert_eq_api!(cv, v => v.as_slice() == v);
1494            assert_eq_api!(cv, v => v == &v.as_slice());
1495            assert_eq_api!(cv, v => &v.as_slice() == v);
1496            assert_eq_api!(mv, v => v == &(&mut [1_u32, 1234][..]).into_tic());
1497            assert_eq_api!(mv, v => &(&mut [1_u32, 1234][..]).into_tic() == v);
1498            assert_eq_api!(cv, v => v.cmp(&alloc::vec![1, 1234].into_tic()));
1499            assert_eq_api!(cv, v => v.partial_cmp(&alloc::vec![1, 1234].into_tic()));
1500
1501            for i in 0..v.len() {
1502                assert_eq_api!(cv, v => v[i.into_tic()]);
1503                assert_eq_api!(mv, v => v[i.into_tic()] = v[i.into_tic()]);
1504            }
1505
1506            unsafe {
1507                assert_eq_api!(cv, v => {
1508                    let mut v = core::mem::ManuallyDrop::new(v.clone());
1509                    TheVec::from_raw_parts(v.as_mut_ptr(), v.len(), v.capacity()).into_std()
1510                });
1511            }
1512        }
1513    }
1514
1515    #[test]
1516    fn test_vec_write_api_compatibility() {
1517        for v in [
1518            &[0_u32; 0][..],
1519            &[1],
1520            &[1, 1234],
1521            &[1, 2, 4],
1522            &[1, 5, 3, 2],
1523            &[1, 1, 9, 2, 4, 1, 12345, 12],
1524        ] {
1525            let mut mv = (v.to_vec(), TiVec::<Id, _>::from(v.to_vec()));
1526            let mut mv = (&mut mv.0, &mut mv.1);
1527
1528            let restore = |mv: &mut (&mut Vec<u32>, &mut TiVec<Id, u32>)| {
1529                *mv.0 = v.to_vec();
1530                *mv.1 = TiVec::from(v.to_vec());
1531            };
1532
1533            restore(&mut mv);
1534            assert_eq_api!(mv, v => v.try_reserve(usize::MAX));
1535            restore(&mut mv);
1536            assert_eq_api!(mv, v => v.try_reserve_exact(usize::MAX));
1537
1538            for i in 0..8 {
1539                restore(&mut mv);
1540                assert_eq_api!(mv, v => v.resize(i, 123));
1541                restore(&mut mv);
1542                assert_eq_api!(mv, v => { let mut a = 1; v.resize_with(i, || { a *= 2; a }) });
1543                restore(&mut mv);
1544                assert_eq_api!(mv, v => v.reserve(i));
1545                assert_eq_api!(mv, v => v.spare_capacity_mut().len());
1546                restore(&mut mv);
1547                assert_eq_api!(mv, v => v.try_reserve(i));
1548                restore(&mut mv);
1549                assert_eq_api!(mv, v => v.reserve_exact(i));
1550                restore(&mut mv);
1551                assert_eq_api!(mv, v => v.try_reserve_exact(i));
1552                restore(&mut mv);
1553                assert_eq_api!(mv, v => v.reserve_exact(i));
1554                assert_eq_api!(mv, v => v.shrink_to_fit());
1555                restore(&mut mv);
1556                assert_eq_api!(mv, v => v.reserve_exact(i * 2));
1557                assert_eq_api!(mv, v => v.shrink_to(i));
1558                restore(&mut mv);
1559                assert_eq_api!(mv, v => v.truncate(i));
1560            }
1561
1562            let l1: Vec<_> = mv.0.clone();
1563            let l1c = l1.capacity();
1564            let l1 = l1.leak();
1565            let l2: TiVec<_, _> = mv.1.clone();
1566            let l2c = l2.capacity();
1567            let l2 = l2.leak();
1568            assert_eq!(l1, &l2.raw);
1569            drop(unsafe { Vec::from_raw_parts(l1.as_mut_ptr(), l1.len(), l1c) });
1570            drop(unsafe { TiVec::<Id, _>::from_raw_parts(l2.as_mut_ptr(), l2.len(), l2c) });
1571
1572            restore(&mut mv);
1573            assert_eq_api!(mv, v => (&*v).into_iter().copied().collect::<Vec<_>>());
1574            assert_eq_api!(mv, v => v.iter_mut().collect::<Vec<_>>());
1575            assert_eq_api!(mv, v => v.clone().into_iter().collect::<Vec<_>>());
1576
1577            restore(&mut mv);
1578            assert_eq_api!(mv, v => v.pop());
1579            assert_eq_api!(mv, v => v.push(123));
1580            assert_eq_api!(mv, v => v.pop());
1581
1582            restore(&mut mv);
1583            assert_eq_api!(mv, v => v.pop_if(|v| *v < 10));
1584            assert_eq_api!(mv, v => v.push(234));
1585
1586            restore(&mut mv);
1587            assert_eq_api!(mv, v => v.append(&mut v.clone()));
1588            restore(&mut mv);
1589            assert_eq_api!(mv, v => v.extend(v.clone().as_slice()));
1590            restore(&mut mv);
1591            assert_eq_api!(mv, v => v.extend(v.clone().iter().copied()));
1592            restore(&mut mv);
1593            assert_eq_api!(mv, v => v.extend_from_slice(&v.clone()));
1594            restore(&mut mv);
1595            assert_eq_api!(mv, v => v.into_iter().collect::<TheVec<_>>().into_std());
1596
1597            restore(&mut mv);
1598            assert_eq_api!(mv, v => v.retain(|value| value % 3 == 0 || value % 4 == 0));
1599
1600            restore(&mut mv);
1601            assert_eq_api!(mv, v => v.retain_mut(|value| {
1602                *value += 1;
1603                *value % 3 == 0 || *value % 4 == 0
1604            }));
1605
1606            restore(&mut mv);
1607            assert_eq_api!(mv, v => v.dedup());
1608
1609            restore(&mut mv);
1610            assert_eq_api!(mv, v => v.dedup_by(|lhs, rhs| lhs < rhs));
1611
1612            restore(&mut mv);
1613            assert_eq_api!(mv, v => v.dedup_by_key(|value| *value % 3));
1614
1615            for i in 0..v.len() {
1616                restore(&mut mv);
1617                assert_eq_api!(mv, v => v.swap_remove(i.into_tic()));
1618                restore(&mut mv);
1619                assert_eq_api!(mv, v => v.insert(i.into_tic(), 123));
1620                restore(&mut mv);
1621                assert_eq_api!(mv, v => v.remove(i.into_tic()));
1622                restore(&mut mv);
1623                unsafe { assert_eq_api!(mv, v => v.set_len(i)) };
1624                restore(&mut mv);
1625                assert_eq_api!(mv, v => v.split_off(i.into_tic()).into_std());
1626            }
1627
1628            for a in 0..v.len() {
1629                for b in a..v.len() {
1630                    restore(&mut mv);
1631                    assert_eq_api!(mv, v => v.drain((a..b).into_tic()).collect::<Vec<_>>());
1632                    restore(&mut mv);
1633                    #[expect(deprecated, reason = "okay in tests")]
1634                    {
1635                        assert_eq_api!(mv, v => v.extend_from_within(a..b));
1636                    }
1637                    restore(&mut mv);
1638                    {
1639                        mv.0.extend_from_within(a..b);
1640                        mv.1.extend_from_within_corrected(Id(a)..Id(b));
1641                        assert_eq!(mv.0.as_slice(), mv.1.raw.as_slice());
1642                        assert_eq!(mv.0.capacity(), mv.1.capacity());
1643                    }
1644                    restore(&mut mv);
1645                    assert_eq_api!(
1646                        mv, v => v.splice((a..b).into_tic(), [1, 2, 3]).collect::<Vec<_>>()
1647                    );
1648                }
1649            }
1650            restore(&mut mv);
1651            assert_eq_api!(mv, v => v.splice(.., [1, 2, 3]).collect::<Vec<_>>());
1652
1653            restore(&mut mv);
1654            assert_eq_api!(mv, v => v.clear());
1655        }
1656    }
1657
1658    #[cfg(feature = "std")]
1659    #[test]
1660    fn test_vec_hash_compatibility() {
1661        for v in [
1662            &[0_u32; 0][..],
1663            &[1],
1664            &[1, 1234],
1665            &[1, 2, 4],
1666            &[1, 5, 3, 2],
1667            &[1, 1, 9, 2, 4, 1, 12345, 12],
1668        ] {
1669            let cv = (v.to_vec(), TiVec::<Id, _>::from(v.to_vec()));
1670            let mut cv = (&cv.0, &cv.1);
1671            assert_eq_api!(cv, v => {
1672                let mut hasher = DefaultHasher::new();
1673                v.hash(&mut hasher);
1674                hasher.finish()
1675            });
1676        }
1677    }
1678
1679    #[test]
1680    fn test_u8_vec_api_compatibility() {
1681        assert_eq!(
1682            Vec::from(TiVec::<Id, u8>::from("abc")),
1683            Vec::<u8>::from("abc"),
1684        );
1685        assert_eq!(
1686            Vec::from(TiVec::<Id, u8>::from("abc".to_owned())),
1687            Vec::<u8>::from("abc".to_owned()),
1688        );
1689        assert_eq!(
1690            Vec::from(TiVec::<Id, u8>::from(CString::new("abc").unwrap())),
1691            Vec::<u8>::from(CString::new("abc").unwrap()),
1692        );
1693
1694        for v in [&b"abc"[..], b"aBc", b"ABC", b"abd", b"a\x80\x81b"] {
1695            let cv = (v.to_vec(), TiVec::<Id, _>::from(v.to_vec()));
1696            let mut cv = (&cv.0, &cv.1);
1697
1698            assert_eq_api!(cv, v => TheVec::from(v.as_slice()).into_std());
1699        }
1700    }
1701
1702    #[test]
1703    fn test_vec_debug() {
1704        let s0: TiVec<Id, u32> = TiVec::from(alloc::vec![]);
1705        let s1: TiVec<Id, u32> = TiVec::from(alloc::vec![12]);
1706        let s2: TiVec<Id, u32> = TiVec::from(alloc::vec![23, 34]);
1707        assert_eq!(&alloc::format!("{s0:?}"), "{}");
1708        assert_eq!(&alloc::format!("{s1:?}"), "{Id(0): 12}");
1709        assert_eq!(&alloc::format!("{s2:?}"), "{Id(0): 23, Id(1): 34}");
1710    }
1711
1712    #[cfg(feature = "std")]
1713    #[test]
1714    fn test_vec_write() {
1715        let mut mv = (Vec::<u8>::new(), TiVec::<Id, u8>::new());
1716        let mut mv = (&mut mv.0, &mut mv.1);
1717
1718        assert_eq_api!(mv, v => v.write(&[1, 2, 3]).unwrap());
1719        assert_eq_api!(mv, v => v.write_vectored(
1720            &[IoSlice::new(&[1, 2, 3]), IoSlice::new(&[4, 5])]
1721        ).unwrap());
1722        assert_eq_api!(mv, v => v.write_all(&[1, 2, 3]).unwrap());
1723        assert_eq_api!(mv, v => v.flush().unwrap());
1724    }
1725
1726    #[cfg(feature = "serde")]
1727    #[test]
1728    fn test_vec_serialize() {
1729        let s0: TiVec<Id, u32> = TiVec::from(alloc::vec![]);
1730        let s1: TiVec<Id, u32> = TiVec::from(alloc::vec![12]);
1731        let s2: TiVec<Id, u32> = TiVec::from(alloc::vec![23, 34]);
1732        assert_eq!(&serde_json::to_string(&s0).unwrap(), "[]");
1733        assert_eq!(&serde_json::to_string(&s1).unwrap(), "[12]");
1734        assert_eq!(&serde_json::to_string(&s2).unwrap(), "[23,34]");
1735    }
1736
1737    #[cfg(feature = "serde")]
1738    #[test]
1739    fn test_vec_deserialize() {
1740        let s0: TiVec<Id, u32> = serde_json::from_str("[]").unwrap();
1741        let s1: TiVec<Id, u32> = serde_json::from_str("[12]").unwrap();
1742        let s2: TiVec<Id, u32> = serde_json::from_str("[23, 34]").unwrap();
1743        assert_eq!(s0.as_slice().raw, [0; 0][..]);
1744        assert_eq!(s1.as_slice().raw, [12][..]);
1745        assert_eq!(s2.as_slice().raw, [23, 34][..]);
1746    }
1747
1748    #[cfg(feature = "bincode")]
1749    #[test]
1750    fn test_vec_encode() {
1751        let config = bincode::config::standard();
1752        let s0: TiVec<Id, u32> = TiVec::from(alloc::vec![]);
1753        let s1: TiVec<Id, u32> = TiVec::from(alloc::vec![12]);
1754        let s2: TiVec<Id, u32> = TiVec::from(alloc::vec![23, 34]);
1755        let s3: TiVec<Id, u32> = TiVec::from(alloc::vec![0x1234_5678, 0x2345_6789]);
1756        assert_eq!(&bincode::encode_to_vec(s0, config).unwrap(), &[0]);
1757        assert_eq!(&bincode::encode_to_vec(s1, config).unwrap(), &[1, 12]);
1758        assert_eq!(&bincode::encode_to_vec(s2, config).unwrap(), &[2, 23, 34]);
1759        assert_eq!(
1760            &bincode::encode_to_vec(s3, config).unwrap(),
1761            &[2, 252, 0x78, 0x56, 0x34, 0x12, 252, 0x89, 0x67, 0x45, 0x23]
1762        );
1763    }
1764
1765    #[cfg(feature = "bincode")]
1766    #[test]
1767    fn test_vec_decode() {
1768        fn decode_whole(bytes: &[u8]) -> TiVec<Id, u32> {
1769            let config = bincode::config::standard();
1770            let (decoded, len) = bincode::decode_from_slice(bytes, config).unwrap();
1771            assert_eq!(len, bytes.len());
1772            decoded
1773        }
1774
1775        let s0: TiVec<Id, u32> = decode_whole(&[0]);
1776        let s1: TiVec<Id, u32> = decode_whole(&[1, 12]);
1777        let s2: TiVec<Id, u32> = decode_whole(&[2, 23, 34]);
1778        let s3: TiVec<Id, u32> =
1779            decode_whole(&[2, 252, 0x78, 0x56, 0x34, 0x12, 252, 0x89, 0x67, 0x45, 0x23]);
1780        assert_eq!(s0.as_slice().raw, [0; 0][..]);
1781        assert_eq!(s1.as_slice().raw, [12][..]);
1782        assert_eq!(s2.as_slice().raw, [23, 34][..]);
1783        assert_eq!(s3.as_slice().raw, [0x1234_5678, 0x2345_6789][..]);
1784    }
1785
1786    #[cfg(feature = "bincode")]
1787    #[test]
1788    fn test_boxed_slice_borrow_decode() {
1789        fn decode_whole(bytes: &[u8]) -> TiVec<Id, &str> {
1790            let config = bincode::config::standard();
1791            let (decoded, len) = bincode::borrow_decode_from_slice(bytes, config).unwrap();
1792            assert_eq!(len, bytes.len());
1793            decoded
1794        }
1795
1796        let s0: TiVec<Id, &str> = decode_whole(&[0]);
1797        let s1: TiVec<Id, &str> = decode_whole(&[1, 1, b'a']);
1798        let s2: TiVec<Id, &str> = decode_whole(&[2, 2, b'b', b'c', 3, b'd', b'e', b'f']);
1799        assert_eq!(s0.as_slice().raw, [""; 0][..]);
1800        assert_eq!(s1.as_slice().raw, ["a"][..]);
1801        assert_eq!(s2.as_slice().raw, ["bc", "def"][..]);
1802    }
1803}
typed_index_collections/vec.rs

typed_index_collections/
vec.rs
