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, 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),
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: usize) -> &'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 #[unstable(feature = "rustc_private")]
116 #[deprecated(since = "1.0.0", reason = "use into_iter")]
117 pub fn move_iter(self) -> IntoIter<T> {
121 pub fn into_iter(self) -> IntoIter<T> {
122 let repr = match self.repr {
123 Zero => ZeroIterator,
124 One(v) => OneIterator(v),
125 Many(vs) => ManyIterator(vs.into_iter())
127 IntoIter { repr: repr }
130 pub fn len(&self) -> usize {
134 Many(ref vals) => vals.len()
138 pub fn is_empty(&self) -> bool { self.len() == 0 }
141 pub struct IntoIter<T> {
142 repr: IntoIterRepr<T>,
145 enum IntoIterRepr<T> {
148 ManyIterator(vec::IntoIter<T>),
151 impl<T> Iterator for IntoIter<T> {
154 fn next(&mut self) -> Option<T> {
156 ZeroIterator => None,
158 let mut replacement = ZeroIterator;
159 mem::swap(&mut self.repr, &mut replacement);
161 OneIterator(v) => Some(v),
165 ManyIterator(ref mut inner) => inner.next()
169 fn size_hint(&self) -> (usize, Option<usize>) {
171 ZeroIterator => (0, Some(0)),
172 OneIterator(..) => (1, Some(1)),
173 ManyIterator(ref inner) => inner.size_hint()
178 impl<T> MoveMap<T> for SmallVector<T> {
179 fn move_map<F>(self, mut f: F) -> SmallVector<T> where F: FnMut(T) -> T {
180 let repr = match self.repr {
183 Many(vs) => Many(vs.move_map(f))
185 SmallVector { repr: repr }
195 let v: SmallVector<isize> = SmallVector::zero();
196 assert_eq!(0, v.len());
198 assert_eq!(1, SmallVector::one(1).len());
199 assert_eq!(5, SmallVector::many(vec![1, 2, 3, 4, 5]).len());
204 let mut v = SmallVector::zero();
206 assert_eq!(1, v.len());
207 assert_eq!(&1, v.get(0));
209 assert_eq!(2, v.len());
210 assert_eq!(&2, v.get(1));
212 assert_eq!(3, v.len());
213 assert_eq!(&3, v.get(2));
217 fn test_from_iter() {
218 let v: SmallVector<isize> = (vec![1, 2, 3]).into_iter().collect();
219 assert_eq!(3, v.len());
220 assert_eq!(&1, v.get(0));
221 assert_eq!(&2, v.get(1));
222 assert_eq!(&3, v.get(2));
226 fn test_move_iter() {
227 let v = SmallVector::zero();
228 let v: Vec<isize> = v.into_iter().collect();
229 assert_eq!(Vec::new(), v);
231 let v = SmallVector::one(1);
232 assert_eq!(vec![1], v.into_iter().collect::<Vec<_>>());
234 let v = SmallVector::many(vec![1, 2, 3]);
235 assert_eq!(vec!(1, 2, 3), v.into_iter().collect::<Vec<_>>());
240 fn test_expect_one_zero() {
241 let _: isize = SmallVector::zero().expect_one("");
246 fn test_expect_one_many() {
247 SmallVector::many(vec!(1, 2)).expect_one("");
251 fn test_expect_one_one() {
252 assert_eq!(1, SmallVector::one(1).expect_one(""));
253 assert_eq!(1, SmallVector::many(vec!(1)).expect_one(""));