Skip to content

High performance LOUDS (Level-Order Unary Degree Sequence) library

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT
Notifications You must be signed in to change notification settings

laysakura/louds-rs

Repository files navigation

louds-rs

High performance LOUDS (Level-Order Unary Degree Sequence) library.

Master API Docs | Released API Docs | Benchmark Results | Changelog

GitHub Actions Status Travis Status Crates.io Version Crates.io Downloads Minimum rustc version License: MIT License: Apache 2.0

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) )
parent_to_children_indices() O(1) O( 1 )
parent_to_children_indices().next() O(log N) at first then O(1) O( 0 )
parent_to_children_indices().next_back() O(log N) at first then O(1) O( 0 )

(node_num_to_index() and child_to_parent() use Fid::select(). index_to_node_num() and parent_to_children() use rank()). parent_to_children_nodes() has the same time complexity as parent_to_children_indices().

Versions

louds-rs uses semantic versioning.

Since current major version is 0, minor version update might involve breaking public API change (although it is carefully avoided).

Rust Version Supports

louds-rs is continuously tested with these Rust versions in Travis CI:

  • 1.33.0
  • Latest stable version

So it expectedly works with Rust 1.33.0 and any newer versions.

Older versions may also work, but are not tested or guaranteed.

Contributing

Any kind of pull requests are appreciated.

Guidelines

  • README.md is generated from $ cargo readme command. Do not manually update README.md but edit src/lib.rs and then $ cargo readme > README.md.
  • Travis CI automatically does the following commit & push to your pull-requests:
    • $ cargo readme > README.md
    • $ cargo fmt --all

License

MIT OR Apache-2.0

About

High performance LOUDS (Level-Order Unary Degree Sequence) library

Topics

Resources

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT

Stars

Watchers

Forks

Packages

No packages published

Contributors 4

  •  
  •  
  •  
  •