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