[RUST]Cons List (#1)

cons-list.rs

// We need a reference counting pointer to have multiple references to a single object
use std::rc::Rc;

// We need a RefCell to be able to internally mutate an immutable value
use std::cell::RefCell;

#[derive(Debug)]
// definition of a linked list
enum List {
  // We may have multiple references to a given list object, therefore we need Rc<T>
  // We want to be able to mutate the value referred to by Rc<List> (which is either Cons or Nil)
  // so we encapsulate it in a RefCell<T> type
  Cons(i32, RefCell<Rc<List>>),
  Nil,
}
use List::{Cons, Nil};


impl List {
  // function simply returns the tail of a list if there is one
  // if there isn't one, return Option::None
  fn tail(&self) -> Option<&RefCell<Rc<List>>> {
    match *self {
      Cons(_, ref item) => Some(item),
      Nil => None,
    }
  }
}


fn main() {
  // We want several references to a, and therefore, we use Rc<T>
  // Recall that the type of the second element in the Cons tuple is RefCell<Rc<T>>
  // We use associated functions to create a new Rc containing Nil inside of a new RefCell (containing Rc<T: Nil>)
  let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil))));
  
  println!("a initial rc count = {}", Rc::strong_count(&a));
  println!("a next item = {:#?}", a.tail());
  
  // Same deal with b, but here instead of Nil, we borrow/reference a as b's tail
  // at this point, a has two owners: fn main() and also b has a reference to a
  let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a))));
  
  println!("a initial ref count after b creation = {}", Rc::strong_count(&a));
  println!("b initial ref count = {}", Rc::strong_count(&b));
  println!("b next item = {:#?}", b.tail());
  
  // if a's tail is something (and not Option::None)
  if let Some(link) = a.tail() {
      // borrow a mutable copy of the tail, set it equal to b
      *link.borrow_mut() = Rc::clone(&b);
  }
  
  // at this point, a references b and vice versa, and both are referenced by fn main()
  // both should have a strong_count of 2
  println!("b rc count after changing a = {}", Rc::strong_count(&b));
  println!("a rc count after changing a = {}", Rc::strong_count(&a)); 
  
  // the line below will cause a stack overflow!
  // recall that the tail of b is a, and we set the tail of a to b!
  // println!("a next item = {:#?}", a.tail()); 
  
  
} // here, a and b's reference counts drop by one, as fn main() no longer references them

// HOWEVER they reference each other, therefore they exist in memory for ever, because a Rc<T> only drops
// when the strong ref count is 0!