#![cfg_attr(feature = "nightly", feature(specialization, try_trait))]
#![allow(clippy::option_option)]
#![forbid(missing_docs)]
mod bit_vec;
use bit_vec::BitVec;
use std::mem::MaybeUninit;
use std::ops::{Bound, Deref, DerefMut, RangeBounds};
#[cold]
unsafe fn unreachable_unchecked() -> ! {
use std::hint::unreachable_unchecked;
debug_assert!(false, "unreachable");
unreachable_unchecked()
}
fn as_range<R: RangeBounds<usize>>(range: &R, len: usize) -> (usize, usize) {
let start = match range.start_bound() {
Bound::Unbounded => 0,
Bound::Included(&x) => x,
Bound::Excluded(&x) => x + 1,
};
let end = match range.end_bound() {
Bound::Unbounded => len,
Bound::Included(&x) => x + 1,
Bound::Excluded(&x) => x,
};
(start, end)
}
trait UnwrapUnchecked {
type Output;
unsafe fn unwrap_unchecked(self) -> Self::Output;
}
impl<T> UnwrapUnchecked for Option<T> {
type Output = T;
unsafe fn unwrap_unchecked(self) -> Self::Output {
match self {
Some(value) => value,
None => unreachable_unchecked(),
}
}
}
unsafe fn from_raw_parts<T>(flag: bool, data: MaybeUninit<T>) -> Option<T> {
if flag {
Some(data.assume_init())
} else {
None
}
}
unsafe fn ref_from_raw_parts<T>(flag: bool, data: &MaybeUninit<T>) -> Option<&T> {
if flag {
Some(&*data.as_ptr())
} else {
None
}
}
pub struct VecOption<T> {
data: Vec<MaybeUninit<T>>,
flag: BitVec,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct CapacityInfo {
pub data: usize,
pub flag: usize,
_priv: (),
}
impl<T> Default for VecOption<T> {
fn default() -> Self {
Self::new()
}
}
pub struct OptionProxy<'a, T> {
data: &'a mut MaybeUninit<T>,
flag: bit_vec::BitProxy<'a>,
value: Option<T>,
}
impl<'a, T> OptionProxy<'a, T> {
unsafe fn new(mut flag: bit_vec::BitProxy<'a>, data: &'a mut MaybeUninit<T>) -> Self {
let data_v = std::mem::replace(data, MaybeUninit::uninit());
let flag_v = std::mem::replace(&mut *flag, false);
flag.flush();
let value = from_raw_parts(flag_v, data_v);
Self { data, flag, value }
}
}
impl<T> Deref for OptionProxy<'_, T> {
type Target = Option<T>;
fn deref(&self) -> &Self::Target {
&self.value
}
}
impl<T> DerefMut for OptionProxy<'_, T> {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.value
}
}
impl<T> Drop for OptionProxy<'_, T> {
fn drop(&mut self) {
if let Some(value) = self.value.take() {
unsafe {
self.data.as_mut_ptr().write(value);
*self.flag = true;
}
}
}
}
impl<T> VecOption<T> {
pub fn new() -> Self {
Self {
data: Vec::new(),
flag: BitVec::new(),
}
}
pub fn with_capacity(cap: usize) -> Self {
Self {
data: Vec::with_capacity(cap),
flag: BitVec::with_capacity(cap),
}
}
pub fn reserve(&mut self, amount: usize) {
self.data.reserve(amount);
self.flag.reserve(amount);
}
pub fn reserve_exact(&mut self, amount: usize) {
self.data.reserve_exact(amount);
self.flag.reserve_exact(amount);
}
pub fn len(&self) -> usize {
self.data.len()
}
pub fn capacity(&self) -> CapacityInfo {
CapacityInfo {
data: self.data.capacity(),
flag: self.flag.alloc_info().cap,
_priv: (),
}
}
pub fn is_empty(&self) -> bool {
self.data.is_empty()
}
pub fn push<V: Into<Option<T>>>(&mut self, value: V) {
let value = value.into();
match value {
Some(value) => {
self.data.push(MaybeUninit::new(value));
self.flag.push(true);
}
None => {
self.data.push(MaybeUninit::uninit());
self.flag.push(false);
}
}
}
pub fn pop(&mut self) -> Option<Option<T>> {
unsafe {
let flag = self.flag.pop()?;
let data = self.data.pop().unwrap_unchecked();
Some(from_raw_parts(flag, data))
}
}
pub fn get_mut(&mut self, index: usize) -> Option<OptionProxy<'_, T>> {
unsafe {
let flag = self.flag.get_mut(index)?;
let data = self.data.get_unchecked_mut(index);
Some(OptionProxy::new(flag, data))
}
}
pub fn get(&self, index: usize) -> Option<Option<&T>> {
unsafe {
let flag = self.flag.get(index)?;
let data = self.data.get_unchecked(index);
Some(ref_from_raw_parts(flag, data))
}
}
pub fn swap(&mut self, a: usize, b: usize) {
self.data.swap(a, b);
unsafe {
let fa = self.flag.get_unchecked(a);
let fb = self.flag.get_unchecked(b);
self.flag.set(a, fb);
self.flag.set(b, fa);
}
}
pub fn take(&mut self, index: usize) -> Option<Option<T>> {
self.replace(index, None)
}
pub fn replace<O: Into<Option<T>>>(&mut self, index: usize, value: O) -> Option<Option<T>> {
unsafe {
let value = value.into();
let flag = self.flag.get(index)?;
let data = self.data.get_unchecked_mut(index);
let out = if flag {
Some(data.as_ptr().read())
} else {
None
};
match value {
Some(value) => {
self.flag.set(index, true);
data.as_mut_ptr().write(value);
}
None => self.flag.set(index, false),
}
Some(out)
}
}
pub fn truncate(&mut self, len: usize) {
if self.data.len() <= len {
return;
}
if std::mem::needs_drop::<T>() {
for (i, data) in self.data.iter_mut().enumerate().skip(len) {
unsafe {
if self.flag.get_unchecked(i) {
self.flag.set(i, false);
data.as_mut_ptr().drop_in_place()
}
}
}
}
unsafe {
self.data.set_len(len);
self.flag.set_len(len);
}
}
pub fn clear(&mut self) {
self.truncate(0)
}
pub fn set_all_none(&mut self) {
if std::mem::needs_drop::<T>() {
for (i, data) in self.data.iter_mut().enumerate() {
unsafe {
if self.flag.get_unchecked(i) {
self.flag.set(i, false);
data.as_mut_ptr().drop_in_place()
}
}
}
} else {
self.flag.set_all(false);
}
}
pub fn extend_none(&mut self, additional: usize) {
self.flag.grow(additional, false);
unsafe {
self.reserve(additional);
let len = self.len();
self.data.set_len(len + additional);
}
}
pub fn iter(&self) -> Iter<'_, T> {
Iter {
data: self.data.iter(),
flag: self.flag.iter(),
}
}
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
IterMut {
data: self.data.iter_mut(),
flag: self.flag.iter_mut(),
}
}
#[cfg(feature = "nightly")]
pub fn try_fold<Range: RangeBounds<usize>, A, R: std::ops::Try<Ok = A>, F: FnMut(A, usize, &mut Option<T>) -> R>(
&mut self,
range: Range,
mut init: A,
mut f: F,
) -> R
where
Range: std::slice::SliceIndex<[MaybeUninit<T>], Output = [MaybeUninit<T>]>,
{
let (start, end) = as_range(&range, self.len());
let data = self.data[range].iter_mut().enumerate();
let flag = self.flag.iter_mut().take(end).skip(start);
for ((i, data_slot), mut flag_slot) in data.zip(flag) {
let flag_slot: &mut bool = &mut flag_slot;
let data = std::mem::replace(data_slot, MaybeUninit::uninit());
let flag = std::mem::replace(flag_slot, false);
let mut opt = unsafe { from_raw_parts(flag, data) };
let res = f(init, i, &mut opt);
if let Some(value) = opt {
*data_slot = MaybeUninit::new(value);
*flag_slot = true;
}
init = res?;
}
R::from_ok(init)
}
#[cfg(not(feature = "nightly"))]
pub fn try_fold<
Range: RangeBounds<usize>,
A,
B,
F: FnMut(A, usize, &mut Option<T>) -> Result<A, B>,
>(
&mut self,
range: Range,
mut init: A,
mut f: F,
) -> Result<A, B>
where
Range: std::slice::SliceIndex<[MaybeUninit<T>], Output = [MaybeUninit<T>]>,
{
let (start, end) = as_range(&range, self.len());
let data = self.data[range].iter_mut().enumerate();
let flag = self.flag.iter_mut().take(end).skip(start);
for ((i, data_slot), mut flag_slot) in data.zip(flag) {
let i = i + start;
let flag_slot: &mut bool = &mut flag_slot;
let data = std::mem::replace(data_slot, MaybeUninit::uninit());
let flag = std::mem::replace(flag_slot, false);
let mut opt = unsafe { from_raw_parts(flag, data) };
let res = f(init, i, &mut opt);
if let Some(value) = opt {
*data_slot = MaybeUninit::new(value);
*flag_slot = true;
}
init = res?;
}
Ok(init)
}
pub fn fold<Range: RangeBounds<usize>, A, F: FnMut(A, usize, &mut Option<T>) -> A>(
&mut self,
range: Range,
init: A,
mut f: F,
) -> A
where
Range: std::slice::SliceIndex<[MaybeUninit<T>], Output = [MaybeUninit<T>]>,
{
let ret = self.try_fold(range, init, move |a, i, x| {
Ok::<_, std::convert::Infallible>(f(a, i, x))
});
match ret {
Ok(x) => x,
Err(x) => match x {},
}
}
#[cfg(feature = "nightly")]
pub fn try_for_each<
Range: RangeBounds<usize>,
R: std::ops::Try<Ok = ()>,
F: FnMut(usize, &mut Option<T>) -> R,
>(
&mut self,
range: Range,
mut f: F,
) -> R
where
Range: std::slice::SliceIndex<[MaybeUninit<T>], Output = [MaybeUninit<T>]>,
{
self.try_fold(range, (), move |(), i, x| f(i, x))
}
#[cfg(not(feature = "nightly"))]
pub fn try_for_each<
Range: RangeBounds<usize>,
B,
F: FnMut(usize, &mut Option<T>) -> Result<(), B>,
>(
&mut self,
range: Range,
mut f: F,
) -> Result<(), B>
where
Range: std::slice::SliceIndex<[MaybeUninit<T>], Output = [MaybeUninit<T>]>,
{
self.try_fold(range, (), move |(), i, x| f(i, x))
}
pub fn for_each<Range: RangeBounds<usize>, F: FnMut(usize, &mut Option<T>)>(
&mut self,
range: Range,
mut f: F,
) where
Range: std::slice::SliceIndex<[MaybeUninit<T>], Output = [MaybeUninit<T>]>,
{
self.fold(range, (), move |(), i, x| f(i, x))
}
}
impl<T> Drop for VecOption<T> {
fn drop(&mut self) {
if std::mem::needs_drop::<T>() {
self.clear()
}
}
}
fn clone_impl<T: Clone>(vec: &VecOption<T>) -> VecOption<T> {
vec.iter().map(|x| x.cloned()).collect()
}
impl<T: Clone> Clone for VecOption<T> {
#[cfg(feature = "nightly")]
default fn clone(&self) -> Self {
clone_impl(self)
}
#[cfg(not(feature = "nightly"))]
fn clone(&self) -> Self {
clone_impl(self)
}
}
#[cfg(feature = "nightly")]
impl<T: Copy> Clone for VecOption<T> {
fn clone(&self) -> Self {
let len = self.len();
let mut new = Self {
data: Vec::with_capacity(len),
flag: self.flag.clone(),
};
unsafe {
new.data.set_len(len);
new.data.copy_from_slice(&self.data);
}
new
}
}
impl<T: PartialEq> PartialEq for VecOption<T> {
fn eq(&self, other: &Self) -> bool {
self.iter().eq(other.iter())
}
}
impl<T: PartialEq> PartialEq<[T]> for VecOption<T> {
fn eq(&self, other: &[T]) -> bool {
self.iter().eq(other.iter().map(Some))
}
}
impl<T: PartialEq, S: AsRef<[Option<T>]>> PartialEq<S> for VecOption<T> {
fn eq(&self, other: &S) -> bool {
self.iter().eq(other.as_ref().iter().map(Option::as_ref))
}
}
impl<T: Eq> Eq for VecOption<T> {}
impl<T: PartialOrd> PartialOrd for VecOption<T> {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
self.iter().partial_cmp(other.iter())
}
}
impl<T: Ord> Ord for VecOption<T> {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.iter().cmp(other.iter())
}
}
use std::hash::{Hash, Hasher};
impl<T: Hash> Hash for VecOption<T> {
fn hash<H: Hasher>(&self, hasher: &mut H) {
self.iter().for_each(|i| i.hash(hasher))
}
}
impl<T> std::iter::Extend<Option<T>> for VecOption<T> {
fn extend<I: IntoIterator<Item = Option<T>>>(&mut self, iter: I) {
let iter = iter.into_iter();
let (additional, _) = iter.size_hint();
self.reserve(additional);
iter.for_each(|x| self.push(x));
}
}
impl<T> std::iter::Extend<T> for VecOption<T> {
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
let iter = iter.into_iter();
let (additional, _) = iter.size_hint();
self.reserve(additional);
iter.for_each(|x| self.push(x));
}
}
impl<T> std::iter::FromIterator<Option<T>> for VecOption<T> {
fn from_iter<I: IntoIterator<Item = Option<T>>>(iter: I) -> Self {
let mut vec = Self::new();
vec.extend(iter);
vec
}
}
impl<T> From<Vec<T>> for VecOption<T> {
fn from(mut vec: Vec<T>) -> Self {
let len = vec.len();
let data = unsafe {
Vec::from_raw_parts(vec.as_mut_ptr() as *mut MaybeUninit<T>, len, vec.capacity())
};
std::mem::forget(vec);
let mut flag = BitVec::with_capacity(len);
flag.grow(len, true);
Self { data, flag }
}
}
impl<T> From<Vec<Option<T>>> for VecOption<T> {
fn from(vec: Vec<Option<T>>) -> Self {
let mut vec_opt = VecOption::new();
vec_opt.extend(vec);
vec_opt
}
}
impl<T> Drop for IntoIter<T> {
fn drop(&mut self) {
self.for_each(drop);
}
}
pub struct IntoIter<T> {
data: std::vec::IntoIter<MaybeUninit<T>>,
flag: bit_vec::IntoIter,
}
impl<T> Iterator for IntoIter<T> {
type Item = Option<T>;
fn next(&mut self) -> Option<Self::Item> {
unsafe {
let flag = self.flag.next()?;
let data = self.data.next().unwrap_unchecked();
Some(from_raw_parts(flag, data))
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.data.size_hint()
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
if std::mem::needs_drop::<T>() {
for _ in 1..n {
self.next()?;
}
self.next()
} else {
unsafe {
let flag = self.flag.nth(n)?;
let data = self.data.nth(n).unwrap_unchecked();
Some(from_raw_parts(flag, data))
}
}
}
}
impl<T> DoubleEndedIterator for IntoIter<T> {
fn next_back(&mut self) -> Option<Self::Item> {
unsafe {
let flag = self.flag.next_back()?;
let data = self.data.next_back().unwrap_unchecked();
Some(from_raw_parts(flag, data))
}
}
#[cfg(feature = "nightly")]
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
if std::mem::needs_drop::<T>() {
for _ in 1..n {
self.next_back()?;
}
self.next_back()
} else {
unsafe {
let flag = self.flag.nth_back(n)?;
let data = self.data.nth_back(n).unwrap_unchecked();
Some(from_raw_parts(flag, data))
}
}
}
}
impl<T> ExactSizeIterator for IntoIter<T> {}
impl<T> std::iter::FusedIterator for IntoIter<T> {}
pub struct IterMut<'a, T> {
data: std::slice::IterMut<'a, MaybeUninit<T>>,
flag: bit_vec::IterMut<'a>,
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = OptionProxy<'a, T>;
fn next(&mut self) -> Option<Self::Item> {
unsafe {
let flag = self.flag.next()?;
let data = self.data.next().unwrap_unchecked();
Some(OptionProxy::new(flag, data))
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.data.size_hint()
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
unsafe {
let data = self.data.nth(n)?;
let flag = self.flag.nth(n).unwrap_unchecked();
Some(OptionProxy::new(flag, data))
}
}
}
impl<T> DoubleEndedIterator for IterMut<'_, T> {
fn next_back(&mut self) -> Option<Self::Item> {
unsafe {
let flag = self.flag.next_back()?;
let data = self.data.next_back().unwrap_unchecked();
Some(OptionProxy::new(flag, data))
}
}
#[cfg(feature = "nightly")]
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
unsafe {
let data = self.data.nth_back(n)?;
let flag = self.flag.nth_back(n).unwrap_unchecked();
Some(OptionProxy::new(flag, data))
}
}
}
pub struct Iter<'a, T> {
data: std::slice::Iter<'a, MaybeUninit<T>>,
flag: bit_vec::Iter<'a>,
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = Option<&'a T>;
fn next(&mut self) -> Option<Self::Item> {
unsafe {
let flag = self.flag.next()?;
let data = self.data.next().unwrap_unchecked();
Some(ref_from_raw_parts(flag, data))
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.data.size_hint()
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
unsafe {
let data = self.data.nth(n)?;
let flag = self.flag.nth(n).unwrap_unchecked();
Some(ref_from_raw_parts(flag, data))
}
}
}
impl<T> DoubleEndedIterator for Iter<'_, T> {
fn next_back(&mut self) -> Option<Self::Item> {
unsafe {
let flag = self.flag.next_back()?;
let data = self.data.next_back().unwrap_unchecked();
Some(ref_from_raw_parts(flag, data))
}
}
#[cfg(feature = "nightly")]
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
unsafe {
let data = self.data.nth_back(n)?;
let flag = self.flag.nth_back(n).unwrap_unchecked();
Some(ref_from_raw_parts(flag, data))
}
}
}
impl<T> ExactSizeIterator for Iter<'_, T> {}
impl<T> std::iter::FusedIterator for Iter<'_, T> {}
impl<T> IntoIterator for VecOption<T> {
type Item = Option<T>;
type IntoIter = IntoIter<T>;
fn into_iter(mut self) -> Self::IntoIter {
IntoIter {
data: std::mem::replace(&mut self.data, Vec::new()).into_iter(),
flag: std::mem::replace(&mut self.flag, BitVec::new()).into_iter(),
}
}
}
impl<'a, T> IntoIterator for &'a mut VecOption<T> {
type Item = OptionProxy<'a, T>;
type IntoIter = IterMut<'a, T>;
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl<'a, T> IntoIterator for &'a VecOption<T> {
type Item = Option<&'a T>;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
use std::fmt;
impl<T: fmt::Debug> fmt::Debug for VecOption<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let mut f = f.debug_list();
for i in self {
f.entry(&i);
}
f.finish()
}
}
#[test]
fn test() {
let mut vec = VecOption::new();
vec.push(10);
vec.push(Some(20));
vec.extend_none(10);
vec.push(30);
vec.push(40);
vec.push(50);
vec.push(60);
assert_eq!(
vec,
[
Some(10),
Some(20),
None,
None,
None,
None,
None,
None,
None,
None,
None,
None,
Some(30),
Some(40),
Some(50),
Some(60)
]
);
vec.set_all_none();
assert!(vec.iter().eq(std::iter::repeat(None).take(16)));
vec.clear();
assert!(vec.is_empty());
vec.extend(vec![10, 30, 20]);
assert_eq!(vec, [Some(10), Some(30), Some(20)]);
assert_eq!(vec, [10, 30, 20][..]);
assert_eq!(vec, vec.clone());
assert_eq!(vec.take(1), Some(Some(30)));
assert_eq!(vec.replace(1, 40), Some(None));
assert_eq!(vec.take(1), Some(Some(40)));
vec.swap(0, 1);
assert_eq!(vec, [None, Some(10), Some(20)]);
vec.clear();
vec.extend(0..10);
vec.for_each(.., |_, opt| {
if let Some(ref mut x) = *opt {
if *x % 2 == 0 {
*opt = None
} else {
*x *= 2
}
}
});
assert_eq!(
vec,
[
None,
Some(2),
None,
Some(6),
None,
Some(10),
None,
Some(14),
None,
Some(18)
]
);
let mut counter = 0;
vec.for_each(.., |_, opt| {
if let Some(ref mut x) = *opt {
if *x % 3 == 0 {
*x /= 2
} else {
*opt = None
}
} else {
counter += 1;
*opt = Some(counter);
}
});
assert_eq!(
vec,
[
Some(1),
None,
Some(2),
Some(3),
Some(3),
None,
Some(4),
None,
Some(5),
Some(9)
]
);
let val = vec.try_fold(2..6, 0, |acc, _, opt| {
let res = opt.map(|x| {
acc + x
}).ok_or(acc);
*opt = None;
res
});
assert_eq!(val, Err(8));
assert_eq!(
vec,
[
Some(1),
None,
None,
None,
None,
None,
Some(4),
None,
Some(5),
Some(9)
]
);
}