use core::{
    borrow::{Borrow, BorrowMut},
    cmp::Ordering,
    fmt,
    hash::{Hash, Hasher},
    iter::FromIterator,
    marker::PhantomData,
    ops, slice,
};

use alloc::{
    boxed::Box,
    vec::{self, Drain, Splice, Vec},
};

#[cfg(feature = "serde")]
use serde::ser::{Serialize, Serializer};

#[cfg(any(feature = "serde-alloc", feature = "serde-std"))]
use serde::de::{Deserialize, Deserializer};

use crate::{TiEnumerated, TiRangeBounds, TiSlice};

/// A contiguous growable array type
/// that only accepts keys of the type `K`.
///
/// `TiVec<K, V>` is a wrapper around Rust container type [`std::vec::Vec`].
/// The struct mirrors the stable API of Rust [`std::vec::Vec`]
/// and forwards to it as much as possible.
///
/// `TiVec<K, V>` uses `K` instead of `usize` for element indices and
/// require the index to implement
/// [`From<usize>`][`From`] and [`Into<usize>`][`Into`] traits.
/// Their implementation can be easily done
/// with [`derive_more`] crate and `#[derive(From, Into)]`.
///
/// `TiVec<K, V>` can be converted to [`std::vec::Vec<V>`][`std::vec::Vec`] and back
/// using [`From`] and [`Into`].
///
/// There are also zero-cost conversions available between references:
/// - [`&std::vec::Vec<V>`][`std::vec::Vec`] and `&TiVec<K, V>` with [`AsRef`],
/// - [`&mut std::vec::Vec<V>`][`std::vec::Vec`] and `&mut TiVec<K, V>` with [`AsMut`],
///
/// Added methods:
/// - [`from_ref`] - Converts a [`&std::vec::Vec<V>`][`std::vec::Vec`]
///   into a `&TiVec<K, V>`.
/// - [`from_mut`] - Converts a [`&mut std::vec::Vec<V>`][`std::vec::Vec`]
///   into a `&mut TiVec<K, V>`.
/// - [`push_and_get_key`] - Appends an element to the back of a collection
///   and returns its index of type `K`.
/// - [`pop_key_value`] - Removes the last element from a vector and returns it
///   with its index of type `K`, or [`None`] if the vector is empty.
/// - [`drain_enumerated`] - Creates a draining iterator that removes the specified
///   range in the vector and yields the current count and the removed items.
///   It acts like `self.drain(range).enumerate()`,
///   but instead of `usize` it returns index of type `K`.
/// - [`into_iter_enumerated`] - Converts the vector into iterator over all key-value pairs
///   with `K` used for iteration indices.
///   It acts like `self.into_iter().enumerate()`,
///   but use `K` instead of `usize` for iteration indices.
///
/// # Example
///
/// ```
/// use typed_index_collections::TiVec;
/// use derive_more::{From, Into};
///
/// #[derive(From, Into)]
/// struct FooId(usize);
///
/// let mut foos: TiVec<FooId, usize> = std::vec![10, 11, 13].into();
/// foos.insert(FooId(2), 12);
/// assert_eq!(foos[FooId(2)], 12);
/// ```
///
/// [`from_ref`]: #method.from_ref
/// [`from_mut`]: #method.from_mut
/// [`push_and_get_key`]: #method.push_and_get_key
/// [`pop_key_value`]: #method.pop_key_value
/// [`drain_enumerated`]: #method.drain_enumerated
/// [`into_iter_enumerated`]: #method.into_iter_enumerated
/// [`std::vec::Vec`]: https://doc.rust-lang.org/std/vec/struct.Vec.html
/// [`From`]: https://doc.rust-lang.org/std/convert/trait.From.html
/// [`Into`]: https://doc.rust-lang.org/std/convert/trait.Into.html
/// [`AsRef`]: https://doc.rust-lang.org/std/convert/trait.AsRef.html
/// [`AsMut`]: https://doc.rust-lang.org/std/convert/trait.AsMut.html
/// [`derive_more`]: https://crates.io/crates/derive_more
#[repr(transparent)]
pub struct TiVec<K, V> {
    /// Raw slice property
    pub raw: Vec<V>,

    /// Tied slice index type
    ///
    /// `fn(T) -> T` is *[PhantomData pattern][phantomdata patterns]*
    /// used to relax auto trait implementations bounds for
    /// [`Send`], [`Sync`], [`Unpin`], [`UnwindSafe`] and [`RefUnwindSafe`].
    ///
    /// Derive attribute is not used for trait implementations because it also requires
    /// the same trait implemented for K that is an unnecessary requirement.
    ///
    /// [phantomdata patterns]: https://doc.rust-lang.org/nomicon/phantom-data.html#table-of-phantomdata-patterns
    /// [`Send`]: https://doc.rust-lang.org/core/marker/trait.Send.html
    /// [`Sync`]: https://doc.rust-lang.org/core/marker/trait.Sync.html
    /// [`Unpin`]: https://doc.rust-lang.org/core/marker/trait.Unpin.html
    /// [`UnwindSafe`]: https://doc.rust-lang.org/core/std/panic/trait.UnwindSafe.html
    /// [`RefUnwindSafe`]: https://doc.rust-lang.org/core/std/panic/trait.RefUnwindSafe.html
    _marker: PhantomData<fn(K) -> K>,
}

impl<K, V> TiVec<K, V> {
    /// Constructs a new, empty `TiVec<K, V>`.
    ///
    /// See [`Vec::new`] for more details.
    ///
    /// [`Vec::new`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.new
    #[inline]
    pub fn new() -> Self {
        Self {
            raw: Vec::new(),
            _marker: PhantomData,
        }
    }

    /// Constructs a new, empty `TiVec<K, V>` with the specified capacity.
    ///
    /// See [`Vec::with_capacity`] for more details.
    ///
    /// [`Vec::with_capacity`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.with_capacity
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            raw: Vec::with_capacity(capacity),
            _marker: PhantomData,
        }
    }

    /// Creates a `TiVec<K, V>` directly from the raw components of another vector.
    ///
    /// See [`Vec::from_raw_parts`] for more details.
    ///
    /// [`Vec::from_raw_parts`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.from_raw_parts
    #[allow(clippy::missing_safety_doc)]
    pub unsafe fn from_raw_parts(ptr: *mut V, length: usize, capacity: usize) -> Self {
        Self {
            raw: Vec::from_raw_parts(ptr, length, capacity),
            _marker: PhantomData,
        }
    }

    /// Converts a [`&std::vec::Vec<V>`] into a `&TiVec<K, V>`.
    ///
    /// Vector reference is intentionally used in the argument
    /// instead of slice reference for conversion with no-op.
    ///
    /// # Example
    ///
    /// ```
    /// # use typed_index_collections::TiVec;
    /// pub struct Id(usize);
    /// let vec: &TiVec<Id, usize> = TiVec::from_ref(&vec![1, 2, 4]);
    /// ```
    ///
    /// [`&std::vec::Vec<V>`]: https://doc.rust-lang.org/std/vec/struct.Vec.html
    #[allow(trivial_casts, clippy::ptr_arg)]
    #[inline]
    pub fn from_ref(raw: &Vec<V>) -> &Self {
        unsafe { &*(raw as *const Vec<V> as *const Self) }
    }

    /// Converts a [`&mut std::vec::Vec<V>`] into a `&mut TiVec<K, V>`.
    ///
    /// # Example
    ///
    /// ```
    /// # use typed_index_collections::TiVec;
    /// pub struct Id(usize);
    /// let vec: &mut TiVec<Id, usize> = TiVec::from_mut(&mut vec![1, 2, 4]);
    /// ```
    ///
    /// [`&std::vec::mut Vec<V>`]: https://doc.rust-lang.org/std/vec/struct.Vec.html
    #[allow(trivial_casts)]
    #[inline]
    pub fn from_mut(raw: &mut Vec<V>) -> &mut Self {
        unsafe { &mut *(raw as *mut Vec<V> as *mut Self) }
    }

    /// Returns the number of elements the vector can hold without
    /// reallocating.
    ///
    /// See [`Vec::capacity`] for more details.
    ///
    /// [`Vec::capacity`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.capacity
    #[inline]
    pub fn capacity(&self) -> usize {
        self.raw.capacity()
    }

    /// Reserves capacity for at least `additional` more elements to be inserted
    /// in the given `TiVec<K, V>`. The collection may reserve more space to avoid
    /// frequent reallocations. After calling `reserve`, capacity will be
    /// greater than or equal to `self.len() + additional`. Does nothing if
    /// capacity is already sufficient.
    ///
    /// See [`Vec::reserve`] for more details.
    ///
    /// [`Vec::reserve`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.reserve
    pub fn reserve(&mut self, additional: usize) {
        self.raw.reserve(additional)
    }

    /// Reserves the minimum capacity for exactly `additional` more elements to
    /// be inserted in the given `TiVec<K, V>`. After calling `reserve_exact`,
    /// capacity will be greater than or equal to `self.len() + additional`.
    /// Does nothing if the capacity is already sufficient.
    ///
    /// See [`Vec::reserve_exact`] for more details.
    ///
    /// [`Vec::reserve_exact`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.reserve_exact
    pub fn reserve_exact(&mut self, additional: usize) {
        self.raw.reserve_exact(additional)
    }

    /// Shrinks the capacity of the vector as much as possible.
    ///
    /// See [`Vec::shrink_to_fit`] for more details.
    ///
    /// [`Vec::shrink_to_fit`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.shrink_to_fit
    pub fn shrink_to_fit(&mut self) {
        self.raw.shrink_to_fit()
    }

    /// Converts the vector into [`Box<TiSlice<K, V>>`][`Box`].
    ///
    /// See [`Vec::into_boxed_slice`] for more details.
    ///
    /// [`Vec::into_boxed_slice`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.into_boxed_slice
    /// [`Box`]: https://doc.rust-lang.org/std/boxed/struct.Box.html
    pub fn into_boxed_slice(self) -> Box<TiSlice<K, V>> {
        self.raw.into_boxed_slice().into()
    }

    /// Shortens the vector, keeping the first `len` elements and dropping
    /// the rest.
    ///
    /// See [`Vec::truncate`] for more details.
    ///
    /// [`Vec::truncate`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.truncate
    pub fn truncate(&mut self, len: usize) {
        self.raw.truncate(len)
    }

    /// Extracts a slice containing the entire vector.
    ///
    /// See [`Vec::as_slice`] for more details.
    ///
    /// [`Vec::as_slice`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.as_slice
    #[inline]
    pub fn as_slice(&self) -> &TiSlice<K, V> {
        self.raw.as_slice().as_ref()
    }

    /// Extracts a mutable slice of the entire vector.
    ///
    /// See [`Vec::as_mut_slice`] for more details.
    ///
    /// [`Vec::as_mut_slice`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.as_mut_slice
    #[inline]
    pub fn as_mut_slice(&mut self) -> &mut TiSlice<K, V> {
        self.raw.as_mut_slice().as_mut()
    }

    /// Returns a raw pointer to the vector's buffer.
    ///
    /// See [`Vec::as_ptr`] for more details.
    ///
    /// [`Vec::as_ptr`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.as_ptr
    #[inline]
    pub fn as_ptr(&self) -> *const V {
        self.raw.as_ptr()
    }

    /// Returns an unsafe mutable pointer to the vector's buffer.
    ///
    /// See [`Vec::as_mut_ptr`] for more details.
    ///
    /// [`Vec::as_mut_ptr`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.as_mut_ptr
    #[inline]
    pub fn as_mut_ptr(&mut self) -> *mut V {
        self.raw.as_mut_ptr()
    }

    /// Forces the length of the vector to `new_len`.
    ///
    /// See [`Vec::set_len`] for more details.
    ///
    /// [`Vec::set_len`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.set_len
    #[allow(clippy::missing_safety_doc)]
    #[inline]
    pub unsafe fn set_len(&mut self, new_len: usize) {
        self.raw.set_len(new_len)
    }

    /// Removes an element from the vector and returns it.
    ///
    /// The removed element is replaced by the last element of the vector.
    ///
    /// See [`Vec::swap_remove`] for more details.
    ///
    /// [`Vec::swap_remove`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.swap_remove
    #[inline]
    pub fn swap_remove(&mut self, index: K) -> V
    where
        usize: From<K>,
    {
        self.raw.swap_remove(index.into())
    }

    /// Inserts an element at position `index` within the vector, shifting all
    /// elements after it to the right.
    ///
    /// See [`Vec::insert`] for more details.
    ///
    /// [`Vec::insert`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.insert
    pub fn insert(&mut self, index: K, element: V)
    where
        usize: From<K>,
    {
        self.raw.insert(index.into(), element)
    }

    /// Removes and returns the element at position `index` within the vector,
    /// shifting all elements after it to the left.
    ///
    /// See [`Vec::remove`] for more details.
    ///
    /// [`Vec::remove`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.remove
    pub fn remove(&mut self, index: K) -> V
    where
        usize: From<K>,
    {
        self.raw.remove(index.into())
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// See [`Vec::retain`] for more details.
    ///
    /// [`Vec::retain`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.retain
    pub fn retain<F>(&mut self, f: F)
    where
        F: FnMut(&V) -> bool,
    {
        self.raw.retain(f)
    }

    /// Removes all but the first of consecutive elements in the vector that resolve to the same
    /// key.
    ///
    /// See [`Vec::dedup_by_key`] for more details.
    ///
    /// [`Vec::dedup_by_key`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.dedup_by_key
    #[inline]
    pub fn dedup_by_key<F, K2>(&mut self, key: F)
    where
        F: FnMut(&mut V) -> K2,
        K2: PartialEq,
    {
        self.raw.dedup_by_key(key)
    }

    /// Removes all but the first of consecutive elements in the vector satisfying a given equality
    /// relation.
    ///
    /// See [`Vec::dedup_by`] for more details.
    ///
    /// [`Vec::dedup_by`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.dedup_by
    pub fn dedup_by<F>(&mut self, same_bucket: F)
    where
        F: FnMut(&mut V, &mut V) -> bool,
    {
        self.raw.dedup_by(same_bucket)
    }

    /// Appends an element to the back of a collection.
    ///
    /// See [`Vec::push`] for more details.
    ///
    /// [`Vec::push`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.push
    #[inline]
    pub fn push(&mut self, value: V) {
        self.raw.push(value)
    }

    /// Appends an element to the back of a collection and returns its index of type `K`.
    ///
    /// It acts like `{ vec.push(...); vec.last_key().unwrap() }`,
    /// but is optimized better.
    ///
    /// See [`Vec::push`] for more details.
    ///
    /// # Example
    ///
    /// ```
    /// # use derive_more::{From, Into};
    /// # use typed_index_collections::TiVec;
    /// #[derive(Eq, Debug, From, Into, PartialEq)]
    /// pub struct Id(usize);
    /// let mut vec: TiVec<Id, usize> = vec![1, 2, 4].into();
    /// assert_eq!(vec.push_and_get_key(8), Id(3));
    /// assert_eq!(vec.push_and_get_key(16), Id(4));
    /// assert_eq!(vec.push_and_get_key(32), Id(5));
    /// ```
    ///
    /// [`Vec::push`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.push
    #[inline]
    pub fn push_and_get_key(&mut self, value: V) -> K
    where
        K: From<usize>,
    {
        let key = self.next_key();
        self.raw.push(value);
        key
    }

    /// Removes the last element from a vector and returns it, or [`None`] if it
    /// is empty.
    ///
    /// See [`Vec::pop`] for more details.
    ///
    /// [`Vec::pop`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.pop
    #[inline]
    pub fn pop(&mut self) -> Option<V> {
        self.raw.pop()
    }

    /// Removes the last element from a vector and returns it with
    /// its index of type `K`, or [`None`] if the vector is empty.
    ///
    /// See [`Vec::pop`] for more details.
    ///
    /// [`Vec::pop`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.pop
    ///
    /// # Example
    ///
    /// ```
    /// # use derive_more::{From, Into};
    /// # use typed_index_collections::TiVec;
    /// #[derive(Eq, Debug, From, Into, PartialEq)]
    /// pub struct Id(usize);
    /// let mut vec: TiVec<Id, usize> = vec![1, 2, 4].into();
    /// assert_eq!(vec.pop_key_value(), Some((Id(2), 4)));
    /// assert_eq!(vec.pop_key_value(), Some((Id(1), 2)));
    /// assert_eq!(vec.pop_key_value(), Some((Id(0), 1)));
    /// assert_eq!(vec.pop_key_value(), None);
    /// ```
    ///
    /// [`Vec::push`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.push
    #[inline]
    pub fn pop_key_value(&mut self) -> Option<(K, V)>
    where
        K: From<usize>,
    {
        self.raw.pop().map(|value| (self.raw.len().into(), value))
    }

    /// Moves all the elements of `other` into `Self`, leaving `other` empty.
    ///
    /// See [`Vec::append`] for more details.
    ///
    /// [`Vec::append`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.append
    #[inline]
    pub fn append(&mut self, other: &mut Self) {
        self.raw.append(&mut other.raw)
    }

    /// Creates a draining iterator that removes the specified range in the vector
    /// and yields the removed items.
    ///
    /// See [`Vec::drain`] for more details.
    ///
    /// [`Vec::drain`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.drain
    pub fn drain<R>(&mut self, range: R) -> Drain<'_, V>
    where
        R: TiRangeBounds<K>,
    {
        self.raw.drain(range.into_range())
    }

    /// Creates a draining iterator that removes the specified
    /// range in the vector and yields the current count and the removed items.
    ///
    /// It acts like `self.drain(range).enumerate()`,
    /// but instead of `usize` it returns index of type `K`.
    ///
    /// Note that the indices started from `K::from_usize(0)`,
    /// regardless of the range starting point.
    ///
    /// See [`Vec::drain`] for more details.
    ///
    /// # Example
    ///
    /// ```
    /// # use derive_more::{From, Into};
    /// # use typed_index_collections::{TiSlice, TiVec};
    /// #[derive(Eq, Debug, From, Into, PartialEq)]
    /// pub struct Id(usize);
    /// let mut vec: TiVec<Id, usize> = vec![1, 2, 4].into();
    /// {
    ///     let mut iterator = vec.drain_enumerated(Id(1)..);
    ///     assert_eq!(iterator.next(), Some((Id(0), 2)));
    ///     assert_eq!(iterator.next(), Some((Id(1), 4)));
    ///     assert_eq!(iterator.next(), None);
    /// }
    /// assert_eq!(vec.as_slice(), TiSlice::from_ref(&[1]));
    /// ```
    ///
    /// [`Vec::drain`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.drain
    #[inline]
    pub fn drain_enumerated<R>(&mut self, range: R) -> TiEnumerated<Drain<'_, V>, K, V>
    where
        K: From<usize>,
        R: TiRangeBounds<K>,
    {
        self.raw
            .drain(range.into_range())
            .enumerate()
            .map(|(key, value)| (key.into(), value))
    }

    /// Clears the vector, removing all values.
    ///
    /// See [`Vec::clear`] for more details.
    ///
    /// [`Vec::clear`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.clear
    #[inline]
    pub fn clear(&mut self) {
        self.raw.clear()
    }

    /// Returns the number of elements in the vector, also referred to
    /// as its 'length'.
    ///
    /// See [`Vec::len`] for more details.
    ///
    /// [`Vec::len`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.len
    #[inline]
    pub fn len(&self) -> usize {
        self.raw.len()
    }

    /// Returns `true` if the vector contains no elements.
    ///
    /// See [`Vec::is_empty`] for more details.
    ///
    /// [`Vec::is_empty`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.is_empty
    pub fn is_empty(&self) -> bool {
        self.raw.is_empty()
    }

    /// Splits the collection into two at the given index.
    ///
    /// See [`Vec::split_off`] for more details.
    ///
    /// [`Vec::split_off`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.split_off
    #[inline]
    #[must_use = "use `.truncate()` if you don't need the other half"]
    pub fn split_off(&mut self, at: K) -> Self
    where
        usize: From<K>,
    {
        self.raw.split_off(at.into()).into()
    }

    /// Resizes the `TiVec` in-place so that `len` is equal to `new_len`.
    ///
    /// See [`Vec::resize_with`] for more details.
    ///
    /// [`Vec::resize_with`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.resize_with
    pub fn resize_with<F>(&mut self, new_len: usize, f: F)
    where
        F: FnMut() -> V,
    {
        self.raw.resize_with(new_len, f)
    }

    /// Resizes the `TiVec` in-place so that `len` is equal to `new_len`.
    ///
    /// See [`Vec::resize`] for more details.
    ///
    /// [`Vec::resize`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.resize
    pub fn resize(&mut self, new_len: usize, value: V)
    where
        V: Clone,
    {
        self.raw.resize(new_len, value)
    }

    /// Clones and appends all elements in a slice to the `TiVec`.
    ///
    /// See [`Vec::extend_from_slice`] for more details.
    ///
    /// [`Vec::extend_from_slice`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.extend_from_slice
    pub fn extend_from_slice(&mut self, other: &TiSlice<K, V>)
    where
        V: Clone,
    {
        self.raw.extend_from_slice(&other.raw)
    }

    /// Removes consecutive repeated elements in the vector according to the
    /// [`PartialEq`] trait implementation.
    ///
    /// See [`Vec::dedup`] for more details.
    ///
    /// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
    /// [`Vec::dedup`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.dedup
    #[inline]
    pub fn dedup(&mut self)
    where
        V: PartialEq,
    {
        self.raw.dedup()
    }

    /// Creates a splicing iterator that replaces the specified range in the vector
    /// with the given `replace_with` iterator and yields the removed items.
    /// `replace_with` does not need to be the same length as `range`.
    ///
    /// See [`Vec::splice`] for more details.
    ///
    /// [`Vec::splice`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.splice
    #[inline]
    pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter>
    where
        R: TiRangeBounds<K>,
        I: IntoIterator<Item = V>,
    {
        self.raw.splice(range.into_range(), replace_with)
    }

    /// Converts the vector into iterator over all key-value pairs
    /// with `K` used for iteration indices.
    ///
    /// It acts like `self.into_iter().enumerate()`,
    /// but use `K` instead of `usize` for iteration indices.
    ///
    /// # Example
    ///
    /// ```
    /// # use derive_more::{From, Into};
    /// # use typed_index_collections::TiVec;
    /// #[derive(Eq, Debug, From, Into, PartialEq)]
    /// pub struct Id(usize);
    /// let vec: TiVec<Id, usize> = vec![1, 2, 4].into();
    /// let mut iterator = vec.into_iter_enumerated();
    /// assert_eq!(iterator.next(), Some((Id(0), 1)));
    /// assert_eq!(iterator.next(), Some((Id(1), 2)));
    /// assert_eq!(iterator.next(), Some((Id(2), 4)));
    /// assert_eq!(iterator.next(), None);
    /// ```
    #[inline(always)]
    pub fn into_iter_enumerated(self) -> TiEnumerated<vec::IntoIter<V>, K, V>
    where
        K: From<usize>,
    {
        self.raw
            .into_iter()
            .enumerate()
            .map(|(key, value)| (key.into(), value))
    }
}

impl<K, V> fmt::Debug for TiVec<K, V>
where
    K: fmt::Debug + From<usize>,
    V: fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_map().entries(self.iter_enumerated()).finish()
    }
}

impl<K, V> AsRef<TiVec<K, V>> for TiVec<K, V> {
    fn as_ref(&self) -> &TiVec<K, V> {
        self
    }
}

impl<K, V> AsMut<TiVec<K, V>> for TiVec<K, V> {
    fn as_mut(&mut self) -> &mut TiVec<K, V> {
        self
    }
}

impl<K, V> AsRef<TiSlice<K, V>> for TiVec<K, V> {
    fn as_ref(&self) -> &TiSlice<K, V> {
        self
    }
}

impl<K, V> AsMut<TiSlice<K, V>> for TiVec<K, V> {
    fn as_mut(&mut self) -> &mut TiSlice<K, V> {
        self
    }
}

impl<K, V> AsRef<Vec<V>> for TiVec<K, V> {
    fn as_ref(&self) -> &Vec<V> {
        &self.raw
    }
}

impl<K, V> AsMut<Vec<V>> for TiVec<K, V> {
    fn as_mut(&mut self) -> &mut Vec<V> {
        &mut self.raw
    }
}

impl<K, V> AsRef<[V]> for TiVec<K, V> {
    fn as_ref(&self) -> &[V] {
        &self.raw
    }
}

impl<K, V> AsMut<[V]> for TiVec<K, V> {
    fn as_mut(&mut self) -> &mut [V] {
        &mut self.raw
    }
}

impl<K, V> AsRef<TiVec<K, V>> for Vec<V> {
    fn as_ref(&self) -> &TiVec<K, V> {
        TiVec::from_ref(self)
    }
}

impl<K, V> AsMut<TiVec<K, V>> for Vec<V> {
    fn as_mut(&mut self) -> &mut TiVec<K, V> {
        TiVec::from_mut(self)
    }
}

impl<K, V> Borrow<TiSlice<K, V>> for TiVec<K, V> {
    fn borrow(&self) -> &TiSlice<K, V> {
        self.as_slice()
    }
}

impl<K, V> BorrowMut<TiSlice<K, V>> for TiVec<K, V> {
    fn borrow_mut(&mut self) -> &mut TiSlice<K, V> {
        self.as_mut_slice()
    }
}

impl<K, V> ops::Deref for TiVec<K, V> {
    type Target = TiSlice<K, V>;

    fn deref(&self) -> &TiSlice<K, V> {
        Self::Target::from_ref(&self.raw)
    }
}

impl<K, V> ops::DerefMut for TiVec<K, V> {
    fn deref_mut(&mut self) -> &mut TiSlice<K, V> {
        Self::Target::from_mut(&mut self.raw)
    }
}

impl<K, V> Extend<V> for TiVec<K, V> {
    #[inline]
    fn extend<I: IntoIterator<Item = V>>(&mut self, iter: I) {
        self.raw.extend(iter)
    }
}

impl<'a, K, V: 'a + Copy> Extend<&'a V> for TiVec<K, V> {
    #[inline]
    fn extend<I: IntoIterator<Item = &'a V>>(&mut self, iter: I) {
        self.raw.extend(iter)
    }
}

impl<K, V> FromIterator<V> for TiVec<K, V> {
    #[inline]
    fn from_iter<I: IntoIterator<Item = V>>(iter: I) -> Self {
        Self {
            raw: Vec::from_iter(iter),
            _marker: PhantomData,
        }
    }
}

impl<K, A, B> PartialEq<TiVec<K, B>> for TiVec<K, A>
where
    A: PartialEq<B>,
{
    #[inline]
    fn eq(&self, other: &TiVec<K, B>) -> bool {
        self.raw == other.raw
    }
}

impl<'a, K, A, B> PartialEq<&'a TiSlice<K, B>> for TiVec<K, A>
where
    A: PartialEq<B>,
{
    #[inline]
    fn eq(&self, other: &&'a TiSlice<K, B>) -> bool {
        *self.raw == other.raw
    }
}

impl<'a, K, A, B> PartialEq<&'a mut TiSlice<K, B>> for TiVec<K, A>
where
    A: PartialEq<B>,
{
    #[inline]
    fn eq(&self, other: &&'a mut TiSlice<K, B>) -> bool {
        *self.raw == other.raw
    }
}

impl<K, V> PartialOrd<TiVec<K, V>> for TiVec<K, V>
where
    V: PartialOrd<V>,
{
    #[inline]
    fn partial_cmp(&self, other: &TiVec<K, V>) -> Option<Ordering> {
        self.raw.partial_cmp(&other.raw)
    }
}

impl<K, V> Clone for TiVec<K, V>
where
    V: Clone,
{
    #[inline]
    fn clone(&self) -> TiVec<K, V> {
        self.raw.clone().into()
    }
}

impl<K, V> Default for TiVec<K, V> {
    #[inline]
    fn default() -> Self {
        Vec::default().into()
    }
}

impl<K, V> Eq for TiVec<K, V> where V: Eq {}

impl<K, V> Hash for TiVec<K, V>
where
    V: Hash,
{
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.raw.hash(state)
    }
}

impl<K, V> Ord for TiVec<K, V>
where
    V: Ord,
{
    #[inline]
    fn cmp(&self, other: &TiVec<K, V>) -> Ordering {
        self.raw.cmp(&other.raw)
    }
}

impl<K, V> From<Vec<V>> for TiVec<K, V> {
    fn from(vec: Vec<V>) -> Self {
        Self {
            raw: vec,
            _marker: PhantomData,
        }
    }
}

impl<K, V> From<TiVec<K, V>> for Vec<V> {
    fn from(vec: TiVec<K, V>) -> Self {
        vec.raw
    }
}

impl<K, V> IntoIterator for TiVec<K, V> {
    type Item = V;
    type IntoIter = vec::IntoIter<V>;

    #[inline]
    fn into_iter(self) -> vec::IntoIter<V> {
        self.raw.into_iter()
    }
}

impl<'a, K, V> IntoIterator for &'a TiVec<K, V> {
    type Item = &'a V;
    type IntoIter = slice::Iter<'a, V>;

    #[inline]
    fn into_iter(self) -> slice::Iter<'a, V> {
        self.raw.iter()
    }
}

impl<'a, K, V> IntoIterator for &'a mut TiVec<K, V> {
    type Item = &'a mut V;
    type IntoIter = slice::IterMut<'a, V>;

    #[inline]
    fn into_iter(self) -> slice::IterMut<'a, V> {
        self.raw.iter_mut()
    }
}

#[cfg(feature = "serde")]
impl<K, V: Serialize> Serialize for TiVec<K, V> {
    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        self.raw.as_slice().serialize(serializer)
    }
}

#[cfg(any(feature = "serde-alloc", feature = "serde-std"))]
impl<'de, K, V: Deserialize<'de>> Deserialize<'de> for TiVec<K, V> {
    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        Vec::deserialize(deserializer).map(Into::into)
    }
}

#[cfg(test)]
mod test {
    use crate::test::Id;

    trait VecWithCapacity
    where
        Self: Sized,
    {
        fn and_capacity(self) -> (usize, Self);
    }

    impl<T> VecWithCapacity for alloc::vec::Vec<T> {
        fn and_capacity(self) -> (usize, Self) {
            (self.capacity(), self)
        }
    }

    macro_rules! assert_eq_vec_api {
        ($source:expr => |&$arg:ident| $expr:expr) => {
            assert_eq_api!($source.clone() => |$arg| {
                let $arg = $arg.into_t();
                let value = $expr;
                (value, $arg.into_t().and_capacity())
            });
        };
        ($source:expr => |&mut $arg:ident| $expr:expr) => {
            assert_eq_api!($source.clone() => |$arg| {
                let mut $arg = $arg.into_t();
                let value = $expr;
                (value, $arg.into_t().and_capacity())
            });
        };
    }

    #[test]
    fn api_compatibility() {
        use crate::TiVec;
        use alloc::vec;
        use alloc::vec::Vec;

        assert_eq_api!(UsizeVec::new().into_t().and_capacity());
        for &j in &[0, 1, 2, 4] {
            assert_eq_api!(UsizeVec::with_capacity(j).into_t().and_capacity());
        }
        for vec in &[
            vec![0; 0],
            vec![1],
            vec![1, 2],
            vec![1, 2, 4],
            vec![1, 2, 4, 8],
            vec![1, 3],
            vec![7, 3, 5],
            vec![10, 6, 35, 4],
            vec![1, 3, 3, 2, 4, 4, 4],
        ] {
            assert_eq_api!(vec.clone() => |vec| {
                let mut vec = core::mem::ManuallyDrop::new(vec);
                unsafe {
                    UsizeVec::from_raw_parts(vec.as_mut_ptr(), vec.len(), vec.capacity())
                }.into_t()
            });
            assert_eq_api!(vec.clone() => |vec| vec.into_t().capacity());
            for j in 0..8 {
                assert_eq_vec_api!(vec => |&mut vec| vec.reserve(j));
                assert_eq_vec_api!(vec => |&mut vec| vec.reserve_exact(j));
                assert_eq_vec_api!(vec => |&mut vec| {
                    vec.reserve(j);
                    vec.shrink_to_fit();
                });
            }
            assert_eq_api!(vec.clone() => |vec| vec.into_t().into_boxed_slice().into_t());
            for j in 0..8 {
                assert_eq_vec_api!(vec => |&mut vec| vec.truncate(j));
            }
            assert_eq_api!(vec.clone() => |vec| vec.into_t().as_slice().into_t());
            assert_eq_api!(vec.clone() => |vec| vec.into_t().as_mut_slice().into_t());
            assert_eq_api!(&vec => |vec| vec.into_t().as_ptr());
            {
                let mut vec = vec.clone();
                let vec_ref_mut = &mut vec;
                let vec_ptr_mut = vec_ref_mut.as_mut_ptr();
                let ti_vec_ref_mut: &mut TiVec<Id, _> = vec_ref_mut.as_mut();
                let ti_vec_ptr_mut = ti_vec_ref_mut.as_mut_ptr();
                assert_eq!(vec_ptr_mut, ti_vec_ptr_mut);
            }
            assert_eq_api!(vec.clone() => |vec| {
                const NUM_ADDED_ITEMS: usize = 4;
                let mut vec = vec.into_t();
                let initial_len = vec.len();
                vec.reserve(NUM_ADDED_ITEMS);
                unsafe {
                    for j in 0..NUM_ADDED_ITEMS {
                        *vec.as_mut_slice().into_t().get_unchecked_mut(initial_len + j) = j;
                    }
                    vec.set_len(initial_len + NUM_ADDED_ITEMS);
                }
                vec.into_t().and_capacity()
            });
            for j in 0..vec.len() {
                assert_eq_vec_api!(vec => |&mut vec| vec.swap_remove(j.into_t()));
                assert_eq_vec_api!(vec => |&mut vec| vec.insert(j.into_t(), 123));
                assert_eq_vec_api!(vec => |&mut vec| vec.remove(j.into_t()));
            }
            assert_eq_vec_api!(vec => |&mut vec|
                vec.retain(|value| value % 3 == 0 || value % 4 == 0));
            assert_eq_vec_api!(vec => |&mut vec|
                vec.dedup_by_key(|value| *value % 3 == 0 || *value % 4 == 0));
            assert_eq_vec_api!(vec => |&mut vec| vec.dedup_by(|lhs, rhs| lhs < rhs));
            assert_eq_vec_api!(vec => |&mut vec| vec.push(123));
            assert_eq_vec_api!(vec => |&mut vec| vec.pop());
            for other_vec in &[
                vec![0; 0],
                vec![1],
                vec![1, 2],
                vec![1, 2, 4],
                vec![1, 2, 4, 8],
                vec![1, 3],
                vec![7, 3, 5],
                vec![10, 6, 35, 4],
            ] {
                assert_eq_api!({
                    let mut vec = vec.clone().into_t();
                    let mut other_vec = other_vec.clone().into_t();
                    vec.append(&mut other_vec);
                    vec.into_t().and_capacity()
                });
            }
            for start in 0..vec.len() {
                for end in start..vec.len() {
                    assert_eq_vec_api!(vec => |&mut vec| {
                        let iter = vec.drain(start.into_t()..end.into_t());
                        let vec: Vec<_> = iter.collect();
                        vec
                    });
                }
            }

            assert_eq_vec_api!(vec => |&mut vec| vec.clear());
            assert_eq_vec_api!(vec => |&vec| vec.len());
            assert_eq_vec_api!(vec => |&vec| vec.is_empty());
            for j in 0..vec.len() {
                assert_eq_vec_api!(vec => |&mut vec| vec.split_off(j.into_t()).into_t());
            }
            for j in 0..8 {
                assert_eq_vec_api!(vec => |&mut vec| {
                    let mut items = 0..;
                    vec.resize_with(j, || items.next().unwrap())
                });
                assert_eq_vec_api!(vec => |&mut vec| vec.resize(j, 123));
            }
            #[allow(clippy::unnecessary_to_owned)]
            for slice in &[
                &[0; 0][..],
                &[1],
                &[1, 2],
                &[1, 2, 4],
                &[1, 2, 4, 8],
                &[1, 3],
                &[7, 3, 5],
                &[10, 6, 35, 4],
            ] {
                assert_eq_vec_api!(vec => |&mut vec| vec.extend_from_slice(slice.into_t()));
                assert_eq_vec_api!(vec => |&mut vec| vec.extend(slice.iter()));
                assert_eq_vec_api!(vec => |&mut vec| vec.extend(slice.to_vec().into_iter()));
            }
            assert_eq_vec_api!(vec => |&mut vec| vec.dedup());
            for start in 0..vec.len() {
                for end in start..vec.len() {
                    assert_eq_vec_api!(vec => |&mut vec| {
                        let iter = vec.splice(start.into_t()..end.into_t(), 10..20);
                        let vec: Vec<_> = iter.collect();
                        vec
                    });
                }
            }
        }
    }
}