dll.rs

// A simple doubly linked list example using slotmap.

extern crate slotmap;

use slotmap::{SlotMap, Key};

struct Node<T> {
    value: T,
    prev: Key,
    next: Key,
}

struct List<T> {
    sm: SlotMap<Node<T>>,
    head: Key,
    tail: Key,
}

impl<T> List<T> {
    fn new() -> Self {
        Self {
            sm: SlotMap::new(),
            head: Key::null(),
            tail: Key::null(),
        }
    }

    fn len(&self) -> usize {
        self.sm.len()
    }

    fn push_head(&mut self, value: T) {
        let k = self.sm.insert(Node {
            value,
            prev: Key::null(),
            next: self.head,
        });

        if !self.head.is_null() {
            self.sm[self.head].prev = k;
        } else {
            self.tail = k;
        }
        self.head = k;
    }
    
    fn push_tail(&mut self, value: T) {
        let k = self.sm.insert(Node {
            value,
            prev: self.tail,
            next: Key::null(),
        });

        if !self.tail.is_null() {
            self.sm[self.tail].next = k;
        } else {
            self.head = k;
        }
        self.tail = k;
    }

    fn pop_head(&mut self) -> Option<T> {
        if self.head.is_null() {
            return None;
        }

        let old_head = self.head;
        self.head = self.sm[old_head].next;
        if self.len() == 1 {
            self.tail = Key::null();
        }

        Some(self.sm.remove(old_head).unwrap().value)
    }

    fn pop_tail(&mut self) -> Option<T> {
        if self.tail.is_null() {
            return None;
        }

        let old_tail = self.tail;
        self.tail = self.sm[old_tail].prev;
        if self.len() == 1 {
            self.head = Key::null();
        }

        Some(self.sm.remove(old_tail).unwrap().value)
    }
}

fn main() {
    let mut dll = List::new();
    dll.push_head(5);
    dll.push_tail(6);
    dll.push_tail(7);
    dll.push_head(4);

    assert_eq!(dll.len(), 4);
    assert_eq!(dll.pop_head(), Some(4));
    assert_eq!(dll.pop_head(), Some(5));
    assert_eq!(dll.pop_tail(), Some(7));
    assert_eq!(dll.pop_tail(), Some(6));
    assert_eq!(dll.pop_head(), None);
}