Skip to content

Instantly share code, notes, and snippets.

@mitghi
Created January 13, 2023 21:53
Show Gist options
  • Save mitghi/bb5ae2ebafba841ce4a8bd87376795a2 to your computer and use it in GitHub Desktop.
Save mitghi/bb5ae2ebafba841ce4a8bd87376795a2 to your computer and use it in GitHub Desktop.
doublili
use std::{rc::{Rc, Weak}, cell::RefCell};
struct Node<T>{
data: T,
next: Option<Rc<RefCell<Node<T>>>>,
prev: Option<Weak<RefCell<Node<T>>>>,
}
struct Doublili<T> {
head: Option<Rc<RefCell<Node<T>>>>,
tail: Option<Rc<RefCell<Node<T>>>>,
}
impl<T> Node<T> {
fn new(t: T) -> Self { Self {data: t, next: None, prev: None} }
fn append(node: &mut Rc<RefCell<Node<T>>>, data: T) -> Option<Rc<RefCell<Node<T>>>>{
let is_none = node.borrow().next.is_none();
if is_none {
let last_node = Some(Rc::new(RefCell::new(Node{data, next: None, prev: Some(Rc::downgrade(node))})));
node.borrow_mut().next = last_node.clone();
last_node
} else if let Some(ref mut next) = node.borrow_mut().next {
Self::append(next, data)
} else {
None
}
}
fn pop(node: &mut Rc<RefCell<Node<T>>>) -> Option<Rc<RefCell<Node<T>>>>{
let has_next = node.borrow().next.is_some();
if has_next {
let next_node = node.borrow().next.clone().unwrap();
next_node.borrow_mut().prev.take();
node.borrow_mut().next.take();
Some(next_node)
} else {
None
}
}
}
impl<T> Doublili<T> {
pub fn new() -> Self { Self { head: None, tail: None } }
pub fn append(&mut self, data: T) {
if let Some(ref mut next) = self.head {
self.tail = Node::append(next, data);
} else {
let node = Rc::new(RefCell::new(Node::new(data)));
self.head = Some(node.clone());
self.tail = Some(node);
}
}
pub fn pop(&mut self) -> Option<Rc<RefCell<Node<T>>>> {
let has_some = self.head.is_some() && self.tail.is_some();
if has_some {
let head = self.head.clone();
let tail = self.tail.clone();
match Rc::ptr_eq(&head.unwrap(), &tail.unwrap()){
true => {
let result = self.head.clone();
self.head.take();
self.tail.take();
return result;
},
false => {
let h = self.head.clone();
let result = Node::pop(&mut h.unwrap());
let head = self.head.take();
self.head = result;
return head;
}
};
}
None
}
}
fn main() {
let mut doublili: Doublili<String> = Doublili::new();
for i in 0..10 {
doublili.append(format!("some input at pos {}", i));
}
let value = doublili.pop().unwrap();
println!("value => {}", value.to_owned().borrow().data);
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_append() {
let mut doublili: Doublili<String> = Doublili::new();
for i in 0..10 {
doublili.append(format!("some input at pos {}", i));
}
let value = doublili.pop().unwrap();
println!("value => {}", value.to_owned().borrow().data);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment