Struct treeid::Node

pub struct Node { /* fields omitted */ }

A position in the tree.

Nodes are encoded to binary in a modified form of LCF[1] (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).

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

Methods

impl Node

pub fn root() -> Self

Returns the root node.

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

pub fn from(v: &[u64]) -> Self

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

pub fn parent(&self) -> Self

pub fn parent_mut(&mut self)

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

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

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

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

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

pub fn succ(&self) -> Self

pub fn is_root(&self) -> bool

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 Clone for Node

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

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 Debug for Node

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

Formats the value using the given formatter.