#![no_std]
#![allow(incomplete_features)]
#![feature(doc_cfg)]
#![feature(core_intrinsics)]
#![feature(const_fn)]
#![feature(const_generics)]
#![feature(maybe_uninit_ref)]
#![feature(maybe_uninit_extra)]
#![feature(exact_size_is_empty)]
#[cfg(feature = "std")]
extern crate alloc;
#[cfg(rustdoc)]
use alloc::vec::Vec;
pub use crate::iterators::*;
use crate::utils::*;
use core::cmp::{Ord, PartialEq};
use core::iter::FromIterator;
use core::marker::PhantomData;
use core::mem::MaybeUninit;
use core::ops::{Bound::Excluded, Bound::Included, Bound::Unbounded, Index, IndexMut, RangeBounds};
use core::ptr;
mod iterators;
mod macros;
#[doc(hidden)]
pub mod utils;
pub struct StaticVec<T, const N: usize> {
data: [MaybeUninit<T>; N],
length: usize,
}
impl<T, const N: usize> StaticVec<T, {N}> {
#[inline(always)]
pub fn new() -> Self {
unsafe {
Self {
data: MaybeUninit::uninit().assume_init(),
length: 0,
}
}
}
#[inline]
pub fn new_from_slice(values: &[T]) -> Self
where T: Copy {
unsafe {
let mut data_: [MaybeUninit<T>; N] = MaybeUninit::uninit().assume_init();
let fill_length = values.len().min(N);
values
.as_ptr()
.copy_to_nonoverlapping(data_.as_mut_ptr() as *mut T, fill_length);
Self {
data: data_,
length: fill_length,
}
}
}
#[inline]
pub fn filled_with<F>(mut initializer: F) -> Self
where F: FnMut() -> T {
let mut res = Self::new();
for i in 0..N {
unsafe {
res.data.get_unchecked_mut(i).write(initializer());
res.length += 1;
}
}
res
}
#[inline(always)]
pub fn len(&self) -> usize {
self.length
}
#[inline(always)]
pub const fn capacity(&self) -> usize {
N
}
#[inline(always)]
pub unsafe fn set_len(&mut self, new_len: usize) {
self.length = new_len;
}
#[inline(always)]
pub fn is_empty(&self) -> bool {
self.length == 0
}
#[inline(always)]
pub fn is_not_empty(&self) -> bool {
self.length > 0
}
#[inline(always)]
pub fn is_full(&self) -> bool {
self.length == N
}
#[inline(always)]
pub fn is_not_full(&self) -> bool {
self.length < N
}
#[inline(always)]
pub fn as_ptr(&self) -> *const T {
self.data.as_ptr() as *const T
}
#[inline(always)]
pub fn as_mut_ptr(&mut self) -> *mut T {
self.data.as_mut_ptr() as *mut T
}
#[inline(always)]
pub fn as_slice(&self) -> &[T] {
unsafe { &*(self.data.get_unchecked(0..self.length) as *const [MaybeUninit<T>] as *const [T]) }
}
#[inline(always)]
pub fn as_mut_slice(&mut self) -> &mut [T] {
unsafe {
&mut *(self.data.get_unchecked_mut(0..self.length) as *mut [MaybeUninit<T>] as *mut [T])
}
}
#[inline(always)]
pub unsafe fn push_unchecked(&mut self, value: T) {
self.data.get_unchecked_mut(self.length).write(value);
self.length += 1;
}
#[inline(always)]
pub unsafe fn pop_unchecked(&mut self) -> T {
self.length -= 1;
self.data.get_unchecked(self.length).read()
}
#[inline(always)]
pub fn push(&mut self, value: T) {
assert!(self.length < N);
unsafe {
self.push_unchecked(value);
}
}
#[inline(always)]
pub fn pop(&mut self) -> Option<T> {
if self.length == 0 {
None
} else {
Some(unsafe { self.pop_unchecked() })
}
}
#[inline]
pub fn remove(&mut self, index: usize) -> T {
assert!(index < self.length);
unsafe {
let p = self.as_mut_ptr().add(index);
let res = p.read();
p.offset(1).copy_to(p, self.length - index - 1);
self.length -= 1;
res
}
}
#[inline(always)]
pub fn remove_item(&mut self, item: &T) -> Option<T>
where T: PartialEq {
if let Some(pos) = self.iter().position(|x| *x == *item) {
Some(self.remove(pos))
} else {
None
}
}
#[inline(always)]
pub fn swap_remove(&mut self, index: usize) -> T {
assert!(index < self.length);
unsafe {
let last_value = self.data.get_unchecked(self.length - 1).read();
self.length -= 1;
self.as_mut_ptr().add(index).replace(last_value)
}
}
#[inline]
pub fn insert(&mut self, index: usize, value: T) {
assert!(self.length < N && index <= self.length);
unsafe {
let p = self.as_mut_ptr().add(index);
p.copy_to(p.offset(1), self.length - index);
p.write(value);
self.length += 1;
}
}
#[inline(always)]
pub fn clear(&mut self) {
unsafe {
ptr::drop_in_place(self.as_mut_slice());
}
self.length = 0;
}
#[cfg(feature = "std")]
#[inline(always)]
pub fn sort(&mut self)
where T: Ord {
self.as_mut_slice().sort();
}
#[inline(always)]
pub fn sort_unstable(&mut self)
where T: Ord {
self.as_mut_slice().sort_unstable();
}
#[inline(always)]
pub fn reverse(&mut self) {
self.as_mut_slice().reverse();
}
#[cfg(feature = "std")]
#[inline]
pub fn sorted(&self) -> Self
where T: Copy + Ord {
unsafe {
let mut res = Self::new();
res.length = self.length;
self
.as_ptr()
.copy_to_nonoverlapping(res.as_mut_ptr(), self.length);
res.sort();
res
}
}
#[inline]
pub fn sorted_unstable(&self) -> Self
where T: Copy + Ord {
unsafe {
let mut res = Self::new();
res.length = self.length;
self
.as_ptr()
.copy_to_nonoverlapping(res.as_mut_ptr(), self.length);
res.sort_unstable();
res
}
}
#[inline]
pub fn reversed(&self) -> Self
where T: Copy {
let mut res = Self::new();
res.length = self.length;
unsafe {
reverse_copy(
self.as_ptr(),
self.as_ptr().add(self.length),
res.as_mut_ptr(),
);
}
res
}
#[inline]
pub fn extend_from_slice(&mut self, other: &[T])
where T: Copy {
let mut added_length = other.len();
if self.length + added_length > N {
added_length = N - self.length;
}
unsafe {
other
.as_ptr()
.copy_to_nonoverlapping(self.as_mut_ptr().add(self.length), added_length);
}
self.length += added_length;
}
#[inline]
pub fn drain<R>(&mut self, range: R) -> Self
where R: RangeBounds<usize> {
let start = match range.start_bound() {
Included(&idx) => idx,
Excluded(&idx) => idx + 1,
Unbounded => 0,
};
let end = match range.end_bound() {
Included(&idx) => idx + 1,
Excluded(&idx) => idx,
Unbounded => self.length,
};
assert!(start <= end && end <= self.length);
let mut res = Self::new();
res.length = end - start;
unsafe {
self
.as_ptr()
.add(start)
.copy_to_nonoverlapping(res.as_mut_ptr(), res.length);
self
.as_ptr()
.add(end)
.copy_to(self.as_mut_ptr().add(start), self.length - end);
}
self.length -= res.length;
res
}
#[inline]
pub fn drain_filter<F>(&mut self, mut filter: F) -> Self
where F: FnMut(&mut T) -> bool {
let mut res = Self::new();
let old_length = self.length;
self.length = 0;
unsafe {
for i in 0..old_length {
let val = self.as_mut_ptr().add(i);
if filter(&mut *val) {
res.data.get_unchecked_mut(res.length).write(val.read());
res.length += 1;
} else if res.length > 0 {
self
.as_ptr()
.add(i)
.copy_to_nonoverlapping(self.as_mut_ptr().add(i - res.length), 1);
}
}
}
self.length = old_length - res.length;
res
}
#[inline(always)]
pub fn retain<F>(&mut self, mut filter: F)
where F: FnMut(&T) -> bool {
self.drain_filter(|val| !filter(val));
}
#[inline(always)]
pub fn truncate(&mut self, length: usize) {
let old_length = self.length;
self.length = length;
unsafe {
ptr::drop_in_place(
&mut *(self.data.get_unchecked_mut(length..old_length) as *mut [MaybeUninit<T>]
as *mut [T]),
);
}
}
#[inline(always)]
pub fn iter<'a>(&'a self) -> StaticVecIterConst<'a, T> {
unsafe {
StaticVecIterConst::<'a, T> {
start: self.as_ptr(),
end: self.as_ptr().add(self.length),
marker: PhantomData,
}
}
}
#[inline(always)]
pub fn iter_mut<'a>(&'a mut self) -> StaticVecIterMut<'a, T> {
unsafe {
StaticVecIterMut::<'a, T> {
start: self.as_mut_ptr(),
end: self.as_mut_ptr().add(self.length),
marker: PhantomData,
}
}
}
}
impl<T, const N: usize> Default for StaticVec<T, {N}> {
#[inline(always)]
fn default() -> Self {
Self::new()
}
}
impl<T, const N: usize> Drop for StaticVec<T, {N}> {
#[inline(always)]
fn drop(&mut self) {
self.clear();
}
}
impl<T, const N: usize> Index<usize> for StaticVec<T, {N}> {
type Output = T;
#[inline(always)]
fn index(&self, index: usize) -> &Self::Output {
assert!(index < self.length);
unsafe { self.data.get_unchecked(index).get_ref() }
}
}
impl<T, const N: usize> IndexMut<usize> for StaticVec<T, {N}> {
#[inline(always)]
fn index_mut(&mut self, index: usize) -> &mut Self::Output {
assert!(index < self.length);
unsafe { self.data.get_unchecked_mut(index).get_mut() }
}
}
impl<T: Copy, const N: usize> From<&[T]> for StaticVec<T, {N}> {
#[inline(always)]
fn from(values: &[T]) -> Self {
Self::new_from_slice(values)
}
}
impl<'a, T: 'a, const N: usize> IntoIterator for &'a StaticVec<T, {N}> {
type IntoIter = StaticVecIterConst<'a, T>;
type Item = <Self::IntoIter as Iterator>::Item;
#[inline(always)]
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a, T: 'a, const N: usize> IntoIterator for &'a mut StaticVec<T, {N}> {
type IntoIter = StaticVecIterMut<'a, T>;
type Item = <Self::IntoIter as Iterator>::Item;
#[inline(always)]
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl<T, const N: usize> FromIterator<T> for StaticVec<T, {N}> {
#[inline]
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
let mut res = Self::new();
let mut it = iter.into_iter();
for i in 0..N {
if let Some(val) = it.next() {
unsafe {
res.data.get_unchecked_mut(i).write(val);
}
} else {
res.length = i;
return res;
}
}
res.length = N;
res
}
}
impl<T, const N: usize> Extend<T> for StaticVec<T, {N}> {
#[inline]
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
let old_length = self.length;
let mut it = iter.into_iter();
for i in old_length..N {
if let Some(val) = it.next() {
unsafe {
self.data.get_unchecked_mut(i).write(val);
}
} else {
self.length += i;
return;
}
}
self.length = N;
}
}