1#![allow(clippy::partialeq_ne_impl)]
131#![no_std]
132extern crate alloc;
133
134use alloc::borrow::{Cow, ToOwned};
135use alloc::boxed::Box;
136use alloc::vec;
137use alloc::vec::Vec;
138use core::borrow::{Borrow, BorrowMut};
139use core::fmt;
140use core::fmt::Debug;
141use core::hash::Hash;
142use core::iter::{self, FromIterator};
143use core::marker::PhantomData;
144use core::ops::Range;
145use core::slice;
146mod idxslice;
147mod indexing;
148pub use idxslice::{IndexBox, IndexSlice};
149pub use indexing::{IdxRangeBounds, IdxSliceIndex};
150
151#[macro_use]
152mod macros;
153
154#[cfg(any(test, feature = "example_generated"))]
155pub mod example_generated;
156
157pub trait Idx: Copy + 'static + Ord + Debug + Hash {
177 fn from_usize(idx: usize) -> Self;
183
184 fn index(self) -> usize;
186}
187
188#[macro_export]
190macro_rules! index_vec {
191 ($($tokens:tt)*) => {
192 $crate::IndexVec::from_vec(vec![$($tokens)*])
193 }
194}
195
196#[macro_export]
199macro_rules! index_box {
200 ($($tokens:tt)*) => {
201 $crate::IndexVec::from_vec(vec![$($tokens)*]).into_boxed_slice()
202 }
203}
204
205#[derive(PartialEq, Eq, PartialOrd, Ord, Hash)]
223pub struct IndexVec<I: Idx, T> {
224 pub raw: Vec<T>,
226 _marker: PhantomData<fn(&I)>,
227}
228
229#[allow(renamed_and_removed_lints, suspicious_auto_trait_impls)]
232unsafe impl<I: Idx, T> Send for IndexVec<I, T> where T: Send {}
233
234impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> {
235 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
236 fmt::Debug::fmt(&self.raw, fmt)
237 }
238}
239type Enumerated<Iter, I, T> = iter::Map<iter::Enumerate<Iter>, fn((usize, T)) -> (I, T)>;
240
241impl<I: Idx, T> IndexVec<I, T> {
242 #[inline]
244 pub fn new() -> Self {
245 IndexVec {
246 raw: Vec::new(),
247 _marker: PhantomData,
248 }
249 }
250
251 #[inline]
255 pub fn from_vec(vec: Vec<T>) -> Self {
256 let _ = I::from_usize(vec.len());
258 IndexVec {
259 raw: vec,
260 _marker: PhantomData,
261 }
262 }
263
264 #[inline]
267 pub fn with_capacity(capacity: usize) -> Self {
268 IndexVec {
269 raw: Vec::with_capacity(capacity),
270 _marker: PhantomData,
271 }
272 }
273
274 #[inline(always)]
277 pub fn into_iter_enumerated(self) -> Enumerated<vec::IntoIter<T>, I, T> {
278 self.raw
279 .into_iter()
280 .enumerate()
281 .map(|(i, t)| (I::from_usize(i), t))
282 }
283
284 #[inline]
288 pub fn splice<R, It>(
289 &mut self,
290 range: R,
291 replace_with: It,
292 ) -> vec::Splice<<It as IntoIterator>::IntoIter>
293 where
294 It: IntoIterator<Item = T>,
295 R: IdxRangeBounds<I>,
296 {
297 self.raw.splice(range.into_range(), replace_with)
298 }
299
300 #[inline]
303 pub fn drain_enumerated<R: IdxRangeBounds<I>>(
304 &mut self,
305 range: R,
306 ) -> Enumerated<vec::Drain<'_, T>, I, T> {
307 self.raw
308 .drain(range.into_range())
309 .enumerate()
310 .map(|(i, t)| (I::from_usize(i), t))
311 }
312
313 #[inline]
316 pub fn next_idx(&self) -> I {
317 I::from_usize(self.len())
318 }
319
320 #[inline(always)]
322 pub fn as_raw_slice(&self) -> &[T] {
323 &self.raw
324 }
325
326 #[inline(always)]
328 pub fn as_raw_slice_mut(&mut self) -> &mut [T] {
329 &mut self.raw
330 }
331
332 #[inline(always)]
334 pub fn as_vec(&self) -> &Vec<T> {
335 &self.raw
336 }
337
338 #[inline(always)]
341 pub fn as_mut_vec(&mut self) -> &mut Vec<T> {
342 &mut self.raw
343 }
344
345 #[inline]
347 pub fn push(&mut self, d: T) -> I {
348 let idx = I::from_usize(self.len());
349 self.raw.push(d);
350 idx
351 }
352
353 #[inline]
355 pub fn pop(&mut self) -> Option<T> {
356 self.raw.pop()
357 }
358
359 #[inline]
361 pub fn into_boxed_slice(self) -> alloc::boxed::Box<IndexSlice<I, [T]>> {
362 let b = self.raw.into_boxed_slice();
363 unsafe { Box::from_raw(Box::into_raw(b) as *mut IndexSlice<I, [T]>) }
364 }
365
366 #[inline]
372 pub fn drain<R: IdxRangeBounds<I>>(&mut self, range: R) -> vec::Drain<'_, T> {
373 self.raw.drain(range.into_range())
374 }
375
376 #[inline]
378 pub fn shrink_to_fit(&mut self) {
379 self.raw.shrink_to_fit()
380 }
381
382 #[inline]
385 pub fn truncate(&mut self, a: usize) {
386 self.raw.truncate(a)
387 }
388
389 #[inline]
391 pub fn clear(&mut self) {
392 self.raw.clear()
393 }
394
395 #[inline]
397 pub fn reserve(&mut self, c: usize) {
398 self.raw.reserve(c)
399 }
400
401 #[inline]
403 pub fn get<J: IdxSliceIndex<I, T>>(&self, index: J) -> Option<&J::Output> {
404 index.get(self.as_slice())
405 }
406
407 #[inline]
410 pub fn get_mut<J: IdxSliceIndex<I, T>>(&mut self, index: J) -> Option<&mut J::Output> {
411 index.get_mut(self.as_mut_slice())
412 }
413
414 #[inline]
416 pub fn resize(&mut self, new_len: usize, value: T)
417 where
418 T: Clone,
419 {
420 self.raw.resize(new_len, value)
421 }
422
423 #[inline]
425 pub fn resize_with<F: FnMut() -> T>(&mut self, new_len: usize, f: F) {
426 self.raw.resize_with(new_len, f)
427 }
428
429 #[inline]
432 pub fn append(&mut self, other: &mut Self) {
433 self.raw.append(&mut other.raw)
434 }
435
436 #[inline]
439 pub fn split_off(&mut self, idx: I) -> Self {
440 Self::from_vec(self.raw.split_off(idx.index()))
441 }
442
443 #[inline]
445 pub fn remove(&mut self, index: I) -> T {
446 self.raw.remove(index.index())
447 }
448
449 #[inline]
452 pub fn swap_remove(&mut self, index: I) -> T {
453 self.raw.swap_remove(index.index())
454 }
455
456 #[inline]
458 pub fn insert(&mut self, index: I, element: T) {
459 self.raw.insert(index.index(), element)
460 }
461
462 #[inline]
466 pub fn extend_from_slice(&mut self, other: &IndexSlice<I, [T]>)
467 where
468 T: Clone,
469 {
470 self.raw.extend_from_slice(&other.raw)
471 }
472
473 #[inline]
475 pub fn retain<F: FnMut(&T) -> bool>(&mut self, f: F) {
476 self.raw.retain(f)
477 }
478
479 #[inline]
481 pub fn dedup_by_key<F: FnMut(&mut T) -> K, K: PartialEq>(&mut self, key: F) {
482 self.raw.dedup_by_key(key)
483 }
484
485 #[inline]
487 pub fn dedup(&mut self)
488 where
489 T: PartialEq,
490 {
491 self.raw.dedup()
492 }
493
494 #[inline]
496 pub fn dedup_by<F: FnMut(&mut T, &mut T) -> bool>(&mut self, same_bucket: F) {
497 self.raw.dedup_by(same_bucket)
498 }
499
500 #[inline(always)]
503 pub fn as_slice(&self) -> &IndexSlice<I, [T]> {
504 IndexSlice::new(&self.raw)
505 }
506
507 #[inline(always)]
510 pub fn as_mut_slice(&mut self) -> &mut IndexSlice<I, [T]> {
511 IndexSlice::new_mut(&mut self.raw)
512 }
513}
514
515impl<I: Idx, T> Default for IndexVec<I, T> {
516 #[inline]
517 fn default() -> Self {
518 Self::new()
519 }
520}
521
522impl<I: Idx, T> Extend<T> for IndexVec<I, T> {
523 #[inline]
524 fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) {
525 self.raw.extend(iter);
526 }
527}
528
529impl<'a, I: Idx, T: 'a + Copy> Extend<&'a T> for IndexVec<I, T> {
530 #[inline]
531 fn extend<J: IntoIterator<Item = &'a T>>(&mut self, iter: J) {
532 self.raw.extend(iter);
533 }
534}
535
536impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> {
537 #[inline]
538 fn from_iter<J>(iter: J) -> Self
539 where
540 J: IntoIterator<Item = T>,
541 {
542 IndexVec {
543 raw: FromIterator::from_iter(iter),
544 _marker: PhantomData,
545 }
546 }
547}
548
549impl<I: Idx, T> IntoIterator for IndexVec<I, T> {
550 type Item = T;
551 type IntoIter = vec::IntoIter<T>;
552
553 #[inline]
554 fn into_iter(self) -> vec::IntoIter<T> {
555 self.raw.into_iter()
556 }
557}
558
559impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> {
560 type Item = &'a T;
561 type IntoIter = slice::Iter<'a, T>;
562
563 #[inline]
564 fn into_iter(self) -> slice::Iter<'a, T> {
565 self.raw.iter()
566 }
567}
568
569impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> {
570 type Item = &'a mut T;
571 type IntoIter = slice::IterMut<'a, T>;
572
573 #[inline]
574 fn into_iter(self) -> slice::IterMut<'a, T> {
575 self.raw.iter_mut()
576 }
577}
578
579impl<I: Idx, T> From<IndexVec<I, T>> for Box<IndexSlice<I, [T]>> {
580 #[inline]
581 fn from(src: IndexVec<I, T>) -> Self {
582 src.into_boxed_slice()
583 }
584}
585
586impl<I: Idx, T> From<Box<IndexSlice<I, [T]>>> for IndexVec<I, T> {
587 #[inline]
588 fn from(src: Box<IndexSlice<I, [T]>>) -> Self {
589 src.into_vec()
590 }
591}
592
593impl<'a, I: Idx, T> From<Cow<'a, IndexSlice<I, [T]>>> for IndexVec<I, T>
594where
595 IndexSlice<I, [T]>: ToOwned<Owned = IndexVec<I, T>>,
596{
597 #[inline]
598 fn from(s: Cow<'a, IndexSlice<I, [T]>>) -> IndexVec<I, T> {
599 s.into_owned()
600 }
601}
602
603impl<'a, I: Idx, T: Clone> From<&'a IndexSlice<I, [T]>> for IndexVec<I, T> {
604 #[inline]
605 fn from(src: &'a IndexSlice<I, [T]>) -> Self {
606 src.to_owned()
607 }
608}
609impl<'a, I: Idx, T: Clone> From<&'a mut IndexSlice<I, [T]>> for IndexVec<I, T> {
610 #[inline]
611 fn from(src: &'a mut IndexSlice<I, [T]>) -> Self {
612 src.to_owned()
613 }
614}
615
616impl<I: Idx, T> From<Vec<T>> for IndexVec<I, T> {
617 #[inline]
618 fn from(v: Vec<T>) -> Self {
619 Self {
620 raw: v,
621 _marker: PhantomData,
622 }
623 }
624}
625
626impl<I: Idx, T: Clone> Clone for IndexVec<I, T> {
627 #[inline]
628 fn clone(&self) -> Self {
629 Self {
630 raw: self.raw.clone(),
631 _marker: PhantomData,
632 }
633 }
634 #[inline]
635 fn clone_from(&mut self, o: &Self) {
636 self.raw.clone_from(&o.raw);
637 }
638}
639
640impl<I: Idx, A> AsRef<[A]> for IndexVec<I, A> {
641 #[inline]
642 fn as_ref(&self) -> &[A] {
643 &self.raw
644 }
645}
646
647impl<I: Idx, A> AsMut<[A]> for IndexVec<I, A> {
648 #[inline]
649 fn as_mut(&mut self) -> &mut [A] {
650 &mut self.raw
651 }
652}
653
654impl<I: Idx, A> AsRef<IndexSlice<I, [A]>> for IndexVec<I, A> {
655 #[inline]
656 fn as_ref(&self) -> &IndexSlice<I, [A]> {
657 IndexSlice::new(&self.raw)
658 }
659}
660
661impl<I: Idx, A> AsMut<IndexSlice<I, [A]>> for IndexVec<I, A> {
662 #[inline]
663 fn as_mut(&mut self) -> &mut IndexSlice<I, [A]> {
664 IndexSlice::new_mut(&mut self.raw)
665 }
666}
667
668impl<I: Idx, A> core::ops::Deref for IndexVec<I, A> {
669 type Target = IndexSlice<I, [A]>;
670 #[inline]
671 fn deref(&self) -> &IndexSlice<I, [A]> {
672 IndexSlice::new(&self.raw)
673 }
674}
675
676impl<I: Idx, A> core::ops::DerefMut for IndexVec<I, A> {
677 #[inline]
678 fn deref_mut(&mut self) -> &mut IndexSlice<I, [A]> {
679 IndexSlice::new_mut(&mut self.raw)
680 }
681}
682
683impl<I: Idx, T> Borrow<IndexSlice<I, [T]>> for IndexVec<I, T> {
684 #[inline]
685 fn borrow(&self) -> &IndexSlice<I, [T]> {
686 self.as_slice()
687 }
688}
689
690impl<I: Idx, T> BorrowMut<IndexSlice<I, [T]>> for IndexVec<I, T> {
691 #[inline]
692 fn borrow_mut(&mut self) -> &mut IndexSlice<I, [T]> {
693 self.as_mut_slice()
694 }
695}
696
697macro_rules! impl_partialeq {
698 ($Lhs: ty, $Rhs: ty) => {
699 impl<'a, 'b, A, B, I: Idx> PartialEq<$Rhs> for $Lhs
700 where
701 A: PartialEq<B>,
702 {
703 #[inline]
704 fn eq(&self, other: &$Rhs) -> bool {
705 self[..] == other[..]
706 }
707 #[inline]
708 fn ne(&self, other: &$Rhs) -> bool {
709 self[..] != other[..]
710 }
711 }
712 };
713}
714
715macro_rules! impl_partialeq2 {
716 ($Lhs: ty, $Rhs: ty) => {
717 impl<'a, 'b, A, B, I: Idx, J: Idx> PartialEq<$Rhs> for $Lhs
718 where
719 A: PartialEq<B>,
720 {
721 #[inline]
722 fn eq(&self, other: &$Rhs) -> bool {
723 self.raw[..] == other.raw[..]
724 }
725 #[inline]
726 fn ne(&self, other: &$Rhs) -> bool {
727 self.raw[..] != other.raw[..]
728 }
729 }
730 };
731}
732
733impl_partialeq! { IndexVec<I, A>, Vec<B> }
734impl_partialeq! { IndexVec<I, A>, &'b [B] }
735impl_partialeq! { IndexVec<I, A>, &'b mut [B] }
736
737impl_partialeq2! { IndexVec<I, A>, &'b IndexSlice<J, [B]> }
738impl_partialeq2! { IndexVec<I, A>, &'b mut IndexSlice<J, [B]> }
739
740impl_partialeq! { &'a IndexSlice<I, [A]>, Vec<B> }
741impl_partialeq! { &'a mut IndexSlice<I, [A]>, Vec<B> }
742
743impl_partialeq! { IndexSlice<I, [A]>, &'b [B] }
744impl_partialeq! { IndexSlice<I, [A]>, &'b mut [B] }
745
746impl_partialeq2! { &'a IndexSlice<I, [A]>, IndexVec<J, B> }
747impl_partialeq2! { &'a mut IndexSlice<I, [A]>, IndexVec<J, B> }
748
749impl_partialeq2! { IndexSlice<I, [A]>, &'a IndexSlice<J, [B]> }
750impl_partialeq2! { IndexSlice<I, [A]>, &'a mut IndexSlice<J, [B]> }
751
752macro_rules! array_impls {
753 ($($N: expr)+) => {$(
754 impl_partialeq! { IndexVec<I, A>, [B; $N] }
755 impl_partialeq! { IndexVec<I, A>, &'b [B; $N] }
756 impl_partialeq! { IndexSlice<I, [A]>, [B; $N] }
757 impl_partialeq! { IndexSlice<I, [A]>, &'b [B; $N] }
758 )+};
761}
762
763array_impls! {
764 0 1 2 3 4 5 6 7 8 9
765 10 11 12 13 14 15 16 17 18 19
766 20 21 22 23 24 25 26 27 28 29
767 30 31 32
768}
769
770#[inline(never)]
771#[cold]
772#[doc(hidden)]
773pub fn __max_check_fail(u: usize, max: usize) -> ! {
774 panic!(
775 "index_vec index overflow: {} is outside the range [0, {})",
776 u, max,
777 )
778}
779
780#[cfg(feature = "serde")]
781impl<I: Idx, T: serde::ser::Serialize> serde::ser::Serialize for IndexVec<I, T> {
782 fn serialize<S: serde::ser::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
783 self.raw.serialize(serializer)
784 }
785}
786
787#[cfg(feature = "serde")]
788impl<'de, I: Idx, T: serde::de::Deserialize<'de>> serde::de::Deserialize<'de> for IndexVec<I, T> {
789 fn deserialize<D: serde::de::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
790 Vec::deserialize(deserializer).map(Self::from_vec)
791 }
792}
793
794#[cfg(feature = "serde")]
795impl<I: Idx, T: serde::ser::Serialize> serde::ser::Serialize for IndexBox<I, T> {
796 fn serialize<S: serde::ser::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
797 self.raw.serialize(serializer)
798 }
799}
800
801#[cfg(feature = "serde")]
802impl<'de, I: Idx, T: serde::de::Deserialize<'de>> serde::de::Deserialize<'de> for IndexBox<I, [T]> {
803 fn deserialize<D: serde::de::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
804 Box::<[T]>::deserialize(deserializer).map(Into::into)
805 }
806}
807
808#[cfg(feature = "rkyv")]
809impl<I: Idx, T: rkyv::Archive> rkyv::Archive for IndexVec<I, T> {
810 type Archived = <Vec<T> as rkyv::Archive>::Archived;
811 type Resolver = <Vec<T> as rkyv::Archive>::Resolver;
812
813 #[inline]
814 unsafe fn resolve(&self, pos: usize, resolver: Self::Resolver, out: *mut Self::Archived) {
815 self.raw.resolve(pos, resolver, out)
816 }
817}
818
819#[cfg(feature = "rkyv")]
820impl<
821 I: Idx,
822 T: rkyv::Serialize<S>,
823 S: rkyv::ser::ScratchSpace + rkyv::ser::Serializer + ?Sized,
824 > rkyv::Serialize<S> for IndexVec<I, T>
825{
826 #[inline]
827 fn serialize(
828 &self,
829 serializer: &mut S,
830 ) -> Result<Self::Resolver, <S as rkyv::Fallible>::Error> {
831 self.raw.serialize(serializer)
832 }
833}
834
835#[cfg(feature = "rkyv")]
836impl<I: Idx, T: rkyv::Archive, D: rkyv::Fallible + ?Sized> rkyv::Deserialize<IndexVec<I, T>, D>
837 for rkyv::vec::ArchivedVec<T::Archived>
838where
839 [T::Archived]: rkyv::DeserializeUnsized<[T], D>,
840{
841 #[inline]
842 fn deserialize(&self, deserializer: &mut D) -> Result<IndexVec<I, T>, D::Error> {
843 let raw = rkyv::vec::ArchivedVec::deserialize(self, deserializer)?;
844
845 Ok(IndexVec::from_vec(raw))
846 }
847}