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
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

// Tells the compiler not to throw warnings for unused code
#[allow(dead_code)]

// Use statements
//
// Standard library
use std::*;
// Gives access to hash utilities 
use hash_util::*;

/*
 *
 * Tree:
 *     - This file contains enums, structs, and impls for creating binary trees, and 
 *       and methods for accessing their information.
 *
 */

/* Enum for the tree used for allowing multiple classifications of trees:
 *
 *     - An empty tree that contains only a hash
 *     - A tree leaf that contains a hash and a value
 *     - A tree node ( or root node ) that contains a hash and left and right children
 *
 */
#[derive(Clone)]
pub enum Tree<T>
{

    // Empty tree definition
    Empty
    {
        
        // Empty trees only contain a hash
        hash: String

    },
    // Leaf definition
    Leaf
    {

        // Leaves act as a node with a hash and value but no children
        hash: String,
        value: T

    },
    // Node ( tree definiton )
    // The node functions as the normal tree definition as it contains a hash field
    // and two children.
    //
    // Note: Boxes are used for allocating memory on the heap for the left and right tree
    // values.
    Node
    {

        // Nodes have a hash and left and right children 
        hash: String,
        left: Box<Tree<T>>,
        right: Box<Tree<T>>

    }

}

// Tree impl 
impl<T: fmt::Display> Tree<T>
{

    // Empty tree constructor
    #[allow(dead_code)]
    pub fn empty( ) -> Self
    {

        // Returns an empty tree with the given hash
        Tree::Empty{ hash: ::hash_util::empty_hash() }

    }
    
    // Leaf node constructor
    #[allow(dead_code)]
    pub fn leaf( value: T ) -> Tree<T>
    {

        // Creates the hash given the leaf's value, create_leaf_hash() takes in
        // a reference to the value so we pass in value.as_ref()
        let leaf_hash = create_leaf_hash( &value );
        // Returns a tree leaf with the given hash and value
        Tree::Leaf
        {

            hash: leaf_hash,
            value: value

        }
        
    }
    // Tree node constructor
    #[allow(dead_code)]
    pub fn node( left: Tree<T>, right: Tree<T> ) -> Tree<T>
    {

        // Creates the node hash using the children's hashes.
        // Passes in the reference to the left and write hashes by
        // using unwrap()
        let node_hash = create_node_hash( left.hash(), right.hash() );
        // Returns a tree node with the given hash and
        // allocates memory for the left and right children 
        Tree::Node
        {

            hash: node_hash,
            left: Box::new(left),
            right: Box::new(right)

        }   

    }
    // Retrieve the hash of a given tree
    #[allow(dead_code)]
    pub fn hash( &self ) -> &String
    {

        // Includes tree
        use self::*;

        // Match self to enum type
        match *self
        {
            
            // ref allows us to reference a field of the enum 
            // If it's an empty tree
            Tree::Empty { ref hash } => hash,
            // If it's a tree node
            Tree::Node { ref hash, .. } => hash,
            // If it's a leaf node 
            Tree::Leaf { ref hash, .. } => hash
                
        }        

    }
    
}