Aleph::Convex_Hull_Trick< T > Class Template Reference

Convex Hull Trick for minimum queries. More...

#include <DP_Optimizations.H>

Collaboration diagram for Aleph::Convex_Hull_Trick< T >:

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

Public Member Functions
size_t	size () const noexcept
bool	is_empty () const noexcept
void	clear ()
void	reset_query_cursor () noexcept
void	add_line (const T slope, const T intercept)
	Insert a new line; slopes must be non-increasing.
T	query (const T x) const
	Query minimum value at arbitrary x (O(log n)).
T	query_monotone (const T x)
	Query minimum with non-decreasing x (amortized O(1)).

Static Private Member Functions
static long double	intersection_x (const Line &a, const Line &b) noexcept

Private Attributes
Array< Line >	lines_
Array< long double >	starts_
size_t	cursor_ = 0

Detailed Description

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

Convex Hull Trick for minimum queries.

Supports insertion of lines with non-increasing slope and minimum queries over x. Query can be done in O(log n) for arbitrary x or amortized O(1) for non-decreasing x via query_monotone().

Template Parameters

T	Numeric type for slopes and coordinates.

Examples

dp_optimizations_example.cc.

Definition at line 387 of file DP_Optimizations.H.

Member Function Documentation

add_line()

template<typename T >

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

inline

Insert a new line; slopes must be non-increasing.

Examples

dp_optimizations_example.cc.

Definition at line 439 of file DP_Optimizations.H.

References ah_domain_error_if, Aleph::Array< T >::append(), Aleph::Convex_Hull_Trick< T >::cursor_, Aleph::divide_and_conquer_partition_dp(), Aleph::Convex_Hull_Trick< T >::Line::intercept, Aleph::intercept(), Aleph::Convex_Hull_Trick< T >::intersection_x(), Aleph::Convex_Hull_Trick< T >::lines_, Aleph::Array< T >::remove_last(), Aleph::Array< T >::size(), Aleph::Convex_Hull_Trick< T >::Line::slope, and Aleph::Convex_Hull_Trick< T >::starts_.

clear()

template<typename T >

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

inline

Definition at line 422 of file DP_Optimizations.H.

References Aleph::Convex_Hull_Trick< T >::cursor_, Aleph::divide_and_conquer_partition_dp(), Aleph::Convex_Hull_Trick< T >::lines_, Aleph::Convex_Hull_Trick< T >::starts_, and Aleph::Array< T >::swap().

intersection_x()

template<typename T >

static long double Aleph::Convex_Hull_Trick< T >::intersection_x ( const Line &  a, const Line &  b  )

inlinestaticprivatenoexcept

Definition at line 411 of file DP_Optimizations.H.

Referenced by Aleph::Convex_Hull_Trick< T >::add_line().

is_empty()

template<typename T >

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

inlinenoexcept

Definition at line 420 of file DP_Optimizations.H.

References Aleph::Convex_Hull_Trick< T >::lines_.

query()

template<typename T >

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

inline

Query minimum value at arbitrary x (O(log n)).

Examples

dp_optimizations_example.cc.

Definition at line 488 of file DP_Optimizations.H.

References ah_runtime_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Convex_Hull_Trick< T >::lines_, and Aleph::Convex_Hull_Trick< T >::starts_.

query_monotone()

template<typename T >

T Aleph::Convex_Hull_Trick< T >::query_monotone ( const T  x )

inline

Query minimum with non-decreasing x (amortized O(1)).

Definition at line 507 of file DP_Optimizations.H.

References ah_runtime_error_if, Aleph::and, Aleph::Convex_Hull_Trick< T >::cursor_, Aleph::Convex_Hull_Trick< T >::lines_, and Aleph::Convex_Hull_Trick< T >::starts_.

reset_query_cursor()

template<typename T >

void Aleph::Convex_Hull_Trick< T >::reset_query_cursor ( )

inlinenoexcept

Definition at line 433 of file DP_Optimizations.H.

References Aleph::Convex_Hull_Trick< T >::cursor_.

size()

template<typename T >

size_t Aleph::Convex_Hull_Trick< T >::size ( ) const

inlinenoexcept

Definition at line 419 of file DP_Optimizations.H.

References Aleph::Convex_Hull_Trick< T >::lines_.

Member Data Documentation

cursor_

template<typename T >

size_t Aleph::Convex_Hull_Trick< T >::cursor_ = 0

private

Definition at line 409 of file DP_Optimizations.H.

Referenced by Aleph::Convex_Hull_Trick< T >::add_line(), Aleph::Convex_Hull_Trick< T >::clear(), Aleph::Convex_Hull_Trick< T >::query_monotone(), and Aleph::Convex_Hull_Trick< T >::reset_query_cursor().

lines_

template<typename T >

Array<Line> Aleph::Convex_Hull_Trick< T >::lines_

private

Definition at line 407 of file DP_Optimizations.H.

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

starts_

template<typename T >

Array<long double> Aleph::Convex_Hull_Trick< T >::starts_

private

Definition at line 408 of file DP_Optimizations.H.

Referenced by Aleph::Convex_Hull_Trick< T >::add_line(), Aleph::Convex_Hull_Trick< T >::clear(), Aleph::Convex_Hull_Trick< T >::query(), and Aleph::Convex_Hull_Trick< T >::query_monotone().

---

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

• DP_Optimizations.H