pub struct Louds { /* private fields */ }
Expand description
LOUDS (Level-Order Unary Degree Sequence).
This class can handle tree structure of virtually arbitrary number of nodes.
In fact, N (number of nodes in the tree) is designed to be limited to: N < 2^64 / 2, while each node is represented in 2bits in average.
It should be enough for almost all usecases since a binary data of length of 2^63 consumes 2^20 = 1,048,576 TB (terabytes), which is hard to handle by state-of-the-art computer architecture.
Implementations§
source§impl Louds
impl Louds
sourcepub fn node_num_to_index(&self, node_num: LoudsNodeNum) -> LoudsIndex
pub fn node_num_to_index(&self, node_num: LoudsNodeNum) -> LoudsIndex
§Panics
node_num
does not exist in this LOUDS.
sourcepub fn index_to_node_num(&self, index: LoudsIndex) -> LoudsNodeNum
pub fn index_to_node_num(&self, index: LoudsIndex) -> LoudsNodeNum
§Panics
index
does not point to any node in this LOUDS.
sourcepub fn child_to_parent(&self, index: LoudsIndex) -> LoudsNodeNum
pub fn child_to_parent(&self, index: LoudsIndex) -> LoudsNodeNum
§Panics
index
does not point to any node in this LOUDS.index == 0
: (node#1 is root and doesn’t have parent)
sourcepub fn parent_to_children(&self, node_num: LoudsNodeNum) -> Vec<LoudsIndex>
pub fn parent_to_children(&self, node_num: LoudsNodeNum) -> Vec<LoudsIndex>
§Panics
node_num
does not exist in this LOUDS.
sourcepub fn parent_to_children_indices(
&self,
node_num: LoudsNodeNum
) -> ChildIndexIter<'_> ⓘ
pub fn parent_to_children_indices( &self, node_num: LoudsNodeNum ) -> ChildIndexIter<'_> ⓘ
§Panics
node_num
does not exist in this LOUDS.
sourcepub fn parent_to_children_nodes(
&self,
node_num: LoudsNodeNum
) -> ChildNodeIter<'_> ⓘ
pub fn parent_to_children_nodes( &self, node_num: LoudsNodeNum ) -> ChildNodeIter<'_> ⓘ
§Panics
node_num
does not exist in this LOUDS.
Trait Implementations§
source§impl From<&str> for Louds
impl From<&str> for Louds
source§fn from(s: &str) -> Self
fn from(s: &str) -> Self
Prepares for building Louds from LBS (LOUDS Bit vector).
It takes O(log s
) time for validation.
§Panics
If s
does not represent a LOUDS tree. s
must satisfy the following condition as LBS.
- Starts from “10”
- In the range of [0, i] for any i (< length of LBS);
- the number of ‘0’ <= the number of ‘1’ + 1, because:
- Each node, including virtual root (node num = 0), has one ‘0’.
- Each node is derived from one ‘1’.
- the number of ‘0’ <= the number of ‘1’ + 1, because:
- In the range of [0, length of LBS);
- the number of ‘0’ == the number of ‘1’ + 1