Whole file
caesar0301/treelib
The author described this change as “fixed the wrong encoding/decoding problem between python 2 and 3 by using the codecs library”. It counts as a record because the check below fails on the code as it stood at 22cf20607 and passes on a0dbcf468, with nothing else changed between the two runs.
Projectcaesar0301/treelib
Fix saved2015-07-15
Sharing licenceApache-2.0 · LICENSE
Change size+689 −690
What the code was meant to do, written into the code itself as a save note
fixed the wrong encoding/decoding problem between python 2 and 3 by using the codecs library
The change
| 8 | 8 | from __future__ import unicode_literals | |
| 9 | 9 | import sys | |
| 10 | 10 | import json | |
| 11 | - | from copy import deepcopy | |
| 12 | - | try: | |
| 13 | - | from .node import Node | |
| 14 | - | except ImportError: | |
| 15 | - | from node import Node | |
| 16 | - | try: | |
| 17 | - | from StringIO import StringIO as BytesIO | |
| 18 | - | except ImportError: | |
| 19 | - | from io import BytesIO | |
| 20 | - | ||
| 21 | - | ||
| 22 | - | ||
| 23 | - | __author__ = 'chenxm' | |
| 24 | - | ||
| 25 | - | ||
| 26 | - | class NodeIDAbsentError(Exception): | |
| 27 | - | """Exception throwed if a node's identifier is unknown""" | |
| 28 | - | pass | |
| 29 | - | ||
| 30 | - | ||
| 31 | - | class MultipleRootError(Exception): | |
| 32 | - | """Exception throwed if more than one root exists in a tree.""" | |
| 33 | - | pass | |
| 34 | - | ||
| 35 | - | ||
| 36 | - | class DuplicatedNodeIdError(Exception): | |
| 37 | - | """Exception throwed if an identifier already exists in a tree.""" | |
| 38 | - | pass | |
| 39 | - | ||
| 40 | - | ||
| 41 | - | class LinkPastRootNodeError(Exception): | |
| 42 | - | """ | |
| 43 | - | Exception throwed in Tree.link_past_node() if one attempts | |
| 44 | - | to "link past" the root node of a tree. | |
| 45 | - | """ | |
| 46 | - | pass | |
| 47 | - | ||
| 48 | - | ||
| 49 | - | class InvalidLevelNumber(Exception): | |
| 50 | - | pass | |
| 51 | - | ||
| 52 | - | def python_2_unicode_compatible(klass): | |
| 53 | - | """ | |
| 54 | - | (slightly modified from : | |
| 55 | - | http://django.readthedocs.org/en/latest/_modules/django/utils/encoding.html) | |
| 56 | - | ||
| 57 | - | A decorator that defines __unicode__ and __str__ methods under Python 2. | |
| 58 | - | Under Python 3 it does nothing. | |
| 59 | - | ||
| 60 | - | To support Python 2 and 3 with a single code base, define a __str__ method | |
| 61 | - | returning text and apply this decorator to the class. | |
| 62 | - | """ | |
| 63 | - | if sys.version_info[0] == 2: | |
| 64 | - | if '__str__' not in klass.__dict__: | |
| 65 | - | raise ValueError("@python_2_unicode_compatible cannot be applied " | |
| 66 | - | "to %s because it doesn't define __str__()." % | |
| 67 | - | klass.__name__) | |
| 68 | - | klass.__unicode__ = klass.__str__ | |
| 69 | - | klass.__str__ = lambda self: self.__unicode__().encode('utf-8') | |
| 70 | - | return klass | |
| 71 | - | ||
| 72 | - | @python_2_unicode_compatible | |
| 73 | - | class Tree(object): | |
| 74 | - | """Tree objects are made of Node(s) stored in _nodes dictionary.""" | |
| 75 | - | ||
| 76 | - | #: ROOT, DEPTH, WIDTH, ZIGZAG constants : | |
| 77 | - | (ROOT, DEPTH, WIDTH, ZIGZAG) = list(range(4)) | |
| 78 | - | ||
| 79 | - | def __contains__(self, identifier): | |
| 80 | - | """Return a list of the nodes'identifiers matching the | |
| 81 | - | identifier argument. | |
| 82 | - | """ | |
| 83 | - | return [node for node in self._nodes | |
| 84 | - | if node == identifier] | |
| 85 | - | ||
| 86 | - | def __init__(self, tree=None, deep=False): | |
| 87 | - | """Initiate a new tree or copy another tree with a shallow or | |
| 88 | - | deep copy. | |
| 89 | - | """ | |
| 90 | - | ||
| 91 | - | #: dictionary, identifier: Node object | |
| 92 | - | self._nodes = {} | |
| 93 | - | ||
| 94 | - | #: identifier of the root node | |
| 95 | - | self.root = None | |
| 96 | - | ||
| 97 | - | if tree is not None: | |
| 98 | - | self.root = tree.root | |
| 99 | - | ||
| 100 | - | if deep: | |
| 101 | - | for nid in tree._nodes: | |
| 102 | - | self._nodes[nid] = deepcopy(tree._nodes[nid]) | |
| 103 | - | else: | |
| 104 | - | self._nodes = tree._nodes | |
| 105 | - | ||
| 106 | - | def __getitem__(self, key): | |
| 107 | - | """Return _nodes[key]""" | |
| 108 | - | try: | |
| 109 | - | return self._nodes[key] | |
| 110 | - | except KeyError: | |
| 111 | - | raise NodeIDAbsentError("Node '%s' is not in the tree" % key) | |
| 112 | - | ||
| 113 | - | def __len__(self): | |
| 114 | - | """Return len(_nodes)""" | |
| 115 | - | return len(self._nodes) | |
| 116 | - | ||
| 117 | - | def __setitem__(self, key, item): | |
| 118 | - | """Set _nodes[key]""" | |
| 119 | - | self._nodes.update({key: item}) | |
| 120 | - | ||
| 121 | - | def __str__(self): | |
| 122 | - | self.reader = "" | |
| 123 | - | ||
| 124 | - | def write(line): | |
| 125 | - | self.reader += line.decode('utf-8') + "\n" | |
| 126 | - | ||
| 127 | - | self.__print_backend(func=write) | |
| 128 | - | return self.reader | |
| 129 | - | ||
| 130 | - | def __print_backend(self, nid=None, level=ROOT, idhidden=True, filter=None, | |
| 131 | - | key=None, reverse=False, line_type='ascii-ex', | |
| 132 | - | func=print, iflast=[]): | |
| 133 | - | """ | |
| 134 | - | Another implementation of printing tree using Stack | |
| 135 | - | Print tree structure in hierarchy style. | |
| 136 | - | ||
| 137 | - | For example: | |
| 138 | - | Root | |
| 139 | - | |___ C01 | |
| 140 | - | | |___ C11 | |
| 141 | - | | |___ C111 | |
| 142 | - | | |___ C112 | |
| 143 | - | |___ C02 | |
| 144 | - | |___ C03 | |
| 145 | - | | |___ C31 | |
| 146 | - | ||
| 147 | - | A more elegant way to achieve this function using Stack | |
| 148 | - | structure, for constructing the Nodes Stack push and pop nodes | |
| 149 | - | with additional level info. | |
| 150 | - | ||
| 151 | - | UPDATE: the @key @reverse is present to sort node at each | |
| 152 | - | level. | |
| 153 | - | """ | |
| 154 | - | line_types = \ | |
| 155 | - | {'ascii': ('|', '|-- ', '+-- '), | |
| 156 | - | 'ascii-ex': ('\u2502', '\u251c\u2500\u2500 ', '\u2514\u2500\u2500 '), | |
| 157 | - | 'ascii-exr': ('\u2502', '\u251c\u2500\u2500 ', '\u2570\u2500\u2500 '), | |
| 158 | - | 'ascii-em': ('\u2551', '\u2560\u2550\u2550 ', '\u255a\u2550\u2550 '), | |
| 159 | - | 'ascii-emv': ('\u2551', '\u255f\u2500\u2500 ', '\u2559\u2500\u2500 '), | |
| 160 | - | 'ascii-emh': ('\u2502', '\u255e\u2550\u2550 ', '\u2558\u2550\u2550 ')} | |
| 161 | - | DT_VLINE, DT_LINE_BOX, DT_LINE_COR = line_types[line_type] | |
| 162 | - | ||
| 163 | - | leading = '' | |
| 164 | - | lasting = DT_LINE_BOX | |
| 165 | - | ||
| 166 | - | nid = self.root if (nid is None) else nid | |
| 167 | - | if not self.contains(nid): | |
| 168 | - | raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) | |
| 169 | - | ||
| 170 | - | label = ('{0}'.format(self[nid].tag))\ | |
| 171 | - | if idhidden \ | |
| 172 | - | else ('{0}[{1}]'.format( | |
| 173 | - | self[nid].tag, | |
| 174 | - | self[nid].identifier)) | |
| 175 | - | ||
| 176 | - | filter = (self.__real_true) if (filter is None) else filter | |
| 177 | - | ||
| 178 | - | if level == self.ROOT: | |
| 179 | - | func(label.encode('utf8')) | |
| 180 | - | else: | |
| 181 | - | leading = ''.join(map(lambda x: DT_VLINE + ' ' * 3 | |
| 182 | - | if not x else ' ' * 4, iflast[0:-1])) | |
| 183 | - | lasting = DT_LINE_COR if iflast[-1] else DT_LINE_BOX | |
| 184 | - | func('{0}{1}{2}'.format(leading, lasting, label).encode('utf-8')) | |
| 185 | - | ||
| 186 | - | if filter(self[nid]) and self[nid].expanded: | |
| 187 | - | queue = [self[i] for i in self[nid].fpointer if filter(self[i])] | |
| 188 | - | key = (lambda x: x) if (key is None) else key | |
| 189 | - | queue.sort(key=key, reverse=reverse) | |
| 190 | - | level += 1 | |
| 191 | - | for element in queue: | |
| 192 | - | iflast.append(queue.index(element) == len(queue)-1) | |
| 193 | - | self.__print_backend(element.identifier, level, idhidden, | |
| 194 | - | filter, key, reverse, line_type, func, iflast) | |
| 195 | - | iflast.pop() | |
| 196 | - | ||
| 197 | - | def __update_bpointer(self, nid, parent_id): | |
| 198 | - | """set self[nid].bpointer""" | |
| 199 | - | self[nid].update_bpointer(parent_id) | |
| 200 | - | ||
| 201 | - | def __update_fpointer(self, nid, child_id, mode): | |
| 202 | - | if nid is None: | |
| 203 | - | return | |
| 204 | - | else: | |
| 205 | - | self[nid].update_fpointer(child_id, mode) | |
| 206 | - | ||
| 207 | - | def __real_true(self, p): | |
| 208 | - | return True | |
| 209 | - | ||
| 210 | - | def to_dict(self, nid=None, key=None, sort=True, reverse=False, with_data=False): | |
| 211 | - | """transform self into a dict""" | |
| 212 | - | ||
| 213 | - | nid = self.root if (nid is None) else nid | |
| 214 | - | ntag = self[nid].tag | |
| 215 | - | tree_dict = {ntag: {"children": []}} | |
| 216 | - | if with_data: | |
| 217 | - | tree_dict[ntag]["data"] = self[nid].data | |
| 218 | - | ||
| 219 | - | if self[nid].expanded: | |
| 220 | - | queue = [self[i] for i in self[nid].fpointer] | |
| 221 | - | key = (lambda x: x) if (key is None) else key | |
| 222 | - | if sort: | |
| 223 | - | queue.sort(key=key, reverse=reverse) | |
| 224 | - | ||
| 225 | - | for elem in queue: | |
| 226 | - | tree_dict[ntag]["children"].append( | |
| 227 | - | self.to_dict(elem.identifier, with_data=with_data, sort=sort, reverse=reverse)) | |
| 228 | - | if len(tree_dict[ntag]["children"]) == 0: | |
| 229 | - | tree_dict = self[nid].tag if not with_data else \ | |
| 230 | - | {ntag: {"data":self[nid].data}} | |
| 231 | - | return tree_dict | |
| 232 | - | ||
| 233 | - | def add_node(self, node, parent=None): | |
| 234 | - | """ | |
| 235 | - | Add a new node to tree. | |
| 236 | - | The 'node' parameter refers to an instance of Class::Node | |
| 237 | - | """ | |
| 238 | - | if not isinstance(node, Node): | |
| 239 | - | raise OSError("First parameter must be object of Class::Node.") | |
| 240 | - | ||
| 241 | - | if node.identifier in self._nodes: | |
| 242 | - | raise DuplicatedNodeIdError("Can't create node " | |
| 243 | - | "with ID '%s'" % node.identifier) | |
| 244 | - | ||
| 245 | - | if parent is None: | |
| 246 | - | if self.root is not None: | |
| 247 | - | raise MultipleRootError("A tree takes one root merely.") | |
| 248 | - | else: | |
| 249 | - | self.root = node.identifier | |
| 250 | - | elif not self.contains(parent): | |
| 251 | - | raise NodeIDAbsentError("Parent node '%s' " | |
| 252 | - | "is not in the tree" % parent) | |
| 253 | - | ||
| 254 | - | self._nodes.update({node.identifier: node}) | |
| 255 | - | self.__update_fpointer(parent, node.identifier, Node.ADD) | |
| 256 | - | self.__update_bpointer(node.identifier, parent) | |
| 257 | - | ||
| 258 | - | def all_nodes(self): | |
| 259 | - | """Return all nodes in a list""" | |
| 260 | - | return list(self._nodes.values()) | |
| 261 | - | ||
| 262 | - | def children(self, nid): | |
| 263 | - | """ | |
| 264 | - | Return the children (Node) list of nid. | |
| 265 | - | Empty list is returned if nid does not exist | |
| 266 | - | """ | |
| 267 | - | return [self[i] for i in self.is_branch(nid)] | |
| 268 | - | ||
| 269 | - | def contains(self, nid): | |
| 270 | - | """Check if the tree contains node of given id""" | |
| 271 | - | return True if nid in self._nodes else False | |
| 272 | - | ||
| 273 | - | def create_node(self, tag=None, identifier=None, parent=None, data=None): | |
| 274 | - | """Create a child node for given @parent node.""" | |
| 275 | - | node = Node(tag=tag, identifier=identifier, data=data) | |
| 276 | - | self.add_node(node, parent) | |
| 277 | - | return node | |
| 278 | - | ||
| 279 | - | def depth(self, node=None): | |
| 280 | - | """ | |
| 281 | - | Get the maximum level of this tree or the level of the given node | |
| 282 | - | ||
| 283 | - | @param node Node instance or identifier | |
| 284 | - | @return int | |
| 285 | - | @throw NodeIDAbsentError | |
| 286 | - | """ | |
| 287 | - | ret = 0 | |
| 288 | - | if node is None: | |
| 289 | - | # Get maximum level of this tree | |
| 290 | - | leaves = self.leaves() | |
| 291 | - | for leave in leaves: | |
| 292 | - | level = self.level(leave.identifier) | |
| 293 | - | ret = level if level >= ret else ret | |
| 294 | - | else: | |
| 295 | - | # Get level of the given node | |
| 296 | - | if not isinstance(node, Node): | |
| 297 | - | nid = node | |
| 298 | - | else: | |
| 299 | - | nid = node.identifier | |
| 300 | - | if not self.contains(nid): | |
| 301 | - | raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) | |
| 302 | - | ret = self.level(nid) | |
| 303 | - | return ret | |
| 304 | - | ||
| 305 | - | def expand_tree(self, nid=None, mode=DEPTH, filter=None, key=None, | |
| 306 | - | reverse=False): | |
| 307 | - | """ | |
| 308 | - | Python generator. Loosly based on an algorithm from | |
| 309 | - | 'Essential LISP' by John R. Anderson, Albert T. Corbett, and | |
| 310 | - | Brian J. Reiser, page 239-241 | |
| 311 | - | ||
| 312 | - | UPDATE: the @filter function is performed on Node object during | |
| 313 | - | traversing. | |
| 314 | - | ||
| 315 | - | UPDATE: the @key and @reverse are present to sort nodes at each | |
| 316 | - | level. | |
| 317 | - | """ | |
| 318 | - | nid = self.root if (nid is None) else nid | |
| 319 | - | if not self.contains(nid): | |
| 320 | - | raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) | |
| 321 | - | ||
| 322 | - | filter = self.__real_true if (filter is None) else filter | |
| 323 | - | if filter(self[nid]): | |
| 324 | - | yield nid | |
| 325 | - | queue = [self[i] for i in self[nid].fpointer if filter(self[i])] | |
| 326 | - | if mode in [self.DEPTH, self.WIDTH]: | |
| 327 | - | queue.sort(key=key, reverse=reverse) | |
| 328 | - | while queue: | |
| 329 | - | yield queue[0].identifier | |
| 330 | - | expansion = [self[i] for i in queue[0].fpointer | |
| 331 | - | if filter(self[i])] | |
| 332 | - | expansion.sort(key=key, reverse=reverse) | |
| 333 | - | if mode is self.DEPTH: | |
| 334 | - | queue = expansion + queue[1:] # depth-first | |
| 335 | - | elif mode is self.WIDTH: | |
| 336 | - | queue = queue[1:] + expansion # width-first | |
| 337 | - | ||
| 338 | - | elif mode is self.ZIGZAG: | |
| 339 | - | # Suggested by Ilya Kuprik (ilya-spy@ynadex.ru). | |
| 340 | - | stack_fw = [] | |
| 341 | - | queue.reverse() | |
| 342 | - | stack = stack_bw = queue | |
| 343 | - | direction = False | |
| 344 | - | while stack: | |
| 345 | - | expansion = [self[i] for i in stack[0].fpointer | |
| 346 | - | if filter(self[i])] | |
| 347 | - | yield stack.pop(0).identifier | |
| 348 | - | if direction: | |
| 349 | - | expansion.reverse() | |
| 350 | - | stack_bw = expansion + stack_bw | |
| 351 | - | else: | |
| 352 | - | stack_fw = expansion + stack_fw | |
| 353 | - | if not stack: | |
| 354 | - | direction = not direction | |
| 355 | - | stack = stack_fw if direction else stack_bw | |
| 356 | - | ||
| 357 | - | def get_node(self, nid): | |
| 358 | - | """Return the node with nid. None returned if nid not exists.""" | |
| 359 | - | if nid is None or not self.contains(nid): | |
| 360 | - | return None | |
| 361 | - | return self._nodes[nid] | |
| 362 | - | ||
| 363 | - | def is_branch(self, nid): | |
| 364 | - | """ | |
| 365 | - | Return the children (ID) list of nid. | |
| 366 | - | Empty list is returned if nid does not exist | |
| 367 | - | """ | |
| 368 | - | if nid is None: | |
| 369 | - | raise OSError("First parameter can't be None") | |
| 370 | - | if not self.contains(nid): | |
| 371 | - | raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) | |
| 372 | - | ||
| 373 | - | try: | |
| 374 | - | fpointer = self[nid].fpointer | |
| 375 | - | except KeyError: | |
| 376 | - | fpointer = [] | |
| 377 | - | return fpointer | |
| 378 | - | ||
| 379 | - | def leaves(self, root=None): | |
| 380 | - | """Get leaves of the whole tree of a subtree.""" | |
| 381 | - | leaves = [] | |
| 382 | - | if root is None: | |
| 383 | - | for node in self._nodes.values(): | |
| 384 | - | if node.is_leaf(): | |
| 385 | - | leaves.append(node) | |
| 386 | - | else: | |
| 387 | - | for node in self.expand_tree(root): | |
| 388 | - | if self[node].is_leaf(): | |
| 389 | - | leaves.append(node) | |
| 390 | - | return leaves | |
| 391 | - | ||
| 392 | - | def level(self, nid, filter=None): | |
| 393 | - | """ | |
| 394 | - | Get the node level in this tree. | |
| 395 | - | The level is an integer starting with '0' at the root. | |
| 396 | - | In other words, the root lives at level '0'; | |
| 397 | - | ||
| 398 | - | Update: @filter params is added to calculate level passing | |
| 399 | - | exclusive nodes. | |
| 400 | - | """ | |
| 401 | - | return len([n for n in self.rsearch(nid, filter)])-1 | |
| 402 | - | ||
| 403 | - | def link_past_node(self, nid): | |
| 404 | - | """ | |
| 405 | - | Delete a node by linking past it. | |
| 406 | - | ||
| 407 | - | For example, if we have a -> b -> c and delete node b, we are left | |
| 985 further changed lines not shown | |||
The check that tells the two apart
fail→pass·tests/test_treelib.py::TreeCase::test_to_dot
Check file tests/test_treelib.py, taken without changes from the fix and copied onto the older code, so the exact same check runs against both versions.
Origin and history
The code before it22cf20607610fcb480c26dac9bdc189eef6e72c8
Broken version dated2015-07-14
Moduletreelib.tree
Units changedTree
Fingerprintcb50add519e2a94c
Checked2026-08-18 by goldset/0.1
Every field above is generated by our program. None of it is written by hand.
Other bugs found in caesar0301/treelib
- 2020-01-13fix root removal in remove_subtree
- 2019-12-18fix removal of root node
- 2014-05-09Fix subtree() cannot cooperate with rsearch()