1 use rustc_serialize
::{Decodable, Decoder, Encodable, Encoder}
;
6 use std
::iter
::FromIterator
;
7 use std
::marker
::PhantomData
;
8 use std
::ops
::{Index, IndexMut, RangeBounds}
;
12 /// Represents some newtyped `usize` wrapper.
14 /// Purpose: avoid mixing indexes for different bitvector domains.
15 pub trait Idx
: Copy
+ '
static + Eq
+ PartialEq
+ Debug
+ Hash
{
16 fn new(idx
: usize) -> Self;
18 fn index(self) -> usize;
20 fn increment_by(&mut self, amount
: usize) {
21 *self = self.plus(amount
);
24 fn plus(self, amount
: usize) -> Self {
25 Self::new(self.index() + amount
)
31 fn new(idx
: usize) -> Self {
35 fn index(self) -> usize {
42 fn new(idx
: usize) -> Self {
43 assert
!(idx
<= u32::MAX
as usize);
47 fn index(self) -> usize {
52 #[derive(Clone, PartialEq, Eq, Hash)]
53 pub struct IndexVec
<I
: Idx
, T
> {
55 _marker
: PhantomData
<fn(&I
)>,
58 // Whether `IndexVec` is `Send` depends only on the data,
59 // not the phantom data.
60 unsafe impl<I
: Idx
, T
> Send
for IndexVec
<I
, T
> where T
: Send {}
62 impl<S
: Encoder
, I
: Idx
, T
: Encodable
<S
>> Encodable
<S
> for IndexVec
<I
, T
> {
63 fn encode(&self, s
: &mut S
) {
64 Encodable
::encode(&self.raw
, s
);
68 impl<D
: Decoder
, I
: Idx
, T
: Decodable
<D
>> Decodable
<D
> for IndexVec
<I
, T
> {
69 fn decode(d
: &mut D
) -> Self {
70 IndexVec { raw: Decodable::decode(d), _marker: PhantomData }
74 impl<I
: Idx
, T
: fmt
::Debug
> fmt
::Debug
for IndexVec
<I
, T
> {
75 fn fmt(&self, fmt
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
76 fmt
::Debug
::fmt(&self.raw
, fmt
)
80 impl<I
: Idx
, T
> IndexVec
<I
, T
> {
82 pub fn new() -> Self {
83 IndexVec { raw: Vec::new(), _marker: PhantomData }
87 pub fn from_raw(raw
: Vec
<T
>) -> Self {
88 IndexVec { raw, _marker: PhantomData }
92 pub fn with_capacity(capacity
: usize) -> Self {
93 IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData }
97 pub fn from_elem
<S
>(elem
: T
, universe
: &IndexVec
<I
, S
>) -> Self
101 IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData }
105 pub fn from_elem_n(elem
: T
, n
: usize) -> Self
109 IndexVec { raw: vec![elem; n], _marker: PhantomData }
112 /// Create an `IndexVec` with `n` elements, where the value of each
113 /// element is the result of `func(i)`. (The underlying vector will
114 /// be allocated only once, with a capacity of at least `n`.)
116 pub fn from_fn_n(func
: impl FnMut(I
) -> T
, n
: usize) -> Self {
117 let indices
= (0..n
).map(I
::new
);
118 Self::from_raw(indices
.map(func
).collect())
122 pub fn push(&mut self, d
: T
) -> I
{
123 let idx
= I
::new(self.len());
129 pub fn pop(&mut self) -> Option
<T
> {
134 pub fn len(&self) -> usize {
138 /// Gives the next index that will be assigned when `push` is
141 pub fn next_index(&self) -> I
{
146 pub fn is_empty(&self) -> bool
{
151 pub fn into_iter(self) -> vec
::IntoIter
<T
> {
156 pub fn into_iter_enumerated(
158 ) -> impl DoubleEndedIterator
<Item
= (I
, T
)> + ExactSizeIterator
{
159 self.raw
.into_iter().enumerate().map(|(n
, t
)| (I
::new(n
), t
))
163 pub fn iter(&self) -> slice
::Iter
<'_
, T
> {
168 pub fn iter_enumerated(
170 ) -> impl DoubleEndedIterator
<Item
= (I
, &T
)> + ExactSizeIterator
+ '_
{
171 self.raw
.iter().enumerate().map(|(n
, t
)| (I
::new(n
), t
))
177 ) -> impl DoubleEndedIterator
<Item
= I
> + ExactSizeIterator
+ Clone
+ '
static {
178 (0..self.len()).map(|n
| I
::new(n
))
182 pub fn iter_mut(&mut self) -> slice
::IterMut
<'_
, T
> {
187 pub fn iter_enumerated_mut(
189 ) -> impl DoubleEndedIterator
<Item
= (I
, &mut T
)> + ExactSizeIterator
+ '_
{
190 self.raw
.iter_mut().enumerate().map(|(n
, t
)| (I
::new(n
), t
))
194 pub fn drain
<'a
, R
: RangeBounds
<usize>>(
197 ) -> impl Iterator
<Item
= T
> + 'a
{
198 self.raw
.drain(range
)
202 pub fn drain_enumerated
<'a
, R
: RangeBounds
<usize>>(
205 ) -> impl Iterator
<Item
= (I
, T
)> + 'a
{
206 self.raw
.drain(range
).enumerate().map(|(n
, t
)| (I
::new(n
), t
))
210 pub fn last(&self) -> Option
<I
> {
211 self.len().checked_sub(1).map(I
::new
)
215 pub fn shrink_to_fit(&mut self) {
216 self.raw
.shrink_to_fit()
220 pub fn swap(&mut self, a
: I
, b
: I
) {
221 self.raw
.swap(a
.index(), b
.index())
225 pub fn truncate(&mut self, a
: usize) {
230 pub fn get(&self, index
: I
) -> Option
<&T
> {
231 self.raw
.get(index
.index())
235 pub fn get_mut(&mut self, index
: I
) -> Option
<&mut T
> {
236 self.raw
.get_mut(index
.index())
239 /// Returns mutable references to two distinct elements, `a` and `b`.
241 /// Panics if `a == b`.
243 pub fn pick2_mut(&mut self, a
: I
, b
: I
) -> (&mut T
, &mut T
) {
244 let (ai
, bi
) = (a
.index(), b
.index());
248 let (c1
, c2
) = self.raw
.split_at_mut(bi
);
249 (&mut c1
[ai
], &mut c2
[0])
251 let (c2
, c1
) = self.pick2_mut(b
, a
);
256 /// Returns mutable references to three distinct elements.
258 /// Panics if the elements are not distinct.
260 pub fn pick3_mut(&mut self, a
: I
, b
: I
, c
: I
) -> (&mut T
, &mut T
, &mut T
) {
261 let (ai
, bi
, ci
) = (a
.index(), b
.index(), c
.index());
262 assert
!(ai
!= bi
&& bi
!= ci
&& ci
!= ai
);
263 let len
= self.raw
.len();
264 assert
!(ai
< len
&& bi
< len
&& ci
< len
);
265 let ptr
= self.raw
.as_mut_ptr();
266 unsafe { (&mut *ptr.add(ai), &mut *ptr.add(bi), &mut *ptr.add(ci)) }
269 pub fn convert_index_type
<Ix
: Idx
>(self) -> IndexVec
<Ix
, T
> {
270 IndexVec { raw: self.raw, _marker: PhantomData }
273 /// Grows the index vector so that it contains an entry for
274 /// `elem`; if that is already true, then has no
275 /// effect. Otherwise, inserts new values as needed by invoking
278 pub fn ensure_contains_elem(&mut self, elem
: I
, fill_value
: impl FnMut() -> T
) {
279 let min_new_len
= elem
.index() + 1;
280 if self.len() < min_new_len
{
281 self.raw
.resize_with(min_new_len
, fill_value
);
286 pub fn resize_to_elem(&mut self, elem
: I
, fill_value
: impl FnMut() -> T
) {
287 let min_new_len
= elem
.index() + 1;
288 self.raw
.resize_with(min_new_len
, fill_value
);
292 /// `IndexVec` is often used as a map, so it provides some map-like APIs.
293 impl<I
: Idx
, T
> IndexVec
<I
, Option
<T
>> {
295 pub fn insert(&mut self, index
: I
, value
: T
) -> Option
<T
> {
296 self.ensure_contains_elem(index
, || None
);
297 self[index
].replace(value
)
301 pub fn get_or_insert_with(&mut self, index
: I
, value
: impl FnOnce() -> T
) -> &mut T
{
302 self.ensure_contains_elem(index
, || None
);
303 self[index
].get_or_insert_with(value
)
307 pub fn remove(&mut self, index
: I
) -> Option
<T
> {
308 self.ensure_contains_elem(index
, || None
);
313 impl<I
: Idx
, T
: Clone
> IndexVec
<I
, T
> {
315 pub fn resize(&mut self, new_len
: usize, value
: T
) {
316 self.raw
.resize(new_len
, value
)
320 impl<I
: Idx
, T
: Ord
> IndexVec
<I
, T
> {
322 pub fn binary_search(&self, value
: &T
) -> Result
<I
, I
> {
323 match self.raw
.binary_search(value
) {
324 Ok(i
) => Ok(Idx
::new(i
)),
325 Err(i
) => Err(Idx
::new(i
)),
330 impl<I
: Idx
, T
> Index
<I
> for IndexVec
<I
, T
> {
334 fn index(&self, index
: I
) -> &T
{
335 &self.raw
[index
.index()]
339 impl<I
: Idx
, T
> IndexMut
<I
> for IndexVec
<I
, T
> {
341 fn index_mut(&mut self, index
: I
) -> &mut T
{
342 &mut self.raw
[index
.index()]
346 impl<I
: Idx
, T
> Default
for IndexVec
<I
, T
> {
348 fn default() -> Self {
353 impl<I
: Idx
, T
> Extend
<T
> for IndexVec
<I
, T
> {
355 fn extend
<J
: IntoIterator
<Item
= T
>>(&mut self, iter
: J
) {
356 self.raw
.extend(iter
);
360 fn extend_one(&mut self, item
: T
) {
365 fn extend_reserve(&mut self, additional
: usize) {
366 self.raw
.reserve(additional
);
370 impl<I
: Idx
, T
> FromIterator
<T
> for IndexVec
<I
, T
> {
372 fn from_iter
<J
>(iter
: J
) -> Self
374 J
: IntoIterator
<Item
= T
>,
376 IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData }
380 impl<I
: Idx
, T
> IntoIterator
for IndexVec
<I
, T
> {
382 type IntoIter
= vec
::IntoIter
<T
>;
385 fn into_iter(self) -> vec
::IntoIter
<T
> {
390 impl<'a
, I
: Idx
, T
> IntoIterator
for &'a IndexVec
<I
, T
> {
392 type IntoIter
= slice
::Iter
<'a
, T
>;
395 fn into_iter(self) -> slice
::Iter
<'a
, T
> {
400 impl<'a
, I
: Idx
, T
> IntoIterator
for &'a
mut IndexVec
<I
, T
> {
401 type Item
= &'a
mut T
;
402 type IntoIter
= slice
::IterMut
<'a
, T
>;
405 fn into_iter(self) -> slice
::IterMut
<'a
, T
> {