module FlatTree

Extended Modules

Defined in:

flat_tree.cr
iterator.cr

Instance Method Summary

Instance Method Detail

def children(i : UInt64, d : UInt64 | Nil = self.depth(i)) : Array(UInt64) | Nil #

Returns an array [left_child, right_child] with the indexes of this elements children. If this element does not have any children it returns null


[View source]
def count(i : UInt64, d : UInt64 | Nil = self.depth(i)) #

Returns how many nodes (including parent nodes) a tree contains


[View source]
def depth(i : UInt64 | Nil) : UInt64 #

Returns the depth of an element


[View source]
def full_roots(i : UInt64, nodes : Array(UInt64) = [] of UInt64) #

Returns a list of all the full roots (subtrees where all nodes have either 2 or 0 children) < index. For example full_roots(8) returns [3] since the subtree rooted at 3 spans 0 -> 6 and the tree rooted at 7 has a child located at 9 which is >= 8.


[View source]
def index(d : UInt64, o : UInt64) : UInt64 #

Returns an array index for the tree element at the given depth and offset


[View source]
def iterator(i : UInt64 = 0_u64) #

Create a stateful tree iterator starting at a given index. The iterator exposes the following methods.


[View source]
def left_child(i : UInt64 | Nil, d : UInt64 | Nil = self.depth(i)) : UInt64 | Nil #

Returns only the left child of a node.


[View source]
def left_span(i : UInt64, d : UInt64 | Nil = self.depth(i)) #

Returns the left spanning in index in the tree index spans.


[View source]
def offset(i : UInt64, d : UInt64 | Nil = self.depth(i)) : UInt64 #

Returns the relative offset of an element


[View source]
def parent(i : UInt64, d : UInt64 | Nil = self.depth(i)) : UInt64 #

Returns the index of the parent element in tree


[View source]
def right_child(i : UInt64 | Nil, d : UInt64 | Nil = self.depth(i)) : UInt64 | Nil #

Returns only the right child of a node.


[View source]
def right_span(i : UInt64, d : UInt64 | Nil = self.depth(i)) #

Returns the right spanning in index in the tree index spans.


[View source]
def sibling(i : UInt64, d : UInt64 | Nil = self.depth(i)) #

Returns the index of this elements sibling


[View source]
def spans(i : UInt64, d : UInt64 | Nil = self.depth(i)) #

Returns the range (inclusive) the tree root at index spans. For example FlatTree.spans(3) would return [0, 6] (see the usage example).


[View source]