You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
375 lines
8.9 KiB
375 lines
8.9 KiB
//! Iterators for `Populator`
|
|
use super::*;
|
|
use std::iter::{
|
|
self,
|
|
DoubleEndedIterator,
|
|
FusedIterator,
|
|
};
|
|
use std::fmt::{self, Debug};
|
|
|
|
#[derive(Debug, Clone)]
|
|
struct FullIter<T>(std::vec::IntoIter<T>);
|
|
#[derive(Debug)]
|
|
struct PartialIter<T>(std::vec::IntoIter<MaybeUninit<T>>,
|
|
std::vec::IntoIter<AtomicBool>, usize);
|
|
|
|
impl<T> Iterator for FullIter<T>
|
|
{
|
|
type Item = T;
|
|
#[inline]
|
|
fn next(&mut self) -> Option<Self::Item> {
|
|
self.0.next()
|
|
}
|
|
#[inline]
|
|
fn size_hint(&self) -> (usize, Option<usize>) {
|
|
self.0.size_hint()
|
|
}
|
|
}
|
|
|
|
impl<T> PartialIter<T> {
|
|
#[inline(always)]
|
|
fn next_raw(&mut self) -> Option<(MaybeUninit<T>, bool)>
|
|
{
|
|
let a = self.0.next()?;
|
|
let b = if cfg!(debug_assertions) { self.1.next()? } else { unsafe { self.1.next().unwrap_unchecked() } };
|
|
|
|
self.2-=1;
|
|
Some((a, b.into_inner()))
|
|
}
|
|
}
|
|
|
|
|
|
|
|
impl<T> Iterator for PartialIter<T>
|
|
{
|
|
type Item = T;
|
|
fn next(&mut self) -> Option<Self::Item> {
|
|
Some(loop {
|
|
match self.next_raw()? {
|
|
(value, true) => break unsafe { value.assume_init() },
|
|
_ => (),
|
|
}
|
|
})
|
|
}
|
|
#[inline]
|
|
fn size_hint(&self) -> (usize, Option<usize>) {
|
|
(self.2, Some(self.2))
|
|
}
|
|
}
|
|
|
|
impl<T> FusedIterator for FullIter<T>{}
|
|
impl<T> ExactSizeIterator for FullIter<T>{}
|
|
|
|
impl<T> FusedIterator for PartialIter<T>{}
|
|
impl<T> ExactSizeIterator for PartialIter<T>{}
|
|
|
|
trait PopulaterIter<T>: private::Sealed + Iterator<Item=T> + FusedIterator + ExactSizeIterator{
|
|
fn as_debug(&self) -> &dyn Debug
|
|
where T: Debug;
|
|
fn is_complete(&self) -> bool;
|
|
}
|
|
|
|
impl<T> private::Sealed for PartialIter<T>{}
|
|
impl<T> private::Sealed for FullIter<T>{}
|
|
|
|
impl<'a, T: 'a + Debug> Debug for dyn PopulaterIter<T> + 'a {
|
|
fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result
|
|
{
|
|
self.as_debug().fmt(fmt)
|
|
}
|
|
}
|
|
|
|
impl<T> PopulaterIter<T> for PartialIter<T>
|
|
{
|
|
#[inline(always)]
|
|
fn as_debug(&self) -> &dyn Debug
|
|
where T: Debug {
|
|
self
|
|
}
|
|
#[inline(always)]
|
|
fn is_complete(&self) -> bool {
|
|
false
|
|
}
|
|
}
|
|
|
|
impl<T> PopulaterIter<T> for FullIter<T>
|
|
{
|
|
#[inline(always)]
|
|
fn as_debug(&self) -> &dyn Debug
|
|
where T: Debug {
|
|
self
|
|
}
|
|
#[inline(always)]
|
|
fn is_complete(&self) -> bool {
|
|
false
|
|
}
|
|
}
|
|
|
|
/// An iterator over a `Populator<'a, T>`'s items.
|
|
///
|
|
/// # Length
|
|
/// It is a full iterator of all completed elements, non-inserted elements are ignored.
|
|
#[derive(Debug)]
|
|
pub struct IntoIter<'a, T: 'a>(Box<dyn PopulaterIter<T> + 'a>);
|
|
|
|
/*
|
|
impl<'a, Iter, T: 'a> From<Iter> for IntoIter<'a, T>
|
|
where Iter: private::Sealed + PopulaterIter<T> + 'a
|
|
{
|
|
#[inline(always)]
|
|
fn from(v: Iter) -> Self {
|
|
Self(Box::new(v))
|
|
}
|
|
}
|
|
*/
|
|
|
|
#[inline(always)]
|
|
unsafe fn assume_init_boxed<T>(bx: Box<[MaybeUninit<T>]>) -> Box<[T]>
|
|
{
|
|
let raw = Box::into_raw(bx);
|
|
|
|
Box::from_raw(raw as *mut [T])
|
|
}
|
|
|
|
#[inline(always)]
|
|
pub(crate) unsafe fn assume_init_mut<T>(slice: &mut [MaybeUninit<T>]) -> &mut [T]
|
|
{
|
|
//MaybeUninit::slice_assume_init_ref(slice)
|
|
&mut (*(slice as *mut [MaybeUninit<T>] as *mut [T]))[..]
|
|
}
|
|
|
|
#[inline(always)]
|
|
pub(crate) unsafe fn assume_init_ref<T>(slice: &[MaybeUninit<T>]) -> &[T]
|
|
{
|
|
//MaybeUninit::slice_assume_init_ref(slice)
|
|
&(*(slice.as_ref() as *const [MaybeUninit<T>] as *const [T]))[..]
|
|
}
|
|
|
|
impl<'a, T> IntoIter<'a, T>
|
|
{
|
|
/// Does this iterator represent a fully completed `Populator<'a, T>`?
|
|
#[inline]
|
|
pub fn is_complete(&self) -> bool
|
|
{
|
|
self.0.as_ref().is_complete()
|
|
}
|
|
pub(super) fn create_from(mut pop: Populator<'a, T>) -> Self
|
|
{
|
|
Self(if pop.is_full_exclusive() {
|
|
let values = pop.take_values();
|
|
|
|
Box::new(FullIter(Vec::from(unsafe { assume_init_boxed(values) }).into_iter()))
|
|
} else {
|
|
let (values, populates) = pop.take_all();
|
|
|
|
Box::new(PartialIter(Vec::from(values).into_iter(),
|
|
Vec::from(populates).into_iter(),
|
|
*pop.populated.get_mut()))
|
|
})
|
|
}
|
|
}
|
|
|
|
impl<'a, T> Iterator for IntoIter<'a, T>
|
|
{
|
|
type Item = T;
|
|
#[inline]
|
|
fn next(&mut self) -> Option<Self::Item> {
|
|
self.0.next()
|
|
}
|
|
fn size_hint(&self) -> (usize, Option<usize>) {
|
|
self.0.size_hint()
|
|
}
|
|
}
|
|
impl<'a, T> FusedIterator for IntoIter<'a, T>{}
|
|
impl<'a, T> ExactSizeIterator for IntoIter<'a, T>{}
|
|
|
|
/// A reference iterator for a full `Populator<'re, T>`.
|
|
#[derive(Debug)]
|
|
pub struct FullIterRef<'re, 'a: 're, T: 'a>(std::slice::Iter<'a, T>, PhantomLifetime<'re>);
|
|
|
|
impl<'re, 'a: 're, T: 'a> FullIterRef<'re, 'a, T>
|
|
{
|
|
#[inline(always)]
|
|
pub(super) fn new(slice: &'a [T]) -> Self
|
|
{
|
|
Self (slice.iter(), PhantomLifetime::new())
|
|
}
|
|
}
|
|
|
|
impl<'re, 'a: 're, T: 'a> Iterator for FullIterRef<'re, 'a, T>
|
|
{
|
|
type Item = &'a T;
|
|
#[inline]
|
|
fn next(&mut self) -> Option<Self::Item> {
|
|
self.0.next()
|
|
}
|
|
#[inline]
|
|
fn size_hint(&self) -> (usize, Option<usize>) {
|
|
self.0.size_hint()
|
|
}
|
|
}
|
|
|
|
impl<'re, 'a: 're, T: 'a> DoubleEndedIterator for FullIterRef<'re, 'a, T>
|
|
{
|
|
fn next_back(&mut self) -> Option<Self::Item> {
|
|
self.0.next_back()
|
|
}
|
|
}
|
|
|
|
impl<'re, 'a: 're, T: 'a> FusedIterator for FullIterRef<'re, 'a, T>{}
|
|
impl<'re, 'a: 're, T: 'a> ExactSizeIterator for FullIterRef<'re, 'a, T>{}
|
|
|
|
/// A mutable reference iterator for a full `Populator<'re, T>`.
|
|
#[derive(Debug)]
|
|
pub struct FullIterMut<'re, 'a: 're, T: 'a>(std::slice::IterMut<'a, T>, PhantomLifetime<'re>);
|
|
|
|
impl<'re, 'a: 're, T: 'a> FullIterMut<'re, 'a, T>
|
|
{
|
|
#[inline(always)]
|
|
pub(super) fn new(slice: &'a mut [T]) -> Self
|
|
{
|
|
Self (slice.iter_mut(), PhantomLifetime::new())
|
|
}
|
|
}
|
|
|
|
impl<'re, 'a: 're, T: 'a> Iterator for FullIterMut<'re, 'a, T>
|
|
{
|
|
type Item = &'a mut T;
|
|
#[inline]
|
|
fn next(&mut self) -> Option<Self::Item> {
|
|
self.0.next()
|
|
}
|
|
#[inline]
|
|
fn size_hint(&self) -> (usize, Option<usize>) {
|
|
self.0.size_hint()
|
|
}
|
|
}
|
|
|
|
impl<'re, 'a: 're, T: 'a> DoubleEndedIterator for FullIterMut<'re, 'a, T>
|
|
{
|
|
fn next_back(&mut self) -> Option<Self::Item> {
|
|
self.0.next_back()
|
|
}
|
|
}
|
|
|
|
impl<'re, 'a: 're, T: 'a> FusedIterator for FullIterMut<'re, 'a, T>{}
|
|
impl<'re, 'a: 're, T: 'a> ExactSizeIterator for FullIterMut<'re, 'a, T>{}
|
|
|
|
/// Internal iterator over a `Populator<'a, T>`
|
|
#[derive(Debug, Clone)] // PartialEq, Eq
|
|
struct IterInternal<'a, T>
|
|
{
|
|
//pop: &'re Populator<'a, T>,
|
|
values: std::slice::Iter<'a, MaybeUninit<T>>,
|
|
populated: std::slice::Iter<'a, AtomicBool>, //XXX: When the iterator ends, this iter will be 1 item behind `values`, so use `values` for size hint.
|
|
}
|
|
|
|
impl<'a, T: 'a> Iterator for IterInternal<'a, T>
|
|
{
|
|
type Item = (&'a MaybeUninit<T>, &'a AtomicBool);
|
|
#[inline]
|
|
fn next(&mut self) -> Option<Self::Item>
|
|
{
|
|
self.values.next()
|
|
.and_then(move |v| self.populated.next()
|
|
.map(move |p| (v, p)))
|
|
}
|
|
#[inline(always)]
|
|
fn size_hint(&self) -> (usize, Option<usize>) {
|
|
self.values.size_hint()
|
|
}
|
|
}
|
|
|
|
|
|
/// An iterator over a full populator, or a range inside a populator.
|
|
#[derive(Debug, Clone)] // PartialEq, Eq
|
|
pub struct Iter<'re, 'a, T>{
|
|
pop: &'re Populator<'a, T>,
|
|
indecies: <std::ops::Range<usize> as IntoIterator>::IntoIter,
|
|
}
|
|
|
|
impl<'re, 'a, T: 'a> Eq for Iter<'re, 'a, T>{}
|
|
impl<'re, 'a, T: 'a> PartialEq for Iter<'re, 'a, T>
|
|
{
|
|
#[inline]
|
|
fn eq(&self, other: &Self) -> bool
|
|
{
|
|
std::ptr::eq(self.pop, other.pop)
|
|
&& self.indecies == other.indecies
|
|
}
|
|
}
|
|
|
|
impl<'re, 'a: 're, T: 'a> Iter<'re, 'a, T>
|
|
{
|
|
#[inline]
|
|
fn create_from(&self, idx: usize) -> Ref<'re, 'a, T>
|
|
{
|
|
Ref {
|
|
pop: self.pop,
|
|
inserted: &self.pop.populates[idx],
|
|
idx,
|
|
}
|
|
}
|
|
|
|
#[inline(always)]
|
|
pub(crate) fn new_range(pop: &'re Populator<'a, T>, indecies: std::ops::Range<usize>) -> Self
|
|
{
|
|
Self {
|
|
pop,
|
|
indecies
|
|
}
|
|
}
|
|
pub(crate) fn new_ranged(pop: &'re Populator<'a, T>, indecies: impl Into<(usize, usize)>) -> Self
|
|
{
|
|
let (a, b) = indecies.into();
|
|
Self {
|
|
indecies: (a..b),
|
|
pop,
|
|
}
|
|
}
|
|
#[inline(always)]
|
|
pub(crate) fn new(pop: &'re Populator<'a, T>) -> Self
|
|
{
|
|
Self::new_ranged(pop, (0, pop.len()))
|
|
}
|
|
}
|
|
|
|
#[inline(always)]
|
|
fn create_from_iter<'iter, 're, 'a: 're, T: 'a>(iter: &'iter Iter<'re, 'a, T>) -> impl Fn(usize) -> Ref<'re, 'a, T> + 'iter
|
|
{
|
|
move |idx| iter.create_from(idx)
|
|
}
|
|
|
|
impl<'re, 'a: 're, T: 'a> Iterator for Iter<'re, 'a, T>
|
|
{
|
|
type Item = Ref<'re, 'a, T>;
|
|
#[inline]
|
|
fn next(&mut self) -> Option<Self::Item>
|
|
{
|
|
self.indecies.next().map(create_from_iter(self))
|
|
}
|
|
#[inline]
|
|
fn size_hint(&self) -> (usize, Option<usize>) {
|
|
self.indecies.size_hint()
|
|
}
|
|
#[inline]
|
|
fn nth(&mut self, idx: usize) -> Option<Self::Item>
|
|
{
|
|
self.indecies.nth(idx).map(create_from_iter(self))
|
|
}
|
|
}
|
|
|
|
impl<'re, 'a: 're, T: 'a> FusedIterator for Iter<'re, 'a, T>{}
|
|
impl<'re, 'a: 're, T: 'a> ExactSizeIterator for Iter<'re, 'a, T>{}
|
|
impl<'re, 'a: 're, T: 'a> DoubleEndedIterator for Iter<'re, 'a, T>
|
|
{
|
|
#[inline]
|
|
fn next_back(&mut self) -> Option<Self::Item> {
|
|
self.indecies.next_back().map(create_from_iter(self))
|
|
}
|
|
#[inline]
|
|
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
|
|
self.indecies.nth_back(n).map(create_from_iter(self))
|
|
}
|
|
}
|