Struct treeid::Node

pub struct Node { /* fields omitted */ }

A position in the tree.

Nodes are encoded to binary in a modified form of LCF1 (mLCF).

Deviations from the LCF encoding as described by Matula et al:

• only suitable for rationals p/q where one (out of 2) of the continued fraction forms has both of the following properties:

  • composed of an odd number of natural terms
  • terms at odd indices are always 1

• leading high bit / low bit is elided because (p >= q >= 1) and we don't need to differentiate from (1 <= p <= q).

This method of encoding sequences allows for a near infinite space of hierarchical nodes with a stable lexicographic sort order. This can be useful for encoding categories/buckets within a lexicographically sorted collection.

The encoded sort order mimics that of floating point digits (in base 2^64) extending to the right of a fixed number. &[1, 2, 3] and &[3, 2] sort relative to eachother just as 0.123 and 0.32 do. The sort order when encoded in binary form is thus equivalent to the sort order of the input sequence itself.

use treeid::Node;

let node = Node::from(&[2, 4]);
let child = Node::from(&[2, 4, 1]);
let sibling = Node::from(&[2, 5]);
assert!(sibling.to_binary().gt(&child.to_binary()));
assert!(child.to_binary().gt(&node.to_binary()));
assert_eq!(node, Node::from_binary(&*node.to_binary()).unwrap());

The key usability difference of treeid style nodes versus using a fixed prefix to encode categories is that treeid nodes can be split arbitrarily, without carefully mapping out a keyspace in advance. The downside is that nodes in treeid form will tend to take up more space than prefixes in a manually partitioned keyspace.

There is no limit to the length of a treeid sequence, other than practical concerns w.r.t. space consumption. The total size of an encoded treeid node can be found by taking the sum of 1 + the doubles of minimum binary sizes of each term - 1, and adding the number of terms - 1. The result rounded up to the next multiple of 64 will be the total bitsize.

For example, to find the size of the sequence &[7, 4, 2], we perform:

• minimum size: [3 (111), 3 (100), 2 (10)]
• subtract one: [2, 2, 1]
• double : [4, 4, 2]
• add one : [5, 5, 3]
• summate : 13
• add terms-1 : 15
• round to 64 : 64

Which corresponds to the encoded form of:

0b110111110001100 0...

use treeid::Node;

let node = Node::from(&[7, 4, 2]);
assert_eq!(
    // 7    |sep|4    |sep|2  |padding
    // 11011|1  |11000|1  |100|0...

    &[0b11011111, 0b0001100_0, 0, 0, 0, 0, 0, 0],
    &*node.to_binary(),
);

Methods

impl Node

pub fn root() -> Self

Returns the root node.

use treeid::*;
assert_eq!(Node::from(&[]), Node::root());

pub fn from_vec(loc: Vec<u64>) -> Self

Constructs a node from its tree position as a series of natural numbers.

Panics if the input contains any zeros.

pub fn parent(&self) -> Self

Get the parent of this node. Sorts before this node and any of its siblings/children.

The parent of the root is the root.

pub fn parent_mut(&mut self)

pub fn child(&self, id: u64) -> Self

Get the specified child of this node. Sorts after this node, but before any higher siblings.

Panics if id is zero.

pub fn child_mut(&mut self, id: u64)

pub fn sibling(&self, id: u64) -> Option<Self>

Get the specified sibling of this node. Sort order is dependent on the value of id, relative to the current node's last term.

Panics if id is zero, and returns None for the root.

pub fn sibling_mut(&mut self, id: u64)

pub fn pred(&self) -> Option<Self>

Get the last sibling of this node. Sorts before this node.

Returns None if this is a first child or the root.

pub fn succ(&self) -> Option<Self>

Get the next sibling of this node. Sorts after this node.

Returns None if this is the root.

pub fn is_root(&self) -> bool

Returns true if this is the root.

pub fn from_binary(mlcf_encoded: &[u8]) -> Option<Self>

Decode an id from its mLCF encoded form. The input must have a length that is an even multiple of 8 to allow unpacking into an &mut [u64] directly.

pub fn to_binary(&self) -> Vec<u8>

Writes this id into a Vec<[u8]> using mLCF encoding. The output will be padded with trailing zero bytes such that its length is a multiple of 8 - from_binary() can then pack it directly into an &mut [u64] and decode up to 8 bytes per iter instead of up to 1.

use treeid::*;
assert_eq!(&[0, 0, 0, 0, 0, 0, 0, 0], &*Node::from(&[1]).to_binary());
assert_eq!(&[0b10000000, 0, 0, 0, 0, 0, 0, 0], &*Node::from(&[2]).to_binary());
assert_eq!(&[0b10011000, 0, 0, 0, 0, 0, 0, 0], &*Node::from(&[2, 2]).to_binary());
assert_eq!(
    &[0b11000110, 0b11100111, 0b00100000, 0, 0, 0, 0, 0],
    &*Node::from(&[4, 3, 2, 5]).to_binary(),
);

Trait Implementations

impl<A: AsRef<[u64]>> From<A> for Node

fn from(loc: A) -> Self

Performs the conversion.

impl Default for Node

fn default() -> Self

Returns the "default value" for a type.

impl PartialEq<Node> for Node

fn eq(&self, other: &Node) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Node) -> bool

This method tests for !=.

impl Clone for Node

fn clone(&self) -> Node

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Node

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.