src/libsyntax/opt_vec.rs

   1 // Copyright 2012 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 /*!
  12  * Defines a type OptVec<T> that can be used in place of ~[T].
  13  * OptVec avoids the need for allocation for empty vectors.
  14  * OptVec implements the iterable interface as well as
  15  * other useful things like `push()` and `len()`.
  16  */
  17
  18 use std::default::Default;
  19 use std::vec;
  20 use std::vec_ng::Vec;
  21
  22 #[deriving(Clone, Encodable, Decodable, Hash)]
  23 pub enum OptVec<T> {
  24     Empty,
  25     Vec(Vec<T> )
  26 }
  27
  28 pub fn with<T>(t: T) -> OptVec<T> {
  29     Vec(vec!(t))
  30 }
  31
  32 pub fn from<T>(t: Vec<T> ) -> OptVec<T> {
  33     if t.len() == 0 {
  34         Empty
  35     } else {
  36         Vec(t)
  37     }
  38 }
  39
  40 impl<T> OptVec<T> {
  41     pub fn push(&mut self, t: T) {
  42         match *self {
  43             Vec(ref mut v) => {
  44                 v.push(t);
  45                 return;
  46             }
  47             Empty => {
  48                 *self = Vec(vec!(t));
  49             }
  50         }
  51     }
  52
  53     pub fn pop(&mut self) -> Option<T> {
  54         match *self {
  55             Vec(ref mut v) => v.pop(),
  56             Empty => None
  57         }
  58     }
  59
  60     pub fn last<'a>(&'a self) -> Option<&'a T> {
  61         match *self {
  62             Vec(ref v) => v.last(),
  63             Empty => None
  64         }
  65     }
  66
  67     pub fn mut_last<'a>(&'a mut self) -> Option<&'a mut T> {
  68         match *self {
  69             Vec(ref mut v) => v.mut_last(),
  70             Empty => None
  71         }
  72     }
  73
  74     pub fn map<U>(&self, op: |&T| -> U) -> OptVec<U> {
  75         match *self {
  76             Empty => Empty,
  77             Vec(ref v) => Vec(v.map(op))
  78         }
  79     }
  80
  81     pub fn map_move<U>(self, op: |T| -> U) -> OptVec<U> {
  82         match self {
  83             Empty => Empty,
  84             Vec(v) => Vec(v.move_iter().map(op).collect())
  85         }
  86     }
  87
  88     pub fn get<'a>(&'a self, i: uint) -> &'a T {
  89         match *self {
  90             Empty => fail!("invalid index {}", i),
  91             Vec(ref v) => v.get(i)
  92         }
  93     }
  94
  95     pub fn is_empty(&self) -> bool {
  96         self.len() == 0
  97     }
  98
  99     pub fn len(&self) -> uint {
 100         match *self {
 101             Empty => 0,
 102             Vec(ref v) => v.len()
 103         }
 104     }
 105
 106     pub fn swap_remove(&mut self, index: uint) {
 107         match *self {
 108             Empty => { fail!("index out of bounds"); }
 109             Vec(ref mut v) => {
 110                 assert!(index < v.len());
 111                 v.swap_remove(index);
 112             }
 113         }
 114     }
 115
 116     #[inline]
 117     pub fn iter<'r>(&'r self) -> Items<'r, T> {
 118         match *self {
 119             Empty => Items{iter: None},
 120             Vec(ref v) => Items{iter: Some(v.iter())}
 121         }
 122     }
 123
 124     #[inline]
 125     pub fn map_to_vec<B>(&self, op: |&T| -> B) -> Vec<B> {
 126         self.iter().map(op).collect()
 127     }
 128
 129     pub fn mapi_to_vec<B>(&self, op: |uint, &T| -> B) -> Vec<B> {
 130         let mut index = 0;
 131         self.map_to_vec(|a| {
 132             let i = index;
 133             index += 1;
 134             op(i, a)
 135         })
 136     }
 137 }
 138
 139 pub fn take_vec<T>(v: OptVec<T>) -> Vec<T> {
 140     match v {
 141         Empty => Vec::new(),
 142         Vec(v) => v
 143     }
 144 }
 145
 146 impl<T:Clone> OptVec<T> {
 147     pub fn prepend(&self, t: T) -> OptVec<T> {
 148         let mut v0 = vec!(t);
 149         match *self {
 150             Empty => {}
 151             Vec(ref v1) => { v0.push_all(v1.as_slice()); }
 152         }
 153         return Vec(v0);
 154     }
 155 }
 156
 157 impl<A:Eq> Eq for OptVec<A> {
 158     fn eq(&self, other: &OptVec<A>) -> bool {
 159         // Note: cannot use #[deriving(Eq)] here because
 160         // (Empty, Vec(~[])) ought to be equal.
 161         match (self, other) {
 162             (&Empty, &Empty) => true,
 163             (&Empty, &Vec(ref v)) => v.is_empty(),
 164             (&Vec(ref v), &Empty) => v.is_empty(),
 165             (&Vec(ref v1), &Vec(ref v2)) => *v1 == *v2
 166         }
 167     }
 168
 169     fn ne(&self, other: &OptVec<A>) -> bool {
 170         !self.eq(other)
 171     }
 172 }
 173
 174 impl<T> Default for OptVec<T> {
 175     fn default() -> OptVec<T> { Empty }
 176 }
 177
 178 pub struct Items<'a, T> {
 179     priv iter: Option<vec::Items<'a, T>>
 180 }
 181
 182 impl<'a, T> Iterator<&'a T> for Items<'a, T> {
 183     #[inline]
 184     fn next(&mut self) -> Option<&'a T> {
 185         match self.iter {
 186             Some(ref mut x) => x.next(),
 187             None => None
 188         }
 189     }
 190
 191     #[inline]
 192     fn size_hint(&self) -> (uint, Option<uint>) {
 193         match self.iter {
 194             Some(ref x) => x.size_hint(),
 195             None => (0, Some(0))
 196         }
 197     }
 198 }
 199
 200 impl<'a, T> DoubleEndedIterator<&'a T> for Items<'a, T> {
 201     #[inline]
 202     fn next_back(&mut self) -> Option<&'a T> {
 203         match self.iter {
 204             Some(ref mut x) => x.next_back(),
 205             None => None
 206         }
 207     }
 208 }
 209
 210 impl<A> FromIterator<A> for OptVec<A> {
 211     fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> OptVec<A> {
 212         let mut r = Empty;
 213         for x in *iterator {
 214             r.push(x);
 215         }
 216         r
 217     }
 218 }