cactus 1.0.7

use std::fmt;
use std::hash::{Hash, Hasher};

/// An immutable cactus stack node. May be empty or contain a value; may have a pointer to a parent
/// or not.
#[derive(Clone, Default)]
pub struct Cactus<T> {
    node: Option<RefCnt<Node<T>>>,
}

#[derive(Clone)]
struct Node<T> {
    val: T,
    parent: Option<RefCnt<Node<T>>>,
}

impl<T> Cactus<T> {
    /// Return an empty cactus stack node.
    pub fn new() -> Cactus<T> {
        Cactus { node: None }
    }

    /// Is this cactus stack node empty?
    ///
    /// # Examples
    /// ```
    /// use cactus::Cactus;
    /// let c = Cactus::new();
    /// assert!(c.is_empty());
    /// let c2 = c.child(1);
    /// assert!(!c2.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.node.is_none()
    }

    /// How many items are there in this cactus stack?
    pub fn len(&self) -> usize {
        self.vals().count()
    }

    /// Create a new cactus stack node containing value `val` and pointing to parent `self`.
    ///
    /// # Examples
    /// ```
    /// use cactus::Cactus;
    /// let c = Cactus::new();
    /// let c2 = c.child(1);
    /// let c3 = c2.child(2);
    /// assert_eq!(c3.vals().cloned().collect::<Vec<_>>(), [2, 1]);
    /// ```
    pub fn child(&self, val: T) -> Cactus<T> {
        Cactus {
            node: Some(RefCnt::new(Node {
                val,
                parent: self.node.clone(),
            })),
        }
    }

    /// Return this cactus stack node's parent node or `None` if this cactus stack is empty.
    ///
    /// # Examples
    /// ```
    /// use cactus::Cactus;
    /// let c = Cactus::new();
    /// let c2 = c.child(1);
    /// assert_eq!(c.parent(), None);
    /// assert_eq!(c2.val(), Some(&1));
    /// assert_eq!(c2.parent().unwrap(), Cactus::new());
    /// ```
    pub fn parent(&self) -> Option<Cactus<T>> {
        self.node.as_ref().map(|n| Cactus {
            node: n.parent.clone(),
        })
    }

    /// Return a reference to this cactus stack node's value or `None` if this cactus stack is
    /// empty.
    ///
    /// # Examples
    /// ```
    /// use cactus::Cactus;
    /// let c = Cactus::new().child(1);
    /// assert_eq!(c.val(), Some(&1));
    /// assert_eq!(c.parent().unwrap().val(), None);
    /// ```
    pub fn val(&self) -> Option<&T> {
        self.node.as_ref().map(|n| &n.val)
    }

    /// Return an iterator over this cactus stack's nodes. Note that the iterator produces nodes
    /// starting from this node and then walking up towards the root.
    ///
    /// # Examples
    /// ```
    /// use cactus::Cactus;
    /// let c = Cactus::new().child(1).child(2).child(3);
    /// assert_eq!(c.nodes().skip(1).next(), Some(Cactus::new().child(1).child(2)));
    /// ```
    pub fn nodes(&self) -> CactusNodesIter<T> {
        CactusNodesIter {
            next: self.node.as_ref(),
        }
    }

    /// Return an iterator over this cactus stack's values. Note that the iterator produces values
    /// starting from this node and then walking up towards the root.
    ///
    /// # Examples
    /// ```
    /// use cactus::Cactus;
    /// let c = Cactus::new().child(1).child(2).child(3);
    /// assert_eq!(c.vals().cloned().collect::<Vec<_>>(), [3, 2, 1]);
    /// ```
    pub fn vals(&self) -> CactusValsIter<T> {
        CactusValsIter {
            next: self.node.as_ref(),
        }
    }

    /// Try to consume this Cactus node and return its data. If the cactus node has no children,
    /// this succeeds; if the cactus node has children, it fails, and returns the original
    /// cactus node.
    ///
    /// # Examples
    /// ```
    /// use cactus::Cactus;
    /// let c = Cactus::new().child(1).child(2);
    /// let p = c.parent().unwrap();
    /// assert_eq!(c.try_unwrap().unwrap(), 2);
    /// // At this point the c variable can no longer be referenced (its value has moved).
    /// assert_eq!(p.val(), Some(&1));
    ///
    /// let d = Cactus::new().child(1);
    /// let d1 = d.child(2);
    /// let d2 = d.child(3);
    /// // At this point d.try_unwrap().unwrap() would return an Err, as d has two children that
    /// // prevent the underlying Cactus from being consumed. We then need to manually clone the
    /// // value if we want to access it uniformly.
    /// assert_eq!(d.try_unwrap().unwrap_or_else(|c| c.val().unwrap().clone()), 1);
    /// // At this point the d variable can no loner be referenced (its value has moved),
    /// // but we can still access the contents it once pointed to:
    /// assert_eq!(*d1.parent().unwrap().val().unwrap(), 1);
    /// ```
    pub fn try_unwrap(self) -> Result<T, Cactus<T>> {
        match self.node {
            None => Err(Cactus { node: None }),
            Some(x) => match RefCnt::try_unwrap(x) {
                Ok(n) => Ok(n.val),
                Err(rc) => Err(Cactus { node: Some(rc) }),
            },
        }
    }
}

/// An iterator over a `Cactus` stack's nodes. Note that the iterator produces nodes starting
/// from this node and then walking up towards the root.
pub struct CactusNodesIter<'a, T>
where
    T: 'a,
{
    next: Option<&'a RefCnt<Node<T>>>,
}

impl<'a, T> Iterator for CactusNodesIter<'a, T> {
    type Item = Cactus<T>;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|n| {
            self.next = n.parent.as_ref();
            Cactus {
                node: Some(n.clone()),
            }
        })
    }
}

/// An iterator over a `Cactus` stack's values. Note that the iterator produces values starting
/// from this node and then walking up towards the root.
pub struct CactusValsIter<'a, T>
where
    T: 'a,
{
    next: Option<&'a RefCnt<Node<T>>>,
}

impl<'a, T> Iterator for CactusValsIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|n| {
            self.next = n.parent.as_ref();
            &n.val
        })
    }
}

impl<T: PartialEq> PartialEq for Cactus<T> {
    fn eq(&self, other: &Cactus<T>) -> bool {
        // This is, in a sense, a manually expanded self.vals().zip(other.vals()) -- doing so
        // allows us to potentially shortcut the checking of every element using RefCnt::ptr_eq.
        let mut si = self.node.as_ref();
        let mut oi = other.node.as_ref();
        while let (Some(sn), Some(on)) = (si, oi) {
            // If we're lucky, the two RefCnt's are pointer equal, proving that the two cactuses are
            // equal even without ascending the parent hierarchy.
            if RefCnt::ptr_eq(sn, on) {
                return true;
            }
            if sn.val != on.val {
                return false;
            }
            si = sn.parent.as_ref();
            oi = on.parent.as_ref();
        }
        // If one of the iterators finished before the other, the two cactuses were of different
        // length and thus unequal by definition; otherwise they were equal.
        !(si.is_some() || oi.is_some())
    }
}

impl<T: Eq> Eq for Cactus<T> {}

impl<T: Hash> Hash for Cactus<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        for v in self.vals() {
            v.hash(state);
        }
    }
}

impl<T: fmt::Debug> fmt::Debug for Cactus<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "Cactus[")?;
        for (i, x) in self.vals().enumerate() {
            if i > 0 {
                write!(f, ", ")?;
            }
            write!(f, "{:?}", x)?;
        }
        write!(f, "]")
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::hash_map::DefaultHasher;
    use std::collections::HashSet;

    #[test]
    fn test_simple() {
        let r = Cactus::new();
        assert!(r.is_empty());
        assert_eq!(r.len(), 0);
        assert!(r.val().is_none());
        assert!(r.parent().is_none());
        let r2 = r.child(2);
        assert!(!r2.is_empty());
        assert_eq!(r2.len(), 1);
        assert_eq!(*r2.val().unwrap(), 2);
        let r3 = r2.parent().unwrap();
        assert_eq!(r3.is_empty(), true);
        assert_eq!(r3.len(), 0);
        let r4 = r.child(3);
        assert_eq!(r4.len(), 1);
        assert_eq!(*r4.val().unwrap(), 3);
        let r5 = r4.parent().unwrap();
        assert!(r5.is_empty());
        let r6 = r4.child(4);
        assert_eq!(r6.len(), 2);
        assert_eq!(*r6.val().unwrap(), 4);
        assert_eq!(*r6.parent().unwrap().val().unwrap(), 3);
    }

    #[test]
    fn test_vals() {
        let c = Cactus::new().child(3).child(2).child(1);
        assert_eq!(c.vals().cloned().collect::<Vec<_>>(), [1, 2, 3]);
    }

    #[test]
    fn test_vals_nodes() {
        let c = Cactus::new().child(3).child(2).child(1);
        assert_eq!(
            c.nodes().skip(1).next().unwrap(),
            Cactus::new().child(3).child(2)
        );
        assert_eq!(c.nodes().skip(2).next().unwrap(), Cactus::new().child(3));
    }

    #[test]
    fn test_eq() {
        let c1 = Cactus::<u8>::new();
        let c2 = Cactus::<u8>::new();
        assert_eq!(c1, c2);
        let c1 = Cactus::new().child(1).child(2);
        assert_eq!(c1, c1);
        let c1_1 = c1.child(4);
        let c1_2 = c1.child(4);
        assert_eq!(c1_1, c1_2);
        let c2 = Cactus::new().child(1).child(2);
        assert_eq!(c1, c2);
        assert!(!(c1 != c2));
        let c3 = Cactus::new().child(2).child(2);
        assert_ne!(c1, c3);
        assert!(!(c1 == c3));
        let c1 = Cactus::new().child(1).child(1);
        let c2 = Cactus::new().child(1);
        assert_ne!(c1, c2);
    }

    #[test]
    fn test_debug() {
        let c = Cactus::new().child(3).child(2).child(1);
        assert_eq!(format!("{:?}", c), "Cactus[1, 2, 3]");
    }

    #[test]
    fn test_try_unwrap() {
        let c = Cactus::new().child(4).child(3);
        let c1 = c.child(2);
        let c2 = c.child(1);
        assert_eq!(c2.try_unwrap(), Ok(1));
        assert_eq!(
            c.try_unwrap().unwrap_or_else(|c| c.val().unwrap().clone()),
            3
        );
        assert_eq!(c1.try_unwrap(), Ok(2));
    }

    #[test]
    fn test_hash() {
        fn calculate_hash<T: Hash>(t: &T) -> u64 {
            let mut s = DefaultHasher::new();
            t.hash(&mut s);
            s.finish()
        }

        let c1 = Cactus::new().child(4).child(3);
        let c2 = Cactus::new().child(4).child(3);
        assert_eq!(calculate_hash(&c1), calculate_hash(&c2));
        // The next test is fragile in theory although probably not in practise. Since there's no
        // guarantee that two distinct things will map to distinct hashes, it's perfectly possible
        // that a hasher returns the same value for two distinct cactuses. But this isn't hugely
        // likely to happen and, if it does, it'll be easy to work out what happened.
        let c3 = Cactus::new().child(3).child(4);
        assert_ne!(calculate_hash(&c1), calculate_hash(&c3));

        let mut s = HashSet::new();
        s.insert(c1.clone());
        s.insert(c2.clone());
        assert_eq!(s.len(), 1);
        assert_eq!(*s.iter().nth(0).unwrap(), c1);
        assert_eq!(*s.iter().nth(0).unwrap(), c2);
    }
}