]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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 self::SmallVectorRepr::*; | |
12 | use self::IntoIterRepr::*; | |
13 | ||
85aaf69f | 14 | use std::iter::{IntoIterator, FromIterator}; |
1a4d82fc JJ |
15 | use std::mem; |
16 | use std::slice; | |
17 | use std::vec; | |
18 | ||
92a42be0 | 19 | use util::move_map::MoveMap; |
1a4d82fc JJ |
20 | |
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>, | |
24 | } | |
25 | ||
26 | enum SmallVectorRepr<T> { | |
27 | Zero, | |
28 | One(T), | |
29 | Many(Vec<T>), | |
30 | } | |
31 | ||
9e0c209e SL |
32 | impl<T> Default for SmallVector<T> { |
33 | fn default() -> Self { | |
34 | SmallVector { repr: Zero } | |
35 | } | |
36 | } | |
37 | ||
3157f602 XL |
38 | impl<T> Into<Vec<T>> for SmallVector<T> { |
39 | fn into(self) -> Vec<T> { | |
40 | match self.repr { | |
41 | Zero => Vec::new(), | |
42 | One(t) => vec![t], | |
43 | Many(vec) => vec, | |
44 | } | |
45 | } | |
46 | } | |
47 | ||
1a4d82fc | 48 | impl<T> FromIterator<T> for SmallVector<T> { |
85aaf69f | 49 | fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> SmallVector<T> { |
1a4d82fc JJ |
50 | let mut v = SmallVector::zero(); |
51 | v.extend(iter); | |
52 | v | |
53 | } | |
54 | } | |
55 | ||
56 | impl<T> Extend<T> for SmallVector<T> { | |
85aaf69f | 57 | fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) { |
1a4d82fc JJ |
58 | for val in iter { |
59 | self.push(val); | |
60 | } | |
61 | } | |
62 | } | |
63 | ||
64 | impl<T> SmallVector<T> { | |
65 | pub fn zero() -> SmallVector<T> { | |
66 | SmallVector { repr: Zero } | |
67 | } | |
68 | ||
69 | pub fn one(v: T) -> SmallVector<T> { | |
70 | SmallVector { repr: One(v) } | |
71 | } | |
72 | ||
73 | pub fn many(vs: Vec<T>) -> SmallVector<T> { | |
74 | SmallVector { repr: Many(vs) } | |
75 | } | |
76 | ||
92a42be0 | 77 | pub fn as_slice(&self) -> &[T] { |
1a4d82fc JJ |
78 | match self.repr { |
79 | Zero => { | |
80 | let result: &[T] = &[]; | |
81 | result | |
82 | } | |
d9579d0f | 83 | One(ref v) => { |
d9579d0f AL |
84 | unsafe { slice::from_raw_parts(v, 1) } |
85 | } | |
85aaf69f | 86 | Many(ref vs) => vs |
1a4d82fc JJ |
87 | } |
88 | } | |
89 | ||
9346a6ac AL |
90 | pub fn pop(&mut self) -> Option<T> { |
91 | match self.repr { | |
92 | Zero => None, | |
93 | One(..) => { | |
94 | let one = mem::replace(&mut self.repr, Zero); | |
95 | match one { | |
96 | One(v1) => Some(v1), | |
97 | _ => unreachable!() | |
98 | } | |
99 | } | |
100 | Many(ref mut vs) => vs.pop(), | |
101 | } | |
102 | } | |
103 | ||
1a4d82fc JJ |
104 | pub fn push(&mut self, v: T) { |
105 | match self.repr { | |
106 | Zero => self.repr = One(v), | |
107 | One(..) => { | |
108 | let one = mem::replace(&mut self.repr, Zero); | |
109 | match one { | |
110 | One(v1) => mem::replace(&mut self.repr, Many(vec!(v1, v))), | |
111 | _ => unreachable!() | |
112 | }; | |
113 | } | |
114 | Many(ref mut vs) => vs.push(v) | |
115 | } | |
116 | } | |
117 | ||
118 | pub fn push_all(&mut self, other: SmallVector<T>) { | |
119 | for v in other.into_iter() { | |
120 | self.push(v); | |
121 | } | |
122 | } | |
123 | ||
92a42be0 | 124 | pub fn get(&self, idx: usize) -> &T { |
1a4d82fc JJ |
125 | match self.repr { |
126 | One(ref v) if idx == 0 => v, | |
127 | Many(ref vs) => &vs[idx], | |
128 | _ => panic!("out of bounds access") | |
129 | } | |
130 | } | |
131 | ||
132 | pub fn expect_one(self, err: &'static str) -> T { | |
133 | match self.repr { | |
134 | One(v) => v, | |
135 | Many(v) => { | |
136 | if v.len() == 1 { | |
137 | v.into_iter().next().unwrap() | |
138 | } else { | |
139 | panic!(err) | |
140 | } | |
141 | } | |
142 | _ => panic!(err) | |
143 | } | |
144 | } | |
145 | ||
85aaf69f | 146 | pub fn len(&self) -> usize { |
1a4d82fc JJ |
147 | match self.repr { |
148 | Zero => 0, | |
149 | One(..) => 1, | |
150 | Many(ref vals) => vals.len() | |
151 | } | |
152 | } | |
153 | ||
154 | pub fn is_empty(&self) -> bool { self.len() == 0 } | |
3157f602 XL |
155 | |
156 | pub fn map<U, F: FnMut(T) -> U>(self, mut f: F) -> SmallVector<U> { | |
157 | let repr = match self.repr { | |
158 | Zero => Zero, | |
159 | One(t) => One(f(t)), | |
160 | Many(vec) => Many(vec.into_iter().map(f).collect()), | |
161 | }; | |
162 | SmallVector { repr: repr } | |
163 | } | |
1a4d82fc JJ |
164 | } |
165 | ||
92a42be0 SL |
166 | impl<T> IntoIterator for SmallVector<T> { |
167 | type Item = T; | |
168 | type IntoIter = IntoIter<T>; | |
169 | fn into_iter(self) -> Self::IntoIter { | |
170 | let repr = match self.repr { | |
171 | Zero => ZeroIterator, | |
172 | One(v) => OneIterator(v), | |
173 | Many(vs) => ManyIterator(vs.into_iter()) | |
174 | }; | |
175 | IntoIter { repr: repr } | |
176 | } | |
177 | } | |
178 | ||
1a4d82fc JJ |
179 | pub struct IntoIter<T> { |
180 | repr: IntoIterRepr<T>, | |
181 | } | |
182 | ||
183 | enum IntoIterRepr<T> { | |
184 | ZeroIterator, | |
185 | OneIterator(T), | |
186 | ManyIterator(vec::IntoIter<T>), | |
187 | } | |
188 | ||
189 | impl<T> Iterator for IntoIter<T> { | |
190 | type Item = T; | |
191 | ||
192 | fn next(&mut self) -> Option<T> { | |
193 | match self.repr { | |
194 | ZeroIterator => None, | |
195 | OneIterator(..) => { | |
196 | let mut replacement = ZeroIterator; | |
197 | mem::swap(&mut self.repr, &mut replacement); | |
198 | match replacement { | |
199 | OneIterator(v) => Some(v), | |
200 | _ => unreachable!() | |
201 | } | |
202 | } | |
203 | ManyIterator(ref mut inner) => inner.next() | |
204 | } | |
205 | } | |
206 | ||
85aaf69f | 207 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
208 | match self.repr { |
209 | ZeroIterator => (0, Some(0)), | |
210 | OneIterator(..) => (1, Some(1)), | |
211 | ManyIterator(ref inner) => inner.size_hint() | |
212 | } | |
213 | } | |
214 | } | |
215 | ||
216 | impl<T> MoveMap<T> for SmallVector<T> { | |
92a42be0 SL |
217 | fn move_flat_map<F, I>(self, mut f: F) -> Self |
218 | where F: FnMut(T) -> I, | |
219 | I: IntoIterator<Item=T> | |
220 | { | |
221 | match self.repr { | |
222 | Zero => Self::zero(), | |
223 | One(v) => f(v).into_iter().collect(), | |
224 | Many(vs) => SmallVector { repr: Many(vs.move_flat_map(f)) }, | |
225 | } | |
1a4d82fc JJ |
226 | } |
227 | } | |
228 | ||
229 | #[cfg(test)] | |
d9579d0f | 230 | mod tests { |
1a4d82fc JJ |
231 | use super::*; |
232 | ||
233 | #[test] | |
234 | fn test_len() { | |
85aaf69f | 235 | let v: SmallVector<isize> = SmallVector::zero(); |
1a4d82fc JJ |
236 | assert_eq!(0, v.len()); |
237 | ||
85aaf69f SL |
238 | assert_eq!(1, SmallVector::one(1).len()); |
239 | assert_eq!(5, SmallVector::many(vec![1, 2, 3, 4, 5]).len()); | |
1a4d82fc JJ |
240 | } |
241 | ||
242 | #[test] | |
243 | fn test_push_get() { | |
244 | let mut v = SmallVector::zero(); | |
85aaf69f | 245 | v.push(1); |
1a4d82fc JJ |
246 | assert_eq!(1, v.len()); |
247 | assert_eq!(&1, v.get(0)); | |
248 | v.push(2); | |
249 | assert_eq!(2, v.len()); | |
250 | assert_eq!(&2, v.get(1)); | |
251 | v.push(3); | |
252 | assert_eq!(3, v.len()); | |
253 | assert_eq!(&3, v.get(2)); | |
254 | } | |
255 | ||
256 | #[test] | |
257 | fn test_from_iter() { | |
85aaf69f | 258 | let v: SmallVector<isize> = (vec![1, 2, 3]).into_iter().collect(); |
1a4d82fc JJ |
259 | assert_eq!(3, v.len()); |
260 | assert_eq!(&1, v.get(0)); | |
261 | assert_eq!(&2, v.get(1)); | |
262 | assert_eq!(&3, v.get(2)); | |
263 | } | |
264 | ||
265 | #[test] | |
266 | fn test_move_iter() { | |
267 | let v = SmallVector::zero(); | |
85aaf69f | 268 | let v: Vec<isize> = v.into_iter().collect(); |
c34b1796 | 269 | assert_eq!(v, Vec::new()); |
1a4d82fc | 270 | |
85aaf69f | 271 | let v = SmallVector::one(1); |
c34b1796 | 272 | assert_eq!(v.into_iter().collect::<Vec<_>>(), [1]); |
1a4d82fc | 273 | |
85aaf69f | 274 | let v = SmallVector::many(vec![1, 2, 3]); |
c34b1796 | 275 | assert_eq!(v.into_iter().collect::<Vec<_>>(), [1, 2, 3]); |
1a4d82fc JJ |
276 | } |
277 | ||
278 | #[test] | |
c34b1796 | 279 | #[should_panic] |
1a4d82fc | 280 | fn test_expect_one_zero() { |
85aaf69f | 281 | let _: isize = SmallVector::zero().expect_one(""); |
1a4d82fc JJ |
282 | } |
283 | ||
284 | #[test] | |
c34b1796 | 285 | #[should_panic] |
1a4d82fc | 286 | fn test_expect_one_many() { |
85aaf69f | 287 | SmallVector::many(vec!(1, 2)).expect_one(""); |
1a4d82fc JJ |
288 | } |
289 | ||
290 | #[test] | |
291 | fn test_expect_one_one() { | |
85aaf69f SL |
292 | assert_eq!(1, SmallVector::one(1).expect_one("")); |
293 | assert_eq!(1, SmallVector::many(vec!(1)).expect_one("")); | |
1a4d82fc JJ |
294 | } |
295 | } |