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; mod louds; pub mod trie; pub use louds::Louds;