smallvec into_iter

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

//! Small vectors in various sizes. These store a certain number of elements inline, and fall back
//! to the heap for larger allocations.  This can be a useful optimization for improving cache
//! locality and reducing allocator traffic for workloads that fit within the inline buffer.

use std::borrow::{Borrow, BorrowMut};
use std::cmp;
use std::fmt;
use std::hash::{Hash, Hasher};
use std::iter::{IntoIterator, FromIterator};
use std::mem;
use std::ops;
use std::ptr;
use std::slice;
use std::os::raw::c_void;

use SmallVecData::{Inline, Heap};

/// Common operations implemented by both `Vec` and `SmallVec`.
///
/// This can be used to write generic code that works with both `Vec` and `SmallVec`.
///
/// ## Example
///
/// ```rust
/// use smallvec::{VecLike, SmallVec8};
///
/// fn initialize<V: VecLike<u8>>(v: &mut V) {
///     for i in 0..5 {
///         v.push(i);
///     }
/// }
///
/// let mut vec = Vec::new();
/// initialize(&mut vec);
///
/// let mut small_vec = SmallVec8::new();
/// initialize(&mut small_vec);
/// ```
pub trait VecLike<T>:
        ops::Index<usize, Output=T> +
        ops::IndexMut<usize> +
        ops::Index<ops::Range<usize>, Output=[T]> +
        ops::IndexMut<ops::Range<usize>> +
        ops::Index<ops::RangeFrom<usize>, Output=[T]> +
        ops::IndexMut<ops::RangeFrom<usize>> +
        ops::Index<ops::RangeTo<usize>, Output=[T]> +
        ops::IndexMut<ops::RangeTo<usize>> +
        ops::Index<ops::RangeFull, Output=[T]> +
        ops::IndexMut<ops::RangeFull> +
        ops::DerefMut<Target = [T]> +
        Extend<T> {

    /// Append an element to the vector.
    fn push(&mut self, value: T);
}

impl<T> VecLike<T> for Vec<T> {
    #[inline]
    fn push(&mut self, value: T) {
        Vec::push(self, value);
    }
}

unsafe fn deallocate<T>(ptr: *mut T, capacity: usize) {
    let _vec: Vec<T> = Vec::from_raw_parts(ptr, 0, capacity);
    // Let it drop.
}

pub struct Drain<'a, T: 'a> {
    iter: slice::IterMut<'a,T>,
}

impl<'a, T: 'a> Iterator for Drain<'a,T> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        match self.iter.next() {
            None => None,
            Some(reference) => {
                unsafe {
                    Some(ptr::read(reference))
                }
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}

impl<'a, T: 'a> DoubleEndedIterator for Drain<'a, T> {
    #[inline]
    fn next_back(&mut self) -> Option<T> {
        match self.iter.next_back() {
            None => None,
            Some(reference) => {
                unsafe {
                    Some(ptr::read(reference))
                }
            }
        }
    }
}

impl<'a, T> ExactSizeIterator for Drain<'a, T> { }

impl<'a, T: 'a> Drop for Drain<'a,T> {
    fn drop(&mut self) {
        // Destroy the remaining elements.
        for _ in self.by_ref() {}
    }
}

enum SmallVecData<A: Array> {
    Inline { array: A },
    Heap { ptr: *mut A::Item, capacity: usize },
}

impl<A: Array> SmallVecData<A> {
    fn ptr_mut(&mut self) -> *mut A::Item {
        match *self {
            Inline { ref mut array } => array.ptr_mut(),
            Heap { ptr, .. } => ptr,
        }
    }
}

unsafe impl<A: Array + Send> Send for SmallVecData<A> {}
unsafe impl<A: Array + Sync> Sync for SmallVecData<A> {}

impl<A: Array> Drop for SmallVecData<A> {
    fn drop(&mut self) {
        unsafe {
            match *self {
                ref mut inline @ Inline { .. } => {
                    // Inhibit the array destructor.
                    ptr::write(inline, Heap {
                        ptr: ptr::null_mut(),
                        capacity: 0,
                    });
                }
                Heap { ptr, capacity } => deallocate(ptr, capacity),
            }
        }
    }
}

/// A `Vec`-like container that can store a small number of elements inline.
///
/// `SmallVec` acts like a vector, but can store a limited amount of data inline within the
/// `Smallvec` struct rather than in a separate allocation.  If the data exceeds this limit, the
/// `SmallVec` will "spill" its data onto the heap, allocating a new buffer to hold it.
///
/// The amount of data that a `SmallVec` can store inline depends on its backing store. The backing
/// store can be any type that implements the `Array` trait; usually it is a small fixed-sized
/// array.  For example a `SmallVec<[u64; 8]>` can hold up to eight 64-bit integers inline.
///
/// Type aliases like `SmallVec8<T>` are provided as convenient shorthand for types like
/// `SmallVec<[T; 8]>`.
///
/// ## Example
///
/// ```rust
/// use smallvec::SmallVec;
/// let mut v = SmallVec::<[u8; 4]>::new(); // initialize an empty vector
///
/// use smallvec::SmallVec4;
/// let mut v: SmallVec4<u8> = SmallVec::new(); // alternate way to write the above
///
/// // SmallVec4 can hold up to 4 items without spilling onto the heap.
/// v.extend(0..4);
/// assert_eq!(v.len(), 4);
/// assert!(!v.spilled());
///
/// // Pushing another element will force the buffer to spill:
/// v.push(4);
/// assert_eq!(v.len(), 5);
/// assert!(v.spilled());
/// ```
pub struct SmallVec<A: Array> {
    len: usize,
    data: SmallVecData<A>,
}

impl<A: Array> SmallVec<A> {
    /// Construct an empty vector
    #[inline]
    pub fn new() -> SmallVec<A> {
        unsafe {
            SmallVec {
                len: 0,
                data: Inline { array: mem::uninitialized() },
            }
        }
    }

    /// Construct a new `SmallVec` from a `Vec<A::Item>` without copying
    /// elements.
    ///
    /// ```rust
    /// use smallvec::SmallVec;
    ///
    /// let vec = vec![1, 2, 3, 4, 5];
    /// let small_vec: SmallVec<[_; 3]> = SmallVec::from_vec(vec);
    ///
    /// assert_eq!(&*small_vec, &[1, 2, 3, 4, 5]);
    /// ```
    #[inline]
    pub fn from_vec(mut vec: Vec<A::Item>) -> SmallVec<A> {
        let (ptr, cap, len) = (vec.as_mut_ptr(), vec.capacity(), vec.len());
        mem::forget(vec);

        SmallVec {
            len: len,
            data: SmallVecData::Heap {
                ptr: ptr,
                capacity: cap
            }
        }
    }

    /// Sets the length of a vector.
    ///
    /// This will explicitly set the size of the vector, without actually
    /// modifying its buffers, so it is up to the caller to ensure that the
    /// vector is actually the specified size.
    pub unsafe fn set_len(&mut self, new_len: usize) {
        self.len = new_len
    }

    /// The maximum number of elements this vector can hold inline
    #[inline]
    pub fn inline_size(&self) -> usize {
        A::size()
    }

    /// The number of elements stored in the vector
    #[inline]
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` if the vector is empty
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// The number of items the vector can hold without reallocating
    #[inline]
    pub fn capacity(&self) -> usize {
        match self.data {
            Inline { .. } => A::size(),
            Heap { capacity, .. } => capacity,
        }
    }

    /// Returns `true` if the data has spilled into a separate heap-allocated buffer.
    #[inline]
    pub fn spilled(&self) -> bool {
        match self.data {
            Inline { .. } => false,
            Heap { .. } => true,
        }
    }

    /// Empty the vector and return an iterator over its former contents.
    pub fn drain(&mut self) -> Drain<A::Item> {
        unsafe {
            let current_len = self.len();
            self.set_len(0);

            let ptr = self.data.ptr_mut();

            let slice = slice::from_raw_parts_mut(ptr, current_len);

            Drain {
                iter: slice.iter_mut(),
            }
        }
    }

    /// Append an item to the vector.
    #[inline]
    pub fn push(&mut self, value: A::Item) {
        let cap = self.capacity();
        if self.len == cap {
            self.grow(cmp::max(cap * 2, 1))
        }
        unsafe {
            let end = self.as_mut_ptr().offset(self.len as isize);
            ptr::write(end, value);
            let len = self.len;
            self.set_len(len + 1)
        }
    }

    /// Append elements from an iterator.
    ///
    /// This function is deprecated; it has been replaced by `Extend::extend`.
    #[deprecated(note = "Use `extend` instead")]
    pub fn push_all_move<V: IntoIterator<Item=A::Item>>(&mut self, other: V) {
        self.extend(other)
    }

    /// Remove an item from the end of the vector and return it, or None if empty.
    #[inline]
    pub fn pop(&mut self) -> Option<A::Item> {
        if self.len == 0 {
            return None
        }
        let last_index = self.len - 1;
        if (last_index as isize) < 0 {
            panic!("overflow")
        }
        unsafe {
            let end_ptr = self.as_mut_ptr().offset(last_index as isize);
            let value = ptr::replace(end_ptr, mem::uninitialized());
            self.set_len(last_index);
            Some(value)
        }
    }

    /// Re-allocate to set the capacity to `new_cap`.
    ///
    /// Panics if `new_cap` is less than the vector's length.
    pub fn grow(&mut self, new_cap: usize) {
        assert!(new_cap >= self.len);
        let mut vec: Vec<A::Item> = Vec::with_capacity(new_cap);
        let new_alloc = vec.as_mut_ptr();
        unsafe {
            mem::forget(vec);
            ptr::copy_nonoverlapping(self.as_ptr(), new_alloc, self.len);

            match self.data {
                Inline { .. } => {}
                Heap { ptr, capacity } => deallocate(ptr, capacity),
            }
            ptr::write(&mut self.data, Heap {
                ptr: new_alloc,
                capacity: new_cap,
            });
        }
    }

    /// Reserve capacity for `additional` more elements to be inserted.
    ///
    /// May reserve more space to avoid frequent reallocations.
    ///
    /// If the new capacity would overflow `usize` then it will be set to `usize::max_value()`
    /// instead. (This means that inserting `additional` new elements is not guaranteed to be
    /// possible after calling this function.)
    pub fn reserve(&mut self, additional: usize) {
        let len = self.len();
        if self.capacity() - len < additional {
            match len.checked_add(additional).and_then(usize::checked_next_power_of_two) {
                Some(cap) => self.grow(cap),
                None => self.grow(usize::max_value()),
            }
        }
    }

    /// Reserve the minumum capacity for `additional` more elements to be inserted.
    ///
    /// Panics if the new capacity overflows `usize`.
    pub fn reserve_exact(&mut self, additional: usize) {
        let len = self.len();
        if self.capacity() - len < additional {
            match len.checked_add(additional) {
                Some(cap) => self.grow(cap),
                None => panic!("reserve_exact overflow"),
            }
        }
    }

    /// Shrink the capacity of the vector as much as possible.
    ///
    /// When possible, this will move data from an external heap buffer to the vector's inline
    /// storage.
    pub fn shrink_to_fit(&mut self) {
        let len = self.len;
        if self.inline_size() >= len {
            unsafe {
                let (ptr, capacity) = match self.data {
                    Inline { .. } => return,
                    Heap { ptr, capacity } => (ptr, capacity),
                };
                ptr::write(&mut self.data, Inline { array: mem::uninitialized() });
                ptr::copy_nonoverlapping(ptr, self.as_mut_ptr(), len);
                deallocate(ptr, capacity);
            }
        } else if self.capacity() > len {
            self.grow(len);
        }
    }

    /// Shorten the vector, keeping the first `len` elements and dropping the rest.
    ///
    /// If `len` is greater than or equal to the vector's current length, this has no
    /// effect.
    ///
    /// This does not re-allocate.  If you want the vector's capacity to shrink, call
    /// `shrink_to_fit` after truncating.
    pub fn truncate(&mut self, len: usize) {
        let end_ptr = self.as_ptr();
        while len < self.len {
            unsafe {
                let last_index = self.len - 1;
                self.set_len(last_index);
                ptr::read(end_ptr.offset(last_index as isize));
            }
        }
    }

    /// Remove the element at position `index`, replacing it with the last element.
    ///
    /// This does not preserve ordering, but is O(1).
    ///
    /// Panics if `index` is out of bounds.
    #[inline]
    pub fn swap_remove(&mut self, index: usize) -> A::Item {
        let len = self.len;
        self.swap(len - 1, index);
        self.pop().unwrap()
    }

    /// Remove all elements from the vector.
    #[inline]
    pub fn clear(&mut self) {
        self.truncate(0);
    }

    /// Remove and return the element at position `index`, shifting all elements after it to the
    /// left.
    ///
    /// Panics if `index` is out of bounds.
    pub fn remove(&mut self, index: usize) -> A::Item {
        let len = self.len();

        assert!(index < len);

        unsafe {
            let ptr = self.as_mut_ptr().offset(index as isize);
            let item = ptr::read(ptr);
            ptr::copy(ptr.offset(1), ptr, len - index - 1);
            self.set_len(len - 1);
            item
        }
    }

    /// Insert an element at position `index`, shifting all elements after it to the right.
    ///
    /// Panics if `index` is out of bounds.
    pub fn insert(&mut self, index: usize, element: A::Item) {
        self.reserve(1);

        let len = self.len;
        assert!(index <= len);

        unsafe {
            let ptr = self.as_mut_ptr().offset(index as isize);
            ptr::copy(ptr, ptr.offset(1), len - index);
            ptr::write(ptr, element);
            self.set_len(len + 1);
        }
    }

    pub fn insert_many<I: IntoIterator<Item=A::Item>>(&mut self, index: usize, iterable: I) {
        let iter = iterable.into_iter();
        let (lower_size_bound, _) = iter.size_hint();
        assert!(lower_size_bound <= std::isize::MAX as usize);  // Ensure offset is indexable
        assert!(index + lower_size_bound >= index);  // Protect against overflow
        self.reserve(lower_size_bound);

        unsafe {
            let old_len = self.len;
            assert!(index <= old_len);
            let ptr = self.as_mut_ptr().offset(index as isize);
            ptr::copy(ptr, ptr.offset(lower_size_bound as isize), old_len - index);
            for (off, element) in iter.enumerate() {
                if off < lower_size_bound {
                    ptr::write(ptr.offset(off as isize), element);
                    self.len = self.len + 1;
                } else {
                    // Iterator provided more elements than the hint.
                    assert!(index + off >= index);  // Protect against overflow.
                    self.insert(index + off, element);
                }
            }
            let num_added = self.len - old_len;
            if num_added < lower_size_bound {
                // Iterator provided fewer elements than the hint
                ptr::copy(ptr.offset(lower_size_bound as isize), ptr.offset(num_added as isize), old_len - index);
            }
        }
    }

    /// Convert a SmallVec to a Vec, without reallocating if the SmallVec has already spilled onto
    /// the heap.
    pub fn into_vec(self) -> Vec<A::Item> {
        match self.data {
            Inline { .. } => self.into_iter().collect(),
            Heap { ptr, capacity } => unsafe {
                let v = Vec::from_raw_parts(ptr, self.len, capacity);
                mem::forget(self);
                v
            }
        }
    }
}

impl<A: Array> SmallVec<A> where A::Item: Copy {
    pub fn from_slice(slice: &[A::Item]) -> Self {
        let mut vec = Self::new();
        vec.extend_from_slice(slice);
        vec
    }

    pub fn insert_from_slice(&mut self, index: usize, slice: &[A::Item]) {
        self.reserve(slice.len());

        let len = self.len;
        assert!(index <= len);

        unsafe {
            let slice_ptr = slice.as_ptr();
            let ptr = self.as_mut_ptr().offset(index as isize);
            ptr::copy(ptr, ptr.offset(slice.len() as isize), len - index);
            ptr::copy(slice_ptr, ptr, slice.len());
            self.set_len(len + slice.len());
        }
    }

    #[inline]
    pub fn extend_from_slice(&mut self, slice: &[A::Item]) {
        let len = self.len();
        self.insert_from_slice(len, slice);
    }
}

impl<A: Array> ops::Deref for SmallVec<A> {
    type Target = [A::Item];
    #[inline]
    fn deref(&self) -> &[A::Item] {
        let ptr: *const _ = match self.data {
            Inline { ref array } => array.ptr(),
            Heap { ptr, .. } => ptr,
        };
        unsafe {
            slice::from_raw_parts(ptr, self.len)
        }
    }
}

impl<A: Array> ops::DerefMut for SmallVec<A> {
    #[inline]
    fn deref_mut(&mut self) -> &mut [A::Item] {
        let ptr = self.data.ptr_mut();
        unsafe {
            slice::from_raw_parts_mut(ptr, self.len)
        }
    }
}

impl<A: Array> AsRef<[A::Item]> for SmallVec<A> {
    #[inline]
    fn as_ref(&self) -> &[A::Item] {
        self
    }
}

impl<A: Array> AsMut<[A::Item]> for SmallVec<A> {
    #[inline]
    fn as_mut(&mut self) -> &mut [A::Item] {
        self
    }
}

impl<A: Array> Borrow<[A::Item]> for SmallVec<A> {
    #[inline]
    fn borrow(&self) -> &[A::Item] {
        self
    }
}

impl<A: Array> BorrowMut<[A::Item]> for SmallVec<A> {
    #[inline]
    fn borrow_mut(&mut self) -> &mut [A::Item] {
        self
    }
}

impl<'a, A: Array> From<&'a [A::Item]> for SmallVec<A> where A::Item: Clone {
    #[inline]
    fn from(slice: &'a [A::Item]) -> SmallVec<A> {
        slice.into_iter().cloned().collect()
    }
}

macro_rules! impl_index {
    ($index_type: ty, $output_type: ty) => {
        impl<A: Array> ops::Index<$index_type> for SmallVec<A> {
            type Output = $output_type;
            #[inline]
            fn index(&self, index: $index_type) -> &$output_type {
                &(&**self)[index]
            }
        }

        impl<A: Array> ops::IndexMut<$index_type> for SmallVec<A> {
            #[inline]
            fn index_mut(&mut self, index: $index_type) -> &mut $output_type {
                &mut (&mut **self)[index]
            }
        }
    }
}

impl_index!(usize, A::Item);
impl_index!(ops::Range<usize>, [A::Item]);
impl_index!(ops::RangeFrom<usize>, [A::Item]);
impl_index!(ops::RangeTo<usize>, [A::Item]);
impl_index!(ops::RangeFull, [A::Item]);


impl<A: Array> VecLike<A::Item> for SmallVec<A> {
    #[inline]
    fn push(&mut self, value: A::Item) {
        SmallVec::push(self, value);
    }
}

impl<A: Array> FromIterator<A::Item> for SmallVec<A> {
    fn from_iter<I: IntoIterator<Item=A::Item>>(iterable: I) -> SmallVec<A> {
        let mut v = SmallVec::new();
        v.extend(iterable);
        v
    }
}

impl<A: Array> Extend<A::Item> for SmallVec<A> {
    fn extend<I: IntoIterator<Item=A::Item>>(&mut self, iterable: I) {
        let iter = iterable.into_iter();
        let (lower_size_bound, _) = iter.size_hint();

        let target_len = self.len + lower_size_bound;

        if target_len > self.capacity() {
           self.grow(target_len);
        }

        for elem in iter {
            self.push(elem);
        }
    }
}

impl<A: Array> fmt::Debug for SmallVec<A> where A::Item: fmt::Debug {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?}", &**self)
    }
}

impl<A: Array> Default for SmallVec<A> {
    #[inline]
    fn default() -> SmallVec<A> {
        SmallVec::new()
    }
}

impl<A: Array> Drop for SmallVec<A> {
    fn drop(&mut self) {
        // Note on panic safety: dropping an element may panic,
        // but the inner SmallVecData destructor will still run
        unsafe {
            let ptr = self.as_ptr();
            for i in 0 .. self.len {
                ptr::read(ptr.offset(i as isize));
            }
        }
    }
}

impl<A: Array> Clone for SmallVec<A> where A::Item: Clone {
    fn clone(&self) -> SmallVec<A> {
        let mut new_vector = SmallVec::new();
        for element in self.iter() {
            new_vector.push((*element).clone())
        }
        new_vector
    }
}

impl<A: Array, B: Array> PartialEq<SmallVec<B>> for SmallVec<A>
    where A::Item: PartialEq<B::Item> {
    #[inline]
    fn eq(&self, other: &SmallVec<B>) -> bool { self[..] == other[..] }
    #[inline]
    fn ne(&self, other: &SmallVec<B>) -> bool { self[..] != other[..] }
}

impl<A: Array> Eq for SmallVec<A> where A::Item: Eq {}

impl<A: Array> PartialOrd for SmallVec<A> where A::Item: PartialOrd {
    #[inline]
    fn partial_cmp(&self, other: &SmallVec<A>) -> Option<cmp::Ordering> {
        PartialOrd::partial_cmp(&**self, &**other)
    }
}

impl<A: Array> Ord for SmallVec<A> where A::Item: Ord {
    #[inline]
    fn cmp(&self, other: &SmallVec<A>) -> cmp::Ordering {
        Ord::cmp(&**self, &**other)
    }
}

impl<A: Array> Hash for SmallVec<A> where A::Item: Hash {
    fn hash<H: Hasher>(&self, state: &mut H) {
        (**self).hash(state)
    }
}

unsafe impl<A: Array> Send for SmallVec<A> where A::Item: Send {}

pub struct IntoIter<A: Array> {
    data: SmallVecData<A>,
    current: usize,
    end: usize,
}

impl<A: Array> Drop for IntoIter<A> {
    fn drop(&mut self) {
        for _ in self { }
    }
}

impl<A: Array> Iterator for IntoIter<A> {
    type Item = A::Item;

    #[inline]
    fn next(&mut self) -> Option<A::Item> {
        if self.current == self.end {
            None
        }
        else {
            unsafe {
                let current = self.current as isize;
                self.current += 1;
                Some(ptr::read(self.data.ptr_mut().offset(current)))
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let size = self.end - self.current;
        (size, Some(size))
    }
}

impl<A: Array> DoubleEndedIterator for IntoIter<A> {
    #[inline]
    fn next_back(&mut self) -> Option<A::Item> {
        if self.current == self.end {
            None
        }
        else {
            unsafe {
                self.end -= 1;
                Some(ptr::read(self.data.ptr_mut().offset(self.end as isize)))
            }
        }
    }
}

impl<A: Array> ExactSizeIterator for IntoIter<A> { }

impl<A: Array> IntoIterator for SmallVec<A> {
    type IntoIter = IntoIter<A>;
    type Item = A::Item;
    fn into_iter(mut self) -> Self::IntoIter {
        let len = self.len();
        unsafe {
            // Only grab the `data` field, the `IntoIter` type handles dropping of the elements
            let data = ptr::read(&mut self.data);
            mem::forget(self);
            IntoIter {
                data: data,
                current: 0,
                end: len,
            }
        }
    }
}

impl<'a, A: Array> IntoIterator for &'a SmallVec<A> {
    type IntoIter = slice::Iter<'a, A::Item>;
    type Item = &'a A::Item;
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, A: Array> IntoIterator for &'a mut SmallVec<A> {
    type IntoIter = slice::IterMut<'a, A::Item>;
    type Item = &'a mut A::Item;
    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

// TODO: Remove these and its users.

/// Deprecated alias to ease transition from an earlier version.
#[deprecated]
pub type SmallVec1<T> = SmallVec<[T; 1]>;

/// Deprecated alias to ease transition from an earlier version.
#[deprecated]
pub type SmallVec2<T> = SmallVec<[T; 2]>;

/// Deprecated alias to ease transition from an earlier version.
#[deprecated]
pub type SmallVec4<T> = SmallVec<[T; 4]>;

/// Deprecated alias to ease transition from an earlier version.
#[deprecated]
pub type SmallVec8<T> = SmallVec<[T; 8]>;

/// Deprecated alias to ease transition from an earlier version.
#[deprecated]
pub type SmallVec16<T> = SmallVec<[T; 16]>;

/// Deprecated alias to ease transition from an earlier version.
#[deprecated]
pub type SmallVec24<T> = SmallVec<[T; 24]>;

/// Deprecated alias to ease transition from an earlier version.
#[deprecated]
pub type SmallVec32<T> = SmallVec<[T; 32]>;

/// Types that can be used as the backing store for a SmallVec
pub unsafe trait Array {
    type Item;
    fn size() -> usize;
    fn ptr(&self) -> *const Self::Item;
    fn ptr_mut(&mut self) -> *mut Self::Item;
}

macro_rules! impl_array(
    ($($size:expr),+) => {
        $(
            unsafe impl<T> Array for [T; $size] {
                type Item = T;
                fn size() -> usize { $size }
                fn ptr(&self) -> *const T { &self[0] }
                fn ptr_mut(&mut self) -> *mut T { &mut self[0] }
            }
        )+
    }
);

impl_array!(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36,
            0x40, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000,
            0x10000, 0x20000, 0x40000, 0x80000, 0x100000);

fn main() {
    let mut a = SmallVec::<[usize; 32]>::new();
    for _ in 0..2 { a.push(42); }
    for x in a.into_iter() {
        println!("{}", x);
    }
}