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
))
175 pub fn indices(&self) -> impl DoubleEndedIterator
<Item
= I
> + ExactSizeIterator
+ '
static {
176 (0..self.len()).map(|n
| I
::new(n
))
180 pub fn iter_mut(&mut self) -> slice
::IterMut
<'_
, T
> {
185 pub fn iter_enumerated_mut(
187 ) -> impl DoubleEndedIterator
<Item
= (I
, &mut T
)> + ExactSizeIterator
+ '_
{
188 self.raw
.iter_mut().enumerate().map(|(n
, t
)| (I
::new(n
), t
))
192 pub fn drain
<'a
, R
: RangeBounds
<usize>>(
195 ) -> impl Iterator
<Item
= T
> + 'a
{
196 self.raw
.drain(range
)
200 pub fn drain_enumerated
<'a
, R
: RangeBounds
<usize>>(
203 ) -> impl Iterator
<Item
= (I
, T
)> + 'a
{
204 self.raw
.drain(range
).enumerate().map(|(n
, t
)| (I
::new(n
), t
))
208 pub fn last(&self) -> Option
<I
> {
209 self.len().checked_sub(1).map(I
::new
)
213 pub fn shrink_to_fit(&mut self) {
214 self.raw
.shrink_to_fit()
218 pub fn swap(&mut self, a
: I
, b
: I
) {
219 self.raw
.swap(a
.index(), b
.index())
223 pub fn truncate(&mut self, a
: usize) {
228 pub fn get(&self, index
: I
) -> Option
<&T
> {
229 self.raw
.get(index
.index())
233 pub fn get_mut(&mut self, index
: I
) -> Option
<&mut T
> {
234 self.raw
.get_mut(index
.index())
237 /// Returns mutable references to two distinct elements, a and b. Panics if a == b.
239 pub fn pick2_mut(&mut self, a
: I
, b
: I
) -> (&mut T
, &mut T
) {
240 let (ai
, bi
) = (a
.index(), b
.index());
244 let (c1
, c2
) = self.raw
.split_at_mut(bi
);
245 (&mut c1
[ai
], &mut c2
[0])
247 let (c2
, c1
) = self.pick2_mut(b
, a
);
252 /// Returns mutable references to three distinct elements or panics otherwise.
254 pub fn pick3_mut(&mut self, a
: I
, b
: I
, c
: I
) -> (&mut T
, &mut T
, &mut T
) {
255 let (ai
, bi
, ci
) = (a
.index(), b
.index(), c
.index());
256 assert
!(ai
!= bi
&& bi
!= ci
&& ci
!= ai
);
257 let len
= self.raw
.len();
258 assert
!(ai
< len
&& bi
< len
&& ci
< len
);
259 let ptr
= self.raw
.as_mut_ptr();
260 unsafe { (&mut *ptr.add(ai), &mut *ptr.add(bi), &mut *ptr.add(ci)) }
263 pub fn convert_index_type
<Ix
: Idx
>(self) -> IndexVec
<Ix
, T
> {
264 IndexVec { raw: self.raw, _marker: PhantomData }
267 /// Grows the index vector so that it contains an entry for
268 /// `elem`; if that is already true, then has no
269 /// effect. Otherwise, inserts new values as needed by invoking
272 pub fn ensure_contains_elem(&mut self, elem
: I
, fill_value
: impl FnMut() -> T
) {
273 let min_new_len
= elem
.index() + 1;
274 if self.len() < min_new_len
{
275 self.raw
.resize_with(min_new_len
, fill_value
);
280 pub fn resize_to_elem(&mut self, elem
: I
, fill_value
: impl FnMut() -> T
) {
281 let min_new_len
= elem
.index() + 1;
282 self.raw
.resize_with(min_new_len
, fill_value
);
286 /// `IndexVec` is often used as a map, so it provides some map-like APIs.
287 impl<I
: Idx
, T
> IndexVec
<I
, Option
<T
>> {
289 pub fn insert(&mut self, index
: I
, value
: T
) -> Option
<T
> {
290 self.ensure_contains_elem(index
, || None
);
291 self[index
].replace(value
)
295 pub fn get_or_insert_with(&mut self, index
: I
, value
: impl FnOnce() -> T
) -> &mut T
{
296 self.ensure_contains_elem(index
, || None
);
297 self[index
].get_or_insert_with(value
)
301 pub fn remove(&mut self, index
: I
) -> Option
<T
> {
302 self.ensure_contains_elem(index
, || None
);
307 impl<I
: Idx
, T
: Clone
> IndexVec
<I
, T
> {
309 pub fn resize(&mut self, new_len
: usize, value
: T
) {
310 self.raw
.resize(new_len
, value
)
314 impl<I
: Idx
, T
: Ord
> IndexVec
<I
, T
> {
316 pub fn binary_search(&self, value
: &T
) -> Result
<I
, I
> {
317 match self.raw
.binary_search(value
) {
318 Ok(i
) => Ok(Idx
::new(i
)),
319 Err(i
) => Err(Idx
::new(i
)),
324 impl<I
: Idx
, T
> Index
<I
> for IndexVec
<I
, T
> {
328 fn index(&self, index
: I
) -> &T
{
329 &self.raw
[index
.index()]
333 impl<I
: Idx
, T
> IndexMut
<I
> for IndexVec
<I
, T
> {
335 fn index_mut(&mut self, index
: I
) -> &mut T
{
336 &mut self.raw
[index
.index()]
340 impl<I
: Idx
, T
> Default
for IndexVec
<I
, T
> {
342 fn default() -> Self {
347 impl<I
: Idx
, T
> Extend
<T
> for IndexVec
<I
, T
> {
349 fn extend
<J
: IntoIterator
<Item
= T
>>(&mut self, iter
: J
) {
350 self.raw
.extend(iter
);
354 fn extend_one(&mut self, item
: T
) {
359 fn extend_reserve(&mut self, additional
: usize) {
360 self.raw
.reserve(additional
);
364 impl<I
: Idx
, T
> FromIterator
<T
> for IndexVec
<I
, T
> {
366 fn from_iter
<J
>(iter
: J
) -> Self
368 J
: IntoIterator
<Item
= T
>,
370 IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData }
374 impl<I
: Idx
, T
> IntoIterator
for IndexVec
<I
, T
> {
376 type IntoIter
= vec
::IntoIter
<T
>;
379 fn into_iter(self) -> vec
::IntoIter
<T
> {
384 impl<'a
, I
: Idx
, T
> IntoIterator
for &'a IndexVec
<I
, T
> {
386 type IntoIter
= slice
::Iter
<'a
, T
>;
389 fn into_iter(self) -> slice
::Iter
<'a
, T
> {
394 impl<'a
, I
: Idx
, T
> IntoIterator
for &'a
mut IndexVec
<I
, T
> {
395 type Item
= &'a
mut T
;
396 type IntoIter
= slice
::IterMut
<'a
, T
>;
399 fn into_iter(self) -> slice
::IterMut
<'a
, T
> {