[−][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