Skip to content

Instantly share code, notes, and snippets.

@BlueZeeKing
Last active January 26, 2024 19:52
Show Gist options
  • Save BlueZeeKing/4e319d794e61e507792c13b816df4dfa to your computer and use it in GitHub Desktop.
Save BlueZeeKing/4e319d794e61e507792c13b816df4dfa to your computer and use it in GitHub Desktop.
A simple doubly linked list in Rust using pointers
use std::{marker::PhantomPinned, pin::Pin};
pub struct Node<T> {
value: T,
next: Option<Box<Node<T>>>,
prev: Option<*mut Node<T>>,
_pantom: PhantomPinned,
}
pub struct List<T> {
first: Option<Box<Node<T>>>,
last: Option<*mut Node<T>>,
}
impl<T> Default for List<T> {
fn default() -> Self {
Self::empty()
}
}
impl<T> List<T> {
pub fn new(value: T) -> Self {
let mut node = Box::new(Node::new(value));
let ptr = node.as_mut() as *mut Node<T>;
Self {
first: Some(node),
last: Some(ptr),
}
}
pub fn empty() -> Self {
Self {
first: None,
last: None,
}
}
pub fn first(&self) -> Option<&Node<T>> {
self.first.as_deref()
}
pub fn first_mut(&mut self) -> Option<Pin<&mut Node<T>>> {
self.first
.as_deref_mut()
.map(|val| unsafe { Pin::new_unchecked(val) })
}
pub fn last(&self) -> Option<&Node<T>> {
self.last.map(|ptr| unsafe { ptr.as_ref().unwrap() })
}
pub fn last_mut(&mut self) -> Option<Pin<&mut Node<T>>> {
self.last
.map(|val| unsafe { Pin::new_unchecked(val.as_mut().unwrap()) })
}
pub fn append(&mut self, value: T) {
if self.first.is_none() {
let mut node = Box::new(Node::new(value));
let ptr = node.as_mut() as *mut Node<T>;
self.first = Some(node);
self.last = Some(ptr);
} else {
let mut node = Box::new(Node::new(value));
let ptr = node.as_mut() as *mut Node<T>;
let last = unsafe { self.last.replace(ptr).unwrap().as_mut().unwrap() };
node.prev = Some(last);
last.next = Some(node);
}
}
pub fn pop(&mut self) -> Option<T> {
if self.last == None {
None
} else if self.first.as_ref().unwrap().next.is_none() {
let val = self.first.take().unwrap().value;
self.last = None;
Some(val)
} else {
self.last = Some(unsafe { self.last.unwrap().as_ref().unwrap().prev.unwrap() });
let last = unsafe { self.last.unwrap().as_mut().unwrap().next.take() };
Some(last.unwrap().value)
}
}
pub fn prepend(&mut self, value: T) {
let mut node = Box::new(Node::new(value));
if self.last.is_none() {
self.last = Some(node.as_mut());
}
if let Some(mut old_node) = self.first.replace(node) {
old_node.prev = Some(self.first.as_deref_mut().unwrap());
self.first.as_mut().unwrap().next = Some(old_node);
}
}
pub fn pop_front(&mut self) -> Option<T> {
if self.first.is_none() {
None
} else if self.first.as_ref().unwrap().next.is_none() {
let val = self.first.take().unwrap().value;
self.last = None;
Some(val)
} else {
let mut first = self.first.take().unwrap();
self.first = Some(first.next.take().unwrap());
Some(first.value)
}
}
}
impl<T> Iterator for List<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.pop_front()
}
}
impl<T> DoubleEndedIterator for List<T> {
fn next_back(&mut self) -> Option<Self::Item> {
self.pop()
}
}
impl<T> Node<T> {
fn new(value: T) -> Self {
Self {
value,
next: None,
prev: None,
_pantom: PhantomPinned,
}
}
pub fn value(&self) -> &T {
&self.value
}
fn unpin_value_mut(&mut self) -> &mut T {
&mut self.value
}
pub fn value_mut(self: Pin<&mut Self>) -> &mut T {
unsafe { Pin::into_inner_unchecked(self) }.unpin_value_mut()
}
pub fn next(&self) -> Option<&Self> {
self.next.as_deref()
}
fn unpin_next_mut(&mut self) -> Option<Pin<&mut Self>> {
self.next
.as_deref_mut()
.map(|value| unsafe { Pin::new_unchecked(value) })
}
pub fn next_mut(self: Pin<&mut Self>) -> Option<Pin<&mut Self>> {
unsafe { Pin::into_inner_unchecked(self) }.unpin_next_mut()
}
pub fn prev(&self) -> Option<&Self> {
if let Some(ptr) = self.prev {
Some(unsafe { ptr.as_ref() }.unwrap())
} else {
None
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment