use rustc_serialize::{Decodable, Decoder, Encodable, Encoder}; use std::fmt; use std::fmt::Debug; use std::hash::Hash; use std::iter::FromIterator; use std::marker::PhantomData; use std::ops::{Index, IndexMut, RangeBounds}; use std::slice; use std::vec; /// Represents some newtyped `usize` wrapper. /// /// Purpose: avoid mixing indexes for different bitvector domains. pub trait Idx: Copy + 'static + Eq + PartialEq + Debug + Hash { fn new(idx: usize) -> Self; fn index(self) -> usize; fn increment_by(&mut self, amount: usize) { *self = self.plus(amount); } fn plus(self, amount: usize) -> Self { Self::new(self.index() + amount) } } impl Idx for usize { #[inline] fn new(idx: usize) -> Self { idx } #[inline] fn index(self) -> usize { self } } impl Idx for u32 { #[inline] fn new(idx: usize) -> Self { assert!(idx <= u32::MAX as usize); idx as u32 } #[inline] fn index(self) -> usize { self as usize } } #[derive(Clone, PartialEq, Eq, Hash)] pub struct IndexVec { pub raw: Vec, _marker: PhantomData, } // Whether `IndexVec` is `Send` depends only on the data, // not the phantom data. unsafe impl Send for IndexVec where T: Send {} impl> Encodable for IndexVec { fn encode(&self, s: &mut S) { Encodable::encode(&self.raw, s); } } impl> Decodable for IndexVec { fn decode(d: &mut D) -> Self { IndexVec { raw: Decodable::decode(d), _marker: PhantomData } } } impl fmt::Debug for IndexVec { fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { fmt::Debug::fmt(&self.raw, fmt) } } impl IndexVec { #[inline] pub fn new() -> Self { IndexVec { raw: Vec::new(), _marker: PhantomData } } #[inline] pub fn from_raw(raw: Vec) -> Self { IndexVec { raw, _marker: PhantomData } } #[inline] pub fn with_capacity(capacity: usize) -> Self { IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData } } #[inline] pub fn from_elem(elem: T, universe: &IndexVec) -> Self where T: Clone, { IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData } } #[inline] pub fn from_elem_n(elem: T, n: usize) -> Self where T: Clone, { IndexVec { raw: vec![elem; n], _marker: PhantomData } } /// Create an `IndexVec` with `n` elements, where the value of each /// element is the result of `func(i)`. (The underlying vector will /// be allocated only once, with a capacity of at least `n`.) #[inline] pub fn from_fn_n(func: impl FnMut(I) -> T, n: usize) -> Self { let indices = (0..n).map(I::new); Self::from_raw(indices.map(func).collect()) } #[inline] pub fn push(&mut self, d: T) -> I { let idx = I::new(self.len()); self.raw.push(d); idx } #[inline] pub fn pop(&mut self) -> Option { self.raw.pop() } #[inline] pub fn len(&self) -> usize { self.raw.len() } /// Gives the next index that will be assigned when `push` is /// called. #[inline] pub fn next_index(&self) -> I { I::new(self.len()) } #[inline] pub fn is_empty(&self) -> bool { self.raw.is_empty() } #[inline] pub fn into_iter(self) -> vec::IntoIter { self.raw.into_iter() } #[inline] pub fn into_iter_enumerated( self, ) -> impl DoubleEndedIterator + ExactSizeIterator { self.raw.into_iter().enumerate().map(|(n, t)| (I::new(n), t)) } #[inline] pub fn iter(&self) -> slice::Iter<'_, T> { self.raw.iter() } #[inline] pub fn iter_enumerated( &self, ) -> impl DoubleEndedIterator + ExactSizeIterator + '_ { self.raw.iter().enumerate().map(|(n, t)| (I::new(n), t)) } #[inline] pub fn indices(&self) -> impl DoubleEndedIterator + ExactSizeIterator + 'static { (0..self.len()).map(|n| I::new(n)) } #[inline] pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> { self.raw.iter_mut() } #[inline] pub fn iter_enumerated_mut( &mut self, ) -> impl DoubleEndedIterator + ExactSizeIterator + '_ { self.raw.iter_mut().enumerate().map(|(n, t)| (I::new(n), t)) } #[inline] pub fn drain<'a, R: RangeBounds>( &'a mut self, range: R, ) -> impl Iterator + 'a { self.raw.drain(range) } #[inline] pub fn drain_enumerated<'a, R: RangeBounds>( &'a mut self, range: R, ) -> impl Iterator + 'a { self.raw.drain(range).enumerate().map(|(n, t)| (I::new(n), t)) } #[inline] pub fn last(&self) -> Option { self.len().checked_sub(1).map(I::new) } #[inline] pub fn shrink_to_fit(&mut self) { self.raw.shrink_to_fit() } #[inline] pub fn swap(&mut self, a: I, b: I) { self.raw.swap(a.index(), b.index()) } #[inline] pub fn truncate(&mut self, a: usize) { self.raw.truncate(a) } #[inline] pub fn get(&self, index: I) -> Option<&T> { self.raw.get(index.index()) } #[inline] pub fn get_mut(&mut self, index: I) -> Option<&mut T> { self.raw.get_mut(index.index()) } /// Returns mutable references to two distinct elements, `a` and `b`. /// /// Panics if `a == b`. #[inline] pub fn pick2_mut(&mut self, a: I, b: I) -> (&mut T, &mut T) { let (ai, bi) = (a.index(), b.index()); assert!(ai != bi); if ai < bi { let (c1, c2) = self.raw.split_at_mut(bi); (&mut c1[ai], &mut c2[0]) } else { let (c2, c1) = self.pick2_mut(b, a); (c1, c2) } } /// Returns mutable references to three distinct elements. /// /// Panics if the elements are not distinct. #[inline] pub fn pick3_mut(&mut self, a: I, b: I, c: I) -> (&mut T, &mut T, &mut T) { let (ai, bi, ci) = (a.index(), b.index(), c.index()); assert!(ai != bi && bi != ci && ci != ai); let len = self.raw.len(); assert!(ai < len && bi < len && ci < len); let ptr = self.raw.as_mut_ptr(); unsafe { (&mut *ptr.add(ai), &mut *ptr.add(bi), &mut *ptr.add(ci)) } } pub fn convert_index_type(self) -> IndexVec { IndexVec { raw: self.raw, _marker: PhantomData } } /// Grows the index vector so that it contains an entry for /// `elem`; if that is already true, then has no /// effect. Otherwise, inserts new values as needed by invoking /// `fill_value`. #[inline] pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) { let min_new_len = elem.index() + 1; if self.len() < min_new_len { self.raw.resize_with(min_new_len, fill_value); } } #[inline] pub fn resize_to_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) { let min_new_len = elem.index() + 1; self.raw.resize_with(min_new_len, fill_value); } } /// `IndexVec` is often used as a map, so it provides some map-like APIs. impl IndexVec> { #[inline] pub fn insert(&mut self, index: I, value: T) -> Option { self.ensure_contains_elem(index, || None); self[index].replace(value) } #[inline] pub fn get_or_insert_with(&mut self, index: I, value: impl FnOnce() -> T) -> &mut T { self.ensure_contains_elem(index, || None); self[index].get_or_insert_with(value) } #[inline] pub fn remove(&mut self, index: I) -> Option { self.ensure_contains_elem(index, || None); self[index].take() } } impl IndexVec { #[inline] pub fn resize(&mut self, new_len: usize, value: T) { self.raw.resize(new_len, value) } } impl IndexVec { #[inline] pub fn binary_search(&self, value: &T) -> Result { match self.raw.binary_search(value) { Ok(i) => Ok(Idx::new(i)), Err(i) => Err(Idx::new(i)), } } } impl Index for IndexVec { type Output = T; #[inline] fn index(&self, index: I) -> &T { &self.raw[index.index()] } } impl IndexMut for IndexVec { #[inline] fn index_mut(&mut self, index: I) -> &mut T { &mut self.raw[index.index()] } } impl Default for IndexVec { #[inline] fn default() -> Self { Self::new() } } impl Extend for IndexVec { #[inline] fn extend>(&mut self, iter: J) { self.raw.extend(iter); } #[inline] fn extend_one(&mut self, item: T) { self.raw.push(item); } #[inline] fn extend_reserve(&mut self, additional: usize) { self.raw.reserve(additional); } } impl FromIterator for IndexVec { #[inline] fn from_iter(iter: J) -> Self where J: IntoIterator, { IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData } } } impl IntoIterator for IndexVec { type Item = T; type IntoIter = vec::IntoIter; #[inline] fn into_iter(self) -> vec::IntoIter { self.raw.into_iter() } } impl<'a, I: Idx, T> IntoIterator for &'a IndexVec { 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 { type Item = &'a mut T; type IntoIter = slice::IterMut<'a, T>; #[inline] fn into_iter(self) -> slice::IterMut<'a, T> { self.raw.iter_mut() } } #[cfg(test)] mod tests;