kaktus 0.1.3

//! Immutable __cactus stack__ implementation.
//!
//! Other terms for cactus stack include __parent pointer tree__,
//! __spaghetti stack__, and __saguaro stack__. See
//! [Wikipedia](https://en.wikipedia.org/wiki/Parent_pointer_tree) for more
//! information.
//!
//! ```ignore
//! // Quickstart
//! extern crate kaktus;
//! // the trait `Stack` needs to be importet for `Stack`/`VStack` to work
//! use kaktus::{Stack, Stack};
//!
//! let root = Stack::root(0);
//! let one = root.push(1);
//! assert_eq!(*one.pop().unwrap(), 0);
//! assert_eq!(*one, 1);
//! ```
//!
//! # Overview
//!
//! The stacks described in this crate differ from traditional stacks in one
//! decisive point, they are *immutable*. This means that a value in itself
//! represents the stack:
//!
//! ```ignore
//! let root = Stack::root(0);
//! let one = root.push(1);
//! let two = root.push(2);
//! assert_eq!(*two, 2);
//! ```
//! Further, popping a value from the stack just returns the parent -- the
//! originial value (and thus the stack it represents) remains valid:
//!
//! ```ignore
//! let one_ = two.pop().unwrap();
//! assert_eq!(*one_, 1);
//! // `two` is still valid
//! assert_eq!(*two, 2);
//! ```
//!
//! For comparison, this shows how stacks are often implemented instead:
//!
//! ```ignore
//! // traditional stack
//! let mut stack = vec![0];
//! stack.push(1);
//! stack.push(2);
//! let two = stack.pop().unwrap();
//! let one = stack.pop().unwrap();
//! ```
//!
//! ## Cactus stacks
//!
//! Due to the immutable property, it is possible to spawn off multiple values
//! from the same parent, making it effecively a tree:
//!
//! ```ignore
//! // tree structure:
//! // 0 -- 1 -- 2
//! //  \
//! //   3 -- 4 -- 5
//!
//! let root = Stack::root(0);
//! let two  = root.push(1).push(2);
//! let five = root.push(3).push(4).push(5);
//!
//! assert_eq!(*two, 2);
//! assert_eq!(*five, 5);
//! ```
//! Crate Content
//!
//! This crate provides two stack implementations:
//! [`Stack`](struct.Stack.html) and [`VStack`](struct.VStack.html). In short:
//! `Stack` uses a recursive (pointer) architecture, whilst `VStackc` uses a
//! vector to store the stack's data.
//!

use std::ops::Deref;
use std::rc::Rc;
use std::fmt::{self, Debug};
use std::iter::{IntoIterator, Iterator};
use std::iter::FromIterator;


pub trait AbstractStack<T> where Self: std::marker::Sized {

    fn push(&self, val: T) -> Self;
    fn pop(&self) -> Option<Self>;
    fn iter(&self) -> StackIterator<T>;
    fn peek(&self) -> Option<&T>;

    fn depth(&self) -> usize {
        self.iter().count()
    }
}

pub trait Collect<T>: AbstractStack<T> where T: Clone {
    fn as_vec(&self) -> Vec<T> {
        let mut v = Vec::new();
        for el in self.iter().map(|ref node| node.deref().clone()) {
            v.push(el)
        }// .collect()
        v
    }
}

// impl<T> AbstractStack<T> where T: Clone {

// }
// fn as_vec(&self) -> Vec<T> {
//         self.iter().map()
//     }

struct StackNode<T> {
    value: T,
    parent: Option<Stack<T>>,
}

struct Empty<T>(Option<T>);


/// Recursive Stack
///
/// A **recursive** implementation for ``Stack``.
///
/// ```rust,ignore
/// pub struct StackNode<T> {
///     value: T,
///     parent: Option<Stack<T>>,
/// }
/// ```
///
pub struct Stack<T>(Rc<StackNode<T>>);

impl<T> Clone for Stack<T> {
    fn clone(&self) -> Self {
        Stack(self.0.clone())
    }
}

impl<T> Stack<T> {

    pub fn iter(&self) -> StackIterator<T> {
        self.into_iter()
    }

    pub fn root(val: T) -> Self {
        Stack(Rc::from(StackNode {
            value: val,
            parent: None,
        }))
    }

    pub fn push(&self, val: T) -> Self {
            Stack(Rc::from(StackNode {
            value: val,
            parent: Some(Stack(self.0.clone())),
        }))
    }

    pub fn pop(&self) -> Option<Self> {
        match self.0.parent {
            None => None,
            Some(ref p) => Some(p.clone()),
        }
    }

    pub fn peek(&self) -> Option<&T> {
        Some(self.deref())
    }

}

impl<T> AbstractStack<T> for Stack<T> {

    // fn iter(&self) -> StackIterator<T> {
    //     self.into_iter()
    // }

    fn push(&self, val: T) -> Self {
        self.push(val)
    }

    fn pop(&self) -> Option<Self> {
        self.pop()
    }

    fn iter(&self) -> StackIterator<T> {
        self.iter()
    }

    fn peek(&self) -> Option<&T> {
        self.peek()
    }

}

// impl<T> Stack<Empty<T>> {
//     pub fn empty() -> Self {
//         Stack::root(Empty(None))
//     }
// }

// impl<T> AbstractStack<T> for Stack<Empty<T>> {
//     // type Out = Stack<T>;

//     // fn iter(&self) -> StackIterator<T> {
//     //     StackIterator { current: None }
//     // }

//     fn push(&self, val: T) -> Stack<T> {
//         Stack::root(val)
//         // AbstractStack::push(self, Empty(Some(val)))
//     }

//     fn pop(&self) -> Option<Stack<T>> {
//         None
//     }
// }


impl<T> Deref for Stack<T> {
    type Target = T;

    fn deref(&self) -> &T {
        &self.0.deref().value
    }
}

impl<T: Debug> Debug for Stack<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "S<{:?}>", **self)
    }
}

impl<T> Debug for Empty<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "-Empty-")
    }
}


impl<'a, T> IntoIterator for &'a Stack<T> {
    type Item = Stack<T>;
    type IntoIter = StackIterator<T>;

    fn into_iter(self) -> StackIterator<T> {
        StackIterator { current: Some(self.clone()) }
    }
}

pub struct StackIterator<T> {
    current: Option<Stack<T>>,
}

impl<T> Iterator for StackIterator<T> {
    type Item = Stack<T>;

    fn next(&mut self) -> Option<Stack<T>> {
        let cur = self.current.take();
        self.current = cur.as_ref().and_then(|s| s.pop());
        cur
    }
}

// impl<T> FromIterator<T> for Vec<T> {
//     fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self {
//         let mut v = Vec::new();

//         for i in iter {
//             v.add(i);
//         }

//         v
//     }
// }


// #[test]
// fn test() {
//     let root = Stack::root(0);
//     let three = root.push(1).push(2).push(3);
//     for e in (StackIterator { current: Some(three.clone()) }) {
//         println!("{:?}", *e);
//     }

//     for e in &three {
//         println!("{:?}", e);
//     }

//     for e in three.iter() {
//         println!("{:?}", e);
//     }

//     println!("{:?}", three.iter().count());
// }

// fn push<T>(stack: &Stack<T>, b: bool, val: T) -> Stack<T> {
//     // if bool {

//     // }
//     // println!("DEPTH: {:?}", stack.iter().count());
//     stack.push(val)
// }

pub struct NStack<T>(Option<Stack<T>>);

impl<T> NStack<T> {
    pub fn new() -> Self {
        NStack(None)
    }

    pub fn iter(&self) -> StackIterator<T> {
        match self.0 {
            None => StackIterator { current: None },
            Some(ref stack) => stack.into_iter()
        }
    }

    pub fn try_into(&self) -> Option<Stack<T>> {
        self.0.as_ref().map(|stack| stack.clone())
    }

    pub fn unwrap(&self) -> Stack<T> {
        self.try_into().unwrap()
    }

    pub fn push(&self, val: T) -> Self {
        NStack(Some(Stack::root(val)))
    }

    pub fn peek(&self) -> Option<&T> {
        self.0.as_ref().map(|s|s.deref())
    }
}

impl<T> AbstractStack<T> for NStack<T> {

    fn push(&self, val: T) -> Self {
        self.push(val)
    }

    fn pop(&self) -> Option<Self> {
        self.0.as_ref()
            .map(|stack| NStack(stack.pop()))
            // .map(|stack| NStack(stack))

            // |stack| NStack(stack.pop()))
    }

    fn iter(&self) -> StackIterator<T> {
        self.iter()
    }

    fn peek(&self) -> Option<&T> {
        self.peek()
    }

}

#[test]
fn test_empty() {
    let root = NStack::new();
    let x = root.push(1);


    // push(&root, 1);
    println!("{:?}", root.iter().count());
    println!("{:?}", x.iter().count());
    println!("XXXX: {:?}", *x.unwrap());
}