snail/tree.py

# 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[0]
        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()