An intrusive linked-list implementation in Rust

linked_list.rs

/*!
 * Intrusive singly linked lists
 */

use std::option::{Option, Some, None};
use std::cell::{Cell};

#[deriving(Show)]
pub struct ListCell<'a, T>(Cell<Option<&'a T>>);

impl<'a, T> ListCell<'a, T> {
  pub fn set_next(&self, new: Option<&'a T>) {
    let &ListCell(ref cell) = self;
    cell.set(new);
  }
  pub fn get_next(&self) -> Option<&'a T> {
    let &ListCell(ref cell) = self;
    cell.get()
  }
  pub fn new() -> ListCell<'a, T> {
    ListCell(Cell::new(None))
  }
}

/// A type with an intrusive linked-list cell. Simply embed a ListCell
/// into your type, implement get_cell, and get linked-list operations for
/// free.
pub trait LinkedList<'a> {
  fn get_cell(&'a self) -> &'a ListCell<'a, Self>;
  fn set_next(&'a self, next: Option<&'a Self>) { self.get_cell().set_next(next); }
  fn get_next(&'a self) -> Option<&'a Self> { return self.get_cell().get_next(); }
}

#[inline]
/// Add an element to the end of the list
pub fn append<'a, T: LinkedList<'a>>(head: &'a ListCell<'a, T>, new: &'a T) {
  new.set_next(None);
  match last(head) {
    None         => head.set_next(Some(new)),
    Some(oldEnd) => oldEnd.set_next(Some(new))
  }
}

#[inline]
/// Add an element to the beginning of the list
pub fn prepend<'a, T: LinkedList<'a>>(head: &'a ListCell<'a, T>, new: &'a T) {
  match head.get_next() {
    None      => head.set_next(Some(new)),
    Some(old) => {
      new.set_next(Some(old));
      head.set_next(Some(new));
    }
  }       
}

/// Remove the element equal to the given value from the list.
pub fn remove<'a, T: Eq+LinkedList<'a>>(head: &'a ListCell<'a, T>, old: &'a T) -> Option<&'a T> {
  let mut cur = iter(head);
  let mut last: &ListCell<T> = head;
  loop {
    match cur.next() {
      None       => return None,
      Some(this) if this == old => {
        last.set_next(this.get_next());
        this.set_next(None);
        return Some(this);
      }
      Some(this) => last = this.get_cell()
    }
  }      
}

#[inline]
/// Return the first value in the list
pub fn head<'a, T: LinkedList<'a>>(head: &'a ListCell<'a, T>) -> Option<&'a T> {
  return head.get_next();
}

#[inline]
/// Return the last value in the list
pub fn last<'a, T: LinkedList<'a>>(head: &'a ListCell<'a, T>) -> Option<&'a T> {
  let mut i = iter(head);
  let mut end: Option<&'a T> = None;
  loop {
    match i.next() {
      None       => break,
      Some(next) => end = Some(next),
    }
  }
  end
}

/// Insert the given value after the current value
pub fn insert_after<'a, T: LinkedList<'a>>(after: &'a T, value: &'a T) {
  append(after.get_cell(), value);
}

pub struct LinkedListIter<'a, T>(Option<&'a T>);

/// Return an iterator over the elements of a list.
pub fn iter<'a, T: LinkedList<'a>>(head: &'a ListCell<'a, T>) -> LinkedListIter<'a, T> {
  match head.get_next() {
    None    => LinkedListIter(None),
    Some(h) => LinkedListIter(Some(h))
  }
}

impl<'a, T: LinkedList<'a>> Iterator<&'a T> for LinkedListIter<'a, T> {
  fn next(&mut self) -> Option<&'a T> {
    match *self {
      LinkedListIter(None) => None,
      LinkedListIter(Some(cur)) => {
        match cur.get_next() {
          None => None,
          Some(next) => {
              (*self) = LinkedListIter(Some(next));
              Some(cur)
          }
        }
      }
    }
  }
}

#[deriving(Show)]
struct Test<'a> {
  n: int,
  next: ListCell<'a, Test<'a>>
}

impl<'a> Eq for Test<'a> {
  fn eq(&self, other: &Test) -> bool { self.n == other.n }
}

impl<'a> LinkedList<'a> for Test<'a> {
  fn get_cell(&'a self) -> &'a ListCell<'a, Test<'a>> { return &self.next; }
}

fn main() {
  println!("hello");
  let t1 = Test{n: 1, next: ListCell::new()};
  let t2 = Test{n: 2, next: ListCell::new()};
  let t3 = Test{n: 3, next: ListCell::new()};
  let head: ListCell<Test> = ListCell::new();
  prepend(&head, &t3);
  prepend(&head, &t2);
  prepend(&head, &t1);
  println!("rm: {}", remove(&head, &t2));
  println!("head: {}", head);
}