Mercurial > hg > MPIWGWeb
annotate HashTree.py @ 161:2b5adc7f5445
english and german footer
| author | casties |
|---|---|
| date | Thu, 06 Jun 2013 19:11:45 +0200 |
| parents | 014efa0923be |
| children | afc96bc56817 |
| rev | line source |
|---|---|
| 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 | |
|
105
246d87d33f25
CLOSED - # 79: sortierung der liste der projekte pro abteilung
casties
parents:
97
diff
changeset
|
33 def getSubtreeAsList(self, depthFirst=True): |
|
246d87d33f25
CLOSED - # 79: sortierung der liste der projekte pro abteilung
casties
parents:
97
diff
changeset
|
34 """Return the subtree as flattened list sorted by key.""" |
|
114
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
35 if depthFirst: |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
36 return self.getSubtreeAsListDepthFirst() |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
37 else: |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
38 return self.getSubtreeAsListBreadthFirst() |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
39 |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
40 |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
41 def getSubtreeAsListDepthFirst(self): |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
42 """Return the subtree as flattened list, depth first, sorted by key.""" |
| 27 | 43 if self.children is None: |
|
114
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
44 if self.value is None: |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
45 return [] |
|
105
246d87d33f25
CLOSED - # 79: sortierung der liste der projekte pro abteilung
casties
parents:
97
diff
changeset
|
46 else: |
|
114
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
47 return [self.value] |
| 27 | 48 |
| 49 else: | |
| 50 if self.value is None: | |
| 51 sub = [] | |
| 52 else: | |
| 53 sub = [self.value] | |
| 54 | |
|
114
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
55 for k in sorted(self.children.keys()): |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
56 sub.extend(self.children.get(k).getSubtreeAsListDepthFirst()) |
|
105
246d87d33f25
CLOSED - # 79: sortierung der liste der projekte pro abteilung
casties
parents:
97
diff
changeset
|
57 |
|
114
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
58 return sub |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
59 |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
60 |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
61 def getSubtreeAsListBreadthFirst(self): |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
62 """Return the subtree as flattened list, breadth first, sorted by key.""" |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
63 q = [self] |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
64 sub = [] |
| 115 | 65 while len(q) > 0: |
|
114
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
66 node = q.pop(0) |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
67 if node.value is not None: |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
68 sub.append(node.value) |
| 27 | 69 |
|
114
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
70 if node.children is not None: |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
71 clist = sorted(node.children.values(), key=lambda x:x.key) |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
72 q.extend(clist) |
|
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
73 |
|
105
246d87d33f25
CLOSED - # 79: sortierung der liste der projekte pro abteilung
casties
parents:
97
diff
changeset
|
74 return sub |
| 27 | 75 |
| 76 | |
| 77 def getSubtreeAsText(self): | |
|
114
1acfcaaa5ca3
fixed HashTree.getSubTreeAsList when using breadth first.
casties
parents:
105
diff
changeset
|
78 """Return whole tree as text. Depth first.""" |
| 27 | 79 if self.children is None: |
| 80 return "(%s:%s)"%(self.key, self.value) | |
| 81 else: | |
| 82 sub = "(%s:%s):["%(self.key, self.value) | |
| 43 | 83 for k in sorted(self.children.keys()): |
| 27 | 84 sub += self.children.get(k).getSubtreeAsText() |
| 85 sub += ", " | |
| 86 | |
| 87 return sub + "] " | |
| 88 | |
| 89 | |
| 90 class HashTree: | |
| 91 """Tree using dictionaries""" | |
| 92 | |
| 43 | 93 # root HashTreeNode |
| 27 | 94 root = None |
| 43 | 95 # separator by which key strings are split into parts |
| 27 | 96 keySeparator = '.' |
| 43 | 97 # function applied to key parts |
| 27 | 98 keyFn = None |
| 99 | |
| 100 def __init__(self, keySeparator='.', keyFn=None): | |
| 52 | 101 """Create a HashTree. |
| 43 | 102 |
| 103 @param keySeparator string by which key strings are split into parts | |
| 104 @param keyFn function applied to key parts (e.g. int if key parts are numbers) | |
| 105 """ | |
| 27 | 106 self.root = HashTreeNode() |
| 107 self.keySeparator = keySeparator | |
| 108 self.keyFn = keyFn | |
| 109 | |
| 110 | |
| 39 | 111 def _splitkey(self, key): |
| 52 | 112 """Return a list of key parts""" |
| 39 | 113 if isinstance(key, basestring): |
| 114 # its a string - split | |
| 115 keys = key.split(self.keySeparator) | |
| 116 if self.keyFn is not None: | |
| 117 keys = [self.keyFn(k) for k in keys] | |
| 43 | 118 |
| 39 | 119 elif isinstance(key, list): |
| 120 # its a list - keep | |
| 121 keys = key | |
| 43 | 122 |
| 39 | 123 else: |
| 124 # not a list - wrap in list | |
| 125 keys = [key] | |
| 126 | |
| 127 return keys | |
| 128 | |
| 129 | |
| 27 | 130 def getNode(self, key): |
| 52 | 131 """Return node under key from the tree. |
| 132 | |
| 27 | 133 key can be sequence of key string or a single string using keySeparator. |
| 30 | 134 If key is None, returns root node. |
| 27 | 135 """ |
| 30 | 136 if key is None: |
| 137 return self.root | |
| 138 | |
| 39 | 139 keys = self._splitkey(key) |
| 27 | 140 |
| 141 node = self.root | |
| 142 for k in keys: | |
| 143 node = node.getNode(k) | |
| 144 if node is None: | |
| 145 return None | |
| 146 | |
| 147 return node | |
| 148 | |
| 149 | |
| 150 def get(self, key): | |
| 52 | 151 """Return value under key from the tree. |
| 152 | |
| 27 | 153 key can be sequence of key string or a single string using keySeparator. |
| 154 """ | |
| 155 node = self.getNode(key) | |
| 156 if node is None: | |
| 157 return None | |
| 158 | |
| 159 return node.value | |
| 160 | |
| 161 | |
| 162 def add(self, key, value): | |
| 52 | 163 """Add value under key to the tree. |
| 164 | |
| 27 | 165 key can be sequence of key string or a single string using keySeparator. |
| 166 """ | |
| 39 | 167 keys = self._splitkey(key) |
| 27 | 168 node = self.root |
| 169 for k in keys: | |
| 170 nextnode = node.getNode(k) | |
| 171 if nextnode is None: | |
| 172 nextnode = HashTreeNode(key=k) | |
| 173 node.addNode(nextnode) | |
| 174 | |
| 175 node = nextnode | |
| 176 | |
| 177 node.value = value | |
| 39 | 178 |
| 27 | 179 |
| 39 | 180 def getChildrenOf(self, key): |
| 52 | 181 """Return the list of child (values) of the node under key.""" |
| 39 | 182 node = self.getNode(key) |
| 97 | 183 if getattr(node, 'children', None) is None: |
| 39 | 184 return [] |
| 185 else: | |
| 43 | 186 # sort children by key |
| 187 childlist = sorted(node.children.items(), key=lambda x:x[0]) | |
| 188 # and return the values | |
| 97 | 189 return [n.value for k, n in childlist if n.value is not None] |
| 39 | 190 |
| 191 | |
| 192 def getAncestorsOf(self, key): | |
| 52 | 193 """Return the list of ancestor (values) of the node under key. |
| 194 | |
| 195 Order: root element first.""" | |
| 39 | 196 keys = self._splitkey(key) |
| 197 node = self.root | |
| 198 ancestors = [] | |
| 199 for k in keys: | |
| 200 if node.value is not None: | |
| 201 ancestors.append(node.value) | |
| 202 | |
| 203 node = node.getNode(k) | |
| 204 if node is None: | |
| 205 return ancestors | |
| 206 | |
| 207 return ancestors | |
| 208 | |
| 27 | 209 |