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