PK!J×ü¸!¸!treestruct/__init__.pyfrom collections import MutableSet from . import helpers FORWARD = 1 # used to look at Node children BACKWARD = -1 # used to look at Node parents class NodeSet(MutableSet): """ A mutable set which automatically populates parent/child node sets. For example, if this NodeSet contains `children` nodes and a new node was added, that node's `parent` NodeSet will automatically be populated with the owner of this NodeSet. """ __slots__ = ('owner', 'items', 'direction') def __init__(self, owner, items, direction): """ :type owner: Node :type items: set[Node] :type direction: int """ self.owner = owner self.items = set() self.direction = direction self.update(items) def __iter__(self): return iter(self.items) def __len__(self): return len(self.items) def add(self, value): """ Adds the node to this NodeSet and populates the node's NodeSet with the owner of this NodeSet. :type value: Node """ if value not in self: value.direction(self.direction * -1).items.add(self.owner) return self.items.add(value) def discard(self, value): """ Removes the node from this NodeSet and removes this NodeSet's owner from the node's NodeSets. :type value: Node """ if value in self: value.direction(self.direction * -1).items.discard(self.owner) return self.items.discard(value) def update(self, nodes): for node in nodes: self.add(node) def discard_many(self, nodes): for node in nodes: self.discard(node) def one(self, raise_on_empty=False): """ Returns an item from this NodeSet if there is only one item. :type raise_on_empty: bool :rtype: Node | None :raises: ValueError """ if not self.items and raise_on_empty: raise ValueError('Called NodeSet.one on empty set') elif len(self.items) > 1: raise ValueError('Called NodeSet.one on set with multiple values') return next(iter(self.items), None) def __contains__(self, x): return self.items.__contains__(x) def __repr__(self): return 'NodeSet{}'.format(tuple(self.items)) class Node(object): __slots__ = ('parents', 'children', 'data') def __init__(self, data=None, parents=None, children=None): self.parents = NodeSet(self, [] if parents is None else parents, BACKWARD) self.children = NodeSet(self, [] if children is None else children, FORWARD) self.data = data def __repr__(self): return '<{} {}>'.format(type(self).__name__, self.data) @property def connections(self): """ Returns all parents and children associated with this Node. :rtype: set[Node] """ return set(list(self.parents) + list(self.children)) def direction(self, direction): """ Returns this node's parents if direction is BACKWARD, else, returns children nodes. :int direction: int :rtype: NodeSet """ return self.parents if direction == BACKWARD else self.children def depth_first_traversal(self, callback, direction, obj=None): """ Executes a depth-first traversal from this node in a given direction. Raising a StopIteration will terminate the traversal. :type callback: (Node, object) -> () :type direction: int :type obj: Any :return: Returns `obj` (or None if no `obj` is supplied). :rtype: Any """ return helpers.depth_first_traversal_for_node(node=self, callback=callback, direction=direction, obj=obj) def breadth_first_traversal(self, callback, direction, obj=None): """ Executes a breadth-first traversal from this node in a given direction. Raising a StopIteration will terminate the traversal. :type callback: (Node, object) -> () :type direction: int :type obj: Any :return: Returns `obj` (or None if no `obj` is supplied). :rtype: Any """ return helpers.breadth_first_traversal_for_node(node=self, callback=callback, direction=direction, obj=obj) def walk_links(self, callback, direction, obj=None): """ Walks the each link for this node. Raising a StopIteration will terminate the traversal. :type callback: (Node, Node, object) -> () :type direction: int :type obj: Any :return: Returns `obj` (or None if no `obj` is supplied). :rtype: Any """ return helpers.walk_links_for_node(node=self, callback=callback, direction=direction, obj=obj) def root(self): """ Returns the root node of this node if it only has one root node. :rtype: Node :raises: ValueError """ roots = self.roots() if len(roots) > 1: raise ValueError('Node.root is not applicable when the node has multiple roots') return next(iter(roots)) def gather_nodes(self, direction=None): """ Returns all nodes in the tree. Nodes can be restricted by specifying a direction. :type direction: int :rtype: set[Node] """ return helpers.gather_nodes(node=self, direction=direction) def flatten(self, direction=None): """ Returns a list of node lists representing a path on the tree. :type direction: int | None :rtype: list[list[treestruct.Node]] """ return helpers.flatten_from_node(node=self, direction=direction) def roots(self): """ Returns all roots (any parent nodes with no parents) of this node. :rtype: set[Node] """ return helpers.roots_for_node(node=self) def leaves(self): """ Returns all leaves (any child nodes with no children) of this node. :rtype: set[Node] """ return helpers.leaves_for_node(node=self) def delete(self, direction=None): """ Removes this node from the NodeSets of connected nodes. If direction is given, only remove the node from the connected nodes in the given direction. :type direction: int :rtype: Node """ return helpers.delete_node_relationships(node=self, direction=direction) def clone(self): """ Clones the node and all its child nodes and forms a new root. :rtype: Node """ return helpers.clone_subtree(node=self, cls=type(self)) def find_all(self, condition, direction=None): """ Returns all nodes which match the given condition. :type condition: (Node) -> bool :type direction: int :rtype: set[Node] """ return helpers.find_nodes(node=self, condition=condition, direction=direction) def find(self, condition, direction=None, raise_on_empty=False): """ Returns a single node which matches the given condition. :type condition: (Node) -> bool :type direction: int :type raise_on_empty: bool :rtype: Node | None :raises: ValueError """ return helpers.find_node(node=self, condition=condition, direction=direction, raise_on_empty=raise_on_empty) def to_dict(self, data_converter=None): """ Converts this node's complete structure into a dictionary. :type data_converter: (Any) -> (Any) | None :rtype: list[dict] """ return helpers.to_dict_from_node(node=self, data_converter=data_converter) @classmethod def from_dict(cls, tree_dict, data_converter=None): """ Converts a dict into a tree of Nodes, with the return value being the root node. :param tree_dict: dict :type data_converter: (Any) -> (Any) | None :rtype: Node """ return helpers.from_dict(tree_dict=tree_dict, data_converter=data_converter, cls=cls) @classmethod def from_nodes(cls, nodes): """ Creates a flat tree structure from a list of nodes. It is assumed that the first Node in the list is the root and each subsequent Node is a child. Any existing parents or children will be disregarded. :type nodes: collections.Sequence[Node] :rtype: Node """ return helpers.node_from_node_sequence(nodes=nodes, cls=cls) PK!4K3ÜÜtreestruct/helpers.pyimport treestruct def leaves_for_node(node): """ Returns all roots (any child nodes with no children) for the given node. :type node: treestruct.Node :rtype: set[treestruct.Node] """ return _absolutes(node, treestruct.FORWARD) def roots_for_node(node): """ Returns all roots (any parent nodes with no parents) for the given node. :type node: treestruct.Node :rtype: set[treestruct.Node] """ return _absolutes(node, treestruct.BACKWARD) def walk_links_for_node(node, callback, direction, obj=None): """ Walks the each link from the given node. Raising a StopIteration will terminate the traversal. :type node: treestruct.Node :type callback: (treestruct.Node, treestruct.Node, object) -> () :type direction: int :type obj: Any :return: Returns `obj` (or None if no `obj` is supplied). :rtype: Any """ try: visited = set() queue = [node] while queue: node = queue.pop(0) if node in visited: continue visited.add(node) for connected_node in node.direction(direction): callback(node, connected_node, obj) queue.append(connected_node) except StopIteration: pass return obj def depth_first_traversal_for_node(node, callback, direction, obj=None): """ Executes a depth-first traversal from this node in a given direction. Raising a StopIteration will terminate the traversal. :type node: treestruct.Node :type callback: (treestruct.Node, treestruct.Node, object) -> () :type direction: int :type obj: Any :return: Returns `obj` (or None if no `obj` is supplied). :rtype: Any """ return _traverse(node, -1, callback, direction, obj) def breadth_first_traversal_for_node(node, callback, direction, obj=None): """ Executes a breadth-first traversal from this node in a given direction. Raising a StopIteration will terminate the traversal. :type node: treestruct.Node :type callback: (treestruct.Node, treestruct.Node, object) -> () :type direction: int :type obj: Any :return: Returns `obj` (or None if no `obj` is supplied). :rtype: Any """ return _traverse(node, 0, callback, direction, obj) def _absolutes(node, direction): nodes = set() node.depth_first_traversal(lambda n, l: l.add(n) if not n.direction(direction) else None, direction, nodes) return nodes def _traverse(node, pop_idx, callback, direction, obj=None): try: visited = set() struct = [node] while struct: node = struct.pop(pop_idx) if node in visited: continue visited.add(node) struct += list(node.direction(direction)) callback(node, obj) except StopIteration: pass return obj def find_nodes(node, condition, direction=None): """ Returns all nodes which match the given condition. :type node: treestruct.Node :type condition: (treestruct.Node) -> bool :type direction: int :rtype: set[treestruct.Node] :raises: ValueError """ return {n for n in gather_nodes(node, direction) if condition(n)} def find_node(node, condition, direction, raise_on_empty): """ Returns a single node which matches the given condition. :type node: treestruct.Node :type condition: (treestruct.Node) -> bool :type direction: int :type raise_on_empty: bool :rtype: treestruct.Node | None :raises: ValueError """ matches = find_nodes(node, condition, direction) if not matches and raise_on_empty: raise ValueError('Called NodeSet.one on empty set') elif len(matches) > 1: raise ValueError('Called NodeSet.one on set with multiple values') return next(iter(matches), None) def gather_nodes(node, direction=None): """ Returns all nodes in the tree. Nodes can be restricted by specifying a direction. :type direction: int :rtype: set[treestruct.Node] """ start_points = node.roots() if direction is None else [node] nodes = set() for start_point in start_points: start_point.depth_first_traversal(lambda n, o: o.add(n), direction or treestruct.FORWARD, nodes) return nodes def flatten_from_node(node, direction=None): """ Returns a list of node lists representing a path on the tree. :type node: treestruct.Node :type direction: int | None :rtype: list[list[treestruct.Node]] """ start_points = node.leaves() if direction is None else [node] flattened_lists = [] for start_point in start_points: flattened_list = start_point.depth_first_traversal(lambda n, l: l.append(n), direction or treestruct.BACKWARD, []) if any(n for n in flattened_list if len(n.parents) > 1): raise Exception('Flattening nodes with multiple parents is not supported at the moment') if direction != treestruct.FORWARD: flattened_list = flattened_list[::-1] flattened_lists.append(flattened_list) return flattened_lists def to_dict_from_node(node, data_converter=None): """ Converts the node structure into a dictionary. :type node: treestruct.Node :type data_converter: (Any) -> (Any) | None :rtype: list[dict] """ data_converter = (lambda n: n) if data_converter is None else data_converter roots = node.roots() or [node] def _convert(n, converter): return { 'data': converter(n.data), 'children': [_convert(c, converter) for c in n.children] } return [_convert(root, data_converter) for root in roots] def from_dict(tree_dict, data_converter=None, cls=None): """ Converts a dict into a tree of Nodes, with the return value being the root node. :param tree_dict: dict :type data_converter: (Any) -> (Any) | None :rtype: treestruct.Node """ cls = treestruct.Node if cls is None else cls data_converter = (lambda n: n) if data_converter is None else data_converter def _build_tree(struct, converter): node = cls(converter(struct['data'])) for child_struct in struct.get('children'): node.children.add(_build_tree(child_struct, converter)) return node return _build_tree(tree_dict, data_converter) def delete_node_relationships(node, direction=None): """ Removes the given node from the NodeSets of connected nodes. If direction is given, only remove the node from the connected nodes in the given direction. :type node: treestruct.Node :type direction: int :rtype: treestruct.Node """ if direction in (None, treestruct.BACKWARD): for parent in tuple(node.parents): parent.children.discard(node) if direction in (None, treestruct.FORWARD): for child in tuple(node.children): node.children.discard(child) return node def clone_subtree(node, cls=None): """ Clones the node and all its child nodes and forms a new root. :type node: Node :rtype: Node """ cls = treestruct.Node if cls is None else cls return cls(node.data, children=[clone_subtree(node=child, cls=cls) for child in node.children]) def node_from_node_sequence(nodes, cls=None): """ Creates a flat tree structure from a list of nodes. It is assumed that the first Node in the list is the root and each subsequent Node is a child. Any existing parents or children will be disregarded. :type nodes: collections.Sequence[treestruct.Node] :rtype: treestruct.Node """ if not nodes: return None cls = treestruct.Node if cls is None else cls child = node_from_node_sequence(nodes[1:], cls=cls) return cls(data=nodes[0].data, children=[child] if child else []) PK!!v;íéétreestruct/visualize.pyimport treestruct import graphviz def _build_walk_formatter(fmt): def formatter(a, b, graph): af = fmt(a.data) bf = fmt(b.data) graph.node(af) graph.node(bf) graph.edge(af, bf) return formatter class Graph(object): def __init__(self, node, **options): self.node = treestruct.helpers.clone_subtree(node) self.graph = graphviz.Digraph(**options) self.__did_draw = False def defaults(self, **attributes): for key, value in attributes.iteritems(): if isinstance(value, dict): self.graph.attr(key, **value) else: self.graph.attr(**{key: value}) def draw_links(self, node_formatter=None): self.draw_links_with_formatter(_build_walk_formatter(node_formatter or str)) def draw_links_with_formatter(self, formatter): self.__did_draw = True self.node.walk_links(callback=formatter, direction=treestruct.FORWARD, obj=self.graph) def draw_via_traversal(self, formatter): self.__did_draw = True self.node.depth_first_traversal(callback=formatter, direction=treestruct.FORWARD, obj=self.graph) def save(self, **options): return self._output_func(self.graph.save, **options) def render(self, **options): return self._output_func(self.graph.render, **options) def view(self, **options): return self._output_func(self.graph.view, **options) def _output_func(self, func, **options): if not self.__did_draw: self.draw_links() return func(**options) def simple_graph(node, options=None, node_formatter=None): graph = Graph(node) graph.defaults(**options or {}) graph.draw_links(node_formatter) return graph def view_graph(node, options=None, node_formatter=None): return simple_graph(node, options, node_formatter).view() def view_inline(node, options=None, node_formatter=None): return simple_graph(node, options, node_formatter).graph PK!ŠC‡Z--"treestruct-0.1.4.dist-info/LICENSEMIT License Copyright (c) 2017 Shady Rafehi Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. PK!H|n-æWY treestruct-0.1.4.dist-info/WHEEL ÊA € н§ð#Z;/í"¢ÖŸ bFF]xûzëwÜÀK;´<ÂÑç͆¦*mTíÖ»0¸Ì*Ri.´4ÅûœÑVm0[ºþÙ—ûH, JÜÍPK!H8+÷Ÿ<º#treestruct-0.1.4.dist-info/METADATA•RËnÂ0¼û+¶· -RTPQ{(* ú8¯'Y5NR?Â××Ҫǜ<ÞÙñÌjý* ¦h0øJS]Eò1‹QŠŒBeÃ~Ùó)Û[)QµìI6%e-˜B€Aýu‰h¨Ê‡îá#>8ƒqÂL:0åöX¢Ö”‘p.© Š`³_Á²iT}©¿»œýO²Uu®PJ?÷«Üº1}ÿ9‘Gaß~>멘ôíç·½w½³¿õ<‘68ESè׋¹ûynEÃ{wNùè†ýPK!Hð"½ÝX!treestruct-0.1.4.dist-info/RECORD}ÌIv‚0Ð}Ïlƒ°è"@P,êÓMµ‚ˆÁÓwÕÖ•ÿ_tŒõ¢âRÞpAéäò}™!Mÿ`\‚t¶1ï¨íÏ´h/ĹJaÄ]žùË‚ÂsuË\º‚ÞÄW²úºþi‹E=§=ÝúF!'½"çÝü´^ÖÑ`M©¢²Yä_gž™€© áóvåýÕ|dOŸ