|
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
|
|
|
33 def getSubtreeList(self):
|
|
|
34 """returns the subtree as list sorted by key (depth first)"""
|
|
|
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
|
|
|
47 keys = self.children.keys()
|
|
|
48 keys.sort()
|
|
|
49 for k in keys:
|
|
|
50 #logging.debug("getSubtreeList: k=%s sub=%s"%(k,sub))
|
|
|
51 sub.extend(self.children.get(k).getSubtreeList())
|
|
|
52
|
|
|
53 return sub
|
|
|
54
|
|
|
55
|
|
|
56 def getSubtreeAsText(self):
|
|
|
57 """prints whole tree as text"""
|
|
|
58 if self.children is None:
|
|
|
59 return "(%s:%s)"%(self.key, self.value)
|
|
|
60 else:
|
|
|
61 sub = "(%s:%s):["%(self.key, self.value)
|
|
|
62 keys = self.children.keys()
|
|
|
63 keys.sort()
|
|
|
64 for k in keys:
|
|
|
65 sub += self.children.get(k).getSubtreeAsText()
|
|
|
66 sub += ", "
|
|
|
67
|
|
|
68 return sub + "] "
|
|
|
69
|
|
|
70
|
|
|
71 class HashTree:
|
|
|
72 """Tree using dictionaries"""
|
|
|
73
|
|
|
74 root = None
|
|
|
75 keySeparator = '.'
|
|
|
76 keyFn = None
|
|
|
77
|
|
|
78 def __init__(self, keySeparator='.', keyFn=None):
|
|
|
79 """creates a HashTree"""
|
|
|
80 self.root = HashTreeNode()
|
|
|
81 self.keySeparator = keySeparator
|
|
|
82 self.keyFn = keyFn
|
|
|
83
|
|
|
84
|
|
|
85 def getNode(self, key):
|
|
|
86 """gets node under key from the tree.
|
|
|
87 key can be sequence of key string or a single string using keySeparator.
|
|
|
88 """
|
|
|
89 #logging.debug("getNode(key=%s)"%(key))
|
|
|
90 if isinstance(key, basestring):
|
|
|
91 keys = key.split(self.keySeparator)
|
|
|
92 if self.keyFn is not None:
|
|
|
93 keys = [self.keyFn(k) for k in keys]
|
|
|
94 elif isinstance(key, list):
|
|
|
95 keys = key
|
|
|
96 else:
|
|
|
97 keys = [key]
|
|
|
98
|
|
|
99 node = self.root
|
|
|
100 for k in keys:
|
|
|
101 #logging.debug("getNode node=%s k=%s"%(node, repr(k)))
|
|
|
102 node = node.getNode(k)
|
|
|
103 #logging.debug("getNode got:%s"%(node))
|
|
|
104 if node is None:
|
|
|
105 return None
|
|
|
106
|
|
|
107 return node
|
|
|
108
|
|
|
109
|
|
|
110 def get(self, key):
|
|
|
111 """gets value under key from the tree.
|
|
|
112 key can be sequence of key string or a single string using keySeparator.
|
|
|
113 """
|
|
|
114 node = self.getNode(key)
|
|
|
115 if node is None:
|
|
|
116 return None
|
|
|
117
|
|
|
118 return node.value
|
|
|
119
|
|
|
120
|
|
|
121 def add(self, key, value):
|
|
|
122 """adds value under key to the tree.
|
|
|
123 key can be sequence of key string or a single string using keySeparator.
|
|
|
124 """
|
|
|
125 #logging.debug("add(key=%s, value=%s)"%(repr(key), value))
|
|
|
126 if isinstance(key, basestring):
|
|
|
127 keys = key.split(self.keySeparator)
|
|
|
128 if self.keyFn is not None:
|
|
|
129 keys = [self.keyFn(k) for k in keys]
|
|
|
130 elif isinstance(key, list):
|
|
|
131 keys = key
|
|
|
132 else:
|
|
|
133 keys = [key]
|
|
|
134
|
|
|
135 node = self.root
|
|
|
136 for k in keys:
|
|
|
137 nextnode = node.getNode(k)
|
|
|
138 if nextnode is None:
|
|
|
139 nextnode = HashTreeNode(key=k)
|
|
|
140 node.addNode(nextnode)
|
|
|
141
|
|
|
142 node = nextnode
|
|
|
143
|
|
|
144 node.value = value
|
|
|
145
|
|
|
146
|
|
|
147
|
