use std::fmt;
use std::mem::replace;
use std::ptr::copy_nonoverlapping;
use std::ops::{Deref, DerefMut};
use std::iter::FromIterator;
use std::hash::{Hash, Hasher};
use std::hint::unreachable_unchecked;
use coalesce::{Coalesce2, coalesce};
use crate::array_vec::ArrayVec;
use crate::vector::Vector;
use crate::array::Array;
#[path = "index_impls.rs"]
mod index_impls;
pub trait Spilled<T> {
fn spill(v: T) -> Self;
}
impl<T: Array> Spilled<ArrayVec<T>> for Vec<T::Item> {
fn spill(mut v: ArrayVec<T>) -> Self {
let len = v.len();
let mut s = Self::with_capacity(len);
unsafe {
v.set_len(0);
copy_nonoverlapping(v.as_ptr(), s.as_mut_ptr(), len);
s.set_len(len);
}
s
}
}
pub struct SmallVec<T: Array, S = Vec<<T as Array>::Item>>(Coalesce2<ArrayVec<T>, S>);
impl<T: Array, S: Clone> Clone for SmallVec<T, S> where ArrayVec<T>: Clone {
fn clone(&self) -> Self {
SmallVec(self.0.clone())
}
}
impl<T: Array, S: Vector + Spilled<ArrayVec<T>>> SmallVec<T, S> {
#[inline]
pub fn spill(&mut self) {
if !self.is_spilled() {
match replace(&mut self.0, Coalesce2::B(S::new())) {
Coalesce2::A(v) => { self.0 = Coalesce2::B(S::spill(v)); },
_ => unsafe { unreachable_unchecked() },
}
}
}
#[inline]
pub fn is_spilled(&self) -> bool {
match self.0.as_ref() {
Coalesce2::A(..) => false,
Coalesce2::B(..) => true,
}
}
}
impl<T: Array, S> SmallVec<T, S> {
#[inline]
pub fn into_inner(self) -> Coalesce2<ArrayVec<T>, S> {
self.0
}
}
impl<T: Array, S> From<ArrayVec<T>> for SmallVec<T, S> {
fn from(v: ArrayVec<T>) -> Self {
SmallVec(Coalesce2::A(v))
}
}
unsafe impl<T: Array, S: Vector<Item=T::Item> + Spilled<ArrayVec<T>>> Vector for SmallVec<T, S> {
type Item = T::Item;
#[inline]
fn with_capacity(cap: usize) -> Self {
SmallVec(if cap > T::len() {
Coalesce2::B(S::with_capacity(cap))
} else {
Coalesce2::A(Default::default())
})
}
#[inline]
fn capacity(&self) -> usize {
let v = self.0.as_ref();
coalesce!(2 => |v| v.capacity())
}
#[inline]
fn reserve(&mut self, additional: usize) {
let cap = self.capacity() - self.len();
if cap < additional {
self.spill();
} else if cap >= additional {
return
}
let v = self.0.as_mut();
coalesce!(2 => |v| v.reserve(additional))
}
#[inline]
fn reserve_exact(&mut self, additional: usize) {
let cap = self.capacity() - self.len();
if cap < additional {
self.spill();
} else if cap > additional {
return
}
let v = self.0.as_mut();
coalesce!(2 => |v| v.reserve_exact(additional))
}
#[inline]
fn shrink_to_fit(&mut self) {
let v = self.0.as_mut();
coalesce!(2 => |v| v.shrink_to_fit())
}
#[inline]
fn into_boxed_slice(self) -> Box<[T::Item]> {
let v = self.into_inner();
coalesce!(2 => |v| v.into_boxed_slice())
}
#[inline]
unsafe fn set_len(&mut self, len: usize) {
let v = self.0.as_mut();
coalesce!(2 => |v| v.set_len(len))
}
#[inline]
fn len(&self) -> usize {
let v = self.0.as_ref();
coalesce!(2 => |v| v.len())
}
#[inline]
fn as_ptr(&self) -> *const T::Item {
let v = self.0.as_ref();
coalesce!(2 => |v| v.as_ptr())
}
#[inline]
fn as_mut_ptr(&mut self) -> *mut T::Item {
let v = self.0.as_mut();
coalesce!(2 => |v| v.as_mut_ptr())
}
}
impl<T: Array, S: Extend<T::Item>> Extend<T::Item> for SmallVec<T, S> where SmallVec<T, S>: Vector {
fn extend<I: IntoIterator<Item=T::Item>>(&mut self, iter: I) {
let iter = iter.into_iter();
self.reserve(iter.size_hint().0);
let v = self.0.as_mut();
coalesce!(2 => |v| v.extend(iter))
}
}
impl<T: Array, S: Extend<T::Item>> FromIterator<T::Item> for SmallVec<T, S> where SmallVec<T, S>: Vector {
fn from_iter<I: IntoIterator<Item=T::Item>>(iter: I) -> Self {
let mut s = Self::new();
s.extend(iter);
s
}
}
pub struct SmallVecIter<T1, T2>(Coalesce2<T1, T2>);
impl<T1: Iterator, T2: Iterator<Item=T1::Item>> Iterator for SmallVecIter<T1, T2> {
type Item = T1::Item;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
let v = self.0.as_mut();
coalesce!(2 => |v| v.next())
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let v = self.0.as_ref();
coalesce!(2 => |v| v.size_hint())
}
#[inline]
fn count(self) -> usize {
let v = self.0;
coalesce!(2 => |v| v.count())
}
}
impl<T: Array, S: IntoIterator<Item=<ArrayVec<T> as IntoIterator>::Item>> IntoIterator for SmallVec<T, S> where ArrayVec<T>: IntoIterator {
type Item = <S as IntoIterator>::Item;
type IntoIter = SmallVecIter<<ArrayVec<T> as IntoIterator>::IntoIter, <S as IntoIterator>::IntoIter>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
SmallVecIter(match self.0 {
Coalesce2::A(v) => Coalesce2::A(v.into_iter()),
Coalesce2::B(v) => Coalesce2::B(v.into_iter()),
})
}
}
impl<T: Array, S: Deref> Deref for SmallVec<T, S> where ArrayVec<T>: Deref<Target=S::Target> {
type Target = S::Target;
fn deref(&self) -> &Self::Target {
let v = self.0.as_ref();
coalesce!(2 => |v| v.deref())
}
}
impl<T: Array, S: DerefMut> DerefMut for SmallVec<T, S> where ArrayVec<T>: DerefMut + Deref<Target=S::Target> {
fn deref_mut(&mut self) -> &mut Self::Target {
let v = self.0.as_mut();
coalesce!(2 => |v| v.deref_mut())
}
}
impl<T: Array, S> Default for SmallVec<T, S> {
fn default() -> Self {
SmallVec(Coalesce2::A(Default::default()))
}
}
impl<T: Array, S: Hash> Hash for SmallVec<T, S> where ArrayVec<T>: Hash {
fn hash<H: Hasher>(&self, h: &mut H) {
let v = self.0.as_ref();
coalesce!(2 => |v| v.hash(h))
}
}
impl<T: Array, S: fmt::Debug + Vector<Item=T::Item> + Spilled<ArrayVec<T>>> fmt::Debug for SmallVec<T, S> where ArrayVec<T>: fmt::Debug {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
let v = self.0.as_ref();
fmt.debug_struct("SmallVec")
.field("is_spilled", &self.is_spilled())
.field("capacity", &self.capacity())
.field("data", &coalesce!(2 => |v| v as &dyn fmt::Debug))
.finish()
}
}
impl<'a, T: Array + 'a, S: Vector<Item=T::Item> + 'a> AsRef<dyn Vector<Item=T::Item> + 'a> for SmallVec<T, S> where T::Item: 'a, T::Index: 'a {
fn as_ref(&self) -> &(dyn Vector<Item=T::Item> + 'a) {
let v = self.0.as_ref();
coalesce!(2 => |v| v as &_)
}
}