#![cfg_attr(feature = "nightly", feature(specialization, try_trait))]
#![allow(clippy::option_option)]
use bit_vec::BitVec;
use std::mem::MaybeUninit;
#[cold]
unsafe fn unreachable_unchecked() -> ! {
use std::hint::unreachable_unchecked;
debug_assert!(false, "unreachable");
unreachable_unchecked()
}
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(),
}
}
}
trait GetUnchecked {
unsafe fn get_unchecked(&self, i: usize) -> bool;
}
impl GetUnchecked for BitVec {
unsafe fn get_unchecked(&self, i: usize) -> bool {
self.get(i).unwrap_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_mut_from_raw_parts<T>(flag: bool, data: &mut MaybeUninit<T>) -> Option<&mut T> {
if flag {
Some(&mut *data.as_mut_ptr())
} 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,
}
impl<T> Default for VecOption<T> {
fn default() -> Self {
Self::new()
}
}
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 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 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 is_empty(&self) -> bool {
self.data.is_empty()
}
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<Option<&mut T>> {
unsafe {
let flag = self.flag.get(index)?;
let data = self.data.get_unchecked_mut(index);
Some(ref_mut_from_raw_parts(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 put(&mut self, index: usize, value: T) -> Option<Option<T>> {
self.replace(index, Some(value))
}
pub fn replace(&mut self, index: usize, value: Option<T>) -> Option<Option<T>> {
unsafe {
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 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 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 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(),
}
}
#[cfg(feature = "nightly")]
pub fn try_fold<A, R: std::ops::Try<Ok = A>, F: FnMut(A, usize, &mut Option<T>) -> R>(&mut self, mut init: A, mut f: F) -> R {
for (i, data_slot) in self.data.iter_mut().enumerate() {
let flag = unsafe { self.flag.get_unchecked(i) };
self.flag.set(i, false);
let data = std::mem::replace(data_slot, MaybeUninit::uninit());
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);
self.flag.set(i, true);
}
init = res?;
}
R::from_ok(init)
}
#[cfg(not(feature = "nightly"))]
pub fn try_fold<A, B, F: FnMut(A, usize, &mut Option<T>) -> Result<A, B>>(&mut self, mut init: A, mut f: F) -> Result<A, B> {
for (i, data_slot) in self.data.iter_mut().enumerate() {
let flag = unsafe { self.flag.get_unchecked(i) };
self.flag.set(i, false);
let data = std::mem::replace(data_slot, MaybeUninit::uninit());
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);
self.flag.set(i, true);
}
init = res?;
}
Ok(init)
}
pub fn fold<A, F: FnMut(A, usize, &mut Option<T>) -> A>(&mut self, init: A, mut f: F) -> A {
let ret = self.try_fold(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<R: std::ops::Try<Ok = ()>, F: FnMut(usize, &mut Option<T>) -> R>(&mut self, mut f: F) -> R {
self.try_fold((), move |(), i, x| f(i, x))
}
#[cfg(not(feature = "nightly"))]
pub fn try_for_each<B, F: FnMut(usize, &mut Option<T>) -> Result<(), B>>(&mut self, mut f: F) -> Result<(), B> {
self.try_fold((), move |(), i, x| f(i, x))
}
pub fn for_each<F: FnMut(usize, &mut Option<T>)>(&mut self, mut f: F) {
self.fold((), move |(), i, x| f(i, x))
}
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.clear()
}
}
}
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))
}
}
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::Iter<'a>,
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = Option<&'a mut T>;
fn next(&mut self) -> Option<Self::Item> {
unsafe {
let flag = self.flag.next()?;
let data = self.data.next().unwrap_unchecked();
Some(ref_mut_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_mut_from_raw_parts(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(ref_mut_from_raw_parts(flag, data))
}
}
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_mut_from_raw_parts(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))
}
}
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 = Option<&'a mut 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.put(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)]);
}