use std::num::NonZeroUsize;
use crate::arena::Arena;
use crate::cell::CopyCell;
#[derive(Debug, PartialEq, Clone, Copy)]
struct ListNode<'arena, T> {
value: T,
next: CopyCell<Option<&'arena ListNode<'arena, T>>>,
}
#[derive(Clone, Copy)]
pub struct List<'arena, T> {
root: CopyCell<Option<&'arena ListNode<'arena, T>>>,
}
impl<'arena, T> List<'arena, T> {
pub const fn empty() -> Self {
List {
root: CopyCell::new(None)
}
}
#[inline]
pub fn clear(&self) {
self.root.set(None);
}
#[inline]
pub fn iter(&self) -> ListIter<'arena, T> {
ListIter {
next: self.root.get()
}
}
#[inline]
pub fn is_empty(&self) -> bool {
self.root.get().is_none()
}
#[inline]
pub fn only_element(&self) -> Option<&'arena T> {
match self.root.get() {
Some(&ListNode {
ref value,
ref next,
..
}) if next.get().is_none() => Some(value),
_ => None
}
}
#[inline]
pub fn first_element(&self) -> Option<&'arena T> {
self.root.get().map(|li| &li.value)
}
#[inline]
pub fn into_unsafe(self) -> UnsafeList {
UnsafeList {
root: self.root.get().map(|ptr| unsafe {
NonZeroUsize::new_unchecked(ptr as *const ListNode<T> as usize)
}),
}
}
}
impl<'arena, T: Copy> List<'arena, T> {
#[inline]
pub fn from(arena: &'arena Arena, value: T) -> List<'arena, T> {
List {
root: CopyCell::new(Some(arena.alloc(ListNode {
value,
next: CopyCell::new(None)
})))
}
}
pub fn from_iter<I>(arena: &'arena Arena, source: I) -> List<'arena, T> where
I: IntoIterator<Item = T>
{
let mut iter = source.into_iter();
let builder = match iter.next() {
Some(item) => ListBuilder::new(arena, item),
None => return List::empty(),
};
for item in iter {
builder.push(arena, item);
}
builder.as_list()
}
#[inline]
pub fn prepend(&self, arena: &'arena Arena, value: T) -> &'arena T {
let root = arena.alloc(
ListNode {
value,
next: self.root
}
);
self.root.set(Some(root));
&root.value
}
#[inline]
pub fn shift(&self) -> Option<&'arena T> {
let list_item = self.root.get()?;
self.root.set(list_item.next.get());
Some(&list_item.value)
}
#[inline]
pub fn shift_ref(&mut self) -> Option<&'arena T> {
let list_item = self.root.get()?;
*self = List {
root: list_item.next
};
Some(&list_item.value)
}
}
impl<'arena, T> IntoIterator for List<'arena, T> {
type Item = &'arena T;
type IntoIter = ListIter<'arena, T>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a, 'arena, T> IntoIterator for &'a List<'arena, T> {
type Item = &'arena T;
type IntoIter = ListIter<'arena, T>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
#[derive(Clone, Copy)]
pub struct GrowableList<'arena, T> {
last: CopyCell<Option<&'arena ListNode<'arena, T>>>,
first: CopyCell<Option<&'arena ListNode<'arena, T>>>,
}
impl<'arena, T> GrowableList<'arena, T>
where
T: Copy,
{
#[inline]
pub fn push(&self, arena: &'arena Arena, item: T) {
let next = Some(&*arena.alloc(ListNode {
value: item,
next: CopyCell::new(None)
}));
match self.last.get() {
Some(ref last) => last.next.set(next),
None => self.first.set(next),
}
self.last.set(next);
}
}
impl<'arena, T> GrowableList<'arena, T> {
pub const fn new() -> Self {
GrowableList {
first: CopyCell::new(None),
last: CopyCell::new(None),
}
}
#[inline]
pub fn as_list(&self) -> List<'arena, T> {
List {
root: self.first
}
}
}
#[derive(Clone, Copy)]
pub struct ListBuilder<'arena, T> {
first: &'arena ListNode<'arena, T>,
last: CopyCell<&'arena ListNode<'arena, T>>,
}
impl<'arena, T: Copy> ListBuilder<'arena, T> {
#[inline]
pub fn new(arena: &'arena Arena, first: T) -> Self {
let first = arena.alloc(ListNode {
value: first,
next: CopyCell::new(None)
});
ListBuilder {
first,
last: CopyCell::new(first),
}
}
#[inline]
pub fn push(&self, arena: &'arena Arena, item: T) {
let next = arena.alloc(ListNode {
value: item,
next: CopyCell::new(None)
});
self.last.get().next.set(Some(next));
self.last.set(next);
}
}
impl<'arena, T> ListBuilder<'arena, T> {
#[inline]
pub fn as_list(&self) -> List<'arena, T> {
List {
root: CopyCell::new(Some(self.first))
}
}
}
#[derive(Debug, Clone, Copy)]
pub struct UnsafeList {
root: Option<NonZeroUsize>,
}
impl UnsafeList {
pub unsafe fn into_list<'arena, T>(self) -> List<'arena, T> {
List {
root: CopyCell::new(self.root.map(|ptr| &*(ptr.get() as *const ListNode<'arena, T>))),
}
}
}
pub struct ListIter<'arena, T> {
next: Option<&'arena ListNode<'arena, T>>
}
impl<'arena, T> Iterator for ListIter<'arena, T> {
type Item = &'arena T;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
let next = self.next;
next.map(|list_item| {
let value = &list_item.value;
self.next = list_item.next.get();
value
})
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn builder() {
let arena = Arena::new();
let builder = ListBuilder::new(&arena, 10);
builder.push(&arena, 20);
builder.push(&arena, 30);
let list = builder.as_list();
assert!(list.iter().eq([10, 20, 30].iter()));
}
#[test]
fn empty_builder() {
let arena = Arena::new();
let builder = GrowableList::new();
builder.push(&arena, 10);
builder.push(&arena, 20);
builder.push(&arena, 30);
let list = builder.as_list();
assert!(list.iter().eq([10, 20, 30].iter()));
}
#[test]
fn from_iter() {
let arena = Arena::new();
let list = List::from_iter(&arena, [10, 20, 30].iter().cloned());
assert!(list.iter().eq([10, 20, 30].iter()));
}
#[test]
fn prepend() {
let arena = Arena::new();
let list = List::from(&arena, 30);
list.prepend(&arena, 20);
list.prepend(&arena, 10);
assert!(list.iter().eq([10, 20, 30].iter()));
}
#[test]
fn only_element() {
let arena = Arena::new();
let list = List::from(&arena, 42);
assert_eq!(list.only_element(), Some(&42));
list.prepend(&arena, 10);
assert_eq!(list.only_element(), None);
}
#[test]
fn shift() {
let arena = Arena::new();
let builder = GrowableList::new();
builder.push(&arena, 10);
builder.push(&arena, 20);
builder.push(&arena, 30);
let list = builder.as_list();
assert_eq!(list.shift(), Some(&10));
assert!(list.iter().eq([20, 30].iter()));
}
#[test]
fn shift_ref() {
let arena = Arena::new();
let builder = GrowableList::new();
builder.push(&arena, 10);
builder.push(&arena, 20);
builder.push(&arena, 30);
let list_a = builder.as_list();
let mut list_b = list_a;
assert_eq!(list_b.shift_ref(), Some(&10));
assert!(list_a.iter().eq([10, 20, 30].iter()));
assert!(list_b.iter().eq([20, 30].iter()));
}
#[test]
fn empty_unsafe_list() {
let list: List<usize> = List::empty();
let raw = list.into_unsafe();
assert!(raw.root.is_none());
let list: List<usize> = unsafe { raw.into_list() };
assert_eq!(list.is_empty(), true);
}
#[test]
fn unsafe_list() {
let arena = Arena::new();
{
let list = List::from(&arena, 42usize);
drop(list);
let raw = list.into_unsafe();
assert!(raw.root.is_some());
let list: List<usize> = unsafe { raw.into_list() };
assert_eq!(list.only_element(), Some(&42));
drop(list);
}
drop(arena);
}
}