src/librustc_data_structures/accumulate_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 //! A vector type intended to be used for collecting from iterators onto the stack.
  12 //!
  13 //! Space for up to N elements is provided on the stack.  If more elements are collected, Vec is
  14 //! used to store the values on the heap.
  15 //!
  16 //! The N above is determined by Array's implementor, by way of an associatated constant.
  17
  18 use std::ops::{Deref, DerefMut};
  19 use std::iter::{self, IntoIterator, FromIterator};
  20 use std::slice;
  21 use std::vec;
  22 use std::collections::range::RangeArgument;
  23
  24 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
  25
  26 use array_vec::{self, Array, ArrayVec};
  27
  28 #[derive(PartialEq, Eq, Hash, Debug)]
  29 pub enum AccumulateVec<A: Array> {
  30     Array(ArrayVec<A>),
  31     Heap(Vec<A::Element>)
  32 }
  33
  34 impl<A> Clone for AccumulateVec<A>
  35     where A: Array,
  36           A::Element: Clone {
  37     fn clone(&self) -> Self {
  38         match *self {
  39             AccumulateVec::Array(ref arr) => AccumulateVec::Array(arr.clone()),
  40             AccumulateVec::Heap(ref vec) => AccumulateVec::Heap(vec.clone()),
  41         }
  42     }
  43 }
  44
  45 impl<A: Array> AccumulateVec<A> {
  46     pub fn new() -> AccumulateVec<A> {
  47         AccumulateVec::Array(ArrayVec::new())
  48     }
  49
  50     pub fn one(el: A::Element) -> Self {
  51         iter::once(el).collect()
  52     }
  53
  54     pub fn many<I: IntoIterator<Item=A::Element>>(iter: I) -> Self {
  55         iter.into_iter().collect()
  56     }
  57
  58     pub fn len(&self) -> usize {
  59         match *self {
  60             AccumulateVec::Array(ref arr) => arr.len(),
  61             AccumulateVec::Heap(ref vec) => vec.len(),
  62         }
  63     }
  64
  65     pub fn is_empty(&self) -> bool {
  66         self.len() == 0
  67     }
  68
  69     pub fn pop(&mut self) -> Option<A::Element> {
  70         match *self {
  71             AccumulateVec::Array(ref mut arr) => arr.pop(),
  72             AccumulateVec::Heap(ref mut vec) => vec.pop(),
  73         }
  74     }
  75
  76     pub fn drain<R>(&mut self, range: R) -> Drain<A>
  77         where R: RangeArgument<usize>
  78     {
  79         match *self {
  80             AccumulateVec::Array(ref mut v) => {
  81                 Drain::Array(v.drain(range))
  82             },
  83             AccumulateVec::Heap(ref mut v) => {
  84                 Drain::Heap(v.drain(range))
  85             },
  86         }
  87     }
  88 }
  89
  90 impl<A: Array> Deref for AccumulateVec<A> {
  91     type Target = [A::Element];
  92     fn deref(&self) -> &Self::Target {
  93         match *self {
  94             AccumulateVec::Array(ref v) => &v[..],
  95             AccumulateVec::Heap(ref v) => &v[..],
  96         }
  97     }
  98 }
  99
 100 impl<A: Array> DerefMut for AccumulateVec<A> {
 101     fn deref_mut(&mut self) -> &mut [A::Element] {
 102         match *self {
 103             AccumulateVec::Array(ref mut v) => &mut v[..],
 104             AccumulateVec::Heap(ref mut v) => &mut v[..],
 105         }
 106     }
 107 }
 108
 109 impl<A: Array> FromIterator<A::Element> for AccumulateVec<A> {
 110     fn from_iter<I>(iter: I) -> AccumulateVec<A> where I: IntoIterator<Item=A::Element> {
 111         let iter = iter.into_iter();
 112         if iter.size_hint().1.map_or(false, |n| n <= A::LEN) {
 113             let mut v = ArrayVec::new();
 114             v.extend(iter);
 115             AccumulateVec::Array(v)
 116         } else {
 117             AccumulateVec::Heap(iter.collect())
 118         }
 119     }
 120 }
 121
 122 pub struct IntoIter<A: Array> {
 123     repr: IntoIterRepr<A>,
 124 }
 125
 126 enum IntoIterRepr<A: Array> {
 127     Array(array_vec::Iter<A>),
 128     Heap(vec::IntoIter<A::Element>),
 129 }
 130
 131 impl<A: Array> Iterator for IntoIter<A> {
 132     type Item = A::Element;
 133
 134     fn next(&mut self) -> Option<A::Element> {
 135         match self.repr {
 136             IntoIterRepr::Array(ref mut arr) => arr.next(),
 137             IntoIterRepr::Heap(ref mut iter) => iter.next(),
 138         }
 139     }
 140
 141     fn size_hint(&self) -> (usize, Option<usize>) {
 142         match self.repr {
 143             IntoIterRepr::Array(ref iter) => iter.size_hint(),
 144             IntoIterRepr::Heap(ref iter) => iter.size_hint(),
 145         }
 146     }
 147 }
 148
 149 pub enum Drain<'a, A: Array>
 150         where A::Element: 'a
 151 {
 152     Array(array_vec::Drain<'a, A>),
 153     Heap(vec::Drain<'a, A::Element>),
 154 }
 155
 156 impl<'a, A: Array> Iterator for Drain<'a, A> {
 157     type Item = A::Element;
 158
 159     fn next(&mut self) -> Option<A::Element> {
 160         match *self {
 161             Drain::Array(ref mut drain) => drain.next(),
 162             Drain::Heap(ref mut drain) => drain.next(),
 163         }
 164     }
 165
 166     fn size_hint(&self) -> (usize, Option<usize>) {
 167         match *self {
 168             Drain::Array(ref drain) => drain.size_hint(),
 169             Drain::Heap(ref drain) => drain.size_hint(),
 170         }
 171     }
 172 }
 173
 174 impl<A: Array> IntoIterator for AccumulateVec<A> {
 175     type Item = A::Element;
 176     type IntoIter = IntoIter<A>;
 177     fn into_iter(self) -> Self::IntoIter {
 178         IntoIter {
 179             repr: match self {
 180                 AccumulateVec::Array(arr) => IntoIterRepr::Array(arr.into_iter()),
 181                 AccumulateVec::Heap(vec) => IntoIterRepr::Heap(vec.into_iter()),
 182             }
 183         }
 184     }
 185 }
 186
 187 impl<'a, A: Array> IntoIterator for &'a AccumulateVec<A> {
 188     type Item = &'a A::Element;
 189     type IntoIter = slice::Iter<'a, A::Element>;
 190     fn into_iter(self) -> Self::IntoIter {
 191         self.iter()
 192     }
 193 }
 194
 195 impl<'a, A: Array> IntoIterator for &'a mut AccumulateVec<A> {
 196     type Item = &'a mut A::Element;
 197     type IntoIter = slice::IterMut<'a, A::Element>;
 198     fn into_iter(self) -> Self::IntoIter {
 199         self.iter_mut()
 200     }
 201 }
 202
 203 impl<A: Array> From<Vec<A::Element>> for AccumulateVec<A> {
 204     fn from(v: Vec<A::Element>) -> AccumulateVec<A> {
 205         AccumulateVec::many(v)
 206     }
 207 }
 208
 209 impl<A: Array> Default for AccumulateVec<A> {
 210     fn default() -> AccumulateVec<A> {
 211         AccumulateVec::new()
 212     }
 213 }
 214
 215 impl<A> Encodable for AccumulateVec<A>
 216     where A: Array,
 217           A::Element: Encodable {
 218     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 219         s.emit_seq(self.len(), |s| {
 220             for (i, e) in self.iter().enumerate() {
 221                 try!(s.emit_seq_elt(i, |s| e.encode(s)));
 222             }
 223             Ok(())
 224         })
 225     }
 226 }
 227
 228 impl<A> Decodable for AccumulateVec<A>
 229     where A: Array,
 230           A::Element: Decodable {
 231     fn decode<D: Decoder>(d: &mut D) -> Result<AccumulateVec<A>, D::Error> {
 232         d.read_seq(|d, len| {
 233             Ok(try!((0..len).map(|i| d.read_seq_elt(i, |d| Decodable::decode(d))).collect()))
 234         })
 235     }
 236 }
 237