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
::{IntoIterator, 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
: IntoIterator
<Item
=T
>>(iter
: I
) -> SmallVector
<T
> {
34 let mut v
= SmallVector
::zero();
40 impl<T
> Extend
<T
> for SmallVector
<T
> {
41 fn extend
<I
: IntoIterator
<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
!(v
, Vec
::new());
231 let v
= SmallVector
::one(1);
232 assert_eq
!(v
.into_iter().collect
::<Vec
<_
>>(), [1]);
234 let v
= SmallVector
::many(vec
![1, 2, 3]);
235 assert_eq
!(v
.into_iter().collect
::<Vec
<_
>>(), [1, 2, 3]);
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(""));