#### 196 lines 5.4 KiB Python Raw Permalink Blame History

 ```# encoding: utf-8 ``` ```""" ``` ```https://dom.spec.whatwg.org/ ``` ``` ``` ```Other URL: ``` ```- https://fr.wikipedia.org/wiki/Document_Object_Model ``` ```""" ``` ``` ``` ``` ``` ```class Node: ``` ``` """ ``` ``` An object that participates in a tree has a parent, which is either null or an ``` ``` object, and has children, which is an ordered set of objects. An object A whose ``` ``` parent is object B is a child of B. ``` ``` """ ``` ``` def __init__(self, parent=None): ``` ``` self.parent = parent ``` ``` self.children = [] ``` ``` self.order = 0 ``` ``` ``` ``` def add_child(self, child): ``` ``` """ ``` ``` Adding a child to Node after lasts known child. ``` ``` """ ``` ``` # Compute new order for modified tree ``` ``` if len(self.children) == 0: ``` ``` order = self.order + 1 ``` ``` else: ``` ``` for node in self.nodes: ``` ``` order = node.order + 1 ``` ``` # Add child to node ``` ``` self.children.append(child) ``` ``` child.parent = self ``` ``` # Reorder tree ``` ``` self.root.reorder(order) ``` ``` child.order = order ``` ``` ``` ``` @property ``` ``` def root(self): ``` ``` """ ``` ``` The root of an object is itself, if its parent is null, or else it is the root ``` ``` of its parent. The root of a tree is any object participating in that tree whose ``` ``` parent is null. ``` ``` """ ``` ``` if self.parent is None: ``` ``` return self ``` ``` else: ``` ``` return self.parent.root ``` ``` ``` ``` @property ``` ``` def first_child(self): ``` ``` """ ``` ``` The first child of an object is its first child or null if it has no children. ``` ``` """ ``` ``` try: ``` ``` return self.children ``` ``` except IndexError: ``` ``` return None ``` ``` ``` ``` @property ``` ``` def last_child(self): ``` ``` """ ``` ``` The last child of an object is its last child or null if it has no children. ``` ``` """ ``` ``` try: ``` ``` return self.children[-1] ``` ``` except IndexError: ``` ``` return None ``` ``` ``` ``` @property ``` ``` def index(self): ``` ``` """ ``` ``` The index of an object is its number of preceding siblings, or 0 if it has none. ``` ``` """ ``` ``` try: ``` ``` return self.parent.children.index(self) ``` ``` except AttributeError: ``` ``` return None ``` ``` ``` ``` @property ``` ``` def previous_sibling(self): ``` ``` """ ``` ``` The previous sibling of an object is its first preceding sibling or null if it ``` ``` has no preceding sibling. ``` ``` """ ``` ``` if self.index == 0: ``` ``` return None ``` ``` return self.parent.children[self.index - 1] ``` ``` ``` ``` @property ``` ``` def next_sibling(self): ``` ``` """ ``` ``` The next sibling of an object is its first following sibling or null if it has ``` ``` no following sibling. ``` ``` """ ``` ``` if self.parent.last_child == self: ``` ``` return None ``` ``` return self.parent.children[self.index + 1] ``` ``` ``` ``` @property ``` ``` def nodes(self): ``` ``` """ ``` ``` List Node and all of its nodes through depth-first traversal ``` ``` See: https://en.wikipedia.org/wiki/Depth-first_search ``` ``` """ ``` ``` yield self ``` ``` for child in self.children: ``` ``` yield from child.nodes ``` ``` ``` ``` def reorder(self, value): ``` ``` """ ``` ``` Increment all nodes with order equal or greater than value ``` ``` """ ``` ``` for node in self.root.nodes: ``` ``` if node.order >= value: ``` ``` node.order += 1 ``` ``` ``` ``` def is_descendant(self, node): ``` ``` """ ``` ``` An object A is called a descendant of an object B, if either A is a child of B ``` ``` or A is a child of an object C that is a descendant of B. ``` ``` """ ``` ``` if ( ``` ``` self.parent == node ``` ``` or self.parent is not None and self.parent.is_descendant(node) ``` ``` ): ``` ``` return True ``` ``` return False ``` ``` ``` ``` def is_inclusive_descendant(self, node): ``` ``` """ ``` ``` An inclusive descendant is an object or one of its descendants. ``` ``` """ ``` ``` if node is self: ``` ``` return True ``` ``` return self.is_descendant(node) ``` ``` ``` ``` def is_ancestor(self, node): ``` ``` """ ``` ``` An object A is called an ancestor of an object B if and only if B is a ``` ``` descendant of A. ``` ``` """ ``` ``` return node.is_descendant(self) ``` ``` ``` ``` def is_inclusive_ancestor(self, node): ``` ``` """ ``` ``` An inclusive ancestor is an object or one of its ancestors. ``` ``` """ ``` ``` if node is self: ``` ``` return True ``` ``` return self.is_ancestor(node) ``` ``` ``` ``` def is_sibling(self, node): ``` ``` """ ``` ``` An object A is called a sibling of an object B, if and only if B and A share the ``` ``` same non-null parent. ``` ``` """ ``` ``` if self.parent is not None and self.parent == node.parent: ``` ``` return True ``` ``` return False ``` ``` ``` ``` def is_inclusive_sibling(self, node): ``` ``` """ ``` ``` An inclusive sibling is an object or one of its siblings. ``` ``` """ ``` ``` if node is self: ``` ``` return True ``` ``` return self.is_sibling(node) ``` ``` ``` ``` def is_preceding(self, node): ``` ``` """ ``` ``` An object A is preceding an object B if A and B are in the same tree and A comes ``` ``` before B in tree order. ``` ``` """ ``` ``` if self.root == node.root: ``` ``` return True ``` ``` return False ``` ``` ``` ``` def is_following(self, node): ``` ``` """ ``` ``` An object A is following an object B if A and B are in the same tree and A comes ``` ``` after B in tree order. ``` ``` """ ``` ``` if self.root == node.root: ``` ``` return True ``` ``` return False ``` ``` ``` ``` ``` ```class Tree: ``` ``` """ ``` ``` A tree is a finite hierarchical tree structure. In tree order is preorder, ``` ``` depth-first traversal of a tree. ``` ``` """ ``` ``` def __init__(self): ``` ``` self.root = Node() ```