src/librustc_data_structures/indexed_vec.rs

   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.
   4 //
   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.
  10
  11 use std::fmt::Debug;
  12 use std::iter::{self, FromIterator};
  13 use std::slice;
  14 use std::marker::PhantomData;
  15 use std::ops::{Index, IndexMut, Range};
  16 use std::fmt;
  17 use std::vec;
  18 use std::u32;
  19
  20 use rustc_serialize as serialize;
  21
  22 /// Represents some newtyped `usize` wrapper.
  23 ///
  24 /// (purpose: avoid mixing indexes for different bitvector domains.)
  25 pub trait Idx: Copy + 'static + Eq + Debug {
  26     fn new(usize) -> Self;
  27     fn index(self) -> usize;
  28 }
  29
  30 impl Idx for usize {
  31     fn new(idx: usize) -> Self { idx }
  32     fn index(self) -> usize { self }
  33 }
  34
  35 impl Idx for u32 {
  36     fn new(idx: usize) -> Self { assert!(idx <= u32::MAX as usize); idx as u32 }
  37     fn index(self) -> usize { self as usize }
  38 }
  39
  40 #[derive(Clone)]
  41 pub struct IndexVec<I: Idx, T> {
  42     pub raw: Vec<T>,
  43     _marker: PhantomData<Fn(&I)>
  44 }
  45
  46 impl<I: Idx, T: serialize::Encodable> serialize::Encodable for IndexVec<I, T> {
  47     fn encode<S: serialize::Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
  48         serialize::Encodable::encode(&self.raw, s)
  49     }
  50 }
  51
  52 impl<I: Idx, T: serialize::Decodable> serialize::Decodable for IndexVec<I, T> {
  53     fn decode<D: serialize::Decoder>(d: &mut D) -> Result<Self, D::Error> {
  54         serialize::Decodable::decode(d).map(|v| {
  55             IndexVec { raw: v, _marker: PhantomData }
  56         })
  57     }
  58 }
  59
  60 impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> {
  61     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
  62         fmt::Debug::fmt(&self.raw, fmt)
  63     }
  64 }
  65
  66 pub type Enumerated<I, J> = iter::Map<iter::Enumerate<J>, IntoIdx<I>>;
  67
  68 impl<I: Idx, T> IndexVec<I, T> {
  69     #[inline]
  70     pub fn new() -> Self {
  71         IndexVec { raw: Vec::new(), _marker: PhantomData }
  72     }
  73
  74     #[inline]
  75     pub fn with_capacity(capacity: usize) -> Self {
  76         IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData }
  77     }
  78
  79     #[inline]
  80     pub fn from_elem<S>(elem: T, universe: &IndexVec<I, S>) -> Self
  81         where T: Clone
  82     {
  83         IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData }
  84     }
  85
  86     #[inline]
  87     pub fn from_elem_n(elem: T, n: usize) -> Self
  88         where T: Clone
  89     {
  90         IndexVec { raw: vec![elem; n], _marker: PhantomData }
  91     }
  92
  93     #[inline]
  94     pub fn push(&mut self, d: T) -> I {
  95         let idx = I::new(self.len());
  96         self.raw.push(d);
  97         idx
  98     }
  99
 100     #[inline]
 101     pub fn len(&self) -> usize {
 102         self.raw.len()
 103     }
 104
 105     #[inline]
 106     pub fn is_empty(&self) -> bool {
 107         self.raw.is_empty()
 108     }
 109
 110     #[inline]
 111     pub fn into_iter(self) -> vec::IntoIter<T> {
 112         self.raw.into_iter()
 113     }
 114
 115     #[inline]
 116     pub fn into_iter_enumerated(self) -> Enumerated<I, vec::IntoIter<T>>
 117     {
 118         self.raw.into_iter().enumerate().map(IntoIdx { _marker: PhantomData })
 119     }
 120
 121     #[inline]
 122     pub fn iter(&self) -> slice::Iter<T> {
 123         self.raw.iter()
 124     }
 125
 126     #[inline]
 127     pub fn iter_enumerated(&self) -> Enumerated<I, slice::Iter<T>>
 128     {
 129         self.raw.iter().enumerate().map(IntoIdx { _marker: PhantomData })
 130     }
 131
 132     #[inline]
 133     pub fn indices(&self) -> iter::Map<Range<usize>, IntoIdx<I>> {
 134         (0..self.len()).map(IntoIdx { _marker: PhantomData })
 135     }
 136
 137     #[inline]
 138     pub fn iter_mut(&mut self) -> slice::IterMut<T> {
 139         self.raw.iter_mut()
 140     }
 141
 142     #[inline]
 143     pub fn iter_enumerated_mut(&mut self) -> Enumerated<I, slice::IterMut<T>>
 144     {
 145         self.raw.iter_mut().enumerate().map(IntoIdx { _marker: PhantomData })
 146     }
 147
 148     #[inline]
 149     pub fn last(&self) -> Option<I> {
 150         self.len().checked_sub(1).map(I::new)
 151     }
 152
 153     #[inline]
 154     pub fn shrink_to_fit(&mut self) {
 155         self.raw.shrink_to_fit()
 156     }
 157
 158     #[inline]
 159     pub fn swap(&mut self, a: usize, b: usize) {
 160         self.raw.swap(a, b)
 161     }
 162
 163     #[inline]
 164     pub fn truncate(&mut self, a: usize) {
 165         self.raw.truncate(a)
 166     }
 167 }
 168
 169 impl<I: Idx, T> Index<I> for IndexVec<I, T> {
 170     type Output = T;
 171
 172     #[inline]
 173     fn index(&self, index: I) -> &T {
 174         &self.raw[index.index()]
 175     }
 176 }
 177
 178 impl<I: Idx, T> IndexMut<I> for IndexVec<I, T> {
 179     #[inline]
 180     fn index_mut(&mut self, index: I) -> &mut T {
 181         &mut self.raw[index.index()]
 182     }
 183 }
 184
 185 impl<I: Idx, T> Extend<T> for IndexVec<I, T> {
 186     #[inline]
 187     fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) {
 188         self.raw.extend(iter);
 189     }
 190 }
 191
 192 impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> {
 193     #[inline]
 194     fn from_iter<J>(iter: J) -> Self where J: IntoIterator<Item=T> {
 195         IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData }
 196     }
 197 }
 198
 199 impl<I: Idx, T> IntoIterator for IndexVec<I, T> {
 200     type Item = T;
 201     type IntoIter = vec::IntoIter<T>;
 202
 203     #[inline]
 204     fn into_iter(self) -> vec::IntoIter<T> {
 205         self.raw.into_iter()
 206     }
 207
 208 }
 209
 210 impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> {
 211     type Item = &'a T;
 212     type IntoIter = slice::Iter<'a, T>;
 213
 214     #[inline]
 215     fn into_iter(self) -> slice::Iter<'a, T> {
 216         self.raw.iter()
 217     }
 218 }
 219
 220 impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> {
 221     type Item = &'a mut T;
 222     type IntoIter = slice::IterMut<'a, T>;
 223
 224     #[inline]
 225     fn into_iter(mut self) -> slice::IterMut<'a, T> {
 226         self.raw.iter_mut()
 227     }
 228 }
 229
 230 pub struct IntoIdx<I: Idx> { _marker: PhantomData<fn(&I)> }
 231 impl<I: Idx, T> FnOnce<((usize, T),)> for IntoIdx<I> {
 232     type Output = (I, T);
 233
 234     extern "rust-call" fn call_once(self, ((n, t),): ((usize, T),)) -> Self::Output {
 235         (I::new(n), t)
 236     }
 237 }
 238
 239 impl<I: Idx, T> FnMut<((usize, T),)> for IntoIdx<I> {
 240     extern "rust-call" fn call_mut(&mut self, ((n, t),): ((usize, T),)) -> Self::Output {
 241         (I::new(n), t)
 242     }
 243 }
 244
 245 impl<I: Idx> FnOnce<(usize,)> for IntoIdx<I> {
 246     type Output = I;
 247
 248     extern "rust-call" fn call_once(self, (n,): (usize,)) -> Self::Output {
 249         I::new(n)
 250     }
 251 }
 252
 253 impl<I: Idx> FnMut<(usize,)> for IntoIdx<I> {
 254     extern "rust-call" fn call_mut(&mut self, (n,): (usize,)) -> Self::Output {
 255         I::new(n)
 256     }
 257 }