Struct treeid::Node

pub struct Node { /* fields omitted */ }

Represents a location in the treeid hierarchy, and an arbitrary key.

Taken together, the primary use case is to allow for arbitrarily nested ranges of keys in a flat, ordered collection like BTreeMap.

Crucially, the sort order of treeid nodes remains stable even when serialized, allowing for them to be used efficiently with on-disk collections that do not support varying comparison operators. Even in collections that do, the lexicographic sort offered by a serialized treeid node is typically faster (and simpler) than having to deserialize keys for every comparison.

Sort order

The location of each node in the hierarchy is represented as a sequence of nonzero unsigned integers:

// Hierarchical Structure
//
//                /------------[root]-------------\
//                |                               |
//       /-------[1]-------\             /-------[2]-------\
//       |                 |             |                 |
//  /---[1,1]---\   /---[1,2]---\   /---[2,1]---\   /---[2,2]---\
//  |           |   |           |   |           |   |           |
// [1,1,1] [1,1,2] [1,2,1] [1,2,2] [2,1,1] [2,1,2] [2,2,1] [2,2,2]

// Ascending Sort Order
//
// [root]
// [1]
// [1,1]
// [1,1,1]
// [1,1,2]
// [1,2]
// [1,2,1]
// [1,2,2]
// [2]
// [2,1]
// [2,1,1]
// [2,1,2]
// [2,2]
// [2,2,1]
// [2,2,2]

Nodes in the same position, but with different keys will be ordered by the key.

use treeid::Node;

let a = Node::from_parts(&[1, 2], b"hello world");
let b = Node::from_parts(&[1, 2, 1], b"1st key");
let c = Node::from_parts(&[1, 2, 1], b"2nd key");
let d = Node::from_parts(&[1, 3], b"some other key");

assert!(a < b && b < c && c < d);
assert!(a.to_binary() < b.to_binary()
     && b.to_binary() < c.to_binary()
     && c.to_binary() < d.to_binary());

Encoding format

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

Technical deviations from 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).

• a trailing zero byte is appended to allow for a suffix key

Size

There is no limit to the length of a treeid position, other than practical concerns w.r.t. space consumption. The total size of the positional portion 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 to the next byte boundary will be the total bitsize.

A single zero byte will follow to dilineate from the key portion, which is appended unchanged.

For example, to find the encoded size of the position &[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 8 : 16
• add a byte : 24

Which corresponds to the encoded form of:

0b11011111 0b00011000 0x0

use treeid::Node;

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

    &[0b11011_1_11, 0b000_1_100_0, 0],
    &*node.to_binary(),
);

Methods

impl Node

pub fn root() -> Self

Returns the root node.

use treeid::*;
assert_eq!(Node::from(&[]), Node::root());
assert_eq!(&[0x0], &*Node::root().to_binary());
assert_eq!(Node::root(), Node::from_binary(&[0x0]).unwrap());

let keyed = Node::root().with_key(b"hello worldo");
assert_eq!(keyed, Node::from_binary(&*keyed.to_binary()).unwrap());

pub fn position(&self) -> &[u64]

Returns a reference to the tree position of this node.

use treeid::*;

let node = Node::from_parts(&[1, 2, 3], b"hello worldo");

assert_eq!(node.position(), &[1, 2, 3]);

pub fn key(&self) -> &[u8]

Returns a reference to the key of this node.

use treeid::*;

let node = Node::from_parts(&[1, 2, 3], b"hello worldo");

assert_eq!(node.key(), b"hello worldo");

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 from_parts<A: AsRef<[u64]>, B: AsRef<[u8]>>(loc: A, key: B) -> Self

Constructs a node from its tree position and key.

Panics if the position contains any zeros.

use treeid::*;

let from_parts = Node::from_parts(&[1, 2, 3], b"a key of some sort");
let another = Node::from(&[1, 2, 3]).with_key(b"a key of some sort");

assert_eq!(from_parts, another);

pub fn from_vec_parts(loc: Vec<u64>, key: Vec<u8>) -> Self

Constructs a node from its (owned) tree position and key.

Panics if the position contains any zeros.

pub fn with_key<K: AsRef<[u8]>>(&self, key: K) -> Self

Returns a node at the same location as the current node, but using the provided key.

pub fn with_vec_key(&self, key: Vec<u8>) -> Self

Returns a node at the same location as the current node, but using the provided (owned) key.

pub fn set_key<K: AsRef<[u8]>>(&mut self, key: K)

Sets the key for this node.

pub fn set_vec_key(&mut self, key: Vec<u8>)

Sets the (owned) key for this node.

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.

use treeid::*;

let node = Node::from(&[1, 2, 3]);
let par = node.parent();
let child = node.child(4);
let sibl = node.sibling(1).unwrap();

assert!(par < node);
assert!(par < child);
assert!(par < sibl);
assert_eq!(par, Node::from(&[1, 2]));

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.

use treeid::*;

let node = Node::from(&[1, 2, 3]);
let sibl = node.sibling(4).unwrap();
let child = node.child(42);

assert!(child > node);
assert!(child < sibl);
assert_eq!(child, Node::from(&[1, 2, 3, 42]));

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.

use treeid::*;

let node = Node::from(&[1, 2, 3]);
let up = node.sibling(44).unwrap();
let down = node.sibling(2).unwrap();

assert!(up > node);
assert!(down < node);
assert_eq!(up, Node::from(&[1, 2, 44]));
assert_eq!(down, Node::from(&[1, 2, 2]));

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.

use treeid::*;

let node = Node::from(&[1, 2, 3]);
let pred = node.pred().unwrap();

assert!(node > pred);
assert_eq!(pred, Node::from(&[1, 2, 2]));

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

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

Returns None if this is the root.

use treeid::*;

let node = Node::from(&[1, 2, 3]);
let succ = node.succ().unwrap();

assert!(node < succ);
assert_eq!(succ, Node::from(&[1, 2, 4]));

pub fn is_root(&self) -> bool

Returns true if this is the root.

use treeid::*;

let root = Node::root();

assert!(root.is_root());

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

Decode a node from its mLCF encoded form.

use treeid::*;

let node = Node::from_parts(&[1,2,32,4,32,5,7,5], b"i am a key");
let serialized = node.to_binary();

assert_eq!(node, Node::from_binary(&serialized).unwrap());

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

Writes this id into a Vec<[u8]> using mLCF encoding.

use treeid::*;

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

Trait Implementations

impl PartialOrd<Node> for Node

fn partial_cmp(&self, other: &Node) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use] fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use] fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use] fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use] fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

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

fn cmp(&self, other: &Node) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

🔬 This is a nightly-only experimental API. (clamp)

Restrict a value to a certain interval.

impl AsRef<[u8]> for Node

fn as_ref(&self) -> &[u8]

Performs the conversion.

impl Eq for Node

impl Default for Node

fn default() -> Node

Returns the "default value" for a type.

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

default fn from(loc: A) -> Self

Performs the conversion.

impl From<Vec<u64>> for Node

fn from(loc: Vec<u64>) -> Self

Performs the conversion.

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.