[−][src]Struct treeid::Node
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
[src]
pub fn root() -> Self
[src]
Returns the root node.
use treeid::*; assert_eq!(Node::from(&[]), Node::root());
pub fn position(&self) -> &[u64]
[src]
Returns a reference to the tree position of this node.
pub fn key(&self) -> &[u8]
[src]
Returns a reference to the key of this node.
pub fn from_vec(loc: Vec<u64>) -> Self
[src]
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
[src]
Constructs a node from its tree position and key.
Panics if the position contains any zeros.
pub fn from_vec_parts(loc: Vec<u64>, key: Vec<u8>) -> Self
[src]
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
[src]
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
[src]
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)
[src]
Sets the key for this node.
pub fn set_vec_key(&mut self, key: Vec<u8>)
[src]
Sets the (owned) key for this node.
pub fn parent(&self) -> Self
[src]
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)
[src]
pub fn child(&self, id: u64) -> Self
[src]
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)
[src]
pub fn sibling(&self, id: u64) -> Option<Self>
[src]
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)
[src]
pub fn pred(&self) -> Option<Self>
[src]
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>
[src]
Get the next sibling of this node. Sorts after this node.
Returns None if this is the root.
pub fn is_root(&self) -> bool
[src]
Returns true
if this is the root.
pub fn from_binary(mlcf_encoded: &[u8]) -> Option<Self>
[src]
Decode a node from its mLCF encoded form.
pub fn to_binary(&self) -> Vec<u8>
[src]
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<A: AsRef<[u64]>> From<A> for Node
[src]
impl From<Vec<u64>> for Node
[src]
impl Default for Node
[src]
impl PartialOrd<Node> for Node
[src]
fn partial_cmp(&self, other: &Node) -> Option<Ordering>
[src]
#[must_use]
fn lt(&self, other: &Rhs) -> bool
1.0.0[src]
This method tests less than (for self
and other
) and is used by the <
operator. Read more
#[must_use]
fn le(&self, other: &Rhs) -> bool
1.0.0[src]
This method tests less than or equal to (for self
and other
) and is used by the <=
operator. Read more
#[must_use]
fn gt(&self, other: &Rhs) -> bool
1.0.0[src]
This method tests greater than (for self
and other
) and is used by the >
operator. Read more
#[must_use]
fn ge(&self, other: &Rhs) -> bool
1.0.0[src]
This method tests greater than or equal to (for self
and other
) and is used by the >=
operator. Read more
impl Eq for Node
[src]
impl Ord for Node
[src]
fn cmp(&self, other: &Node) -> Ordering
[src]
fn max(self, other: Self) -> Self
1.21.0[src]
Compares and returns the maximum of two values. Read more
fn min(self, other: Self) -> Self
1.21.0[src]
Compares and returns the minimum of two values. Read more
impl AsRef<[u8]> for Node
[src]
impl PartialEq<Node> for Node
[src]
impl Clone for Node
[src]
fn clone(&self) -> Node
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl Debug for Node
[src]
Auto Trait Implementations
Blanket Implementations
impl<T, U> Into for T where
U: From<T>,
[src]
U: From<T>,
impl<T> From for T
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
impl<T, U> TryFrom for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = !
try_from
)The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T> Borrow for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T, U> TryInto for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
try_from
)The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,