use std::cell::RefCell;
use crate::Arena;
/*
-- Continuing with 'pseudocode', a node of doubly linked list is like
data Node a = Node
{ left :: Maybe (Node a)
, right :: Maybe (Node a)
, elem :: a
}
*/
// Compared to the code above, in rust we'll have to use mutable cells to
// construct non-trivial nodes. I'll explain why later.
#[derive(Clone)]
struct Node<'a, T> {
left: RefCell<Option<&'a Node<'a, T>>>,
right: RefCell<Option<&'a Node<'a, T>>>,
elem: T,
}
/// Save me 3 keystrokes (and recover a drop of aesthetics)
type BNode<'a, T> = &'a Node<'a, T>;
// Let's first do a simple task and just construct this list.
/// Returns left node
fn copy_from_slice<'d, T: Clone>(xs: &[T], a: &'d Arena) -> Option<BNode<'d, T>> {
// You might notice that node always has an element, unlike single-linked
// lists, or even slices that we're working with here. So first step is to
// check if slice even has data
if let Some(x) = xs.first() {
// First we create the leftmost node - the one we'll return from the
// function. At first it contains no references to neighbours.
let leftmost = Node {
left: RefCell::new(None),
right: RefCell::new(None),
elem: x.clone(),
};
let leftmost = a.share(leftmost);
// Next we go through the rest of the slice...
let mut left = leftmost;
for x in xs.iter().skip(1) {
// ..and create a node for each element. At node creation we already
// know what the left neighbour is
let current = Node {
left: RefCell::new(Some(left)),
right: RefCell::new(None),
elem: x.clone(),
};
let current = a.share(current);
// And then we need to go to the previous node and update its right
// neighbour to the one we just made.
left.right.replace(Some(current));
left = current;
}
Some(leftmost)
} else {
None
}
}
/*
-- Now, written in a real /programming/ language
fromList :: [a] -> Maybe (Node a)
fromList = go Nothing where
go left [] = left
go left (x:xs) =
let self = Node {left, right = go self xs, elem = x}
in self
-- Ask yourself: why do we create a variable and immediately return it?
*/
/*
-- Let's start with some inspirational pseudocode
reverse
:: Node a -- ^ leftmost
-> Node a -- ^ new leftmost, which was rightmost in the original list
reverse Node{elem = begin, right} = reverseOnto (nil begin) right where
-- thus nil becomes rightmost
nil :: a -> Maybe (Node a) -> Node a
nil elem left = Node { right = Nothing, left, elem }
reverseOnto :: (Maybe (Node a) -> Node a) -> Maybe (Node a) -> Node a
reverseOnto make Nothing = make Nothing
-- take the node, previous node (obtained by make) becomes its right
-- neighbour, next node becomes left neighbour
reverseOnto make (Just Node{right, elem}) =
let make' left = Node {right = Just $ make (Just self), left = left, elem}
left = reverseOnto make' right
self = make' (Just left)
in left
*/
// I just want to stop for a second a talk about how cool the code above is.
// (And to pat myself on the back for writing it without looking it up). We
// construct an object by simultaneously constructing all its parts and
// assembing them: we don't need mutability to set future computations in place,
// we can just refer to them when they don't exist yet. This technique is called
// "tying the knot": we construct a function "make'" by using a variable "self"
// defined later, and we construct "self" by calling this "make'" function.
// There's also "left" there as a third rope end so the rope analogy kind of
// breaks. How is it possible to construct an object using an object that
// doesn't yet exist? That's the magic of lazyness!
//
// I expect most of you readers to not understand the code above, and I advise
// you to try learning haskell. It's not that hard and it will forever change
// the way you think about data structures.
//
// Unfortunately in rust we don't have lazyness, so we'll have to deal with
// mutable cells to write down "future computations". Argh. Please observe the
// parallels between the knot-tying through lazyness in pseudocode and rust:
// there we thread computations however we want, and in rust we have to go back
// and explicitly fix those up
fn reverse<'a, T: Clone>(mut leftmost: BNode<'a, T>, a: &'a Arena) -> BNode<'a, T> {
// This is written specifically similar to the singly-linked version
let mut r = a.share(Node {
left: RefCell::new(None),
right: RefCell::new(None),
elem: leftmost.elem.clone(),
});
// One difference is that we don't have nil, so `r` is created with an
// element already (but no neighbours, like in `fromList`)
loop {
let next = match *leftmost.right.borrow() {
None => break r,
Some(node) => {
// Old `r` goes to the right, like with singly-linked version
let current = a.share(Node {
left: RefCell::new(None),
right: RefCell::new(Some(r)),
elem: node.elem.clone(),
});
// Again, fixup `r` with the new node on the left
*r.left.borrow_mut() = Some(current);
r = current;
node
}
};
// I would like to not have this `next` variable, but silly rustc thinks
// that `leftmost` is still borrowed inside match, even though I
// explicitly copied the result with dereferencing? I actually hate
// autoderef and autoreborrow
leftmost = next;
}
}
/*
toList :: Node a -> [a]
toList Node{right, elem} = elem : maybe [] toList right
*/
fn insert_at<'a, T>(index: usize, elem: T, left: BNode<'a, T>, a: &'a Arena) -> BNode<'a, T> {
if index == 0 {
let node = Node {
left: RefCell::new(None),
right: RefCell::new(Some(left)),
elem,
};
let node = a.share(node);
left.left.replace(Some(node));
node
} else {
let mut pos = left;
let mut index = index;
loop {
index -= 1;
if index == 0 {
let node = Node {
left: RefCell::new(Some(pos)),
right: RefCell::new(pos.right.take()),
elem,
};
let node = a.share(node);
pos.right.replace(Some(node));
if let Some(right) = *node.right.borrow() {
right.left.replace(Some(node));
}
break;
}
let next_pos = if let Some(next_pos) = *pos.right.borrow() {
next_pos
} else {
break;
};
// You would think that we can skip creating next_pos, but using
// `borrow()` borrows `pos` until the end of the whole expression
// it seems, so you can't reassign it while it's borrowed.
pos = next_pos;
}
left
}
}
struct CopyIter<'a, T> {
current: Option<BNode<'a, T>>,
}
impl<'a, T: Copy> Iterator for CopyIter<'a, T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
let current = self.current?;
let item = current.elem;
self.current = *current.right.borrow();
Some(item)
}
}
/*
struct IntoIter<'a, T> {
current: Option<BNode<'a, T>>,
}
impl<'a, T> Iterator for IntoIter<'a, T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
let current = self.current?;
let next = *current.right.borrow();
if let Some(next) = next {
next.left.replace(None);
}
self.current = next;
// Riiight, the problem is we can never move out of Shared because,
// guess what, it can be shared and we would never know. What could help
// here is using a more specific to doubly-linked lists solution, but I
// went for a generic one.
Some(current.elem)
}
}
*/
fn iter_copy<T: Copy>(head: BNode<'_, T>) -> CopyIter<'_, T> {
CopyIter { current: Some(head) }
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn node_no_drop() {
assert!(!std::mem::needs_drop::<Node<'static, i64>>());
}
#[test]
fn copied() {
let arena = Arena::new(128);
let xs = copy_from_slice(&[1, 2, 3], &arena);
let xs = CopyIter{ current: xs }.collect::<Vec<_>>();
assert_eq!(xs, vec![1, 2, 3]);
}
#[test]
fn inserts() {
let arena = Arena::new(128);
let xs = copy_from_slice(&[1, 2, 3], &arena).unwrap();
let xs = insert_at(0, 100, xs, &arena);
let xs_ = iter_copy(xs).collect::<Vec<_>>();
assert_eq!(xs_, vec![100, 1, 2, 3]);
let xs = insert_at(2, 200, xs, &arena);
let xs_ = iter_copy(xs).collect::<Vec<_>>();
assert_eq!(xs_, vec![100, 1, 200, 2, 3]);
let xs = insert_at(5, 300, xs, &arena);
let xs_ = iter_copy(xs).collect::<Vec<_>>();
assert_eq!(xs_, vec![100, 1, 200, 2, 3, 300]);
}
#[test]
fn reverses() {
let arena = Arena::new(128);
let xs = copy_from_slice(&[1, 2, 3, 4, 5], &arena).unwrap();
let rev = reverse(xs, &arena);
let rev_ = iter_copy(rev).collect::<Vec<_>>();
assert_eq!(rev_, vec![5, 4, 3, 2, 1]);
}
}