src/libsyntax/util/small_vector.rs

   1 // Copyright 2013-2014 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 self::SmallVectorRepr::*;
  12 use self::IntoIterRepr::*;
  13
  14 use std::iter::FromIterator;
  15 use std::mem;
  16 use std::slice;
  17 use std::vec;
  18
  19 use fold::MoveMap;
  20
  21 /// A vector type optimized for cases where the size is almost always 0 or 1
  22 pub struct SmallVector<T> {
  23     repr: SmallVectorRepr<T>,
  24 }
  25
  26 enum SmallVectorRepr<T> {
  27     Zero,
  28     One(T),
  29     Many(Vec<T>),
  30 }
  31
  32 impl<T> FromIterator<T> for SmallVector<T> {
  33     fn from_iter<I: Iterator<Item=T>>(iter: I) -> SmallVector<T> {
  34         let mut v = SmallVector::zero();
  35         v.extend(iter);
  36         v
  37     }
  38 }
  39
  40 impl<T> Extend<T> for SmallVector<T> {
  41     fn extend<I: Iterator<Item=T>>(&mut self, mut iter: I) {
  42         for val in iter {
  43             self.push(val);
  44         }
  45     }
  46 }
  47
  48 impl<T> SmallVector<T> {
  49     pub fn zero() -> SmallVector<T> {
  50         SmallVector { repr: Zero }
  51     }
  52
  53     pub fn one(v: T) -> SmallVector<T> {
  54         SmallVector { repr: One(v) }
  55     }
  56
  57     pub fn many(vs: Vec<T>) -> SmallVector<T> {
  58         SmallVector { repr: Many(vs) }
  59     }
  60
  61     pub fn as_slice<'a>(&'a self) -> &'a [T] {
  62         match self.repr {
  63             Zero => {
  64                 let result: &[T] = &[];
  65                 result
  66             }
  67             One(ref v) => slice::ref_slice(v),
  68             Many(ref vs) => vs.as_slice()
  69         }
  70     }
  71
  72     pub fn push(&mut self, v: T) {
  73         match self.repr {
  74             Zero => self.repr = One(v),
  75             One(..) => {
  76                 let one = mem::replace(&mut self.repr, Zero);
  77                 match one {
  78                     One(v1) => mem::replace(&mut self.repr, Many(vec!(v1, v))),
  79                     _ => unreachable!()
  80                 };
  81             }
  82             Many(ref mut vs) => vs.push(v)
  83         }
  84     }
  85
  86     pub fn push_all(&mut self, other: SmallVector<T>) {
  87         for v in other.into_iter() {
  88             self.push(v);
  89         }
  90     }
  91
  92     pub fn get<'a>(&'a self, idx: usize) -> &'a T {
  93         match self.repr {
  94             One(ref v) if idx == 0 => v,
  95             Many(ref vs) => &vs[idx],
  96             _ => panic!("out of bounds access")
  97         }
  98     }
  99
 100     pub fn expect_one(self, err: &'static str) -> T {
 101         match self.repr {
 102             One(v) => v,
 103             Many(v) => {
 104                 if v.len() == 1 {
 105                     v.into_iter().next().unwrap()
 106                 } else {
 107                     panic!(err)
 108                 }
 109             }
 110             _ => panic!(err)
 111         }
 112     }
 113
 114     /// Deprecated: use `into_iter`.
 115     #[deprecated = "use into_iter"]
 116     pub fn move_iter(self) -> IntoIter<T> {
 117         self.into_iter()
 118     }
 119
 120     pub fn into_iter(self) -> IntoIter<T> {
 121         let repr = match self.repr {
 122             Zero => ZeroIterator,
 123             One(v) => OneIterator(v),
 124             Many(vs) => ManyIterator(vs.into_iter())
 125         };
 126         IntoIter { repr: repr }
 127     }
 128
 129     pub fn len(&self) -> usize {
 130         match self.repr {
 131             Zero => 0,
 132             One(..) => 1,
 133             Many(ref vals) => vals.len()
 134         }
 135     }
 136
 137     pub fn is_empty(&self) -> bool { self.len() == 0 }
 138 }
 139
 140 pub struct IntoIter<T> {
 141     repr: IntoIterRepr<T>,
 142 }
 143
 144 enum IntoIterRepr<T> {
 145     ZeroIterator,
 146     OneIterator(T),
 147     ManyIterator(vec::IntoIter<T>),
 148 }
 149
 150 impl<T> Iterator for IntoIter<T> {
 151     type Item = T;
 152
 153     fn next(&mut self) -> Option<T> {
 154         match self.repr {
 155             ZeroIterator => None,
 156             OneIterator(..) => {
 157                 let mut replacement = ZeroIterator;
 158                 mem::swap(&mut self.repr, &mut replacement);
 159                 match replacement {
 160                     OneIterator(v) => Some(v),
 161                     _ => unreachable!()
 162                 }
 163             }
 164             ManyIterator(ref mut inner) => inner.next()
 165         }
 166     }
 167
 168     fn size_hint(&self) -> (usize, Option<usize>) {
 169         match self.repr {
 170             ZeroIterator => (0, Some(0)),
 171             OneIterator(..) => (1, Some(1)),
 172             ManyIterator(ref inner) => inner.size_hint()
 173         }
 174     }
 175 }
 176
 177 impl<T> MoveMap<T> for SmallVector<T> {
 178     fn move_map<F>(self, mut f: F) -> SmallVector<T> where F: FnMut(T) -> T {
 179         let repr = match self.repr {
 180             Zero => Zero,
 181             One(v) => One(f(v)),
 182             Many(vs) => Many(vs.move_map(f))
 183         };
 184         SmallVector { repr: repr }
 185     }
 186 }
 187
 188 #[cfg(test)]
 189 mod test {
 190     use super::*;
 191
 192     #[test]
 193     fn test_len() {
 194         let v: SmallVector<isize> = SmallVector::zero();
 195         assert_eq!(0, v.len());
 196
 197         assert_eq!(1, SmallVector::one(1is).len());
 198         assert_eq!(5, SmallVector::many(vec!(1is, 2, 3, 4, 5)).len());
 199     }
 200
 201     #[test]
 202     fn test_push_get() {
 203         let mut v = SmallVector::zero();
 204         v.push(1is);
 205         assert_eq!(1, v.len());
 206         assert_eq!(&1, v.get(0));
 207         v.push(2);
 208         assert_eq!(2, v.len());
 209         assert_eq!(&2, v.get(1));
 210         v.push(3);
 211         assert_eq!(3, v.len());
 212         assert_eq!(&3, v.get(2));
 213     }
 214
 215     #[test]
 216     fn test_from_iter() {
 217         let v: SmallVector<isize> = (vec![1is, 2, 3]).into_iter().collect();
 218         assert_eq!(3, v.len());
 219         assert_eq!(&1, v.get(0));
 220         assert_eq!(&2, v.get(1));
 221         assert_eq!(&3, v.get(2));
 222     }
 223
 224     #[test]
 225     fn test_move_iter() {
 226         let v = SmallVector::zero();
 227         let v: Vec<isize> = v.into_iter().collect();
 228         assert_eq!(Vec::new(), v);
 229
 230         let v = SmallVector::one(1is);
 231         assert_eq!(vec!(1is), v.into_iter().collect::<Vec<_>>());
 232
 233         let v = SmallVector::many(vec!(1is, 2is, 3is));
 234         assert_eq!(vec!(1is, 2is, 3is), v.into_iter().collect::<Vec<_>>());
 235     }
 236
 237     #[test]
 238     #[should_fail]
 239     fn test_expect_one_zero() {
 240         let _: isize = SmallVector::zero().expect_one("");
 241     }
 242
 243     #[test]
 244     #[should_fail]
 245     fn test_expect_one_many() {
 246         SmallVector::many(vec!(1is, 2)).expect_one("");
 247     }
 248
 249     #[test]
 250     fn test_expect_one_one() {
 251         assert_eq!(1is, SmallVector::one(1is).expect_one(""));
 252         assert_eq!(1is, SmallVector::many(vec!(1is)).expect_one(""));
 253     }
 254 }