1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//! LOUDS (level order unary degree sequence) Tree implementation for Rust
//!
//! This crate provides a succinct data structure for ordered trees
//! that supports constant-time tree traversal operations.
//!
//! In LOUDS, a tree structure containing n nodes is repsresented as
//! a bit sequence of length 2n + 1.
//! We compress the sequence by using [fid](https://crates.io/crates/fid).
//!
//! It also includes [Trie](https://en.wikipedia.org/wiki/Trie) implementation with LOUDS.
//!
//! # Examples
//!
//! This example creates the following ordered tree.
//! Nodes are identified by breadth-first numbering.
//! ```text
//! 0
//! / \
//! 1 2
//! / | \ / \
//! 3 4 5 6 7
//! / \ | |
//! 8 9 10 11
//! ```
//!
//! ```rust
//! extern crate louds;
//! use louds::Louds;
//!
//! // Degrees (# of children) of each node
//! let degrees = &[ 2, 3, 2, 0, 2, 1, 1, 0, 0, 0, 0, 0 ];
//! let mut louds = Louds::new();
//! for &d in degrees {
//! louds.push_node(d);
//! }
//!
//! // Tree traversal operations (move to parent/children/sibling)
//! // are supported in constant-time.
//! assert_eq!(louds.first_child(1), Some(3));
//! assert_eq!(louds.first_child(3), None);
//! assert_eq!(louds.last_child(2), Some(7));
//! assert_eq!(louds.last_child(7), None);
//! assert_eq!(louds.child(1, 1), Some(4));
//! assert_eq!(louds.parent(4), Some(1));
//! assert_eq!(louds.sibling(4), Some(5));
//! assert_eq!(louds.degree(4), 2);
//!
//! // Computing depth of a node takes time proportional to
//! // the height of the tree.
//! assert_eq!(louds.depth(4), 2);
//! ```
extern crate fid;
pub use Louds;