Offline subtree and path queries on N-ary trees (Tree_Node). More...

#include <tpl_mo_on_trees.H>

Collaboration diagram for Aleph::Gen_Mo_On_Tree_Node< T, Policy >:

Public Types
using	Node = Tree_Node< T >

using	answer_type = typename Policy::answer_type

Public Member Functions
	Gen_Mo_On_Tree_Node (Node *root, Policy p=Policy())
	Construct a Mo's algorithm query engine for N-ary trees.

size_t	size () const noexcept
	Number of nodes in the tree.

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

Array< answer_type >	subtree_solve (const Array< Node * > &query_roots) const
	Answer subtree queries on the N-ary tree.

Array< answer_type >	subtree_solve (std::initializer_list< Node * > il) const
	Solve subtree queries (initializer-list overload).

Array< answer_type >	path_solve (const Array< std::pair< Node , Node > > &query_pairs) const
	Answer path queries on the N-ary tree.

Array< answer_type >	path_solve (std::initializer_list< std::pair< Node , Node > > il) const
	Solve path queries (initializer-list overload).

Private Member Functions
void	build ()

size_t	lca (size_t u, size_t v) const

Array< answer_type >	mo_sweep (const Array< T > &data, Array< Mo_Query > queries, size_t nn) const

Private Attributes
Node *	root_

Policy	pol_

size_t	n_ = 0

Array< Node * >	id_to_node_

MapOLhash< Node *, size_t >	node_to_id_

Array< T >	node_values_

Array< size_t >	tin_

Array< size_t >	tout_

Array< T >	flat_sub_

Array< size_t >	first_

Array< size_t >	last_

Array< size_t >	flat_node_

size_t	log_n_ = 0

Array< size_t >	depth_

Array< size_t >	parent_

Array< size_t >	up_

Static Private Attributes
static constexpr size_t	NONE = ~size_t(0)

Detailed Description

template<typename T, class Policy>
requires MoPolicy<Policy, T>
class Aleph::Gen_Mo_On_Tree_Node< T, Policy >

Offline subtree and path queries on N-ary trees (Tree_Node).

Same algorithm as Gen_Mo_On_Trees but works directly with the first-child / next-sibling representation of Tree_Node<T>. The tree is traversed via get_left_child() / get_right_sibling() instead of graph adjacency iterators.

Template Parameters

T	Value type stored in each Tree_Node.
Policy	A type satisfying `MoPolicy<Policy, T>`.

Example: auto * r = new Tree_Node<int>(10);

auto * a = new Tree_Node<int>(20);

auto * b = new Tree_Node<int>(10);

r->insert_rightmost_child(a);

r->insert_rightmost_child(b);

Gen_Mo_On_Tree_Node<int, Distinct_Count_Policy<int>> mot(r);

auto ans = mot.subtree_solve({r}); // ans(0) == 2

Aleph::Gen_Mo_On_Tree_Node
Offline subtree and path queries on N-ary trees (Tree_Node).
Definition tpl_mo_on_trees.H:701

Aleph::Tree_Node
Generic m-ary trees.
Definition tpl_tree_node.H:89

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

r
gsl_rng * r
Definition test_sort_lists.C:40

Definition at line 700 of file tpl_mo_on_trees.H.

Member Typedef Documentation

◆ answer_type

template<typename T , class Policy >

using Aleph::Gen_Mo_On_Tree_Node< T, Policy >::answer_type = typename Policy::answer_type

Definition at line 704 of file tpl_mo_on_trees.H.

◆ Node

template<typename T , class Policy >

using Aleph::Gen_Mo_On_Tree_Node< T, Policy >::Node = Tree_Node<T>

Definition at line 703 of file tpl_mo_on_trees.H.

Constructor & Destructor Documentation

◆ Gen_Mo_On_Tree_Node()

template<typename T , class Policy >

Aleph::Gen_Mo_On_Tree_Node< T, Policy >::Gen_Mo_On_Tree_Node	(	Node *	root,
		Policy	p = `Policy()`
	)

inline

Construct a Mo's algorithm query engine for N-ary trees.

Performs an O(N log N) preprocessing step. The tree is not modified in any way.

Parameters

root	Root of the N-ary tree (must not be null).
p	Policy object copied/moved into the query engine.

Exceptions

std::domain_error	If root is null or tree is inconsistent.
std::bad_alloc	If auxiliary arrays/tables cannot be allocated.

Note: Complexity: O(N log N) time and O(N log N) space.

Definition at line 995 of file tpl_mo_on_trees.H.

References ah_domain_error_if, Aleph::Gen_Mo_On_Tree_Node< T, Policy >::build(), and root().

Member Function Documentation

◆ build()

template<typename T , class Policy >

void Aleph::Gen_Mo_On_Tree_Node< T, Policy >::build ( )

inlineprivate

Definition at line 736 of file tpl_mo_on_trees.H.

Referenced by Aleph::Gen_Mo_On_Tree_Node< T, Policy >::Gen_Mo_On_Tree_Node().

◆ is_empty()

template<typename T , class Policy >

bool Aleph::Gen_Mo_On_Tree_Node< T, Policy >::is_empty ( ) const

inlinenoexcept

True if the tree is empty.

Definition at line 1007 of file tpl_mo_on_trees.H.

References Aleph::Gen_Mo_On_Tree_Node< T, Policy >::n_.

◆ lca()

template<typename T , class Policy >

size_t Aleph::Gen_Mo_On_Tree_Node< T, Policy >::lca	(	size_t	u,
		size_t	v
	)		const

inlineprivate

Definition at line 909 of file tpl_mo_on_trees.H.

References Aleph::Gen_Mo_On_Tree_Node< T, Policy >::depth_, Aleph::diff(), k, Aleph::Gen_Mo_On_Tree_Node< T, Policy >::log_n_, Aleph::Gen_Mo_On_Tree_Node< T, Policy >::n_, and Aleph::Gen_Mo_On_Tree_Node< T, Policy >::up_.

Referenced by Aleph::Gen_Mo_On_Tree_Node< T, Policy >::path_solve().

◆ mo_sweep()

template<typename T , class Policy >

Array< answer_type > Aleph::Gen_Mo_On_Tree_Node< T, Policy >::mo_sweep	(	const Array< T > &	data,
		Array< Mo_Query >	queries,
		size_t	nn
	)		const

inlineprivate

Definition at line 933 of file tpl_mo_on_trees.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Mo_Query::l, Aleph::Gen_Mo_On_Tree_Node< T, Policy >::pol_, r, and Aleph::Mo_Query::r.

Referenced by Aleph::Gen_Mo_On_Tree_Node< T, Policy >::subtree_solve().

◆ path_solve() [1/2]

template<typename T , class Policy >

Array< answer_type > Aleph::Gen_Mo_On_Tree_Node< T, Policy >::path_solve ( const Array< std::pair< Node *, Node * > > & query_pairs ) const

inline

Answer path queries on the N-ary tree.

Parameters

query_pairs Array of (u, v) node-pointer pairs.

Returns: Array<answer_type> with answers in the same order as query_pairs.

Exceptions

std::domain_error	If any query endpoint is not in the tree.
Any	exception thrown by `Policy::init`, `Policy::add`, `Policy::remove`, or `Policy::answer`.