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

/// A unique identifier for any node in a tree.
///
/// This is how we are able to reference nodes and their relationships without having pointers
/// all over the place. Rust is known for having very confusing and non beginner friendly
/// implementations for Graph-like data structures, and this idea of keeping an id as
/// a handle gets around this entire issue.
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub struct NodeId {
    index: usize,
}

impl NodeId {
    /// Generate a new `NodeId` for a given `index`.
    pub fn new(index: usize) -> Self {
        Self { index }
    }
}

/// Defines all the common operations that must be supported for any node
pub trait NodeOperations {
    type T;

    /// Create a new instance of the node with a given NodeId
    fn new(data: Self::T, id: NodeId) -> Self;

    /// Get a reference to the id of the node
    fn get_id(&self) -> NodeId;

    /// Get a reference to the data inside the node
    fn get_data(&self) -> &Self::T;

    /// Get a mutable reference to the data inside the node
    fn get_data_mut(&mut self) -> &mut Self::T;
}

/// Defines all the common operations that must be supported for Binary Nodes, i.e., ones with a left and right child
pub trait BinaryNodeOperations: NodeOperations {
    /// Get the left node
    fn get_left(&self) -> Option<NodeId>;

    /// Get the right node
    fn get_right(&self) -> Option<NodeId>;

    /// Set the left node to a node by it's `NodeId`
    fn set_left(&mut self, left_node_id: Option<NodeId>);

    /// Set the right node to a node by it's `NodeId`
    fn set_right(&mut self, right_node_id: Option<NodeId>);
}