A series of functions to map a binary tree to a list ported from flat-tree.
With clibs for a local install do
$ clib install arablocks/flat-tree.c --save
or from source:
$ git clone git@github.com:arablocks/flat-tree.c.git $ cd flat-tree.c $ make $ make install ## you may need sudo
or even with ghi:
$ ghi arablocks/flat-tree.c
which simply invokes make install
Build the static library by running:
#include <flat-tree/flat-tree.h>
ft_ulong ft_two_pow(ft_ulong n);
TODO
ft_ulong ft_right_shift(ft_ulong n);
TODO
ft_ulong ft_index(ft_ulong depth, ft_ulong offset);
Returns an array index for the tree element at the given depth and offset
ft_ulong ft_parent(ft_ulong index, ft_ulong depth);
Returns the index of the parent element in tree
ft_ulong ft_sibling(ft_ulong index, ft_ulong depth);
Returns the index of this elements sibling
ft_long ft_left_child(ft_ulong index, ft_ulong depth);
TODO
ft_long ft_right_child(ft_ulong index, ft_ulong depth);
TODO
bool ft_children(ft_ulong children[2], ft_ulong index, ft_ulong depth);
Returns true if the array children[leftChild, rightChild] was set with the indices of this element's children. Otherwise it returns false;
void ft_spans(ft_ulong range[2], ft_ulong index, ft_ulong depth);
Returns the range (inclusive) the tree root at index spans. For example, tree.spans(3) would return [0, 6]
ft_ulong ft_left_span(ft_ulong index, ft_ulong depth);
Returns the left spanning in index in the tree index spans
ft_ulong ft_right_span(ft_ulong index, ft_ulong depth);
Returns the right spanning in index in the tree index spans.
ft_ulong ft_count(ft_ulong index, ft_ulong depth);
Returns how many nodes (including parent nodes) a tree contains
ft_ulong ft_depth(ft_ulong index);
Returns the depth of an element
ft_ulong ft_offset(ft_ulong index, ft_ulong depth);
Returns the relative offset of an element
ft_long ft_full_roots(ft_ulong** roots, ft_ulong index);
Returns the number of rull roots. Sets roots[] with all the full roots (subtrees where all nodes have either 2 or 0 children) < index. For example, fullRoots(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
ft_iterator_t* ft_iterator_new(ft_ulong index);
Create a stateful tree iterator starting at a given index.
ft_ulong ft_iterator_next(ft_iterator_t* iterator);
Move the iterator to the next item in the tree. This will increment the iterator offset and increment the index by the iterator factor.
ft_ulong ft_iterator_prev(ft_iterator_t* iterator);
Move the iterator to the previous item in the tree. This will decrement the iterator offset and decrement the index by the iterator factor.
void ft_iterator_seek(ft_iterator_t* iterator, ft_ulong index);
Move the iterator the this specific tree index.
ft_ulong ft_iterator_parent(ft_iterator_t* iterator);
Move the iterator to the current parent index
ft_long ft_iterator_left_child(ft_iterator_t* iterator);
Move the iterator to the current left child index.
ft_long ft_iterator_right_child(ft_iterator_t* iterator);
Move the iterator to the current right child index.
ft_ulong ft_iterator_left_span(ft_iterator_t* iterator);
Move the iterator to the current left span index.
ft_ulong ft_iterator_right_span(ft_iterator_t* iterator);
Move the iterator to the current right span index
bool ft_iterator_is_left(ft_iterator_t* iterator);
Is the iterator at a left sibling?
bool ft_iterator_is_right(ft_iterator_t* iterator);
Is the iterator at a right sibling?
ft_ulong ft_iterator_sibling(ft_iterator_t* iterator);
Move the iterator to the current sibling
MIT
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4