[−][src]Crate louds_rs
High performance LOUDS (Level-Order Unary Degree Sequence) library.
Master API Docs | Released API Docs | Benchmark Results | Changelog
Quickstart
To use louds-rs, add the following to your Cargo.toml
file:
[dependencies]
louds-rs = "0.1" # NOTE: Replace to latest minor version.
Usage Overview
Say we want to hold the following tree structure in minimum length of bits.
(1)
|
|---+---+
| | |
(2) (3) (4)
| |
| |---+-----+
| | | |
(5) (6) (7) (8)
| |
| |----+
| | |
(9) (10) (11)
This tree has NodeNum (node number of 1-origin, assigned from left node to right & top to bottom) and edges. With LOUDS, this tree is represented as the following LBS (LOUDS Bit String).
NodeNum | 0 (virtual root) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
LBS | 1 0 | 1 1 1 0 | 1 0 | 0 | 1 1 1 0 | 0 | 0 | 1 0 | 1 1 0 | 0 | 0 | 0 |
Child NodeNum | 1 - | 2 3 4 - | 5 - | - | 6 7 8 - | - | - | 9 - | 10 11 - | - | - | - |
Index | 0 1 | 2 3 4 5 | 6 7 | 8 | 9 10 11 12| 13| 14| 15 16| 17 18 19| 20| 21 | 22 |
The same tree is represented as follows using index.
<0>
|
|---+---+
| | |
<2> <3> <4>
| |
| |---+-----+
| | | |
<6> <9> <10> <11>
| |
| |----+
| | |
<15> <17> <18>
Then, create this tree structure with Louds
and call operations to it.
use louds_rs::{Louds, LoudsIndex, LoudsNodeNum}; // Construct from LBS. let s = "10_1110_10_0_1110_0_0_10_110_0_0_0"; let louds = Louds::from(s); // LoudsNodeNum <-> LoudsIndex let node8 = LoudsNodeNum(8); let index11 = louds.node_num_to_index(node8); assert_eq!(louds.index_to_node_num(index11), node8); // Search for children. assert_eq!(louds.parent_to_children(node8), vec!(LoudsIndex(17), LoudsIndex(18))); // Search for parent. assert_eq!(louds.child_to_parent(index11), LoudsNodeNum(4));
Constructors
use louds_rs::Louds; // Most human-friendly way: Louds::from::<&str>() let louds1 = Louds::from("10_1110_10_0_1110_0_0_10_110_0_0_0"); // Simple way: Louds::from::<&[bool]>() let mut arr = vec![ true, false, true, true, true, false, true, false, false, true, true, true, false, false, false, true, false, true, true, false, false, false, false, ]; let louds2 = Louds::from(&arr[..]);
Features
- Arbitrary length support with minimum working memory: louds-rs provides virtually arbitrary size of LOUDS. It is carefully designed to use as small memory space as possible.
- Based on fid-rs, which is fast, parallelized, and memory efficient. It provides fast construction (
Louds::from()
). - Latest benchmark results are always accessible: louds-rs is continuously benchmarked in Travis CI using Criterion.rs. Graphical benchmark results are published here.
Complexity
When the number of nodes in the tree represented as LOUDS is N:
Operation | Time-complexity | Space-complexity |
---|---|---|
Louds::from::<&str>() | O(N) | N + o(N) |
Louds::from::<&[bool]>() | O(N) | N + o(N) |
node_num_to_index() | O() | N + o(N) |
index_to_node_num() | O(1) | O(1) |
child_to_parent() | O(1) | O(1) |
parent_to_children() | O( max(log N, max num of children a node has) ) | O( max(log N, max num of children a node has) ) |
(node_num_to_index()
and child_to_parent()
use Fid::select(). index_to_node_num()
and parent_to_children()
use rank()).
Re-exports
pub use louds::Louds; |
pub use louds::LoudsIndex; |
pub use louds::LoudsNodeNum; |
Modules
louds |