Sparse Table over an arbitrary associative and idempotent binary operation. More...

#include <tpl_sparse_table.H>

Inheritance diagram for Aleph::Gen_Sparse_Table< T, Op >:

Collaboration diagram for Aleph::Gen_Sparse_Table< T, Op >:

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

Public Member Functions
	Gen_Sparse_Table (const size_t num, const T &init_val, Op oper=Op())
	Construct a sparse table with `num` elements, all equal to `init_val`.

	Gen_Sparse_Table (std::initializer_list< T > il, Op oper=Op())
	Construct from an initializer list in O(n log n) time.

	Gen_Sparse_Table (const Array< T > &values, Op oper=Op())
	Construct from an Array<T> in O(n log n) time.

	Gen_Sparse_Table (const std::vector< T > &values, Op oper=Op())
	Construct from a std::vector<T> in O(n log n) time.

	Gen_Sparse_Table (const DynList< T > &values, Op oper=Op())
	Construct from a DynList<T> in O(n log n) time.

	Gen_Sparse_Table (const Gen_Sparse_Table &)=default

	Gen_Sparse_Table (Gen_Sparse_Table &&) noexcept(std::is_nothrow_move_constructible_v< Array< T > > &&std::is_nothrow_move_constructible_v< Op >)=default

Gen_Sparse_Table &	operator= (const Gen_Sparse_Table &)=default

Gen_Sparse_Table &	operator= (Gen_Sparse_Table &&) noexcept(std::is_nothrow_move_assignable_v< Array< T > > &&std::is_nothrow_move_assignable_v< Op >)=default

T	query (const size_t l, const size_t r) const
	Range query over `[l, r]` in O(1).

T	get (const size_t i) const
	Retrieve the value `a[i]` in O(1).

constexpr size_t	size () const noexcept
	Number of logical elements.

constexpr bool	is_empty () const noexcept
	True if the table contains no elements.

constexpr size_t	num_levels () const noexcept
	Number of precomputed levels (floor(log2(n)) + 1).

Array< T >	values () const
	Reconstruct all original values into an Array.

void	swap (Gen_Sparse_Table &other) noexcept
	Swap this table with `other` in O(1).

Private Member Functions
T &	at (const size_t k, const size_t i)
	Access table[k][i] (0-based row k, 0-based column i).

const T &	at (const size_t k, const size_t i) const

void	build_log_table ()
	Precompute the log lookup table for lengths [0..n].

void	build_upper_levels ()
	Build levels k >= 1 from already-populated level 0.

template<class Getter >
void	fill_and_build (Getter getter)
	Fill level 0 from a 0-based indexed getter and build higher levels.

template<class AlephIt >
void	fill_from_aleph_it (AlephIt it)
	Fill level 0 from an Aleph-style iterator and build higher levels.

Static Private Member Functions
static constexpr size_t	compute_levels (const size_t nn) noexcept
	Compute levels = floor(log2(n)) + 1; 0 if n == 0.

static constexpr size_t	compute_cells (const size_t nn) noexcept
	Number of flattened cells needed to store all levels.

Private Attributes
Array< T >	table

Array< size_t >	log_tbl

size_t	n = 0

size_t	levels = 0

Op	op

Detailed Description

template<typename T, class Op>
requires SparseTableOp<Op, T>
class Aleph::Gen_Sparse_Table< T, Op >

Sparse Table over an arbitrary associative and idempotent binary operation.

Maintains a precomputed table table[k][i] storing the result of applying Op over the subarray a[i .. i + 2^k - 1]. Since the operation is associative and idempotent, overlapping sub-ranges can be combined in O(1):

\[ \text{query}(l, r) = \text{Op}\bigl( \text{table}[k][l],\; \text{table}[k][r - 2^k + 1] \bigr), \quad k = \lfloor \log_2(r - l + 1) \rfloor \]

Template Parameters

T	element type.
Op	associative and idempotent binary functor.

Example: // Range-GCD sparse table

struct Gcd {

int operator()(int a, int b) const { return std::gcd(a, b); }

};

Gen_Sparse_Table<int, Gcd> st = {12, 6, 9, 3, 15};

int g = st.query(1, 3); // gcd(6, 9, 3) = 3

Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693

Definition at line 168 of file tpl_sparse_table.H.

Member Typedef Documentation

◆ Item_Type

template<typename T , class Op >

using Aleph::Gen_Sparse_Table< T, Op >::Item_Type = T

The type of the element stored in the table.

Definition at line 243 of file tpl_sparse_table.H.

Constructor & Destructor Documentation

◆ Gen_Sparse_Table() [1/7]

template<typename T , class Op >

Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table	(	const size_t	num,
		const T &	init_val,
		Op	oper = `Op()`
	)

inline

Construct a sparse table with num elements, all equal to init_val.

Parameters

num	number of elements.
init_val	value for every position.
oper	associative and idempotent binary functor.

Definition at line 252 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::build_log_table(), Aleph::Gen_Sparse_Table< T, Op >::fill_and_build(), Aleph::maps(), and Aleph::Gen_Sparse_Table< T, Op >::n.

◆ Gen_Sparse_Table() [2/7]

template<typename T , class Op >

Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table	(	std::initializer_list< T >	il,
		Op	oper = `Op()`
	)

inline

Construct from an initializer list in O(n log n) time.

Example: Gen_Sparse_Table<int, Min_Op<int>> st = {3, 1, 4, 1, 5, 9};

assert(st.query(0, 3) == 1); // min(3, 1, 4, 1)

Aleph::Gen_Sparse_Table
Sparse Table over an arbitrary associative and idempotent binary operation.
Definition tpl_sparse_table.H:169

Aleph::Gen_Sparse_Table::query
T query(const size_t l, const size_t r) const
Range query over [l, r] in O(1).
Definition tpl_sparse_table.H:347

Definition at line 270 of file tpl_sparse_table.H.

References StlAlephIterator< SetName >::begin(), Aleph::Gen_Sparse_Table< T, Op >::build_log_table(), Aleph::Gen_Sparse_Table< T, Op >::fill_and_build(), Aleph::maps(), and Aleph::Gen_Sparse_Table< T, Op >::n.

◆ Gen_Sparse_Table() [3/7]

template<typename T , class Op >

Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table	(	const Array< T > &	values,
		Op	oper = `Op()`
	)

inline

Construct from an Array<T> in O(n log n) time.

Parameters

values	source array with the initial element values.
oper	associative and idempotent binary functor.

Definition at line 287 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::build_log_table(), Aleph::Gen_Sparse_Table< T, Op >::fill_and_build(), Aleph::Gen_Sparse_Table< T, Op >::n, and Aleph::Gen_Sparse_Table< T, Op >::values().

◆ Gen_Sparse_Table() [4/7]

template<typename T , class Op >

Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table	(	const std::vector< T > &	values,
		Op	oper = `Op()`
	)

inline

Construct from a std::vector<T> in O(n log n) time.

Parameters

values	source vector with the initial element values.
oper	associative and idempotent binary functor.

Definition at line 301 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::build_log_table(), Aleph::Gen_Sparse_Table< T, Op >::fill_and_build(), Aleph::Gen_Sparse_Table< T, Op >::n, and Aleph::Gen_Sparse_Table< T, Op >::values().

◆ Gen_Sparse_Table() [5/7]

template<typename T , class Op >

Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table	(	const DynList< T > &	values,
		Op	oper = `Op()`
	)

inline

Construct from a DynList<T> in O(n log n) time.

Parameters

values	source list with the initial element values.
oper	associative and idempotent binary functor.

Definition at line 315 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::build_log_table(), Aleph::Gen_Sparse_Table< T, Op >::fill_from_aleph_it(), Aleph::Gen_Sparse_Table< T, Op >::n, and Aleph::Gen_Sparse_Table< T, Op >::values().

◆ Gen_Sparse_Table() [6/7]

template<typename T , class Op >

Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table ( const Gen_Sparse_Table< T, Op > & )

default

◆ Gen_Sparse_Table() [7/7]

template<typename T , class Op >

Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table ( Gen_Sparse_Table< T, Op > && ) const &&

defaultnoexcept

Member Function Documentation

◆ at() [1/2]

template<typename T , class Op >

T & Aleph::Gen_Sparse_Table< T, Op >::at	(	const size_t	k,
		const size_t	i
	)

inlineprivate

Access table[k][i] (0-based row k, 0-based column i).

Definition at line 178 of file tpl_sparse_table.H.

References Aleph::maps(), Aleph::Gen_Sparse_Table< T, Op >::n, and Aleph::Gen_Sparse_Table< T, Op >::table.

Referenced by Aleph::Gen_Sparse_Table< T, Op >::build_upper_levels(), Aleph::Gen_Sparse_Table< T, Op >::fill_and_build(), Aleph::Gen_Sparse_Table< T, Op >::fill_from_aleph_it(), Aleph::Gen_Sparse_Table< T, Op >::get(), Aleph::Gen_Sparse_Table< T, Op >::query(), and Aleph::Gen_Sparse_Table< T, Op >::values().

◆ at() [2/2]

template<typename T , class Op >

const T & Aleph::Gen_Sparse_Table< T, Op >::at	(	const size_t	k,
		const size_t	i
	)		const

inlineprivate

Definition at line 179 of file tpl_sparse_table.H.

References Aleph::maps(), Aleph::Gen_Sparse_Table< T, Op >::n, and Aleph::Gen_Sparse_Table< T, Op >::table.

◆ build_log_table()

template<typename T , class Op >

void Aleph::Gen_Sparse_Table< T, Op >::build_log_table ( )

inlineprivate

Precompute the log lookup table for lengths [0..n].

Definition at line 194 of file tpl_sparse_table.H.

References Aleph::Array< T >::create(), Aleph::Gen_Sparse_Table< T, Op >::log_tbl, and Aleph::Gen_Sparse_Table< T, Op >::n.

Referenced by Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table(), Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table(), Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table(), Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table(), and Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table().

◆ build_upper_levels()

template<typename T , class Op >

void Aleph::Gen_Sparse_Table< T, Op >::build_upper_levels ( )

inlineprivate

Build levels k >= 1 from already-populated level 0.

Definition at line 207 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::at(), Aleph::Gen_Sparse_Table< T, Op >::levels, Aleph::maps(), Aleph::Gen_Sparse_Table< T, Op >::n, and Aleph::Gen_Sparse_Table< T, Op >::op.

Referenced by Aleph::Gen_Sparse_Table< T, Op >::fill_and_build(), and Aleph::Gen_Sparse_Table< T, Op >::fill_from_aleph_it().

◆ compute_cells()

template<typename T , class Op >

static constexpr size_t Aleph::Gen_Sparse_Table< T, Op >::compute_cells ( const size_t nn )

inlinestaticconstexprprivatenoexcept

Number of flattened cells needed to store all levels.

Definition at line 188 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::compute_levels(), and Aleph::maps().

◆ compute_levels()

template<typename T , class Op >

static constexpr size_t Aleph::Gen_Sparse_Table< T, Op >::compute_levels ( const size_t nn )

inlinestaticconstexprprivatenoexcept

Compute levels = floor(log2(n)) + 1; 0 if n == 0.

Definition at line 182 of file tpl_sparse_table.H.

References Aleph::maps().

Referenced by Aleph::Gen_Sparse_Table< T, Op >::compute_cells().

◆ fill_and_build()

template<typename T , class Op >

template<class Getter >

void Aleph::Gen_Sparse_Table< T, Op >::fill_and_build ( Getter getter )

inlineprivate

Fill level 0 from a 0-based indexed getter and build higher levels.

Definition at line 221 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::at(), Aleph::Gen_Sparse_Table< T, Op >::build_upper_levels(), Aleph::maps(), and Aleph::Gen_Sparse_Table< T, Op >::n.

Referenced by Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table(), Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table(), Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table(), and Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table().

◆ fill_from_aleph_it()

template<typename T , class Op >

template<class AlephIt >

void Aleph::Gen_Sparse_Table< T, Op >::fill_from_aleph_it ( AlephIt it )

inlineprivate

Fill level 0 from an Aleph-style iterator and build higher levels.

Definition at line 232 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::at(), and Aleph::Gen_Sparse_Table< T, Op >::build_upper_levels().

Referenced by Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table().

◆ get()

template<typename T , class Op >

T Aleph::Gen_Sparse_Table< T, Op >::get ( const size_t i ) const

inline

Retrieve the value a[i] in O(1).

Equivalent to query(i, i).

Parameters

i	0-based index.

Exceptions

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

Definition at line 365 of file tpl_sparse_table.H.

References ah_out_of_range_error_if, Aleph::Gen_Sparse_Table< T, Op >::at(), and Aleph::Gen_Sparse_Table< T, Op >::n.

Referenced by scenario_range_gcd(), test_boundary_queries_valid(), test_construct_from_array(), test_get_all_elements(), test_get_equals_point_query(), test_get_out_of_range(), test_self_copy_assignment(), test_single_element(), and test_stress_all_point_queries().

◆ is_empty()

template<typename T , class Op >

constexpr bool Aleph::Gen_Sparse_Table< T, Op >::is_empty ( ) const

inlineconstexprnoexcept

True if the table contains no elements.

Definition at line 377 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::n.

Referenced by test_single_element().

◆ num_levels()

template<typename T , class Op >

constexpr size_t Aleph::Gen_Sparse_Table< T, Op >::num_levels ( ) const

inlineconstexprnoexcept

Number of precomputed levels (floor(log2(n)) + 1).

Definition at line 380 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::levels.

Referenced by scenario_range_gcd(), test_num_levels_correctness(), and test_single_element().

◆ operator=() [1/2]

template<typename T , class Op >

Gen_Sparse_Table & Aleph::Gen_Sparse_Table< T, Op >::operator= ( const Gen_Sparse_Table< T, Op > & )

default

◆ operator=() [2/2]

template<typename T , class Op >

Gen_Sparse_Table & Aleph::Gen_Sparse_Table< T, Op >::operator= ( Gen_Sparse_Table< T, Op > && ) &&

defaultnoexcept

◆ query()

template<typename T , class Op >

T Aleph::Gen_Sparse_Table< T, Op >::query	(	const size_t	l,
		const size_t	r
	)		const

inline

Range query over [l, r] in O(1).

Returns Op(a[l], a[l+1], ..., a[r]).

Note: Correctness requires Op to be associative and idempotent.

Parameters

l	0-based left index (inclusive).
r	0-based right index (inclusive).

Returns: result of applying Op over the range.

Exceptions

std::out_of_range if l > r or r >= size().

Definition at line 347 of file tpl_sparse_table.H.

References ah_out_of_range_error_if, Aleph::Gen_Sparse_Table< T, Op >::at(), l, Aleph::Gen_Sparse_Table< T, Op >::log_tbl, Aleph::maps(), Aleph::Gen_Sparse_Table< T, Op >::n, and Aleph::Gen_Sparse_Table< T, Op >::op.

Referenced by scenario_range_gcd(), test_adversarial_plateau_with_dip(), test_adversarial_single_outlier(), test_adversarial_zigzag(), test_all_equal(), test_bitwise_and_stress(), test_bitwise_or_stress(), test_boundary_queries_valid(), test_construct_from_array(), test_construct_from_dynlist(), test_construct_from_initlist(), test_construct_from_vector(), test_construct_uniform_value(), test_copy_assignment(), test_disjoint_split_min(), test_double_values(), test_gcd_known(), test_gcd_stress(), test_get_equals_point_query(), test_idempotent_overlap_split(), test_int_extremes(), test_known_max_array(), test_known_min_array(), test_long_long_values(), test_max_cross_validation(), test_min_cross_validation(), test_move_assignment(), test_negative_values(), test_non_power_of_two_sizes(), test_overlapping_ranges_idempotent(), test_performance_build_large(), test_performance_queries(), test_power_of_two_sizes(), test_query_l_greater_than_r(), test_query_r_out_of_range(), test_self_copy_assignment(), test_self_swap(), test_single_element(), test_single_element_max(), test_sliding_window(), test_stress_all_point_queries(), test_stress_max_small(), test_stress_min_medium(), test_stress_min_small(), and test_swap().

◆ size()

template<typename T , class Op >

constexpr size_t Aleph::Gen_Sparse_Table< T, Op >::size ( ) const

inlineconstexprnoexcept

Number of logical elements.

Definition at line 374 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::n.

Referenced by scenario_range_gcd(), test_construct_from_array(), test_construct_from_dynlist(), test_construct_from_initlist(), test_construct_from_vector(), test_construct_uniform_value(), test_copy_assignment(), test_move_assignment(), test_non_power_of_two_sizes(), test_performance_build(), test_performance_build_large(), test_power_of_two_sizes(), test_self_copy_assignment(), test_self_swap(), test_single_element(), and test_swap().

◆ swap()

template<typename T , class Op >

void Aleph::Gen_Sparse_Table< T, Op >::swap ( Gen_Sparse_Table< T, Op > & other )

inlinenoexcept

Swap this table with other in O(1).

Definition at line 398 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::levels, Aleph::Gen_Sparse_Table< T, Op >::log_tbl, Aleph::maps(), Aleph::Gen_Sparse_Table< T, Op >::n, Aleph::Gen_Sparse_Table< T, Op >::op, Aleph::Array< T >::swap(), and Aleph::Gen_Sparse_Table< T, Op >::table.

Referenced by test_self_swap(), and test_swap().

◆ values()

template<typename T , class Op >

Array< T > Aleph::Gen_Sparse_Table< T, Op >::values ( ) const

inline

Reconstruct all original values into an Array.

O(n).

Definition at line 389 of file tpl_sparse_table.H.

References Aleph::Gen_Sparse_Table< T, Op >::at(), Aleph::Array< T >::create(), Aleph::maps(), and Aleph::Gen_Sparse_Table< T, Op >::n.

Referenced by Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table(), Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table(), Aleph::Gen_Sparse_Table< T, Op >::Gen_Sparse_Table(), and test_values_reconstruction().

Member Data Documentation

◆ levels

template<typename T , class Op >

size_t Aleph::Gen_Sparse_Table< T, Op >::levels = 0

private

Definition at line 173 of file tpl_sparse_table.H.

Referenced by Aleph::Gen_Sparse_Table< T, Op >::build_upper_levels(), Aleph::Gen_Sparse_Table< T, Op >::num_levels(), and Aleph::Gen_Sparse_Table< T, Op >::swap().

◆ log_tbl

template<typename T , class Op >

Array<size_t> Aleph::Gen_Sparse_Table< T, Op >::log_tbl

private

Definition at line 171 of file tpl_sparse_table.H.

Referenced by Aleph::Gen_Sparse_Table< T, Op >::build_log_table(), Aleph::Gen_Sparse_Table< T, Op >::query(), and Aleph::Gen_Sparse_Table< T, Op >::swap().

◆ n

template<typename T , class Op >

size_t Aleph::Gen_Sparse_Table< T, Op >::n = 0

private

Definition at line 172 of file tpl_sparse_table.H.

◆ op

template<typename T , class Op >

Op Aleph::Gen_Sparse_Table< T, Op >::op

private

Definition at line 175 of file tpl_sparse_table.H.

Referenced by Aleph::Gen_Sparse_Table< T, Op >::build_upper_levels(), Aleph::Gen_Sparse_Table< T, Op >::query(), and Aleph::Gen_Sparse_Table< T, Op >::swap().

◆ table

template<typename T , class Op >

Array<T> Aleph::Gen_Sparse_Table< T, Op >::table

private

Definition at line 170 of file tpl_sparse_table.H.

Referenced by Aleph::Gen_Sparse_Table< T, Op >::at(), Aleph::Gen_Sparse_Table< T, Op >::at(), and Aleph::Gen_Sparse_Table< T, Op >::swap().

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

tpl_sparse_table.H

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Item_Type

Constructor & Destructor Documentation

◆ Gen_Sparse_Table() [1/7]

◆ Gen_Sparse_Table() [2/7]

◆ Gen_Sparse_Table() [3/7]

◆ Gen_Sparse_Table() [4/7]

◆ Gen_Sparse_Table() [5/7]

◆ Gen_Sparse_Table() [6/7]

◆ Gen_Sparse_Table() [7/7]

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ build_log_table()

◆ build_upper_levels()

◆ compute_cells()

◆ compute_levels()

◆ fill_and_build()

◆ fill_from_aleph_it()

◆ get()

◆ is_empty()

◆ num_levels()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ query()

◆ size()

◆ swap()

◆ values()

Member Data Documentation

◆ levels

◆ log_tbl

◆ n

◆ op

◆ table