Skip to content
Snippets Groups Projects
  • Vasileios Karakasis's avatar
    Low-level algorithms for manipulating cell trees. · 526953b5
    Vasileios Karakasis authored
    At this low level a cell tree is just a sequence of parent indices,
    where each parent index is the parent of the current index in the
    sequence. There four basic algorithms:
    
    1. child_count(parent_index):
       Computes the number of children for each node in parent_index
       	Time: O(N), Space: O(1)
    2. branches(parent_index):
       Returns a set of the branching nodes in parent_index, last branch
       index equals the parent_index's size.
    	 Time: O(N), Space: O(N)
    3. expand_branches(branch_index):
       Takes a branch_index (result from branches()) and expands it at the
       size of the original tree with all the nodes inside a branch having
       the same number.
             Time: O(parent_index), Space: O(1)
    4. make_parent_index(parent_index, branch_index):
       Return a compacted tree (single node per branch) from parent_index
       and its corresponding branch_index.
    	Time: O(N), Space: O(N)
    
    There is another utility function as well:
    
    find_branch(branch_index, nid):
        Returns the id of the branch where nid belongs to.
    	Time: O(N), Space: O(1)
    526953b5