louds-rs

高性能LOUDS（层序单值度序列）库。

主API文档 | 发布API文档 | 基准测试结果 | 变更日志

快速入门

要使用louds-rs，请将以下内容添加到您的 Cargo.toml 文件中

[dependencies]
louds-rs = "0.1"  # NOTE: Replace to latest minor version.

使用概述

假设我们想以最小位长度存储以下树结构。

(1)
 |
 |---+---+
 |   |   |
(2) (3) (4)
 |       |
 |       |---+-----+
 |       |   |     |
(5)     (6) (7)   (8)
             |     |
             |     |----+
             |     |    |
            (9)   (10) (11)

此树具有NodeNum（节点编号，从1开始，从左到右和从上到下分配）和边。使用LOUDS，此树表示为以下LBS（LOUDS位字符串）。

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 |

使用索引表示相同的树。

<0>
 |
 |---+---+
 |   |   |
<2> <3> <4>
 |       |
 |       |---+-----+
 |       |   |     |
<6>     <9> <10>  <11>
             |     |
             |     |----+
             |     |    |
            <15>  <17> <18>

然后，使用Louds创建此树结构并对其调用操作。

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));

构造函数

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[..]);

特性

• 支持任意长度且工作内存最小：louds-rs提供几乎任意大小的LOUDS。它被精心设计以使用尽可能小的内存空间。
• 基于fid-rs，它快速、并行且内存高效。它提供快速构建（Louds::from()）。
• 最新基准测试结果始终可访问：louds-rs在Travis CI上使用Criterion.rs持续基准测试。图形基准测试结果发布在此。

复杂度

当表示为LOUDS的树的节点数为N

(node_num_to_index() 和 child_to_parent() 使用 Fid::select(). index_to_node_num() 和 parent_to_children() 使用 rank()). parent_to_children_nodes() 的时间复杂度与 parent_to_children_indices() 相同。

版本

louds-rs 使用 语义版本控制.

由于当前主版本为 0，次要版本更新可能涉及破坏公共 API 的更改（尽管会尽量避免）。

Rust 版本支持

louds-rs 在 Travis CI 中持续使用这些 Rust 版本进行测试

• 1.33.0
• 最新稳定版本

因此，它预期与 Rust 1.33.0 及任何更高版本兼容。

旧版本也可能工作，但未经测试或保证。

贡献

任何类型的拉取请求都受到欢迎。

指南

• README.md 是由 $ cargo readme 命令生成的。不要手动更新 README.md，而是编辑 src/lib.rs，然后执行 $ cargo readme > README.md。
• Travis CI 会自动执行以下提交 & 推送到您的 pull-requests
  • $ cargo readme > README.md
  • $cargo fmt --all

许可证

MIT OR Apache-2.0