1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use std
::collections
::range
::RangeArgument
;
13 use std
::iter
::{self, FromIterator}
;
15 use std
::marker
::PhantomData
;
16 use std
::ops
::{Index, IndexMut, Range}
;
21 use rustc_serialize
as serialize
;
23 /// Represents some newtyped `usize` wrapper.
25 /// (purpose: avoid mixing indexes for different bitvector domains.)
26 pub trait Idx
: Copy
+ '
static + Eq
+ Debug
{
27 fn new(idx
: usize) -> Self;
28 fn index(self) -> usize;
32 fn new(idx
: usize) -> Self { idx }
33 fn index(self) -> usize { self }
37 fn new(idx
: usize) -> Self { assert!(idx <= u32::MAX as usize); idx as u32 }
38 fn index(self) -> usize { self as usize }
42 pub struct IndexVec
<I
: Idx
, T
> {
44 _marker
: PhantomData
<Fn(&I
)>
47 impl<I
: Idx
, T
: serialize
::Encodable
> serialize
::Encodable
for IndexVec
<I
, T
> {
48 fn encode
<S
: serialize
::Encoder
>(&self, s
: &mut S
) -> Result
<(), S
::Error
> {
49 serialize
::Encodable
::encode(&self.raw
, s
)
53 impl<I
: Idx
, T
: serialize
::Decodable
> serialize
::Decodable
for IndexVec
<I
, T
> {
54 fn decode
<D
: serialize
::Decoder
>(d
: &mut D
) -> Result
<Self, D
::Error
> {
55 serialize
::Decodable
::decode(d
).map(|v
| {
56 IndexVec { raw: v, _marker: PhantomData }
61 impl<I
: Idx
, T
: fmt
::Debug
> fmt
::Debug
for IndexVec
<I
, T
> {
62 fn fmt(&self, fmt
: &mut fmt
::Formatter
) -> fmt
::Result
{
63 fmt
::Debug
::fmt(&self.raw
, fmt
)
67 pub type Enumerated
<I
, J
> = iter
::Map
<iter
::Enumerate
<J
>, IntoIdx
<I
>>;
69 impl<I
: Idx
, T
> IndexVec
<I
, T
> {
71 pub fn new() -> Self {
72 IndexVec { raw: Vec::new(), _marker: PhantomData }
76 pub fn with_capacity(capacity
: usize) -> Self {
77 IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData }
81 pub fn from_elem
<S
>(elem
: T
, universe
: &IndexVec
<I
, S
>) -> Self
84 IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData }
88 pub fn from_elem_n(elem
: T
, n
: usize) -> Self
91 IndexVec { raw: vec![elem; n], _marker: PhantomData }
95 pub fn push(&mut self, d
: T
) -> I
{
96 let idx
= I
::new(self.len());
102 pub fn len(&self) -> usize {
107 pub fn is_empty(&self) -> bool
{
112 pub fn into_iter(self) -> vec
::IntoIter
<T
> {
117 pub fn into_iter_enumerated(self) -> Enumerated
<I
, vec
::IntoIter
<T
>>
119 self.raw
.into_iter().enumerate().map(IntoIdx { _marker: PhantomData }
)
123 pub fn iter(&self) -> slice
::Iter
<T
> {
128 pub fn iter_enumerated(&self) -> Enumerated
<I
, slice
::Iter
<T
>>
130 self.raw
.iter().enumerate().map(IntoIdx { _marker: PhantomData }
)
134 pub fn indices(&self) -> iter
::Map
<Range
<usize>, IntoIdx
<I
>> {
135 (0..self.len()).map(IntoIdx { _marker: PhantomData }
)
139 pub fn iter_mut(&mut self) -> slice
::IterMut
<T
> {
144 pub fn iter_enumerated_mut(&mut self) -> Enumerated
<I
, slice
::IterMut
<T
>>
146 self.raw
.iter_mut().enumerate().map(IntoIdx { _marker: PhantomData }
)
150 pub fn drain
<'a
, R
: RangeArgument
<usize>>(
151 &'a
mut self, range
: R
) -> impl Iterator
<Item
=T
> + 'a
{
152 self.raw
.drain(range
)
156 pub fn drain_enumerated
<'a
, R
: RangeArgument
<usize>>(
157 &'a
mut self, range
: R
) -> impl Iterator
<Item
=(I
, T
)> + 'a
{
158 self.raw
.drain(range
).enumerate().map(IntoIdx { _marker: PhantomData }
)
162 pub fn last(&self) -> Option
<I
> {
163 self.len().checked_sub(1).map(I
::new
)
167 pub fn shrink_to_fit(&mut self) {
168 self.raw
.shrink_to_fit()
172 pub fn swap(&mut self, a
: usize, b
: usize) {
177 pub fn truncate(&mut self, a
: usize) {
182 pub fn get(&self, index
: I
) -> Option
<&T
> {
183 self.raw
.get(index
.index())
187 pub fn get_mut(&mut self, index
: I
) -> Option
<&mut T
> {
188 self.raw
.get_mut(index
.index())
192 impl<I
: Idx
, T
: Clone
> IndexVec
<I
, T
> {
194 pub fn resize(&mut self, new_len
: usize, value
: T
) {
195 self.raw
.resize(new_len
, value
)
199 impl<I
: Idx
, T
> Index
<I
> for IndexVec
<I
, T
> {
203 fn index(&self, index
: I
) -> &T
{
204 &self.raw
[index
.index()]
208 impl<I
: Idx
, T
> IndexMut
<I
> for IndexVec
<I
, T
> {
210 fn index_mut(&mut self, index
: I
) -> &mut T
{
211 &mut self.raw
[index
.index()]
215 impl<I
: Idx
, T
> Default
for IndexVec
<I
, T
> {
217 fn default() -> Self {
222 impl<I
: Idx
, T
> Extend
<T
> for IndexVec
<I
, T
> {
224 fn extend
<J
: IntoIterator
<Item
= T
>>(&mut self, iter
: J
) {
225 self.raw
.extend(iter
);
229 impl<I
: Idx
, T
> FromIterator
<T
> for IndexVec
<I
, T
> {
231 fn from_iter
<J
>(iter
: J
) -> Self where J
: IntoIterator
<Item
=T
> {
232 IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData }
236 impl<I
: Idx
, T
> IntoIterator
for IndexVec
<I
, T
> {
238 type IntoIter
= vec
::IntoIter
<T
>;
241 fn into_iter(self) -> vec
::IntoIter
<T
> {
247 impl<'a
, I
: Idx
, T
> IntoIterator
for &'a IndexVec
<I
, T
> {
249 type IntoIter
= slice
::Iter
<'a
, T
>;
252 fn into_iter(self) -> slice
::Iter
<'a
, T
> {
257 impl<'a
, I
: Idx
, T
> IntoIterator
for &'a
mut IndexVec
<I
, T
> {
258 type Item
= &'a
mut T
;
259 type IntoIter
= slice
::IterMut
<'a
, T
>;
262 fn into_iter(mut self) -> slice
::IterMut
<'a
, T
> {
267 pub struct IntoIdx
<I
: Idx
> { _marker: PhantomData<fn(&I)> }
268 impl<I
: Idx
, T
> FnOnce
<((usize, T
),)> for IntoIdx
<I
> {
269 type Output
= (I
, T
);
271 extern "rust-call" fn call_once(self, ((n
, t
),): ((usize, T
),)) -> Self::Output
{
276 impl<I
: Idx
, T
> FnMut
<((usize, T
),)> for IntoIdx
<I
> {
277 extern "rust-call" fn call_mut(&mut self, ((n
, t
),): ((usize, T
),)) -> Self::Output
{
282 impl<I
: Idx
> FnOnce
<(usize,)> for IntoIdx
<I
> {
285 extern "rust-call" fn call_once(self, (n
,): (usize,)) -> Self::Output
{
290 impl<I
: Idx
> FnMut
<(usize,)> for IntoIdx
<I
> {
291 extern "rust-call" fn call_mut(&mut self, (n
,): (usize,)) -> Self::Output
{