oftlisp 0.1.3

//! Various garbage-collected collections.

use gc::{Gc, Trace};
use std::fmt::{Debug, Formatter, Result as FmtResult};
use std::iter::FromIterator;

use symbol::Symbol;

#[derive(Clone, Eq, Finalize, Hash, Ord, PartialEq, PartialOrd, Trace)]
enum Link<T: 'static + Trace> {
    Cons(Gc<T>, Gc<Link<T>>),
    Nil,
}

/// A garbage-collected linked list, akin to the traditional lists of ML-family
/// languages.
#[derive(Eq, Finalize, Hash, Ord, PartialEq, PartialOrd, Trace)]
pub struct GcLinkedList<T: 'static + Trace> {
    // Must always be Some when outside of a method.
    // This is an optimization to avoid a clone on push.
    head: Option<Gc<Link<T>>>,
    length: usize,
}

impl<T: 'static + Trace> GcLinkedList<T> {
    /// Creates a empty `GcLinkedList`.
    pub fn new() -> Self {
        GcLinkedList {
            head: Some(Gc::new(Link::Nil)),
            length: 0,
        }
    }

    /// Removes all elements from the list.
    pub fn clear(&mut self) {
        self.head = Some(Gc::new(Link::Nil));
        self.length = 0;
    }

    /// Returns whether the list is empty.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns an iterator over the list.
    pub fn iter(&self) -> GcLinkedListIter<T> {
        self.clone().into_iter()
    }

    /// Returns the head of the list, if it exists.
    pub fn head(&self) -> Option<Gc<T>> {
        match **self.head.as_ref().unwrap() {
            Link::Nil => None,
            Link::Cons(ref h, _) => Some(h.clone()),
        }
    }

    /// Returns the length of the list in O(1).
    pub fn len(&self) -> usize {
        self.length
    }

    /// Pops a value from the head of the list.
    pub fn pop(&mut self) -> Option<Gc<T>> {
        let (h, t) = match *self.head.take().unwrap() {
            Link::Nil => (None, Gc::new(Link::Nil)),
            Link::Cons(ref h, ref t) => (Some(h.clone()), t.clone()),
        };
        self.head = Some(t);
        self.length -= 1;
        h
    }

    /// Pushes a value onto the head of the list, moving it into a `Gc` first.
    pub fn push(&mut self, h: T) {
        self.push_gc(Gc::new(h))
    }

    /// Pushes all the given values onto the head of the list, moving them into
    /// `Gc`s first.
    pub fn push_all<II: IntoIterator<Item = T>>(&mut self, iter: II) {
        for h in iter {
            self.push(h)
        }
    }

    /// Pushes a value onto the head of the list.
    pub fn push_gc(&mut self, h: Gc<T>) {
        let head = self.head.take().unwrap();
        self.head = Some(Gc::new(Link::Cons(h, head)));
        self.length += 1
    }

    /// Pushes all the given values onto the head of the list, moving them into
    /// `Gc`s first.
    pub fn push_all_gc<II: IntoIterator<Item = Gc<T>>>(&mut self, iter: II) {
        for h in iter {
            self.push_gc(h)
        }
    }

    /// Returns the tail of the list, if it exists.
    pub fn tail(&self) -> Option<GcLinkedList<T>> {
        match **self.head.as_ref().unwrap() {
            Link::Nil => None,
            Link::Cons(_, ref t) => Some(GcLinkedList {
                head: Some(t.clone()),
                length: self.length - 1,
            }),
        }
    }

    /// Attempts to remove the first item from the linked list, returning a
    /// pair `(self.head(), self.tail())`. Does not modify the list.
    pub fn uncons(&self) -> Option<(Gc<T>, GcLinkedList<T>)> {
        match **self.head.as_ref().unwrap() {
            Link::Nil => None,
            Link::Cons(ref h, ref t) => {
                let h = h.clone();
                let t = GcLinkedList {
                    head: Some(t.clone()),
                    length: self.length - 1,
                };
                Some((h, t))
            }
        }
    }
}

impl<T: 'static + Clone + Trace> GcLinkedList<(Symbol, T)> {
    /// Looks up a value in the GcLinkedList, as if it were a dictionary.
    pub fn lookup(&self, key: Symbol) -> Option<T> {
        let mut head = self.head.as_ref().unwrap();
        loop {
            match **head {
                Link::Nil => break None,
                Link::Cons(ref h, ref t) => {
                    let (ref k, ref v) = **h;
                    if *k == key {
                        break Some(v.clone());
                    } else {
                        head = t;
                    }
                }
            }
        }
    }
}

impl<T: 'static + Trace> Clone for GcLinkedList<T> {
    fn clone(&self) -> Self {
        GcLinkedList {
            head: self.head.clone(),
            length: self.length,
        }
    }
}

impl<T: 'static + Debug + Trace> Debug for GcLinkedList<T> {
    fn fmt(&self, fmt: &mut Formatter) -> FmtResult {
        fmt.debug_list().entries(self.clone().into_iter()).finish()
    }
}

impl<T: 'static + Trace> Default for GcLinkedList<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T: 'static + Trace> FromIterator<T> for GcLinkedList<T> {
    fn from_iter<II: IntoIterator<Item = T>>(iter: II) -> Self {
        fn link<I: Iterator<Item = T>, T: 'static + Trace>(mut iter: I) -> (Gc<Link<T>>, usize) {
            let next = iter.next();
            match next {
                Some(x) => {
                    let (t, l) = link(iter);
                    (Gc::new(Link::Cons(Gc::new(x), t)), l + 1)
                }
                None => (Gc::new(Link::Nil), 0),
            }
        }

        let (head, length) = link(iter.into_iter());
        GcLinkedList {
            head: Some(head),
            length,
        }
    }
}

impl<T: 'static + Trace> FromIterator<Gc<T>> for GcLinkedList<T> {
    fn from_iter<II: IntoIterator<Item = Gc<T>>>(iter: II) -> Self {
        fn link<I: Iterator<Item = Gc<T>>, T: 'static + Trace>(
            mut iter: I,
        ) -> (Gc<Link<T>>, usize) {
            let next = iter.next();
            match next {
                Some(x) => {
                    let (t, l) = link(iter);
                    (Gc::new(Link::Cons(x, t)), l + 1)
                }
                None => (Gc::new(Link::Nil), 0),
            }
        }

        let (head, length) = link(iter.into_iter());
        GcLinkedList {
            head: Some(head),
            length,
        }
    }
}

impl<T: 'static + Trace> IntoIterator for GcLinkedList<T> {
    type Item = Gc<T>;
    type IntoIter = GcLinkedListIter<T>;
    fn into_iter(self) -> GcLinkedListIter<T> {
        GcLinkedListIter { list: self }
    }
}

/// An iterator over a [`GcLinkedList`](struct.GcLinkedList.html).
pub struct GcLinkedListIter<T: 'static + Trace> {
    list: GcLinkedList<T>,
}

impl<T: 'static + Trace> ExactSizeIterator for GcLinkedListIter<T> {
    fn len(&self) -> usize {
        self.list.len()
    }
}

impl<T: 'static + Trace> Iterator for GcLinkedListIter<T> {
    type Item = Gc<T>;
    fn next(&mut self) -> Option<Gc<T>> {
        let (h, t) = try_opt!(self.list.uncons());
        self.list = t;
        Some(h)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.len();
        (len, Some(len))
    }
}