Struct CartesianTree

pub struct CartesianTree<'a, T: Ord> { /* private fields */ }

A cartesian tree is a heap ordered binary tree derived from some underlying array. An in-order traversal of the tree yields the underlying array.

Implementations

impl<'a, T: Ord> CartesianTree<'a, T>

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

pub fn cartesian_tree_number(&self) -> u64

Calculates the cartesian tree number of this tree using the sequence of push and pop operations stored in the action_profile. Note that calculating this value only makes sense when the underlying array is small. More specifically, this procedure assumes that the underlying array has at most 32 items. This makes sense in our context since we’re mostly interested in the cartesian tree numbers of RMQ blocks

Trait Implementations

impl<'a, T: Debug + Ord> Debug for CartesianTree<'a, T>

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

Formats the value using the given formatter.

impl<'a, T: Ord> From<&'a [T]> for CartesianTree<'a, T>

fn from(underlying: &'a [T]) -> Self

Converts to this type from the input type.