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.move_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.move_iter().next().unwrap()
120 pub fn move_iter(self) -> MoveItems<T> {
121 let repr = match self.repr {
122 Zero => ZeroIterator,
123 One(v) => OneIterator(v),
124 Many(vs) => ManyIterator(vs.move_iter())
126 MoveItems { repr: repr }
130 pub struct MoveItems<T> {
131 repr: MoveItemsRepr<T>,
134 enum MoveItemsRepr<T> {
137 ManyIterator(vec::MoveItems<T>),
140 impl<T> Iterator<T> for MoveItems<T> {
141 fn next(&mut self) -> Option<T> {
143 ZeroIterator => None,
145 let mut replacement = ZeroIterator;
146 mem::swap(&mut self.repr, &mut replacement);
148 OneIterator(v) => Some(v),
152 ManyIterator(ref mut inner) => inner.next()
156 fn size_hint(&self) -> (uint, Option<uint>) {
158 ZeroIterator => (0, Some(0)),
159 OneIterator(..) => (1, Some(1)),
160 ManyIterator(ref inner) => inner.size_hint()
165 impl<T> MoveMap<T> for SmallVector<T> {
166 fn move_map(self, f: |T| -> T) -> SmallVector<T> {
167 let repr = match self.repr {
170 Many(vs) => Many(vs.move_map(f))
172 SmallVector { repr: repr }
182 let v: SmallVector<int> = SmallVector::zero();
183 assert_eq!(0, v.len());
185 assert_eq!(1, SmallVector::one(1i).len());
186 assert_eq!(5, SmallVector::many(vec!(1i, 2, 3, 4, 5)).len());
191 let mut v = SmallVector::zero();
193 assert_eq!(1, v.len());
194 assert_eq!(&1, v.get(0));
196 assert_eq!(2, v.len());
197 assert_eq!(&2, v.get(1));
199 assert_eq!(3, v.len());
200 assert_eq!(&3, v.get(2));
204 fn test_from_iter() {
205 let v: SmallVector<int> = (vec!(1i, 2, 3)).move_iter().collect();
206 assert_eq!(3, v.len());
207 assert_eq!(&1, v.get(0));
208 assert_eq!(&2, v.get(1));
209 assert_eq!(&3, v.get(2));
213 fn test_move_iter() {
214 let v = SmallVector::zero();
215 let v: Vec<int> = v.move_iter().collect();
216 assert_eq!(Vec::new(), v);
218 let v = SmallVector::one(1i);
219 assert_eq!(vec!(1i), v.move_iter().collect());
221 let v = SmallVector::many(vec!(1i, 2i, 3i));
222 assert_eq!(vec!(1i, 2i, 3i), v.move_iter().collect());
227 fn test_expect_one_zero() {
228 let _: int = SmallVector::zero().expect_one("");
233 fn test_expect_one_many() {
234 SmallVector::many(vec!(1i, 2)).expect_one("");
238 fn test_expect_one_one() {
239 assert_eq!(1i, SmallVector::one(1i).expect_one(""));
240 assert_eq!(1i, SmallVector::many(vec!(1i)).expect_one(""));