Aleph-w: Aleph::Li_Chao_Tree< T > Class Template Reference

Aleph-w 3.0

A C++ Library for Data Structures and Algorithms

Loading...

Searching...

No Matches

Li Chao tree for min line queries on an integral x-domain. More...

#include <DP_Optimizations.H>

Collaboration diagram for Aleph::Li_Chao_Tree< T >:

Classes
struct	Line
	Affine line y = m*x + b. More...

struct	Node

Public Member Functions
	Li_Chao_Tree (const T x_left, const T x_right)

bool	is_empty () const noexcept

size_t	node_count () const noexcept

void	clear ()

void	add_line (const T slope, const T intercept)

T	query (const T x) const

Private Member Functions
size_t	new_node (const Line &line)

void	add_line_impl (const size_t idx, const T l, const T r, Line line)

T	query_impl (const size_t idx, const T l, const T r, const T x) const

Private Attributes
T	x_left_

T	x_right_

Array< Node >	nodes_

size_t	root_ = NIL

Static Private Attributes
static constexpr size_t	NIL = std::numeric_limits<size_t>::max()

Detailed Description

template<typename T>
class Aleph::Li_Chao_Tree< T >

Li Chao tree for min line queries on an integral x-domain.

Supports arbitrary line insertion order and O(log X) min queries where X is the domain length.

Template Parameters

T	Signed integral numeric type for coordinates.

Definition at line 529 of file DP_Optimizations.H.

Constructor & Destructor Documentation

◆ Li_Chao_Tree()

template<typename T >

Aleph::Li_Chao_Tree< T >::Li_Chao_Tree	(	const T	x_left,
		const T	x_right
	)

inline

Definition at line 621 of file DP_Optimizations.H.

References ah_domain_error_if, Aleph::Li_Chao_Tree< T >::x_left_, and Aleph::Li_Chao_Tree< T >::x_right_.

Member Function Documentation

◆ add_line()

template<typename T >

void Aleph::Li_Chao_Tree< T >::add_line	(	const T	slope,
		const T	intercept
	)

inline

Definition at line 638 of file DP_Optimizations.H.

References Aleph::Li_Chao_Tree< T >::add_line_impl(), Aleph::intercept(), Aleph::Li_Chao_Tree< T >::new_node(), Aleph::Li_Chao_Tree< T >::NIL, Aleph::Li_Chao_Tree< T >::root_, Aleph::Li_Chao_Tree< T >::x_left_, and Aleph::Li_Chao_Tree< T >::x_right_.

◆ add_line_impl()

template<typename T >

void Aleph::Li_Chao_Tree< T >::add_line_impl	(	const size_t	idx,
		const T	l,
		const T	r,
		Line	line
	)

inlineprivate

Definition at line 570 of file DP_Optimizations.H.

References Aleph::Li_Chao_Tree< T >::add_line_impl(), Aleph::divide_and_conquer_partition_dp(), l, Aleph::Li_Chao_Tree< T >::new_node(), Aleph::Li_Chao_Tree< T >::NIL, Aleph::Li_Chao_Tree< T >::nodes_, r, and Aleph::Li_Chao_Tree< T >::Line::value_at().

Referenced by Aleph::Li_Chao_Tree< T >::add_line(), and Aleph::Li_Chao_Tree< T >::add_line_impl().

◆ clear()

template<typename T >

void Aleph::Li_Chao_Tree< T >::clear ( )

inline

Definition at line 631 of file DP_Optimizations.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Li_Chao_Tree< T >::NIL, Aleph::Li_Chao_Tree< T >::nodes_, Aleph::Li_Chao_Tree< T >::root_, and Aleph::Array< T >::swap().

◆ is_empty()

template<typename T >

bool Aleph::Li_Chao_Tree< T >::is_empty ( ) const

inlinenoexcept

Definition at line 628 of file DP_Optimizations.H.

References Aleph::Li_Chao_Tree< T >::NIL, and Aleph::Li_Chao_Tree< T >::root_.

◆ new_node()

template<typename T >

size_t Aleph::Li_Chao_Tree< T >::new_node ( const Line & line )

inlineprivate

Definition at line 564 of file DP_Optimizations.H.

References Aleph::Li_Chao_Tree< T >::NIL, and Aleph::Li_Chao_Tree< T >::nodes_.

Referenced by Aleph::Li_Chao_Tree< T >::add_line(), and Aleph::Li_Chao_Tree< T >::add_line_impl().

◆ node_count()

template<typename T >

size_t Aleph::Li_Chao_Tree< T >::node_count ( ) const

inlinenoexcept

Definition at line 629 of file DP_Optimizations.H.

References Aleph::Li_Chao_Tree< T >::nodes_.

◆ query()

template<typename T >

T Aleph::Li_Chao_Tree< T >::query ( const T x ) const

inline

Definition at line 649 of file DP_Optimizations.H.

References ah_out_of_range_error_if, ah_runtime_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Li_Chao_Tree< T >::NIL, Aleph::Li_Chao_Tree< T >::query_impl(), Aleph::Li_Chao_Tree< T >::root_, Aleph::Li_Chao_Tree< T >::x_left_, and Aleph::Li_Chao_Tree< T >::x_right_.

◆ query_impl()

template<typename T >

T Aleph::Li_Chao_Tree< T >::query_impl	(	const size_t	idx,
		const T	l,
		const T	r,
		const T	x
	)		const

inlineprivate

Definition at line 602 of file DP_Optimizations.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), l, Aleph::Li_Chao_Tree< T >::NIL, Aleph::Li_Chao_Tree< T >::nodes_, Aleph::Li_Chao_Tree< T >::query_impl(), and r.

Referenced by Aleph::Li_Chao_Tree< T >::query(), and Aleph::Li_Chao_Tree< T >::query_impl().

Member Data Documentation

◆ NIL

template<typename T >

constexpr size_t Aleph::Li_Chao_Tree< T >::NIL = std::numeric_limits<size_t>::max()

staticconstexprprivate

Definition at line 557 of file DP_Optimizations.H.

Referenced by Aleph::Li_Chao_Tree< T >::add_line(), Aleph::Li_Chao_Tree< T >::add_line_impl(), Aleph::Li_Chao_Tree< T >::clear(), Aleph::Li_Chao_Tree< T >::is_empty(), Aleph::Li_Chao_Tree< T >::new_node(), Aleph::Li_Chao_Tree< T >::query(), and Aleph::Li_Chao_Tree< T >::query_impl().

◆ nodes_

template<typename T >

Array<Node> Aleph::Li_Chao_Tree< T >::nodes_

private

Definition at line 561 of file DP_Optimizations.H.

Referenced by Aleph::Li_Chao_Tree< T >::add_line_impl(), Aleph::Li_Chao_Tree< T >::clear(), Aleph::Li_Chao_Tree< T >::new_node(), Aleph::Li_Chao_Tree< T >::node_count(), and Aleph::Li_Chao_Tree< T >::query_impl().

◆ root_

template<typename T >

size_t Aleph::Li_Chao_Tree< T >::root_ = NIL

private

Definition at line 562 of file DP_Optimizations.H.

Referenced by Aleph::Li_Chao_Tree< T >::add_line(), Aleph::Li_Chao_Tree< T >::clear(), Aleph::Li_Chao_Tree< T >::is_empty(), and Aleph::Li_Chao_Tree< T >::query().

◆ x_left_

template<typename T >

T Aleph::Li_Chao_Tree< T >::x_left_

private

Definition at line 559 of file DP_Optimizations.H.

Referenced by Aleph::Li_Chao_Tree< T >::Li_Chao_Tree(), Aleph::Li_Chao_Tree< T >::add_line(), and Aleph::Li_Chao_Tree< T >::query().

◆ x_right_

template<typename T >

T Aleph::Li_Chao_Tree< T >::x_right_

private

Definition at line 560 of file DP_Optimizations.H.

Referenced by Aleph::Li_Chao_Tree< T >::Li_Chao_Tree(), Aleph::Li_Chao_Tree< T >::add_line(), and Aleph::Li_Chao_Tree< T >::query().

The documentation for this class was generated from the following file:

DP_Optimizations.H

Aleph
Li_Chao_Tree
Generated by 1.9.8