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.
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>,
22 enum SmallVectorRepr<T> {
28 impl<T> Collection for SmallVector<T> {
29 fn len(&self) -> uint {
33 Many(ref vals) => vals.len()
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();
46 impl<T> Extendable<T> for SmallVector<T> {
47 fn extend<I: Iterator<T>>(&mut self, mut iter: I) {
54 impl<T> SmallVector<T> {
55 pub fn zero() -> SmallVector<T> {
56 SmallVector { repr: Zero }
59 pub fn one(v: T) -> SmallVector<T> {
60 SmallVector { repr: One(v) }
63 pub fn many(vs: Vec<T>) -> SmallVector<T> {
64 SmallVector { repr: Many(vs) }
67 pub fn as_slice<'a>(&'a self) -> &'a [T] {
70 let result: &[T] = &[];
73 One(ref v) => slice::ref_slice(v),
74 Many(ref vs) => vs.as_slice()
78 pub fn push(&mut self, v: T) {
80 Zero => self.repr = One(v),
82 let one = mem::replace(&mut self.repr, Zero);
84 One(v1) => mem::replace(&mut self.repr, Many(vec!(v1, v))),
88 Many(ref mut vs) => vs.push(v)
92 pub fn push_all(&mut self, other: SmallVector<T>) {
93 for v in other.into_iter() {
98 pub fn get<'a>(&'a self, idx: uint) -> &'a T {
100 One(ref v) if idx == 0 => v,
101 Many(ref vs) => vs.get(idx),
102 _ => fail!("out of bounds access")
106 pub fn expect_one(self, err: &'static str) -> T {
111 v.into_iter().next().unwrap()
120 /// Deprecated: use `into_iter`.
121 #[deprecated = "use into_iter"]
122 pub fn move_iter(self) -> MoveItems<T> {
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())
132 MoveItems { repr: repr }
136 pub struct MoveItems<T> {
137 repr: MoveItemsRepr<T>,
140 enum MoveItemsRepr<T> {
143 ManyIterator(vec::MoveItems<T>),
146 impl<T> Iterator<T> for MoveItems<T> {
147 fn next(&mut self) -> Option<T> {
149 ZeroIterator => None,
151 let mut replacement = ZeroIterator;
152 mem::swap(&mut self.repr, &mut replacement);
154 OneIterator(v) => Some(v),
158 ManyIterator(ref mut inner) => inner.next()
162 fn size_hint(&self) -> (uint, Option<uint>) {
164 ZeroIterator => (0, Some(0)),
165 OneIterator(..) => (1, Some(1)),
166 ManyIterator(ref inner) => inner.size_hint()
171 impl<T> MoveMap<T> for SmallVector<T> {
172 fn move_map(self, f: |T| -> T) -> SmallVector<T> {
173 let repr = match self.repr {
176 Many(vs) => Many(vs.move_map(f))
178 SmallVector { repr: repr }
188 let v: SmallVector<int> = SmallVector::zero();
189 assert_eq!(0, v.len());
191 assert_eq!(1, SmallVector::one(1i).len());
192 assert_eq!(5, SmallVector::many(vec!(1i, 2, 3, 4, 5)).len());
197 let mut v = SmallVector::zero();
199 assert_eq!(1, v.len());
200 assert_eq!(&1, v.get(0));
202 assert_eq!(2, v.len());
203 assert_eq!(&2, v.get(1));
205 assert_eq!(3, v.len());
206 assert_eq!(&3, v.get(2));
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));
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);
224 let v = SmallVector::one(1i);
225 assert_eq!(vec!(1i), v.into_iter().collect());
227 let v = SmallVector::many(vec!(1i, 2i, 3i));
228 assert_eq!(vec!(1i, 2i, 3i), v.into_iter().collect());
233 fn test_expect_one_zero() {
234 let _: int = SmallVector::zero().expect_one("");
239 fn test_expect_one_many() {
240 SmallVector::many(vec!(1i, 2)).expect_one("");
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(""));