Mercurial > hg > MPIWGWeb

comparison HashTree.py @ 27:9a75eb1b31b3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
more work on projects.
author casties
date Mon, 22 Apr 2013 21:01:00 +0200
parents
children 224023958871
comparison
equal deleted inserted replaced
26:8a99ad8713d6 27:9a75eb1b31b3
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