catalan 0.3.3

binary tree of n variables where the parent node represents a function and the child node represents a value.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

use std::{
    fmt::{Debug, Formatter},
    sync::Arc,
};

use crate::BinaryNode;

pub mod inverse_polish;
pub mod operators;

#[derive(Clone, Eq, PartialEq, Hash)]
pub enum ExpressionNode<V, O> {
    /// A atom in full binary tree
    Atomic {
        /// value type
        value: V,
    },
    /// A node in full binary tree
    Binary {
        /// left hand side leaf
        lhs: Arc<Self>,
        /// Operator
        operator: O,
        /// right hand side leaf
        rhs: Arc<Self>,
    },
}

impl<V, O> Debug for ExpressionNode<V, O>
where
    V: Debug,
    O: Debug,
{
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self {
            ExpressionNode::Atomic { value, .. } => Debug::fmt(value, f),
            ExpressionNode::Binary { lhs, operator, rhs } => f.debug_tuple("Binary").field(lhs).field(operator).field(rhs).finish(),
        }
    }
}

impl<V, O> ExpressionNode<V, O> {
    pub fn atomic(value: V) -> Arc<Self> {
        Arc::new(ExpressionNode::Atomic { value })
    }
    pub fn binary(operator: O, lhs: &Arc<Self>, rhs: &Arc<Self>) -> Arc<Self> {
        Arc::new(ExpressionNode::Binary { operator, lhs: lhs.clone(), rhs: rhs.clone() })
    }
    /// Count nodes in a full binary tree
    pub fn nodes(&self) -> usize {
        match self {
            ExpressionNode::Atomic { .. } => 1,
            ExpressionNode::Binary { lhs, rhs, .. } => lhs.nodes() + rhs.nodes(),
        }
    }
}

impl BinaryNode {
    /// Make the binary tree into an expression tree
    pub fn as_expression<V, O>(&self, mut values: Vec<V>, mut actions: Vec<O>) -> Arc<ExpressionNode<V, O>> {
        assert_eq!(values.len(), actions.len() + 1);
        self.eat_expression(&mut values, &mut actions)
    }
    fn eat_expression<V, O>(&self, values: &mut Vec<V>, actions: &mut Vec<O>) -> Arc<ExpressionNode<V, O>> {
        match self {
            BinaryNode::Atomic => {
                let atom = values.remove(0);
                ExpressionNode::atomic(atom)
            }
            BinaryNode::Binary { lhs, rhs } => {
                let operator = actions.remove(0);
                let lhs = lhs.eat_expression(values, actions);
                let rhs = rhs.eat_expression(values, actions);
                ExpressionNode::binary(operator, &lhs, &rhs)
            }
        }
    }
}