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