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.
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 use std::mem;
12 use std::slice;
13 use std::vec;
14
15 /// A vector type optimized for cases where the size is almost always 0 or 1
16 pub struct SmallVector<T> {
17 repr: SmallVectorRepr<T>,
18 }
19
20 enum SmallVectorRepr<T> {
21 Zero,
22 One(T),
23 Many(Vec<T> ),
24 }
25
26 impl<T> Container for SmallVector<T> {
27 fn len(&self) -> uint {
28 match self.repr {
29 Zero => 0,
30 One(..) => 1,
31 Many(ref vals) => vals.len()
32 }
33 }
34 }
35
36 impl<T> FromIterator<T> for SmallVector<T> {
37 fn from_iter<I: Iterator<T>>(iter: I) -> SmallVector<T> {
38 let mut v = SmallVector::zero();
39 v.extend(iter);
40 v
41 }
42 }
43
44 impl<T> Extendable<T> for SmallVector<T> {
45 fn extend<I: Iterator<T>>(&mut self, mut iter: I) {
46 for val in iter {
47 self.push(val);
48 }
49 }
50 }
51
52 impl<T> SmallVector<T> {
53 pub fn zero() -> SmallVector<T> {
54 SmallVector { repr: Zero }
55 }
56
57 pub fn one(v: T) -> SmallVector<T> {
58 SmallVector { repr: One(v) }
59 }
60
61 pub fn many(vs: Vec<T>) -> SmallVector<T> {
62 SmallVector { repr: Many(vs) }
63 }
64
65 pub fn as_slice<'a>(&'a self) -> &'a [T] {
66 match self.repr {
67 Zero => &[],
68 One(ref v) => slice::ref_slice(v),
69 Many(ref vs) => vs.as_slice()
70 }
71 }
72
73 pub fn push(&mut self, v: T) {
74 match self.repr {
75 Zero => self.repr = One(v),
76 One(..) => {
77 let one = mem::replace(&mut self.repr, Zero);
78 match one {
79 One(v1) => mem::replace(&mut self.repr, Many(vec!(v1, v))),
80 _ => unreachable!()
81 };
82 }
83 Many(ref mut vs) => vs.push(v)
84 }
85 }
86
87 pub fn push_all(&mut self, other: SmallVector<T>) {
88 for v in other.move_iter() {
89 self.push(v);
90 }
91 }
92
93 pub fn get<'a>(&'a self, idx: uint) -> &'a T {
94 match self.repr {
95 One(ref v) if idx == 0 => v,
96 Many(ref vs) => vs.get(idx),
97 _ => fail!("out of bounds access")
98 }
99 }
100
101 pub fn expect_one(self, err: &'static str) -> T {
102 match self.repr {
103 One(v) => v,
104 Many(v) => {
105 if v.len() == 1 {
106 v.move_iter().next().unwrap()
107 } else {
108 fail!(err)
109 }
110 }
111 _ => fail!(err)
112 }
113 }
114
115 pub fn move_iter(self) -> MoveItems<T> {
116 let repr = match self.repr {
117 Zero => ZeroIterator,
118 One(v) => OneIterator(v),
119 Many(vs) => ManyIterator(vs.move_iter())
120 };
121 MoveItems { repr: repr }
122 }
123 }
124
125 pub struct MoveItems<T> {
126 repr: MoveItemsRepr<T>,
127 }
128
129 enum MoveItemsRepr<T> {
130 ZeroIterator,
131 OneIterator(T),
132 ManyIterator(vec::MoveItems<T>),
133 }
134
135 impl<T> Iterator<T> for MoveItems<T> {
136 fn next(&mut self) -> Option<T> {
137 match self.repr {
138 ZeroIterator => None,
139 OneIterator(..) => {
140 let mut replacement = ZeroIterator;
141 mem::swap(&mut self.repr, &mut replacement);
142 match replacement {
143 OneIterator(v) => Some(v),
144 _ => unreachable!()
145 }
146 }
147 ManyIterator(ref mut inner) => inner.next()
148 }
149 }
150
151 fn size_hint(&self) -> (uint, Option<uint>) {
152 match self.repr {
153 ZeroIterator => (0, Some(0)),
154 OneIterator(..) => (1, Some(1)),
155 ManyIterator(ref inner) => inner.size_hint()
156 }
157 }
158 }
159
160 #[cfg(test)]
161 mod test {
162 use super::*;
163
164 #[test]
165 fn test_len() {
166 let v: SmallVector<int> = SmallVector::zero();
167 assert_eq!(0, v.len());
168
169 assert_eq!(1, SmallVector::one(1).len());
170 assert_eq!(5, SmallVector::many(vec!(1, 2, 3, 4, 5)).len());
171 }
172
173 #[test]
174 fn test_push_get() {
175 let mut v = SmallVector::zero();
176 v.push(1);
177 assert_eq!(1, v.len());
178 assert_eq!(&1, v.get(0));
179 v.push(2);
180 assert_eq!(2, v.len());
181 assert_eq!(&2, v.get(1));
182 v.push(3);
183 assert_eq!(3, v.len());
184 assert_eq!(&3, v.get(2));
185 }
186
187 #[test]
188 fn test_from_iter() {
189 let v: SmallVector<int> = (vec!(1, 2, 3)).move_iter().collect();
190 assert_eq!(3, v.len());
191 assert_eq!(&1, v.get(0));
192 assert_eq!(&2, v.get(1));
193 assert_eq!(&3, v.get(2));
194 }
195
196 #[test]
197 fn test_move_iter() {
198 let v = SmallVector::zero();
199 let v: Vec<int> = v.move_iter().collect();
200 assert_eq!(Vec::new(), v);
201
202 let v = SmallVector::one(1);
203 assert_eq!(vec!(1), v.move_iter().collect());
204
205 let v = SmallVector::many(vec!(1, 2, 3));
206 assert_eq!(vec!(1, 2, 3), v.move_iter().collect());
207 }
208
209 #[test]
210 #[should_fail]
211 fn test_expect_one_zero() {
212 let _: int = SmallVector::zero().expect_one("");
213 }
214
215 #[test]
216 #[should_fail]
217 fn test_expect_one_many() {
218 SmallVector::many(vec!(1, 2)).expect_one("");
219 }
220
221 #[test]
222 fn test_expect_one_one() {
223 assert_eq!(1, SmallVector::one(1).expect_one(""));
224 assert_eq!(1, SmallVector::many(vec!(1)).expect_one(""));
225 }
226 }