Explicit Cartesian Tree built in O(n) with a monotonic stack. More...

#include <tpl_cartesian_tree.H>

Inheritance diagram for Aleph::Gen_Cartesian_Tree< T, Comp >:

Collaboration diagram for Aleph::Gen_Cartesian_Tree< T, Comp >:

Public Types
using	Item_Type = T
	The type of the element stored in the tree.

Public Member Functions
	Gen_Cartesian_Tree (const Array< T > &values, Comp c=Comp())
	Construct from an Array<T>.

	Gen_Cartesian_Tree (const std::vector< T > &values, Comp c=Comp())
	Construct from a std::vector<T>.

	Gen_Cartesian_Tree (std::initializer_list< T > il, Comp c=Comp())
	Construct from an initializer_list<T>.

	Gen_Cartesian_Tree (const DynList< T > &values, Comp c=Comp())
	Construct from a DynList<T>.

	Gen_Cartesian_Tree (const size_t num, const T &init, Comp c=Comp())
	Construct with `num` elements all equal to `init`.

	Gen_Cartesian_Tree (const Gen_Cartesian_Tree &)=default
	Copy constructor.

Gen_Cartesian_Tree &	operator= (const Gen_Cartesian_Tree &)=default
	Copy assignment operator.

	Gen_Cartesian_Tree (Gen_Cartesian_Tree &&) noexcept(std::is_nothrow_move_constructible_v< Array< T > > and std::is_nothrow_move_constructible_v< Comp >)=default

Gen_Cartesian_Tree &	operator= (Gen_Cartesian_Tree &&) noexcept(std::is_nothrow_move_assignable_v< Array< T > > and std::is_nothrow_move_assignable_v< Comp >)=default

constexpr size_t	root () const noexcept
	Index of the root node.

size_t	left_child (const size_t i) const
	Left child of node `i`.

size_t	right_child (const size_t i) const
	Right child of node `i`.

size_t	parent_of (const size_t i) const
	Parent of node `i`.

const T &	data_at (const size_t i) const
	Value at node `i`.

constexpr size_t	size () const noexcept
	Number of nodes.

constexpr bool	is_empty () const noexcept
	True if the tree is empty.

bool	is_leaf (const size_t i) const
	True if node `i` is a leaf (no children).

bool	is_root (const size_t i) const
	True if node `i` is the root.

size_t	height () const
	Height of the tree (longest root-to-leaf path).

Array< size_t >	inorder () const
	Inorder traversal of the tree.

Array< T >	values () const
	Copy of the original data array.

void	swap (Gen_Cartesian_Tree &other) noexcept(noexcept(data_.swap(other.data_)) &&noexcept(parent_.swap(other.parent_)) &&noexcept(left_.swap(other.left_)) &&noexcept(right_.swap(other.right_)) &&noexcept(std::swap(root_, other.root_)) &&noexcept(std::swap(n_, other.n_)) &&std::is_nothrow_swappable_v< Comp >)
	Swap with `other` in O(1).

Static Public Attributes
static constexpr size_t	NONE = static_cast<size_t>(-1)
	Sentinel value for absent parent/child links.

Private Member Functions
void	build ()
	Build the Cartesian Tree using a monotonic stack in O(n).

void	init_and_build ()
	Initialize arrays of size n with NONE and build.

Private Attributes
Array< T >	data_

Array< size_t >	parent_

Array< size_t >	left_

Array< size_t >	right_

size_t	root_

size_t	n_

Comp	comp_

Detailed Description

template<typename T, class Comp>
requires StrictWeakOrder<Comp, T>
class Aleph::Gen_Cartesian_Tree< T, Comp >

Explicit Cartesian Tree built in O(n) with a monotonic stack.

A Cartesian Tree over an array a[0..n-1] is a binary tree where:

The heap property holds: no child is strictly better than its parent under Comp, i.e. !Comp(a[child], a[parent]) for every parent–child pair (min-heap by default; equality is allowed).
The inorder traversal reproduces the original array order 0, 1, 2, ..., n-1.

The tree is represented implicitly with three parallel arrays (parent, left, right) indexed by position in the original array. A sentinel value NONE = size_t(-1) marks absent links.

Template Parameters

T	element type.
Comp	binary comparator defining the heap property.

Example: Cartesian_Tree<int> ct = {3, 2, 6, 1, 9};

// Root is at index 3 (value 1, the minimum)

assert(ct.root() == 3);

assert(ct.data_at(ct.root()) == 1);

// Inorder traversal = {0, 1, 2, 3, 4}

auto io = ct.inorder();

for (size_t i = 0; i < io.size(); ++i)

assert(io(i) == i);

Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133

Aleph::Cartesian_Tree
Cartesian Tree for min-heap (range minimum).
Definition tpl_cartesian_tree.H:474

Definition at line 119 of file tpl_cartesian_tree.H.

Member Typedef Documentation

◆ Item_Type

template<typename T , class Comp >

using Aleph::Gen_Cartesian_Tree< T, Comp >::Item_Type = T

The type of the element stored in the tree.

Definition at line 196 of file tpl_cartesian_tree.H.

Constructor & Destructor Documentation

◆ Gen_Cartesian_Tree() [1/7]

template<typename T , class Comp >

Aleph::Gen_Cartesian_Tree< T, Comp >::Gen_Cartesian_Tree	(	const Array< T > &	values,
		Comp	c = `Comp()`
	)

inline

Construct from an Array<T>.

Parameters

values	source array.
c	comparator (default-constructed).

Definition at line 202 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree< T, Comp >::init_and_build().

◆ Gen_Cartesian_Tree() [2/7]

template<typename T , class Comp >

Aleph::Gen_Cartesian_Tree< T, Comp >::Gen_Cartesian_Tree	(	const std::vector< T > &	values,
		Comp	c = `Comp()`
	)

inline

Construct from a std::vector<T>.

Parameters

values	source vector.
c	comparator.

Definition at line 212 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree< T, Comp >::data_, Aleph::Gen_Cartesian_Tree< T, Comp >::init_and_build(), Aleph::Gen_Cartesian_Tree< T, Comp >::n_, and Aleph::Gen_Cartesian_Tree< T, Comp >::values().

◆ Gen_Cartesian_Tree() [3/7]

template<typename T , class Comp >

Aleph::Gen_Cartesian_Tree< T, Comp >::Gen_Cartesian_Tree	(	std::initializer_list< T >	il,
		Comp	c = `Comp()`
	)

inline

Construct from an initializer_list<T>.

Parameters

il	initializer list.
c	comparator.

Definition at line 225 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree< T, Comp >::data_, Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Cartesian_Tree< T, Comp >::init_and_build().

◆ Gen_Cartesian_Tree() [4/7]

template<typename T , class Comp >

Aleph::Gen_Cartesian_Tree< T, Comp >::Gen_Cartesian_Tree	(	const DynList< T > &	values,
		Comp	c = `Comp()`
	)

inline

Construct from a DynList<T>.

Parameters

values	source list.
c	comparator.

Definition at line 239 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree< T, Comp >::data_, Aleph::Gen_Cartesian_Tree< T, Comp >::init_and_build(), and Aleph::Gen_Cartesian_Tree< T, Comp >::values().

◆ Gen_Cartesian_Tree() [5/7]

template<typename T , class Comp >

Aleph::Gen_Cartesian_Tree< T, Comp >::Gen_Cartesian_Tree	(	const size_t	num,
		const T &	init,
		Comp	c = `Comp()`
	)

inline

Construct with num elements all equal to init.

Parameters

num	number of elements.
init	initial value for every position.
c	comparator.

Definition at line 254 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree< T, Comp >::data_, Aleph::init, Aleph::Gen_Cartesian_Tree< T, Comp >::init_and_build(), and Aleph::Gen_Cartesian_Tree< T, Comp >::n_.

◆ Gen_Cartesian_Tree() [6/7]

template<typename T , class Comp >

Aleph::Gen_Cartesian_Tree< T, Comp >::Gen_Cartesian_Tree ( const Gen_Cartesian_Tree< T, Comp > & )

default

Copy constructor.

◆ Gen_Cartesian_Tree() [7/7]

template<typename T , class Comp >

Aleph::Gen_Cartesian_Tree< T, Comp >::Gen_Cartesian_Tree ( Gen_Cartesian_Tree< T, Comp > && ) const

defaultnoexcept

Member Function Documentation

◆ build()

template<typename T , class Comp >

void Aleph::Gen_Cartesian_Tree< T, Comp >::build ( )

inlineprivate

Build the Cartesian Tree using a monotonic stack in O(n).

Definition at line 136 of file tpl_cartesian_tree.H.

References Aleph::and, Aleph::Gen_Cartesian_Tree< T, Comp >::comp_, Aleph::Array< T >::create(), Aleph::Gen_Cartesian_Tree< T, Comp >::data_, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Cartesian_Tree< T, Comp >::left_, Aleph::Gen_Cartesian_Tree< T, Comp >::n_, Aleph::Gen_Cartesian_Tree< T, Comp >::NONE, Aleph::Gen_Cartesian_Tree< T, Comp >::parent_, Aleph::Gen_Cartesian_Tree< T, Comp >::right_, and Aleph::Gen_Cartesian_Tree< T, Comp >::root_.

Referenced by Aleph::Gen_Cartesian_Tree< T, Comp >::init_and_build().

◆ data_at()

template<typename T , class Comp >

const T & Aleph::Gen_Cartesian_Tree< T, Comp >::data_at ( const size_t i ) const

inline

Value at node i.

Exceptions

std::out_of_range if i >= size().

Definition at line 314 of file tpl_cartesian_tree.H.

References ah_out_of_range_error_if, Aleph::Gen_Cartesian_Tree< T, Comp >::data_, and Aleph::Gen_Cartesian_Tree< T, Comp >::n_.

Referenced by scenario_2().

◆ height()

template<typename T , class Comp >

size_t Aleph::Gen_Cartesian_Tree< T, Comp >::height ( ) const

inline

Height of the tree (longest root-to-leaf path).

Note: This function takes no parameters.

Returns: Height in number of nodes on the longest root-to-leaf path (0 if empty, 1 for a single-node tree), returned by value.

Exceptions

std::bad_alloc if temporary DFS stack allocation fails.

Note: No bounds-related exceptions are thrown (this method receives no indices).; Complexity: O(n) time and O(n) auxiliary space (explicit stack).

Definition at line 355 of file tpl_cartesian_tree.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Cartesian_Tree< T, Comp >::left_, Aleph::Gen_Cartesian_Tree< T, Comp >::n_, Aleph::Gen_Cartesian_Tree< T, Comp >::NONE, Aleph::Gen_Cartesian_Tree< T, Comp >::right_, and Aleph::Gen_Cartesian_Tree< T, Comp >::root_.

◆ init_and_build()

template<typename T , class Comp >

void Aleph::Gen_Cartesian_Tree< T, Comp >::init_and_build ( )

inlineprivate

Initialize arrays of size n with NONE and build.

Definition at line 180 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree< T, Comp >::build(), Aleph::Array< T >::create(), Aleph::Gen_Cartesian_Tree< T, Comp >::left_, Aleph::Gen_Cartesian_Tree< T, Comp >::n_, Aleph::Gen_Cartesian_Tree< T, Comp >::NONE, Aleph::Gen_Cartesian_Tree< T, Comp >::parent_, and Aleph::Gen_Cartesian_Tree< T, Comp >::right_.

Referenced by Aleph::Gen_Cartesian_Tree< T, Comp >::Gen_Cartesian_Tree(), Aleph::Gen_Cartesian_Tree< T, Comp >::Gen_Cartesian_Tree(), Aleph::Gen_Cartesian_Tree< T, Comp >::Gen_Cartesian_Tree(), Aleph::Gen_Cartesian_Tree< T, Comp >::Gen_Cartesian_Tree(), and Aleph::Gen_Cartesian_Tree< T, Comp >::Gen_Cartesian_Tree().

◆ inorder()

template<typename T , class Comp >

Array< size_t > Aleph::Gen_Cartesian_Tree< T, Comp >::inorder ( ) const

inline

Inorder traversal of the tree.

Note: This function takes no parameters.

Returns: A new Array<size_t> with node indices in inorder, returned by value (ownership transferred to the caller). For a correctly built Cartesian Tree, this sequence is {0, 1, ..., n-1}. If the tree is empty, returns an empty Array<size_t>.

Exceptions

std::bad_alloc if result/stack allocation fails.

Note: No bounds-related exceptions are thrown (this method receives no indices).; Complexity: O(n) time and O(n) auxiliary space (result array + traversal stack).

Definition at line 399 of file tpl_cartesian_tree.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Cartesian_Tree< T, Comp >::left_, Aleph::Gen_Cartesian_Tree< T, Comp >::n_, Aleph::Gen_Cartesian_Tree< T, Comp >::NONE, Aleph::Gen_Cartesian_Tree< T, Comp >::right_, and Aleph::Gen_Cartesian_Tree< T, Comp >::root_.

◆ is_empty()

template<typename T , class Comp >

constexpr bool Aleph::Gen_Cartesian_Tree< T, Comp >::is_empty ( ) const

inlineconstexprnoexcept

True if the tree is empty.

Definition at line 325 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree< T, Comp >::n_.

◆ is_leaf()

template<typename T , class Comp >

bool Aleph::Gen_Cartesian_Tree< T, Comp >::is_leaf ( const size_t i ) const

inline

True if node i is a leaf (no children).

Exceptions

std::out_of_range if i >= size().

Definition at line 330 of file tpl_cartesian_tree.H.

References ah_out_of_range_error_if, Aleph::and, Aleph::Gen_Cartesian_Tree< T, Comp >::left_, Aleph::Gen_Cartesian_Tree< T, Comp >::n_, Aleph::Gen_Cartesian_Tree< T, Comp >::NONE, and Aleph::Gen_Cartesian_Tree< T, Comp >::right_.

◆ is_root()

template<typename T , class Comp >

bool Aleph::Gen_Cartesian_Tree< T, Comp >::is_root ( const size_t i ) const

inline

True if node i is the root.

Definition at line 338 of file tpl_cartesian_tree.H.

References ah_out_of_range_error_if, Aleph::Gen_Cartesian_Tree< T, Comp >::n_, and Aleph::Gen_Cartesian_Tree< T, Comp >::root_.

◆ left_child()

template<typename T , class Comp >

size_t Aleph::Gen_Cartesian_Tree< T, Comp >::left_child ( const size_t i ) const

inline

Left child of node i.

Exceptions

std::out_of_range if i >= size().

Definition at line 284 of file tpl_cartesian_tree.H.

References ah_out_of_range_error_if, Aleph::Gen_Cartesian_Tree< T, Comp >::left_, and Aleph::Gen_Cartesian_Tree< T, Comp >::n_.

◆ operator=() [1/2]

template<typename T , class Comp >

Gen_Cartesian_Tree & Aleph::Gen_Cartesian_Tree< T, Comp >::operator= ( const Gen_Cartesian_Tree< T, Comp > & )

default

Copy assignment operator.

◆ operator=() [2/2]

template<typename T , class Comp >

Gen_Cartesian_Tree & Aleph::Gen_Cartesian_Tree< T, Comp >::operator= ( Gen_Cartesian_Tree< T, Comp > && )

defaultnoexcept

◆ parent_of()

template<typename T , class Comp >

size_t Aleph::Gen_Cartesian_Tree< T, Comp >::parent_of ( const size_t i ) const

inline

Parent of node i.

Exceptions

std::out_of_range if i >= size().

Definition at line 304 of file tpl_cartesian_tree.H.

References ah_out_of_range_error_if, Aleph::Gen_Cartesian_Tree< T, Comp >::n_, and Aleph::Gen_Cartesian_Tree< T, Comp >::parent_.

◆ right_child()

template<typename T , class Comp >

size_t Aleph::Gen_Cartesian_Tree< T, Comp >::right_child ( const size_t i ) const

inline

Right child of node i.

Exceptions

std::out_of_range if i >= size().

Definition at line 294 of file tpl_cartesian_tree.H.

References ah_out_of_range_error_if, Aleph::Gen_Cartesian_Tree< T, Comp >::n_, and Aleph::Gen_Cartesian_Tree< T, Comp >::right_.

◆ root()

template<typename T , class Comp >

constexpr size_t Aleph::Gen_Cartesian_Tree< T, Comp >::root ( ) const

inlineconstexprnoexcept

Index of the root node.

Returns: root index, or NONE if empty.

Definition at line 279 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree< T, Comp >::root_.

Referenced by scenario_1(), and TEST().

◆ size()

template<typename T , class Comp >

constexpr size_t Aleph::Gen_Cartesian_Tree< T, Comp >::size ( ) const

inlineconstexprnoexcept

Number of nodes.

Definition at line 322 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree< T, Comp >::n_.

◆ swap()

template<typename T , class Comp >

void Aleph::Gen_Cartesian_Tree< T, Comp >::swap ( Gen_Cartesian_Tree< T, Comp > & other )

inlinenoexcept

Swap with other in O(1).

Definition at line 448 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree< T, Comp >::comp_, Aleph::Gen_Cartesian_Tree< T, Comp >::data_, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Cartesian_Tree< T, Comp >::left_, Aleph::Gen_Cartesian_Tree< T, Comp >::n_, Aleph::Gen_Cartesian_Tree< T, Comp >::parent_, Aleph::Gen_Cartesian_Tree< T, Comp >::right_, Aleph::Gen_Cartesian_Tree< T, Comp >::root_, and Aleph::Array< T >::swap().

Referenced by TEST().

◆ values()

template<typename T , class Comp >

Array< T > Aleph::Gen_Cartesian_Tree< T, Comp >::values ( ) const

inline

Copy of the original data array.

Note: This function takes no parameters.

Returns: A new Array<T> with all stored values in original index order, returned by value (ownership transferred to the caller). If the tree is empty, returns an empty Array<T>.

Exceptions