Implementation

Implementation design decisions

                                       | perlA         | Java        | utreex      | Treex

-------------------------------------------|---------------|-------------|-------------|-----------| object | array | compiled | slots | hash children | linkedL | array | sorted-array| bi-linkedL all-nodes | sorted-array | no | sorted-array| no descendants | via-children | via-children| via-children| via-children root | stored | stored | computed | computed

object

Data structure of the Node objects.

• array: Perl array-based objects (bless [@fields], $class)
• slots: Python __slots__, similar to Perl array-based objects
• hash, dict: Perl/Python hash-table-based objects, any attributes possible
• compiled: Java standard

children

How is the sequence of children of a given node represented?

• array: ArrayList in Java, list in Python, not sorted by ord
• sorted-array: kept sorted by ord
• linkedL: linked list, each node has pointers (or references) first_child and next_sibling
• bi-linkedL: doubly-linked list, each node has in addition to linkedL pointers last_child and prev_sibling. This allows faster removal of a node from its parent (no need to iterate over the whole list of children), but needs slightly more memory.

all-nodes

Iterating though all nodes of a given tree is a very frequent task, which can be optimized.

• sorted-array: root keeps an array of all nodes sorted by ord
• sorted-linkedL: each node (including root) has a next_node pointer
• no: all-descendants are not precomputed, but obtained via children and sorted (unless unsorted asked)

descendants

How is method descendants() implemented if called on a non-root node?

• via-children: depth-in traversal via children, sorted (unless unsorted asked)
• via-all-nodes (not implemented yet): Each node has pointers (or ord numbers) first_desc and last_desc, so if its subtree is projective, it can directly return its descendants from the all-nodes array. If it is non-projective (i.e. if last_desc.ord - first_desc.ord >= number of nodes in the subtree), we can either store a list of "exception-ancestors" in each node or back off to via-children (but reuse any projective subtree with via-all-nodes).

root

• stored: each node has a direct pointer to the root node (or, in Java, to the Tree object which stores the root)
• computed: following the parent pointers