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