dogs/data_structures/
decision_tree.rs

1use std::rc::Rc;
2
3/**
4Implements a data-structure that maintains decisions taken in the tree. It helps avoiding
5having to copy a Vector in each node to maintain the solution value.
6Using this data-structure works great on large instances and large branching factors.
7*/
8#[derive(Debug)]
9pub struct DecisionTree<D> {
10    /// decision of the node
11    pub d:D,
12    /// pointer towards the parent (empty if the node is the root)
13    pub parent:Option<Rc<DecisionTree<D>>>,
14}
15
16impl<D> DecisionTree<D> where D:Clone {
17    /**
18     creates a new decision tree (only a root node)
19    */
20    pub fn new(d:D) -> Rc<Self> {
21        Rc::new(Self {
22            d,
23            parent: None,
24        })
25    }
26
27    /**
28     * returns the decision held by the current node
29     */
30    pub fn decision(n:&Rc<Self>) -> &D {
31        &n.as_ref().d
32    }
33
34    /**
35    * creates a new child and point it to the current decision tree
36    */
37    pub fn add_child(n:&Rc<Self>, d:D) -> Rc<Self> {
38        Rc::new(Self {
39            d,
40            parent:Some(n.clone())
41        })
42    }
43
44    /**
45    returns all decisions taken so far from the root to the current node
46    */
47    pub fn decisions_from_root(n:&Rc<Self>) -> Vec<D> {
48        let mut res:Vec<D> = Vec::new();
49        let mut c = n.clone();
50        loop {
51            res.push(DecisionTree::decision(&c).clone());
52            let c2;
53            match &c.as_ref().parent {
54                None => {
55                    res.reverse();
56                    return res;
57                },
58                Some(p) => {
59                    c2 = p.clone();
60                }
61            }
62            c = c2;
63        }
64    }
65}
66
67
68/*
69 * UNIT TESTING
70 */
71#[cfg(test)]
72mod tests {
73    use super::*;
74 
75    #[test]
76    fn create_root() {
77        let tree = DecisionTree::new(0);
78        assert_eq!(*DecisionTree::decision(&tree), 0);
79    }
80
81    #[test]
82    fn create_child() {
83        let a = DecisionTree::new(0);
84        let b = DecisionTree::add_child(&a, 1);
85        let c = DecisionTree::add_child(&b, 42);
86        assert_eq!(DecisionTree::decisions_from_root(&c), vec![0,1,42]);
87    }
88
89    #[test]
90    fn multiple_children() {
91        let node_a = DecisionTree::new(0);
92        let node_b = DecisionTree::add_child(&node_a, 1);
93        let node_c = DecisionTree::add_child(&node_b, 2);
94        let node_d = DecisionTree::add_child(&node_a, 3);
95        let node_e = DecisionTree::add_child(&node_d, 4);
96        assert_eq!(DecisionTree::decisions_from_root(&node_c), vec![0,1,2]);
97        assert_eq!(DecisionTree::decisions_from_root(&node_e), vec![0,3,4]);
98    }
99}
100
dogs/data_structures/decision_tree.rs

dogs/data_structures/
decision_tree.rs
