|
27
|
1 import logging
|
|
|
2
|
|
|
3 class HashTreeNode:
|
|
|
4 """Node of a HashTree.
|
|
|
5 Has a value and keeps children in a dict indexed by key."""
|
|
|
6 key = None
|
|
|
7 value = None
|
|
|
8 children = None
|
|
|
9
|
|
|
10 def __init__(self, key=None, value=None, children=None):
|
|
|
11 """create node"""
|
|
|
12 self.key = key
|
|
|
13 self.value = value
|
|
|
14 self.children = children
|
|
|
15
|
|
|
16
|
|
|
17 def getNode(self, key):
|
|
|
18 """return node under key"""
|
|
|
19 if self.children is None:
|
|
|
20 return None
|
|
|
21 else:
|
|
|
22 return self.children.get(key, None)
|
|
|
23
|
|
|
24
|
|
|
25 def addNode(self, node):
|
|
|
26 """add child node using key from node"""
|
|
|
27 if self.children is None:
|
|
|
28 self.children = {node.key : node}
|
|
|
29 else:
|
|
|
30 self.children[node.key] = node
|
|
|
31
|
|
|
32
|
|
29
|
33 def getSubtreeAsList(self):
|
|
34
|
34 """returns the subtree as flattened list sorted by key (depth first)"""
|
|
27
|
35 if self.children is None:
|
|
|
36 if self.value is None:
|
|
|
37 return []
|
|
|
38 else:
|
|
|
39 return [self.value]
|
|
|
40
|
|
|
41 else:
|
|
|
42 if self.value is None:
|
|
|
43 sub = []
|
|
|
44 else:
|
|
|
45 sub = [self.value]
|
|
|
46
|
|
43
|
47 for k in sorted(self.children.keys()):
|
|
29
|
48 sub.extend(self.children.get(k).getSubtreeAsList())
|
|
27
|
49
|
|
|
50 return sub
|
|
|
51
|
|
|
52
|
|
|
53 def getSubtreeAsText(self):
|
|
|
54 """prints whole tree as text"""
|
|
|
55 if self.children is None:
|
|
|
56 return "(%s:%s)"%(self.key, self.value)
|
|
|
57 else:
|
|
|
58 sub = "(%s:%s):["%(self.key, self.value)
|
|
43
|
59 for k in sorted(self.children.keys()):
|
|
27
|
60 sub += self.children.get(k).getSubtreeAsText()
|
|
|
61 sub += ", "
|
|
|
62
|
|
|
63 return sub + "] "
|
|
|
64
|
|
39
|
65
|
|
|
66
|
|
27
|
67
|
|
|
68 class HashTree:
|
|
|
69 """Tree using dictionaries"""
|
|
|
70
|
|
43
|
71 # root HashTreeNode
|
|
27
|
72 root = None
|
|
43
|
73 # separator by which key strings are split into parts
|
|
27
|
74 keySeparator = '.'
|
|
43
|
75 # function applied to key parts
|
|
27
|
76 keyFn = None
|
|
|
77
|
|
|
78 def __init__(self, keySeparator='.', keyFn=None):
|
|
52
|
79 """Create a HashTree.
|
|
43
|
80
|
|
|
81 @param keySeparator string by which key strings are split into parts
|
|
|
82 @param keyFn function applied to key parts (e.g. int if key parts are numbers)
|
|
|
83 """
|
|
27
|
84 self.root = HashTreeNode()
|
|
|
85 self.keySeparator = keySeparator
|
|
|
86 self.keyFn = keyFn
|
|
|
87
|
|
|
88
|
|
39
|
89 def _splitkey(self, key):
|
|
52
|
90 """Return a list of key parts"""
|
|
39
|
91 if isinstance(key, basestring):
|
|
|
92 # its a string - split
|
|
|
93 keys = key.split(self.keySeparator)
|
|
|
94 if self.keyFn is not None:
|
|
|
95 keys = [self.keyFn(k) for k in keys]
|
|
43
|
96
|
|
39
|
97 elif isinstance(key, list):
|
|
|
98 # its a list - keep
|
|
|
99 keys = key
|
|
43
|
100
|
|
39
|
101 else:
|
|
|
102 # not a list - wrap in list
|
|
|
103 keys = [key]
|
|
|
104
|
|
|
105 return keys
|
|
|
106
|
|
|
107
|
|
27
|
108 def getNode(self, key):
|
|
52
|
109 """Return node under key from the tree.
|
|
|
110
|
|
27
|
111 key can be sequence of key string or a single string using keySeparator.
|
|
30
|
112 If key is None, returns root node.
|
|
27
|
113 """
|
|
30
|
114 if key is None:
|
|
|
115 return self.root
|
|
|
116
|
|
39
|
117 keys = self._splitkey(key)
|
|
27
|
118
|
|
|
119 node = self.root
|
|
|
120 for k in keys:
|
|
|
121 node = node.getNode(k)
|
|
|
122 if node is None:
|
|
|
123 return None
|
|
|
124
|
|
|
125 return node
|
|
|
126
|
|
|
127
|
|
|
128 def get(self, key):
|
|
52
|
129 """Return value under key from the tree.
|
|
|
130
|
|
27
|
131 key can be sequence of key string or a single string using keySeparator.
|
|
|
132 """
|
|
|
133 node = self.getNode(key)
|
|
|
134 if node is None:
|
|
|
135 return None
|
|
|
136
|
|
|
137 return node.value
|
|
|
138
|
|
|
139
|
|
|
140 def add(self, key, value):
|
|
52
|
141 """Add value under key to the tree.
|
|
|
142
|
|
27
|
143 key can be sequence of key string or a single string using keySeparator.
|
|
|
144 """
|
|
39
|
145 keys = self._splitkey(key)
|
|
27
|
146 node = self.root
|
|
|
147 for k in keys:
|
|
|
148 nextnode = node.getNode(k)
|
|
|
149 if nextnode is None:
|
|
|
150 nextnode = HashTreeNode(key=k)
|
|
|
151 node.addNode(nextnode)
|
|
|
152
|
|
|
153 node = nextnode
|
|
|
154
|
|
|
155 node.value = value
|
|
39
|
156
|
|
27
|
157
|
|
39
|
158 def getChildrenOf(self, key):
|
|
52
|
159 """Return the list of child (values) of the node under key."""
|
|
39
|
160 node = self.getNode(key)
|
|
|
161 if node.children is None:
|
|
|
162 return []
|
|
|
163 else:
|
|
43
|
164 # sort children by key
|
|
|
165 childlist = sorted(node.children.items(), key=lambda x:x[0])
|
|
|
166 # and return the values
|
|
|
167 return [n.value for (k, n) in childlist if n.value is not None]
|
|
39
|
168
|
|
|
169
|
|
|
170 def getAncestorsOf(self, key):
|
|
52
|
171 """Return the list of ancestor (values) of the node under key.
|
|
|
172
|
|
|
173 Order: root element first."""
|
|
39
|
174 keys = self._splitkey(key)
|
|
|
175 node = self.root
|
|
|
176 ancestors = []
|
|
|
177 for k in keys:
|
|
|
178 if node.value is not None:
|
|
|
179 ancestors.append(node.value)
|
|
|
180
|
|
|
181 node = node.getNode(k)
|
|
|
182 if node is None:
|
|
|
183 return ancestors
|
|
|
184
|
|
|
185 return ancestors
|
|
|
186
|
|
27
|
187
|
