~launchpad-p-s/sofastatistics/main

« back to all changes in this revision

Viewing changes to tree.py

  • Committer: Grant Paton-Simpson
  • Date: 2009-05-19 04:21:43 UTC
  • Revision ID: g@ubuntu-20090519042143-p561mbokz3inefvd
Initial import

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
 
 
2
class Nodes(object):
 
3
    """
 
4
    Nodes functionality used by Nodes and Trees
 
5
    """
 
6
    def addChild(self, child_node):
 
7
        """
 
8
        Add child node.  Set level, and parent of node.
 
9
        Returns child node
 
10
        """
 
11
        if isinstance(self, NodeTree):
 
12
            start_node = self.root_node
 
13
        else:
 
14
            start_node = self
 
15
        child_node.level = start_node.level + 1
 
16
        child_node.parent = start_node
 
17
        start_node.children.append(child_node)
 
18
        return child_node
 
19
        
 
20
    def getDepth(self):
 
21
        "Get tree depth (including root node)"
 
22
        if isinstance(self, NodeTree):
 
23
            start_node = self.root_node
 
24
        else:
 
25
            start_node = self
 
26
        max_depth = 1 # initialise
 
27
        for child_node in start_node.children:
 
28
            child_depth = child_node.getDepth()
 
29
            if (child_depth + 1) > max_depth:
 
30
                max_depth = child_depth + 1
 
31
        return max_depth
 
32
 
 
33
    def getTerminalNodes(self):
 
34
        "Gets list of terminal nodes"
 
35
        if isinstance(self, NodeTree):
 
36
            if not self.root_node.children:
 
37
                raise Exception, "Cannot get terminal nodes until " + \
 
38
                    "there is at least one node added to tree"                
 
39
            start_node = self.root_node
 
40
        else:
 
41
            start_node = self            
 
42
        if not start_node.children:
 
43
            return [start_node]
 
44
        else:
 
45
            term_nodes_lst = []
 
46
            children_term_nodes = \
 
47
                [child_node.getTerminalNodes() for child_node in start_node.children]
 
48
            for child_term_nodes in children_term_nodes:
 
49
                term_nodes_lst += child_term_nodes
 
50
            return term_nodes_lst
 
51
        
 
52
    def generNode(self):
 
53
        yield self
 
54
        for child_node in self.children:
 
55
            for node in child_node.generNode():
 
56
                yield node
 
57
    
 
58
class NodeTree(Nodes):
 
59
    """
 
60
    Object names follow standard tree data structure terminology of 
 
61
    root, nodes, subtrees, terminal nodes, parent, child, sibling, 
 
62
    and tree depth.
 
63
    Nodes can only have one parent.  All nodes come from root.
 
64
    """
 
65
    
 
66
    def __init__(self):
 
67
        self.root_node = Node(label="Root")
 
68
        self.root_node.level = 0
 
69
 
 
70
    def printChildren(self, node):
 
71
        l = []
 
72
        for child_node in node.children:
 
73
            l.append(str(child_node))
 
74
            children_str = str(self.printChildren(child_node))
 
75
            if children_str: #otherwise an empty string will get own line
 
76
                l.append(str(self.printChildren(child_node)))
 
77
        return "\n".join(l)
 
78
    
 
79
    def __str__(self):
 
80
        l = []
 
81
        l.append(str(self.root_node))
 
82
        l.append(self.printChildren(self.root_node))
 
83
        return "\n".join(l)
 
84
        
 
85
class Node(Nodes):
 
86
    """
 
87
    Optionally, has details (a dictionary) and a text label.    
 
88
    Node index is set when added to either a tree 
 
89
    or an existing node.
 
90
    Parent is set when added to a node (or left as None if added
 
91
    to a tree). Children is updated as children are added.
 
92
    """
 
93
    
 
94
    def __init__(self, dets_dic=None, label=""):
 
95
        if dets_dic:
 
96
            self.dets_dic = dets_dic
 
97
        else:
 
98
            self.dets_dic = {}
 
99
        self.level = None
 
100
        self.parent = None
 
101
        self.children=[]
 
102
        self.label = label
 
103
        
 
104
    def __str__(self):
 
105
        return self.level*2*" " + "Level: " + str(self.level) + \
 
106
            "; Label: " + self.label + \
 
107
            "; Details: " + str(self.dets_dic) + \
 
108
            "; Child labels: " + ", ".join([x.label for x in self.children])
 
109
            
 
 
b'\\ No newline at end of file'