#![allow(clippy::partialeq_ne_impl)]
#![no_std]
extern crate alloc;
use alloc::borrow::{Cow, ToOwned};
use alloc::boxed::Box;
use alloc::vec;
use alloc::vec::Vec;
use core::borrow::{Borrow, BorrowMut};
use core::fmt;
use core::fmt::Debug;
use core::hash::Hash;
use core::iter::{self, FromIterator};
use core::marker::PhantomData;
use core::ops::Range;
use core::slice;
mod idxslice;
mod indexing;
pub use idxslice::{IndexBox, IndexSlice};
pub use indexing::{IdxRangeBounds, IdxSliceIndex};
#[macro_use]
mod macros;
pub use macros::*;
#[cfg(any(test, feature = "example_generated"))]
pub mod example_generated;
pub trait Idx: Copy + 'static + Ord + Debug + Hash {
fn from_usize(idx: usize) -> Self;
fn index(self) -> usize;
}
#[macro_export]
macro_rules! index_vec {
($($tokens:tt)*) => {
$crate::IndexVec::from_vec(vec![$($tokens)*])
}
}
#[macro_export]
macro_rules! index_box {
($($tokens:tt)*) => {
$crate::IndexVec::from_vec(vec![$($tokens)*]).into_boxed_slice()
}
}
#[derive(PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct IndexVec<I: Idx, T> {
pub raw: Vec<T>,
_marker: PhantomData<fn(&I)>,
}
unsafe impl<I: Idx, T> Send for IndexVec<I, T> where T: Send {}
impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> {
fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
fmt::Debug::fmt(&self.raw, fmt)
}
}
type Enumerated<Iter, I, T> = iter::Map<iter::Enumerate<Iter>, fn((usize, T)) -> (I, T)>;
impl<I: Idx, T> IndexVec<I, T> {
#[inline]
pub fn new() -> Self {
IndexVec {
raw: Vec::new(),
_marker: PhantomData,
}
}
#[inline]
pub fn from_vec(vec: Vec<T>) -> Self {
let _ = I::from_usize(vec.len());
IndexVec {
raw: vec,
_marker: PhantomData,
}
}
#[inline]
pub fn with_capacity(capacity: usize) -> Self {
IndexVec {
raw: Vec::with_capacity(capacity),
_marker: PhantomData,
}
}
#[inline(always)]
pub fn into_iter_enumerated(self) -> Enumerated<vec::IntoIter<T>, I, T> {
self.raw
.into_iter()
.enumerate()
.map(|(i, t)| (I::from_usize(i), t))
}
#[inline]
pub fn splice<R, It>(
&mut self,
range: R,
replace_with: It,
) -> vec::Splice<<It as IntoIterator>::IntoIter>
where
It: IntoIterator<Item = T>,
R: IdxRangeBounds<I>,
{
self.raw.splice(range.into_range(), replace_with)
}
#[inline]
pub fn drain_enumerated<R: IdxRangeBounds<I>>(
&mut self,
range: R,
) -> Enumerated<vec::Drain<'_, T>, I, T> {
self.raw
.drain(range.into_range())
.enumerate()
.map(|(i, t)| (I::from_usize(i), t))
}
#[inline]
pub fn next_idx(&self) -> I {
I::from_usize(self.len())
}
#[inline(always)]
pub fn as_raw_slice(&self) -> &[T] {
&self.raw
}
#[inline(always)]
pub fn as_raw_slice_mut(&mut self) -> &mut [T] {
&mut self.raw
}
#[inline(always)]
pub fn as_vec(&self) -> &Vec<T> {
&self.raw
}
#[inline(always)]
pub fn as_mut_vec(&mut self) -> &mut Vec<T> {
&mut self.raw
}
#[inline]
pub fn push(&mut self, d: T) -> I {
let idx = I::from_usize(self.len());
self.raw.push(d);
idx
}
#[inline]
pub fn pop(&mut self) -> Option<T> {
self.raw.pop()
}
#[inline]
pub fn into_boxed_slice(self) -> alloc::boxed::Box<IndexSlice<I, [T]>> {
let b = self.raw.into_boxed_slice();
unsafe { Box::from_raw(Box::into_raw(b) as *mut IndexSlice<I, [T]>) }
}
#[inline]
pub fn drain<R: IdxRangeBounds<I>>(&mut self, range: R) -> vec::Drain<'_, T> {
self.raw.drain(range.into_range())
}
#[inline]
pub fn shrink_to_fit(&mut self) {
self.raw.shrink_to_fit()
}
#[inline]
pub fn truncate(&mut self, a: usize) {
self.raw.truncate(a)
}
#[inline]
pub fn clear(&mut self) {
self.raw.clear()
}
#[inline]
pub fn reserve(&mut self, c: usize) {
self.raw.reserve(c)
}
#[inline]
pub fn get<J: IdxSliceIndex<I, T>>(&self, index: J) -> Option<&J::Output> {
index.get(self.as_slice())
}
#[inline]
pub fn get_mut<J: IdxSliceIndex<I, T>>(&mut self, index: J) -> Option<&mut J::Output> {
index.get_mut(self.as_mut_slice())
}
#[inline]
pub fn resize(&mut self, new_len: usize, value: T)
where
T: Clone,
{
self.raw.resize(new_len, value)
}
#[inline]
pub fn resize_with<F: FnMut() -> T>(&mut self, new_len: usize, f: F) {
self.raw.resize_with(new_len, f)
}
#[inline]
pub fn append(&mut self, other: &mut Self) {
self.raw.append(&mut other.raw)
}
#[inline]
pub fn split_off(&mut self, idx: I) -> Self {
Self::from_vec(self.raw.split_off(idx.index()))
}
#[inline]
pub fn remove(&mut self, index: I) -> T {
self.raw.remove(index.index())
}
#[inline]
pub fn swap_remove(&mut self, index: I) -> T {
self.raw.swap_remove(index.index())
}
#[inline]
pub fn insert(&mut self, index: I, element: T) {
self.raw.insert(index.index(), element)
}
#[inline]
pub fn extend_from_slice(&mut self, other: &IndexSlice<I, [T]>)
where
T: Clone,
{
self.raw.extend_from_slice(&other.raw)
}
#[inline]
pub fn retain<F: FnMut(&T) -> bool>(&mut self, f: F) {
self.raw.retain(f)
}
#[inline]
pub fn dedup_by_key<F: FnMut(&mut T) -> K, K: PartialEq>(&mut self, key: F) {
self.raw.dedup_by_key(key)
}
#[inline]
pub fn dedup(&mut self)
where
T: PartialEq,
{
self.raw.dedup()
}
#[inline]
pub fn dedup_by<F: FnMut(&mut T, &mut T) -> bool>(&mut self, same_bucket: F) {
self.raw.dedup_by(same_bucket)
}
#[inline(always)]
pub fn as_slice(&self) -> &IndexSlice<I, [T]> {
IndexSlice::new(&self.raw)
}
#[inline(always)]
pub fn as_mut_slice(&mut self) -> &mut IndexSlice<I, [T]> {
IndexSlice::new_mut(&mut self.raw)
}
}
impl<I: Idx, T> Default for IndexVec<I, T> {
#[inline]
fn default() -> Self {
Self::new()
}
}
impl<I: Idx, T> Extend<T> for IndexVec<I, T> {
#[inline]
fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) {
self.raw.extend(iter);
}
}
impl<'a, I: Idx, T: 'a + Copy> Extend<&'a T> for IndexVec<I, T> {
#[inline]
fn extend<J: IntoIterator<Item = &'a T>>(&mut self, iter: J) {
self.raw.extend(iter);
}
}
impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> {
#[inline]
fn from_iter<J>(iter: J) -> Self
where
J: IntoIterator<Item = T>,
{
IndexVec {
raw: FromIterator::from_iter(iter),
_marker: PhantomData,
}
}
}
impl<I: Idx, T> IntoIterator for IndexVec<I, T> {
type Item = T;
type IntoIter = vec::IntoIter<T>;
#[inline]
fn into_iter(self) -> vec::IntoIter<T> {
self.raw.into_iter()
}
}
impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> {
type Item = &'a T;
type IntoIter = slice::Iter<'a, T>;
#[inline]
fn into_iter(self) -> slice::Iter<'a, T> {
self.raw.iter()
}
}
impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> {
type Item = &'a mut T;
type IntoIter = slice::IterMut<'a, T>;
#[inline]
fn into_iter(self) -> slice::IterMut<'a, T> {
self.raw.iter_mut()
}
}
impl<I: Idx, T> From<IndexVec<I, T>> for Box<IndexSlice<I, [T]>> {
#[inline]
fn from(src: IndexVec<I, T>) -> Self {
src.into_boxed_slice()
}
}
impl<I: Idx, T> From<Box<IndexSlice<I, [T]>>> for IndexVec<I, T> {
#[inline]
fn from(src: Box<IndexSlice<I, [T]>>) -> Self {
src.into_vec()
}
}
impl<'a, I: Idx, T> From<Cow<'a, IndexSlice<I, [T]>>> for IndexVec<I, T>
where
IndexSlice<I, [T]>: ToOwned<Owned = IndexVec<I, T>>,
{
#[inline]
fn from(s: Cow<'a, IndexSlice<I, [T]>>) -> IndexVec<I, T> {
s.into_owned()
}
}
impl<'a, I: Idx, T: Clone> From<&'a IndexSlice<I, [T]>> for IndexVec<I, T> {
#[inline]
fn from(src: &'a IndexSlice<I, [T]>) -> Self {
src.to_owned()
}
}
impl<'a, I: Idx, T: Clone> From<&'a mut IndexSlice<I, [T]>> for IndexVec<I, T> {
#[inline]
fn from(src: &'a mut IndexSlice<I, [T]>) -> Self {
src.to_owned()
}
}
impl<I: Idx, T> From<Vec<T>> for IndexVec<I, T> {
#[inline]
fn from(v: Vec<T>) -> Self {
Self {
raw: v,
_marker: PhantomData,
}
}
}
impl<I: Idx, T: Clone> Clone for IndexVec<I, T> {
#[inline]
fn clone(&self) -> Self {
Self {
raw: self.raw.clone(),
_marker: PhantomData,
}
}
#[inline]
fn clone_from(&mut self, o: &Self) {
self.raw.clone_from(&o.raw);
}
}
impl<I: Idx, A> AsRef<[A]> for IndexVec<I, A> {
#[inline]
fn as_ref(&self) -> &[A] {
&self.raw
}
}
impl<I: Idx, A> AsMut<[A]> for IndexVec<I, A> {
#[inline]
fn as_mut(&mut self) -> &mut [A] {
&mut self.raw
}
}
impl<I: Idx, A> AsRef<IndexSlice<I, [A]>> for IndexVec<I, A> {
#[inline]
fn as_ref(&self) -> &IndexSlice<I, [A]> {
IndexSlice::new(&self.raw)
}
}
impl<I: Idx, A> AsMut<IndexSlice<I, [A]>> for IndexVec<I, A> {
#[inline]
fn as_mut(&mut self) -> &mut IndexSlice<I, [A]> {
IndexSlice::new_mut(&mut self.raw)
}
}
impl<I: Idx, A> core::ops::Deref for IndexVec<I, A> {
type Target = IndexSlice<I, [A]>;
#[inline]
fn deref(&self) -> &IndexSlice<I, [A]> {
IndexSlice::new(&self.raw)
}
}
impl<I: Idx, A> core::ops::DerefMut for IndexVec<I, A> {
#[inline]
fn deref_mut(&mut self) -> &mut IndexSlice<I, [A]> {
IndexSlice::new_mut(&mut self.raw)
}
}
impl<I: Idx, T> Borrow<IndexSlice<I, [T]>> for IndexVec<I, T> {
#[inline]
fn borrow(&self) -> &IndexSlice<I, [T]> {
self.as_slice()
}
}
impl<I: Idx, T> BorrowMut<IndexSlice<I, [T]>> for IndexVec<I, T> {
#[inline]
fn borrow_mut(&mut self) -> &mut IndexSlice<I, [T]> {
self.as_mut_slice()
}
}
macro_rules! impl_partialeq {
($Lhs: ty, $Rhs: ty) => {
impl<'a, 'b, A, B, I: Idx> PartialEq<$Rhs> for $Lhs
where
A: PartialEq<B>,
{
#[inline]
fn eq(&self, other: &$Rhs) -> bool {
self[..] == other[..]
}
#[inline]
fn ne(&self, other: &$Rhs) -> bool {
self[..] != other[..]
}
}
};
}
macro_rules! impl_partialeq2 {
($Lhs: ty, $Rhs: ty) => {
impl<'a, 'b, A, B, I: Idx, J: Idx> PartialEq<$Rhs> for $Lhs
where
A: PartialEq<B>,
{
#[inline]
fn eq(&self, other: &$Rhs) -> bool {
self.raw[..] == other.raw[..]
}
#[inline]
fn ne(&self, other: &$Rhs) -> bool {
self.raw[..] != other.raw[..]
}
}
};
}
impl_partialeq! { IndexVec<I, A>, Vec<B> }
impl_partialeq! { IndexVec<I, A>, &'b [B] }
impl_partialeq! { IndexVec<I, A>, &'b mut [B] }
impl_partialeq2! { IndexVec<I, A>, &'b IndexSlice<J, [B]> }
impl_partialeq2! { IndexVec<I, A>, &'b mut IndexSlice<J, [B]> }
impl_partialeq! { &'a IndexSlice<I, [A]>, Vec<B> }
impl_partialeq! { &'a mut IndexSlice<I, [A]>, Vec<B> }
impl_partialeq! { IndexSlice<I, [A]>, &'b [B] }
impl_partialeq! { IndexSlice<I, [A]>, &'b mut [B] }
impl_partialeq2! { &'a IndexSlice<I, [A]>, IndexVec<J, B> }
impl_partialeq2! { &'a mut IndexSlice<I, [A]>, IndexVec<J, B> }
impl_partialeq2! { IndexSlice<I, [A]>, &'a IndexSlice<J, [B]> }
impl_partialeq2! { IndexSlice<I, [A]>, &'a mut IndexSlice<J, [B]> }
macro_rules! array_impls {
($($N: expr)+) => {$(
impl_partialeq! { IndexVec<I, A>, [B; $N] }
impl_partialeq! { IndexVec<I, A>, &'b [B; $N] }
impl_partialeq! { IndexSlice<I, [A]>, [B; $N] }
impl_partialeq! { IndexSlice<I, [A]>, &'b [B; $N] }
)+};
}
array_impls! {
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32
}
#[inline(never)]
#[cold]
#[doc(hidden)]
pub fn __max_check_fail(u: usize, max: usize) -> ! {
panic!(
"index_vec index overflow: {} is outside the range [0, {})",
u, max,
)
}
#[cfg(feature = "serde")]
impl<I: Idx, T: serde::ser::Serialize> serde::ser::Serialize for IndexVec<I, T> {
fn serialize<S: serde::ser::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
self.raw.serialize(serializer)
}
}
#[cfg(feature = "serde")]
impl<'de, I: Idx, T: serde::de::Deserialize<'de>> serde::de::Deserialize<'de> for IndexVec<I, T> {
fn deserialize<D: serde::de::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
Vec::deserialize(deserializer).map(Self::from_vec)
}
}
#[cfg(feature = "serde")]
impl<I: Idx, T: serde::ser::Serialize> serde::ser::Serialize for IndexBox<I, T> {
fn serialize<S: serde::ser::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
self.raw.serialize(serializer)
}
}
#[cfg(feature = "serde")]
impl<'de, I: Idx, T: serde::de::Deserialize<'de>> serde::de::Deserialize<'de> for IndexBox<I, [T]> {
fn deserialize<D: serde::de::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
Box::<[T]>::deserialize(deserializer).map(Into::into)
}
}