lighttree.tree module

class lighttree.tree.Tree

Bases: typing.Generic

Principles: - each node is identified by an id - a tree cannot contain multiple nodes with same id - there are 2 types of nodes:

• “map” nodes under which children nodes are referenced by a key (keyed=True)
• “list” nodes under which children nodes are referenced by order (keyed=False)

• node referencing in tree is done by defining under which node it should be placed and under which key/order

For performance reasons, child id <-> parent id is store both ways: - parent id -> children ids - children id -> parent id

ancestors(nid: str, from_root: bool = False, include_current: bool = False) → List[Tuple[Union[str, int, None], GenericNode]]

From element to root. :param nid: :param from_root: :param include_current: :return:

ancestors_ids(nid: str, from_root: bool = False, include_current: bool = False) → List[str]

child(nid: str, key: Union[str, int]) → Tuple[Union[str, int, None], GenericNode]

child_id(nid: str, key: Union[str, int]) → str

children(nid: str) → List[Tuple[Union[str, int, None], GenericNode]]

Return set of given node children node ids.

children_ids(nid: str) → List[str]

clone(with_nodes: bool = True, deep: bool = False, new_root: Optional[str] = None) → GenTree

Clone current instance, with or without nodes.

depth(nid: str) → int

Return node depth, 0 means root.

drop_node(nid: str, with_children: bool = True) → Tuple[Union[str, int, None], GenericNode]

If with_children is False, children of this node will take as new parent the dropped node parent. Possible only if node type is same as parent node type.

Return key, node.

drop_subtree(nid: str) → Tuple[Union[str, int, None], GenTree]

expand_tree(nid: Optional[str] = None, mode: str = 'depth', filter_: Optional[Callable[[Union[None, str, int], GenericNode], bool]] = None, filter_through: bool = False, reverse: bool = False) → Iterator[Tuple[Union[str, int, None], GenericNode]]

Python generator traversing the tree (or a subtree) with optional node filtering.

Inspired by treelib implementation https://github.com/caesar0301/treelib/blob/master/treelib/tree.py#L374

Parameters:

• nid – Node identifier from which tree traversal will start. If None tree root will be used
• mode – Traversal mode, may be either “depth” or “width”
• filter – filter function performed on nodes. Node excluded from filter function won’t be yielded.
• filter_through – if True, excluded nodes don’t exclude their children.
• reverse – the reverse param for sorting Node objects in the same level

Returns:

node ids that satisfy the conditions if id_only is True, else nodes.

get(nid: str) → Tuple[Union[str, int, None], GenericNode]

get_key(nid: str) → Union[str, int, None]

Get a node’s key. :param nid: str, identifier of node

If root: -> return None If parent node is a map: return key If parent node is a list: return index

get_node_id_by_path(path: Iterable[Union[str, int]], strict: bool = True) → str

get_path(nid: str) → Iterable[Union[str, int]]

insert(item: Union[GenericNode, GenTree], parent_id: Optional[str] = None, child_id: Optional[str] = None, child_id_below: Optional[str] = None, key: Union[str, int, None] = None) → GenTree

insert_node(node: GenericNode, parent_id: Optional[str] = None, child_id: Optional[str] = None, key: Union[str, int, None] = None) → Union[str, int, None]

insert_tree(new_tree: GenTree, parent_id: Optional[str] = None, child_id: Optional[str] = None, child_id_below: Optional[str] = None, key: Union[str, int, None] = None) → Union[str, int, None]

is_empty() → bool

Return whether tree is empty (contains nodes) or not. :rtype: bool

is_leaf(nid: str) → bool

Return is node is a leaf in this tree.

leaves(nid: Optional[str] = None) → List[Tuple[Union[str, int, None], GenericNode]]

Return leaves under a node subtree.

leaves_ids(nid: Optional[str] = None) → List[str]

list(id_in: Optional[Sequence[str]] = None, depth_in: Optional[Sequence[int]] = None, filter_: Optional[Callable[[GenericNode], bool]] = None) → List[Tuple[Union[str, int, None], GenericNode]]

List nodes. :param id_in: list of str, optional, filter nodes among provided identifiers :param depth_in: list of int, optional, filter nodes whose depth in tree is among provided values :param filter_: function, optional, filtering function to apply to each node

merge(new_tree: GenTree, nid: Optional[str] = None) → GenTree

Merge “new_tree” on current tree by pasting its root children on current tree “nid” node.

Consider the following trees:

>>> self.show()
root
├── A
└── B
>>> new_tree.show()
root2
├── C
└── D
    └── D1

Merging new_tree on B node:

>>> self.merge(new_tree, 'B')
>>> self.show()
root
├── A
└── B
    ├── C
    └── D
        └── D1

Note: if current tree is empty and nid is None, the new_tree root will be used as root on current tree. In all other cases new_tree root is not pasted.

parent(nid: str) → Tuple[Union[str, int, None], GenericNode]

Return parent node. Return None if given node id is root.

parent_id(nid: str) → str

show(nid: Optional[str] = None, filter_: Optional[Callable[[GenericNode], bool]] = None, display_key: bool = True, reverse: bool = False, line_type: str = 'ascii-ex', limit: Optional[int] = None, line_max_length: int = 60, key_delimiter: str = ': ', **kwargs) → str

Return tree structure in hierarchy style.

Parameters:

• nid – Node identifier from which tree traversal will start. If None tree root will be used
• filter_ – filter function performed on nodes. Nodes excluded from filter function nor their children won’t be displayed
• reverse – the reverse param for sorting Node objects in the same level
• display_key – boolean, if True display keyed nodes keys
• reverse – reverse parameter applied at sorting
• line_type – display type choice
• limit – int, truncate tree display to this number of lines
• kwargs – kwargs params passed to node line_repr method

:param line_max_length

siblings(nid: str) → List[Tuple[Union[str, int, None], GenericNode]]

Return set of ids of nodes that share the provided node’s parent.

siblings_ids(nid: str) → List[str]

subtree(nid: str, deep: bool = False) → Tuple[Union[str, int, None], GenTree]