Struct PQTree

pub struct PQTree<T>
where
    T: Clone + Eq + Hash,
{ /* private fields */ }

Implementations

impl<T: Clone + Eq + Hash> PQTree<T>

pub fn new() -> PQTree<T>

Creates an empty PQTree.

pub fn from_leaves(initial: &[T]) -> Result<Self, ReplacementError<T>>

Creates PQTree from list of leaves.

First creates an empty tree, then replaces whole tree by new leaves:

PQTree::new().replace_tree_by_new_leaves(initial)

Errors

Returns Err(ReplacementError::DuplicateLeaf(leaf)) if leaf presents in initial more than one time.

pub fn reduction(self, s: &[T]) -> Result<Self, ReductionError<T>>

Applies reduction to the tree enforcing leaves from s to be consequent and marks pertinent subroot.

Errors

Returns Err(ReductionError::EmptyLeafSet) if s is empty.

Returns Err(ReductionError::LeafNotFound(leaf)) if leaf from s not found in the tree.

Returns Err(ReductionError::IrreducibleTree) if tree cannot be reduced over new constraint.

pub fn replace_tree_by_new_leaves( self, leaves: &[T], ) -> Result<Self, ReplacementError<T>>

Replaces whole tree by new leaves.

Same as PQTree::from_leaves but without reallocation.

Errors

Returns Err(ReplacementError::DuplicateLeaf(leaf)) if leaf presents in leaves more than one time.

pub fn replace_leaf_by_new_leaves( self, leaf: &T, leaves: &[T], ) -> Result<Self, ReplacementError<T>>

Replaces single leaf by new leaves. Can be called with empty leaves to remove leaf from tree.

First removes leaf from tree, then adds new leaves.

Clears pertinent root mark if any.

Errors

Returns Err(ReplacementError::LeafNotFound(leaf)) if leaf not found in the tree.

Returns Err(ReplacementError::DuplicateLeaf(leaf)) if leaf already exists in the tree or presents in leaves more than one time.

pub fn replace_pertinent_by_new_leaves( self, leaves: &[T], ) -> Result<Self, ReplacementError<T>>

Replaces full children of the pertinent root by new leaves. Can be called with empty leaves to remove all full children from the tree.

First removes all full nodes and leaves from the tree, then adds new leaves.

Marks added subtree root as the pertinent root if leaves is not empty or clears the mark.

Errors

Returns Err(ReplacementError::DuplicateLeaf(leaf)) if leaf already exists in the tree or presents in leaves more than one time.

Returns Err(ReplacementError::NoPertinentRoot)) if no pertinent root is marked in the tree.

pub fn frontier(&self) -> Vec<T>

Returns the tree frontier: a vector of leaves ordered in an allowed way for the tree.

impl<T: Clone + Eq + Hash + Ord> PQTree<T>

pub fn sort_minimal(&mut self)

Sorts the tree by “minimal order”

pub fn sort_lexicographically(&mut self)

Sorts the tree “lexicographically”

Trait Implementations

impl<T> Clone for PQTree<T>

where T: Clone + Eq + Hash + Clone,

fn clone(&self) -> PQTree<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Debug for PQTree<T>

where T: Clone + Eq + Hash + Debug,

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

Formats the value using the given formatter.

impl<T: Clone + Eq + Hash + Display> Display for PQTree<T>

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

Formats the value using the given formatter.