Struct crdt_tree::tree::Tree

pub struct Tree<ID: TreeId, TM: TreeMeta> { /* fields omitted */ }

From the paper:

We can represent the tree as a set of (parent, meta, child) triples, denoted in Isabelle/HOL as (’n × ’m × ’n) set. When we have (p, m, c) ∈ tree, that means c is a child of p in the tree, with associated metadata m. Given a tree, we can construct a new tree’ in which the child c is moved to a new parent p, with associated metadata m, as follows:

tree’ = {(p’, m’, c’) ∈ tree. c’ != c} ∪ {(p, m, c)}

That is, we remove any existing parent-child relationship for c from the set tree, and then add {(p, m, c)} to represent the new parent-child relationship.

Implementations

impl<ID: TreeId, TM: TreeMeta> Tree<ID, TM>

pub fn new() -> Self

create a new Tree instance

pub fn rm_child(&mut self, child_id: &ID)

helper for removing a triple based on child_id

pub fn rm_subtree(&mut self, parent_id: &ID, include_parent: bool)

removes a subtree. useful for emptying trash. not used by crdt algo.

pub fn add_node(&mut self, child_id: ID, tt: TreeNode<ID, TM>)

adds a node to the tree

pub fn find(&self, child_id: &ID) -> Option<&TreeNode<ID, TM>>

returns matching node, or None.

pub fn children(&self, parent_id: &ID) -> Vec<ID>

returns children (IDs) of a given parent node. useful for walking tree. not used by crdt algo.

pub fn walk<F>(&self, parent_id: &ID, f: &F) where
    F: Fn(&Self, &ID, usize), 

walks tree and calls callback fn for each node. not used by crdt algo.

pub fn is_ancestor(&self, child_id: &ID, ancestor_id: &ID) -> bool

parent | child

1 2 1 3 3 5 2 6 6 8 1 2 3 6 5 8

is 2 ancestor of 8? yes. is 2 ancestor of 5? no. determines if ancestor_id is an ancestor of node_id in tree. returns bool

Trait Implementations

impl<ID: Clone + TreeId, TM: Clone + TreeMeta> Clone for Tree<ID, TM>

fn clone(&self) -> Tree<ID, TM>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<ID: Debug + TreeId, TM: Debug + TreeMeta> Debug for Tree<ID, TM>

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

Formats the value using the given formatter.

impl<ID: Default + TreeId, TM: Default + TreeMeta> Default for Tree<ID, TM>

fn default() -> Tree<ID, TM>

Returns the "default value" for a type.

impl<'de, ID: TreeId, TM: TreeMeta> Deserialize<'de> for Tree<ID, TM> where
    ID: Deserialize<'de>,
    TM: Deserialize<'de>, 

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
    __D: Deserializer<'de>, 

Deserialize this value from the given Serde deserializer.

impl<ID: Eq + TreeId, TM: Eq + TreeMeta> Eq for Tree<ID, TM>

impl<ID: TreeId, TM: TreeMeta> IntoIterator for Tree<ID, TM>

Implement IntoIterator for Tree. This is useful for walking all Nodes in tree without knowing a starting point.

type Item = (ID, TreeNode<ID, TM>)

The type of the elements being iterated over.

type IntoIter = IntoIter<ID, TreeNode<ID, TM>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<ID: PartialEq + TreeId, TM: PartialEq + TreeMeta> PartialEq<Tree<ID, TM>> for Tree<ID, TM>

fn eq(&self, other: &Tree<ID, TM>) -> bool

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

fn ne(&self, other: &Tree<ID, TM>) -> bool

This method tests for !=.

impl<ID: TreeId, TM: TreeMeta> Serialize for Tree<ID, TM> where
    ID: Serialize,
    TM: Serialize, 

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error> where
    __S: Serializer, 

Serialize this value into the given Serde serializer.

impl<ID: TreeId, TM: TreeMeta> StructuralEq for Tree<ID, TM>

impl<ID: TreeId, TM: TreeMeta> StructuralPartialEq for Tree<ID, TM>