extern crate odds;
extern crate nodrop;
use std::iter;
use std::mem;
use std::ptr;
use std::ops::{
Deref,
DerefMut,
};
use std::slice;
use nodrop::NoDrop;
use std::borrow::{Borrow, BorrowMut};
use std::hash::{Hash, Hasher};
use std::fmt;
mod array;
pub use array::Array;
pub use odds::IndexRange as RangeArgument;
use array::Index;
unsafe fn new_array<A: Array>() -> A {
mem::uninitialized()
}
pub struct ArrayVec<A: Array> {
xs: NoDrop<A>,
len: A::Index,
}
impl<A: Array> Drop for ArrayVec<A> {
fn drop(&mut self) {
while let Some(_) = self.pop() {
}
}
}
impl<A: Array> ArrayVec<A> {
pub fn new() -> ArrayVec<A> {
unsafe {
ArrayVec { xs: NoDrop::new(new_array()), len: Index::zero() }
}
}
#[inline]
pub fn len(&self) -> usize { self.len.to_usize() }
#[inline]
pub fn capacity(&self) -> usize { A::capacity() }
pub fn push(&mut self, element: A::Item) -> Option<A::Item> {
if self.len() < A::capacity() {
let len = self.len();
unsafe {
ptr::write(self.get_unchecked_mut(len), element);
self.set_len(len + 1);
}
None
} else {
Some(element)
}
}
pub fn pop(&mut self) -> Option<A::Item> {
if self.len() == 0 {
return None
}
unsafe {
let new_len = self.len() - 1;
self.set_len(new_len);
Some(ptr::read(self.get_unchecked_mut(new_len)))
}
}
pub fn insert(&mut self, index: usize, element: A::Item) -> Option<A::Item> {
if index >= self.capacity() {
return Some(element);
}
let mut ret = None;
let old_len = self.len();
if old_len == self.capacity() {
ret = self.pop();
}
let len = self.len();
unsafe { {
let p = self.as_mut_ptr().offset(index as isize);
ptr::copy(&*p, p.offset(1), len - index);
ptr::write(&mut *p, element);
}
self.set_len(len + 1);
}
ret
}
pub fn swap_remove(&mut self, index: usize) -> Option<A::Item> {
let len = self.len();
if index >= len {
return None
}
self.swap(index, len - 1);
self.pop()
}
pub fn remove(&mut self, index: usize) -> Option<A::Item> {
if index >= self.len() {
None
} else {
self.drain(index..index + 1).next()
}
}
pub fn clear(&mut self) {
while let Some(_) = self.pop() { }
}
#[inline]
pub unsafe fn set_len(&mut self, length: usize) {
debug_assert!(length <= self.capacity());
self.len = Index::from(length);
}
pub fn drain<R: RangeArgument>(&mut self, range: R) -> Drain<A> {
let len = self.len();
let start = range.start().unwrap_or(0);
let end = range.end().unwrap_or(len);
let range_slice: *const _ = &self[start..end];
unsafe {
self.set_len(start);
Drain {
tail_start: end,
tail_len: len - end,
iter: (*range_slice).iter(),
vec: self as *mut _,
}
}
}
pub fn into_inner(self) -> Result<A, Self> {
if self.len() < self.capacity() {
Err(self)
} else {
unsafe {
let array = ptr::read(&*self.xs);
mem::forget(self);
Ok(array)
}
}
}
}
impl<A: Array> Deref for ArrayVec<A> {
type Target = [A::Item];
#[inline]
fn deref(&self) -> &[A::Item] {
unsafe {
slice::from_raw_parts(self.xs.as_ptr(), self.len())
}
}
}
impl<A: Array> DerefMut for ArrayVec<A> {
#[inline]
fn deref_mut(&mut self) -> &mut [A::Item] {
let len = self.len();
unsafe {
slice::from_raw_parts_mut(self.xs.as_mut_ptr(), len)
}
}
}
impl<A: Array> From<A> for ArrayVec<A> {
fn from(array: A) -> Self {
ArrayVec { xs: NoDrop::new(array), len: Index::from(A::capacity()) }
}
}
impl<'a, A: Array> IntoIterator for &'a ArrayVec<A> {
type Item = &'a A::Item;
type IntoIter = slice::Iter<'a, A::Item>;
fn into_iter(self) -> Self::IntoIter { self.iter() }
}
impl<'a, A: Array> IntoIterator for &'a mut ArrayVec<A> {
type Item = &'a mut A::Item;
type IntoIter = slice::IterMut<'a, A::Item>;
fn into_iter(self) -> Self::IntoIter { self.iter_mut() }
}
impl<A: Array> IntoIterator for ArrayVec<A> {
type Item = A::Item;
type IntoIter = IntoIter<A>;
fn into_iter(self) -> IntoIter<A> {
IntoIter { index: Index::zero(), v: self, }
}
}
pub struct IntoIter<A: Array> {
index: A::Index,
v: ArrayVec<A>,
}
impl<A: Array> Iterator for IntoIter<A> {
type Item = A::Item;
#[inline]
fn next(&mut self) -> Option<A::Item> {
if self.index == self.v.len {
None
} else {
unsafe {
let index = self.index.to_usize();
self.index = Index::from(index + 1);
Some(ptr::read(self.v.get_unchecked_mut(index)))
}
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.v.len() - self.index.to_usize();
(len, Some(len))
}
}
impl<A: Array> DoubleEndedIterator for IntoIter<A> {
#[inline]
fn next_back(&mut self) -> Option<A::Item> {
if self.index == self.v.len {
None
} else {
unsafe {
let new_len = self.v.len() - 1;
self.v.set_len(new_len);
Some(ptr::read(self.v.get_unchecked_mut(new_len)))
}
}
}
}
impl<A: Array> ExactSizeIterator for IntoIter<A> { }
impl<A: Array> Drop for IntoIter<A> {
fn drop(&mut self) {
let index = self.index.to_usize();
let len = self.v.len();
unsafe {
self.v.set_len(0);
let elements = slice::from_raw_parts(self.v.get_unchecked_mut(index),
len - index);
for elt in elements {
ptr::read(elt);
}
}
}
}
pub struct Drain<'a, A>
where A: Array,
A::Item: 'a,
{
tail_start: usize,
tail_len: usize,
iter: slice::Iter<'a, A::Item>,
vec: *mut ArrayVec<A>,
}
unsafe impl<'a, A: Array + Sync> Sync for Drain<'a, A> {}
unsafe impl<'a, A: Array + Send> Send for Drain<'a, A> {}
impl<'a, A: Array> Iterator for Drain<'a, A>
where A::Item: 'a,
{
type Item = A::Item;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(|elt|
unsafe {
ptr::read(elt as *const _)
}
)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<'a, A: Array> DoubleEndedIterator for Drain<'a, A>
where A::Item: 'a,
{
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
self.iter.next_back().map(|elt|
unsafe {
ptr::read(elt as *const _)
}
)
}
}
impl<'a, A: Array> ExactSizeIterator for Drain<'a, A> where A::Item: 'a {}
impl<'a, A: Array> Drop for Drain<'a, A>
where A::Item: 'a
{
fn drop(&mut self) {
while let Some(_) = self.next() { }
if self.tail_len > 0 {
unsafe {
let source_vec = &mut *self.vec;
let start = source_vec.len();
let tail = self.tail_start;
let src = source_vec.as_ptr().offset(tail as isize);
let dst = source_vec.as_mut_ptr().offset(start as isize);
ptr::copy(src, dst, self.tail_len);
source_vec.set_len(start + self.tail_len);
}
}
}
}
impl<A: Array> Extend<A::Item> for ArrayVec<A> {
fn extend<T: IntoIterator<Item=A::Item>>(&mut self, iter: T) {
let take = self.capacity() - self.len();
for elt in iter.into_iter().take(take) {
self.push(elt);
}
}
}
impl<A: Array> iter::FromIterator<A::Item> for ArrayVec<A> {
fn from_iter<T: IntoIterator<Item=A::Item>>(iter: T) -> Self {
let mut array = ArrayVec::new();
array.extend(iter);
array
}
}
impl<A: Array> Clone for ArrayVec<A>
where A::Item: Clone
{
fn clone(&self) -> Self {
self.iter().cloned().collect()
}
}
impl<A: Array> Hash for ArrayVec<A>
where A::Item: Hash
{
fn hash<H: Hasher>(&self, state: &mut H) {
Hash::hash(&**self, state)
}
}
impl<A: Array> PartialEq for ArrayVec<A>
where A::Item: PartialEq
{
fn eq(&self, other: &Self) -> bool {
**self == **other
}
}
impl<A: Array> Eq for ArrayVec<A> where A::Item: Eq { }
impl<A: Array> Borrow<[A::Item]> for ArrayVec<A> {
fn borrow(&self) -> &[A::Item] { self }
}
impl<A: Array> BorrowMut<[A::Item]> for ArrayVec<A> {
fn borrow_mut(&mut self) -> &mut [A::Item] { self }
}
impl<A: Array> AsRef<[A::Item]> for ArrayVec<A> {
fn as_ref(&self) -> &[A::Item] { self }
}
impl<A: Array> AsMut<[A::Item]> for ArrayVec<A> {
fn as_mut(&mut self) -> &mut [A::Item] { self }
}
impl<A: Array> fmt::Debug for ArrayVec<A> where A::Item: fmt::Debug {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { (**self).fmt(f) }
}