527 lines
11 KiB
Rust
527 lines
11 KiB
Rust
#![cfg_attr(not(feature = "std"), no_std)]
|
|
|
|
#[cfg(feature = "alloc")]
|
|
extern crate alloc;
|
|
|
|
use core::ops::{Deref, DerefMut};
|
|
|
|
#[cfg(feature = "alloc")]
|
|
use alloc::boxed::Box;
|
|
|
|
pub trait Node {
|
|
type Value;
|
|
|
|
fn value_ref(&self) -> &Self::Value;
|
|
fn value_mut(&mut self) -> &mut Self::Value;
|
|
fn next(&mut self) -> Option<&mut dyn Node<Value = Self::Value>>;
|
|
fn next_immutable(&self) -> Option<&dyn Node<Value = Self::Value>>;
|
|
}
|
|
|
|
pub trait ReverseOnto<Input> {
|
|
type Output;
|
|
|
|
fn reverse_onto(self, input: Input) -> Self::Output;
|
|
}
|
|
|
|
pub trait PrependOnto<Input> {
|
|
type Output;
|
|
|
|
fn prepend_onto(self, input: Input) -> Self::Output;
|
|
}
|
|
|
|
pub trait PopBack {
|
|
type Output;
|
|
|
|
fn pop_back(self) -> Self::Output;
|
|
}
|
|
|
|
pub fn new() -> Empty {
|
|
Empty
|
|
}
|
|
|
|
#[derive(Clone, Debug)]
|
|
pub struct Empty;
|
|
|
|
#[derive(Clone, Debug)]
|
|
pub struct ListNode<T, N> {
|
|
value: T,
|
|
next: N,
|
|
}
|
|
|
|
pub struct Iter<'a, T> {
|
|
node: Option<&'a dyn Node<Value = T>>,
|
|
}
|
|
|
|
pub type Reversed<List> = <List as ReverseOnto<Empty>>::Output;
|
|
pub type Prepend<First, Second> = <First as PrependOnto<Second>>::Output;
|
|
pub type PushBack<T, List> = Prepend<List, ListNode<T, Empty>>;
|
|
|
|
impl<'a, T> Iterator for Iter<'a, T> {
|
|
type Item = &'a T;
|
|
|
|
fn next(&mut self) -> Option<Self::Item> {
|
|
let node = self.node.take()?;
|
|
let value = node.value_ref();
|
|
self.node = node.next_immutable();
|
|
Some(value)
|
|
}
|
|
}
|
|
|
|
impl<T, N> Deref for ListNode<T, N> {
|
|
type Target = T;
|
|
|
|
fn deref(&self) -> &Self::Target {
|
|
&self.value
|
|
}
|
|
}
|
|
|
|
impl<T, N> DerefMut for ListNode<T, N> {
|
|
fn deref_mut(&mut self) -> &mut Self::Target {
|
|
&mut self.value
|
|
}
|
|
}
|
|
|
|
impl<T, N> AsRef<T> for ListNode<T, N> {
|
|
fn as_ref(&self) -> &T {
|
|
&self.value
|
|
}
|
|
}
|
|
|
|
impl<T, N> AsMut<T> for ListNode<T, N> {
|
|
fn as_mut(&mut self) -> &mut T {
|
|
&mut self.value
|
|
}
|
|
}
|
|
|
|
impl Empty {
|
|
pub fn push_front<T>(self, value: T) -> ListNode<T, Empty> {
|
|
ListNode { value, next: Empty }
|
|
}
|
|
|
|
pub fn push_back<T>(self, value: T) -> ListNode<T, Empty> {
|
|
ListNode { value, next: Empty }
|
|
}
|
|
|
|
pub fn prepend<L>(self, other: L) -> Prepend<L, Self>
|
|
where
|
|
L: PrependOnto<Self>,
|
|
{
|
|
other.prepend_onto(self)
|
|
}
|
|
|
|
pub fn append<L>(self, other: L) -> Prepend<Self, L>
|
|
where
|
|
Self: PrependOnto<L>,
|
|
{
|
|
self.prepend_onto(other)
|
|
}
|
|
|
|
pub fn reverse(self) -> Self {
|
|
Empty
|
|
}
|
|
|
|
pub fn is_empty(&self) -> bool {
|
|
true
|
|
}
|
|
}
|
|
|
|
impl<T, N> ListNode<T, N> {
|
|
pub fn push_front(self, value: T) -> ListNode<T, Self> {
|
|
ListNode { value, next: self }
|
|
}
|
|
|
|
pub fn push_front_borrowed(&mut self, value: T) -> ListNode<T, &mut Self> {
|
|
ListNode { value, next: self }
|
|
}
|
|
|
|
pub fn pop_front(self) -> N {
|
|
self.next
|
|
}
|
|
|
|
pub fn push_back(self, value: T) -> PushBack<T, Self>
|
|
where
|
|
Self: PrependOnto<ListNode<T, Empty>>,
|
|
{
|
|
self.prepend_onto(new().push_front(value))
|
|
}
|
|
|
|
pub fn pop_back(self) -> <Self as PopBack>::Output
|
|
where
|
|
Self: PopBack,
|
|
{
|
|
PopBack::pop_back(self)
|
|
}
|
|
|
|
pub fn prepend<L>(self, other: L) -> Prepend<L, Self>
|
|
where
|
|
L: PrependOnto<Self>,
|
|
{
|
|
other.prepend_onto(self)
|
|
}
|
|
|
|
pub fn append<L>(self, other: L) -> Prepend<Self, L>
|
|
where
|
|
Self: PrependOnto<L>,
|
|
{
|
|
self.prepend_onto(other)
|
|
}
|
|
|
|
pub fn split(self) -> (T, N) {
|
|
(self.value, self.next)
|
|
}
|
|
|
|
pub fn iter(&self) -> Iter<'_, T>
|
|
where
|
|
N: Node<Value = T>,
|
|
{
|
|
Iter {
|
|
node: Some(self as &dyn Node<Value = T>),
|
|
}
|
|
}
|
|
|
|
pub fn reverse(self) -> Reversed<Self>
|
|
where
|
|
Self: ReverseOnto<Empty>,
|
|
{
|
|
self.reverse_onto(Empty)
|
|
}
|
|
|
|
pub fn is_empty(&self) -> bool {
|
|
false
|
|
}
|
|
}
|
|
|
|
impl<'a, N> IntoIterator for &'a ListNode<N::Value, N>
|
|
where
|
|
N: Node,
|
|
{
|
|
type IntoIter = Iter<'a, N::Value>;
|
|
type Item = &'a N::Value;
|
|
|
|
fn into_iter(self) -> Self::IntoIter {
|
|
self.iter()
|
|
}
|
|
}
|
|
|
|
impl<T, N> Node for ListNode<T, N>
|
|
where
|
|
N: Node<Value = T>,
|
|
{
|
|
type Value = T;
|
|
|
|
fn value_ref(&self) -> &Self::Value {
|
|
&self.value
|
|
}
|
|
|
|
fn value_mut(&mut self) -> &mut Self::Value {
|
|
&mut self.value
|
|
}
|
|
|
|
fn next(&mut self) -> Option<&mut dyn Node<Value = Self::Value>> {
|
|
Some(&mut self.next)
|
|
}
|
|
|
|
fn next_immutable(&self) -> Option<&dyn Node<Value = Self::Value>> {
|
|
Some(&self.next)
|
|
}
|
|
}
|
|
|
|
impl<T> Node for ListNode<T, Empty> {
|
|
type Value = T;
|
|
|
|
fn value_ref(&self) -> &Self::Value {
|
|
&self.value
|
|
}
|
|
|
|
fn value_mut(&mut self) -> &mut Self::Value {
|
|
&mut self.value
|
|
}
|
|
|
|
fn next(&mut self) -> Option<&mut dyn Node<Value = Self::Value>> {
|
|
None
|
|
}
|
|
|
|
fn next_immutable(&self) -> Option<&dyn Node<Value = Self::Value>> {
|
|
None
|
|
}
|
|
}
|
|
|
|
impl<'a, N> Node for &'a mut N
|
|
where
|
|
N: Node + ?Sized,
|
|
{
|
|
type Value = N::Value;
|
|
|
|
fn value_ref(&self) -> &Self::Value {
|
|
N::value_ref(self)
|
|
}
|
|
|
|
fn value_mut(&mut self) -> &mut Self::Value {
|
|
N::value_mut(self)
|
|
}
|
|
|
|
fn next(&mut self) -> Option<&mut dyn Node<Value = Self::Value>> {
|
|
N::next(self)
|
|
}
|
|
|
|
fn next_immutable(&self) -> Option<&dyn Node<Value = Self::Value>> {
|
|
N::next_immutable(self)
|
|
}
|
|
}
|
|
|
|
impl<Input> ReverseOnto<Input> for Empty {
|
|
type Output = Input;
|
|
|
|
fn reverse_onto(self, input: Input) -> Self::Output {
|
|
input
|
|
}
|
|
}
|
|
|
|
impl<T, N, Input> ReverseOnto<Input> for ListNode<T, N>
|
|
where
|
|
N: ReverseOnto<ListNode<T, Input>>,
|
|
{
|
|
type Output = N::Output;
|
|
|
|
fn reverse_onto(self, input: Input) -> Self::Output {
|
|
let ListNode { value, next } = self;
|
|
|
|
next.reverse_onto(ListNode { value, next: input })
|
|
}
|
|
}
|
|
|
|
impl<Input> PrependOnto<Input> for Empty {
|
|
type Output = Input;
|
|
|
|
fn prepend_onto(self, input: Input) -> Self::Output {
|
|
input
|
|
}
|
|
}
|
|
|
|
impl<T, N, Input> PrependOnto<Input> for ListNode<T, N>
|
|
where
|
|
N: PrependOnto<Input>,
|
|
{
|
|
type Output = ListNode<T, N::Output>;
|
|
|
|
fn prepend_onto(self, input: Input) -> Self::Output {
|
|
let ListNode { value, next } = self;
|
|
|
|
ListNode {
|
|
value,
|
|
next: next.prepend_onto(input),
|
|
}
|
|
}
|
|
}
|
|
|
|
impl<T> PopBack for ListNode<T, Empty> {
|
|
type Output = Empty;
|
|
|
|
fn pop_back(self) -> Self::Output {
|
|
self.next
|
|
}
|
|
}
|
|
|
|
impl<T, N> PopBack for ListNode<T, N>
|
|
where
|
|
N: PopBack,
|
|
{
|
|
type Output = ListNode<T, N::Output>;
|
|
|
|
fn pop_back(self) -> Self::Output {
|
|
let ListNode { value, next } = self;
|
|
|
|
ListNode {
|
|
value,
|
|
next: next.pop_back(),
|
|
}
|
|
}
|
|
}
|
|
|
|
#[cfg(feature = "alloc")]
|
|
impl<N> Node for Box<N>
|
|
where
|
|
N: Node + ?Sized,
|
|
{
|
|
type Value = N::Value;
|
|
|
|
fn value_ref(&self) -> &Self::Value {
|
|
N::value_ref(self)
|
|
}
|
|
|
|
fn value_mut(&mut self) -> &mut Self::Value {
|
|
N::value_mut(self)
|
|
}
|
|
|
|
fn next(&mut self) -> Option<&mut dyn Node<Value = Self::Value>> {
|
|
N::next(self)
|
|
}
|
|
|
|
fn next_immutable(&self) -> Option<&dyn Node<Value = Self::Value>> {
|
|
N::next_immutable(self)
|
|
}
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod std_tests {
|
|
use super::{new, Node};
|
|
|
|
#[test]
|
|
fn construct_list() {
|
|
let mut list = new()
|
|
.push_front(5)
|
|
.push_front(4)
|
|
.push_front(3)
|
|
.push_front(2)
|
|
.push_front(1)
|
|
.push_front(0);
|
|
|
|
let mut next = Some(&mut list as &mut dyn Node<Value = i32>);
|
|
|
|
let mut out = [0; 6];
|
|
let mut index = 0;
|
|
while let Some(node) = next {
|
|
out[index] = *node.value_ref();
|
|
index += 1;
|
|
next = node.next();
|
|
}
|
|
|
|
assert_eq!(out, [0, 1, 2, 3, 4, 5]);
|
|
|
|
let mut out = [0; 6];
|
|
for (index, item) in list.iter().enumerate() {
|
|
out[index] = *item;
|
|
}
|
|
|
|
assert_eq!(out, [0, 1, 2, 3, 4, 5]);
|
|
|
|
let mut list = list.pop_front();
|
|
|
|
next = Some(&mut list as &mut dyn Node<Value = i32>);
|
|
|
|
let mut out = [0; 5];
|
|
let mut index = 0;
|
|
while let Some(node) = next {
|
|
out[index] = *node.value_ref();
|
|
index += 1;
|
|
next = node.next();
|
|
}
|
|
|
|
assert_eq!(out, [1, 2, 3, 4, 5]);
|
|
|
|
let mut out = [0; 5];
|
|
for (index, item) in list.iter().enumerate() {
|
|
out[index] = *item;
|
|
}
|
|
|
|
assert_eq!(out, [1, 2, 3, 4, 5]);
|
|
|
|
let list = list.reverse();
|
|
|
|
let mut out = [0; 5];
|
|
for (index, item) in list.iter().enumerate() {
|
|
out[index] = *item;
|
|
}
|
|
|
|
assert_eq!(out, [5, 4, 3, 2, 1]);
|
|
|
|
let second_list = new()
|
|
.push_front(9)
|
|
.push_front(8)
|
|
.push_front(7)
|
|
.push_front(6);
|
|
|
|
let list = list.prepend(second_list);
|
|
|
|
let mut out = [0; 9];
|
|
for (index, item) in list.iter().enumerate() {
|
|
out[index] = *item;
|
|
}
|
|
|
|
assert_eq!(out, [6, 7, 8, 9, 5, 4, 3, 2, 1]);
|
|
|
|
let third_list = new()
|
|
.push_front(10)
|
|
.push_front(11)
|
|
.push_front(12)
|
|
.push_front(13);
|
|
|
|
let list = list.append(third_list);
|
|
|
|
let mut out = [0; 13];
|
|
for (index, item) in list.iter().enumerate() {
|
|
out[index] = *item;
|
|
}
|
|
|
|
assert_eq!(out, [6, 7, 8, 9, 5, 4, 3, 2, 1, 13, 12, 11, 10]);
|
|
|
|
let list = list.push_back(0);
|
|
|
|
let mut out = [0; 14];
|
|
for (index, item) in list.iter().enumerate() {
|
|
out[index] = *item;
|
|
}
|
|
|
|
assert_eq!(out, [6, 7, 8, 9, 5, 4, 3, 2, 1, 13, 12, 11, 10, 0]);
|
|
|
|
let list = list.pop_back();
|
|
|
|
let mut out = [0; 13];
|
|
for (index, item) in list.iter().enumerate() {
|
|
out[index] = *item;
|
|
}
|
|
|
|
assert_eq!(out, [6, 7, 8, 9, 5, 4, 3, 2, 1, 13, 12, 11, 10]);
|
|
}
|
|
|
|
#[test]
|
|
fn construct_list_borroed() {
|
|
let mut list = new().push_front(5);
|
|
let mut list = list.push_front_borrowed(4);
|
|
let mut list = list.push_front_borrowed(3);
|
|
let mut list = list.push_front_borrowed(2);
|
|
let mut list = list.push_front_borrowed(1);
|
|
let mut list = list.push_front_borrowed(0);
|
|
|
|
let mut next = Some(&mut list as &mut dyn Node<Value = i32>);
|
|
|
|
let mut out = [0; 6];
|
|
let mut index = 0;
|
|
while let Some(node) = next {
|
|
out[index] = *node.value_ref();
|
|
index += 1;
|
|
next = node.next();
|
|
}
|
|
|
|
assert_eq!(out, [0, 1, 2, 3, 4, 5]);
|
|
|
|
let mut out = [0; 6];
|
|
for (index, item) in list.iter().enumerate() {
|
|
out[index] = *item;
|
|
}
|
|
|
|
assert_eq!(out, [0, 1, 2, 3, 4, 5]);
|
|
|
|
let mut list = list.pop_front();
|
|
|
|
next = Some(&mut list as &mut dyn Node<Value = i32>);
|
|
|
|
let mut out = [0; 5];
|
|
let mut index = 0;
|
|
while let Some(node) = next {
|
|
out[index] = *node.value_ref();
|
|
index += 1;
|
|
next = node.next();
|
|
}
|
|
|
|
assert_eq!(out, [1, 2, 3, 4, 5]);
|
|
|
|
let mut out = [0; 5];
|
|
for (index, item) in list.iter().enumerate() {
|
|
out[index] = *item;
|
|
}
|
|
|
|
assert_eq!(out, [1, 2, 3, 4, 5]);
|
|
}
|
|
}
|