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.
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.
11 use self::SmallVectorRepr::*;
12 use self::IntoIterRepr::*;
14 use std::iter::FromIterator;
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>,
26 enum SmallVectorRepr<T> {
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();
40 impl<T> Extend<T> for SmallVector<T> {
41 fn extend<I: Iterator<Item=T>>(&mut self, mut iter: I) {
48 impl<T> SmallVector<T> {
49 pub fn zero() -> SmallVector<T> {
50 SmallVector { repr: Zero }
53 pub fn one(v: T) -> SmallVector<T> {
54 SmallVector { repr: One(v) }
57 pub fn many(vs: Vec<T>) -> SmallVector<T> {
58 SmallVector { repr: Many(vs) }
61 pub fn as_slice<'a>(&'a self) -> &'a [T] {
64 let result: &[T] = &[];
67 One(ref v) => slice::ref_slice(v),
68 Many(ref vs) => vs.as_slice()
72 pub fn push(&mut self, v: T) {
74 Zero => self.repr = One(v),
76 let one = mem::replace(&mut self.repr, Zero);
78 One(v1) => mem::replace(&mut self.repr, Many(vec!(v1, v))),
82 Many(ref mut vs) => vs.push(v)
86 pub fn push_all(&mut self, other: SmallVector<T>) {
87 for v in other.into_iter() {
92 pub fn get<'a>(&'a self, idx: uint) -> &'a T {
94 One(ref v) if idx == 0 => v,
95 Many(ref vs) => &vs[idx],
96 _ => panic!("out of bounds access")
100 pub fn expect_one(self, err: &'static str) -> T {
105 v.into_iter().next().unwrap()
114 /// Deprecated: use `into_iter`.
115 #[deprecated = "use into_iter"]
116 pub fn move_iter(self) -> IntoIter<T> {
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())
126 IntoIter { repr: repr }
129 pub fn len(&self) -> uint {
133 Many(ref vals) => vals.len()
137 pub fn is_empty(&self) -> bool { self.len() == 0 }
140 pub struct IntoIter<T> {
141 repr: IntoIterRepr<T>,
144 enum IntoIterRepr<T> {
147 ManyIterator(vec::IntoIter<T>),
150 impl<T> Iterator for IntoIter<T> {
153 fn next(&mut self) -> Option<T> {
155 ZeroIterator => None,
157 let mut replacement = ZeroIterator;
158 mem::swap(&mut self.repr, &mut replacement);
160 OneIterator(v) => Some(v),
164 ManyIterator(ref mut inner) => inner.next()
168 fn size_hint(&self) -> (uint, Option<uint>) {
170 ZeroIterator => (0, Some(0)),
171 OneIterator(..) => (1, Some(1)),
172 ManyIterator(ref inner) => inner.size_hint()
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 {
182 Many(vs) => Many(vs.move_map(f))
184 SmallVector { repr: repr }
194 let v: SmallVector<int> = SmallVector::zero();
195 assert_eq!(0, v.len());
197 assert_eq!(1, SmallVector::one(1i).len());
198 assert_eq!(5, SmallVector::many(vec!(1i, 2, 3, 4, 5)).len());
203 let mut v = SmallVector::zero();
205 assert_eq!(1, v.len());
206 assert_eq!(&1, v.get(0));
208 assert_eq!(2, v.len());
209 assert_eq!(&2, v.get(1));
211 assert_eq!(3, v.len());
212 assert_eq!(&3, v.get(2));
216 fn test_from_iter() {
217 let v: SmallVector<int> = (vec!(1i, 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));
225 fn test_move_iter() {
226 let v = SmallVector::zero();
227 let v: Vec<int> = v.into_iter().collect();
228 assert_eq!(Vec::new(), v);
230 let v = SmallVector::one(1i);
231 assert_eq!(vec!(1i), v.into_iter().collect::<Vec<_>>());
233 let v = SmallVector::many(vec!(1i, 2i, 3i));
234 assert_eq!(vec!(1i, 2i, 3i), v.into_iter().collect::<Vec<_>>());
239 fn test_expect_one_zero() {
240 let _: int = SmallVector::zero().expect_one("");
245 fn test_expect_one_many() {
246 SmallVector::many(vec!(1i, 2)).expect_one("");
250 fn test_expect_one_one() {
251 assert_eq!(1i, SmallVector::one(1i).expect_one(""));
252 assert_eq!(1i, SmallVector::many(vec!(1i)).expect_one(""));