Disjoint Sparse Table over an arbitrary associative binary operation. More...

#include <tpl_disjoint_sparse_table.H>

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

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

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

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

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

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

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

	Gen_Disjoint_Sparse_Table (const Gen_Disjoint_Sparse_Table &)=default

	Gen_Disjoint_Sparse_Table (Gen_Disjoint_Sparse_Table &&) noexcept=default

Gen_Disjoint_Sparse_Table &	operator= (const Gen_Disjoint_Sparse_Table &)=default

Gen_Disjoint_Sparse_Table &	operator= (Gen_Disjoint_Sparse_Table &&) noexcept=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.

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

void	swap (Gen_Disjoint_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 ()
	Build the disjoint sparse table from the data array.

template<class Getter >
void	fill_data (Getter getter)
	Fill data array from a 0-based indexed getter.

template<class AlephIt >
void	fill_data_from_aleph_it (AlephIt it)
	Fill data array from an Aleph-style iterator.

Static Private Member Functions
static constexpr size_t	compute_levels (const size_t nn) noexcept
	Compute the number of levels for n elements.

Private Attributes
Array< T >	data

Array< T >	table

size_t	n = 0

size_t	levels = 0

Op	op

Detailed Description

template<typename T, class Op>
requires DisjointSparseTableOp<Op, T>
class Aleph::Gen_Disjoint_Sparse_Table< T, Op >

Disjoint Sparse Table over an arbitrary associative binary operation.

The structure decomposes the array into disjoint blocks at each level and stores prefix/suffix aggregates from each block's midpoint. For a query [l, r] with l != r, the answer is obtained by combining the suffix aggregate ending at l with the prefix aggregate starting at r, both relative to the block midpoint at the appropriate level:

\[ \text{query}(l, r) = \text{Op}\bigl( \text{suffix}[k][l],\; \text{prefix}[k][r] \bigr), \quad k = \lfloor \log_2(l \oplus r) \rfloor \]

Because the sub-ranges are disjoint (non-overlapping), the operation need not be idempotent — only associative.

Template Parameters

T	element type.
Op	associative binary functor.

Example: // Range-sum disjoint sparse table

Gen_Disjoint_Sparse_Table<int, Aleph::plus<int>> st = {3, 1, 4, 1, 5};

int s = st.query(1, 3); // 1 + 4 + 1 = 6

Aleph::Gen_Disjoint_Sparse_Table
Disjoint Sparse Table over an arbitrary associative binary operation.
Definition tpl_disjoint_sparse_table.H:157

Aleph::Gen_Disjoint_Sparse_Table::query
T query(const size_t l, const size_t r) const
Range query over [l, r] in O(1).
Definition tpl_disjoint_sparse_table.H:351

Definition at line 156 of file tpl_disjoint_sparse_table.H.

Member Typedef Documentation

◆ Item_Type

template<typename T , class Op >

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

The type of the element stored in the table.

Definition at line 240 of file tpl_disjoint_sparse_table.H.

Constructor & Destructor Documentation

◆ Gen_Disjoint_Sparse_Table() [1/7]

template<typename T , class Op >

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

inline

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

Parameters

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

Definition at line 249 of file tpl_disjoint_sparse_table.H.

References Aleph::Gen_Disjoint_Sparse_Table< T, Op >::build(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::fill_data(), and Aleph::maps().

◆ Gen_Disjoint_Sparse_Table() [2/7]

template<typename T , class Op >

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

inline

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

Example: Gen_Disjoint_Sparse_Table<int, Aleph::plus<int>> st = {3, 1, 4, 1, 5};

assert(st.query(0, 4) == 14); // 3 + 1 + 4 + 1 + 5

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

Definition at line 268 of file tpl_disjoint_sparse_table.H.

References StlAlephIterator< SetName >::begin(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::build(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::fill_data(), and Aleph::maps().

◆ Gen_Disjoint_Sparse_Table() [3/7]

template<typename T , class Op >

Aleph::Gen_Disjoint_Sparse_Table< T, Op >::Gen_Disjoint_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 binary functor.

Definition at line 284 of file tpl_disjoint_sparse_table.H.

References Aleph::Gen_Disjoint_Sparse_Table< T, Op >::build(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::fill_data(), and Aleph::Gen_Disjoint_Sparse_Table< T, Op >::values().

◆ Gen_Disjoint_Sparse_Table() [4/7]

template<typename T , class Op >

Aleph::Gen_Disjoint_Sparse_Table< T, Op >::Gen_Disjoint_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 binary functor.

Definition at line 300 of file tpl_disjoint_sparse_table.H.

References Aleph::Gen_Disjoint_Sparse_Table< T, Op >::build(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::fill_data(), and Aleph::Gen_Disjoint_Sparse_Table< T, Op >::values().

◆ Gen_Disjoint_Sparse_Table() [5/7]

template<typename T , class Op >

Aleph::Gen_Disjoint_Sparse_Table< T, Op >::Gen_Disjoint_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 binary functor.

Definition at line 317 of file tpl_disjoint_sparse_table.H.

References Aleph::Gen_Disjoint_Sparse_Table< T, Op >::build(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::fill_data_from_aleph_it(), and Aleph::Gen_Disjoint_Sparse_Table< T, Op >::values().

◆ Gen_Disjoint_Sparse_Table() [6/7]

template<typename T , class Op >

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

default

◆ Gen_Disjoint_Sparse_Table() [7/7]

template<typename T , class Op >

Aleph::Gen_Disjoint_Sparse_Table< T, Op >::Gen_Disjoint_Sparse_Table ( Gen_Disjoint_Sparse_Table< T, Op > && )

defaultnoexcept

Member Function Documentation

◆ at() [1/2]

template<typename T , class Op >

T & Aleph::Gen_Disjoint_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 166 of file tpl_disjoint_sparse_table.H.

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

Referenced by Aleph::Gen_Disjoint_Sparse_Table< T, Op >::build(), and Aleph::Gen_Disjoint_Sparse_Table< T, Op >::query().

◆ at() [2/2]

template<typename T , class Op >

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

inlineprivate

Definition at line 167 of file tpl_disjoint_sparse_table.H.

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

◆ build()

template<typename T , class Op >

void Aleph::Gen_Disjoint_Sparse_Table< T, Op >::build ( )

inlineprivate

Build the disjoint sparse table from the data array.

For each level k (block size 2^(k+1), half = 2^k):

Compute suffix aggregates from midpoint-1 going left.
Compute prefix aggregates from midpoint going right.

Definition at line 189 of file tpl_disjoint_sparse_table.H.

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

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

◆ compute_levels()

template<typename T , class Op >

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

inlinestaticconstexprprivatenoexcept

Compute the number of levels for n elements.

For n <= 1 no levels are needed (single-element queries use data directly). For n >= 2, levels = bit_width(n - 1).

Definition at line 177 of file tpl_disjoint_sparse_table.H.

References Aleph::maps().

◆ fill_data()

template<typename T , class Op >

template<class Getter >

void Aleph::Gen_Disjoint_Sparse_Table< T, Op >::fill_data ( Getter getter )

inlineprivate

Fill data array from a 0-based indexed getter.

Definition at line 223 of file tpl_disjoint_sparse_table.H.

References Aleph::Gen_Disjoint_Sparse_Table< T, Op >::data, Aleph::maps(), and Aleph::Gen_Disjoint_Sparse_Table< T, Op >::n.

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

◆ fill_data_from_aleph_it()

template<typename T , class Op >

template<class AlephIt >

void Aleph::Gen_Disjoint_Sparse_Table< T, Op >::fill_data_from_aleph_it ( AlephIt it )

inlineprivate

Fill data array from an Aleph-style iterator.

Definition at line 231 of file tpl_disjoint_sparse_table.H.

References Aleph::Gen_Disjoint_Sparse_Table< T, Op >::data.

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

◆ get()

template<typename T , class Op >

T Aleph::Gen_Disjoint_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 372 of file tpl_disjoint_sparse_table.H.

References ah_out_of_range_error_if, Aleph::Gen_Disjoint_Sparse_Table< T, Op >::data, and Aleph::Gen_Disjoint_Sparse_Table< T, Op >::n.

Referenced by test_boundary_queries_no_throw(), test_exception_get_out_of_range(), test_get_all_elements(), test_get_equals_point_query(), test_prefix_sum_consistency(), test_self_copy_assignment(), test_single_element_sum(), test_stress_point_queries(), and test_string_concatenation().

◆ is_empty()

template<typename T , class Op >

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

inlineconstexprnoexcept

True if the table contains no elements.

Definition at line 385 of file tpl_disjoint_sparse_table.H.

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

Referenced by test_single_element_sum().

◆ num_levels()

template<typename T , class Op >

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

inlineconstexprnoexcept

Number of precomputed levels.

Definition at line 388 of file tpl_disjoint_sparse_table.H.

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

Referenced by test_single_element_sum().

◆ operator=() [1/2]

template<typename T , class Op >

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

default

◆ operator=() [2/2]

template<typename T , class Op >

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

defaultnoexcept

◆ query()

template<typename T , class Op >

T Aleph::Gen_Disjoint_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. Idempotency is not required.

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 351 of file tpl_disjoint_sparse_table.H.

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

Referenced by test_adversarial_plateau_with_spike(), test_adversarial_single_outlier(), test_adversarial_zigzag(), test_all_equal(), test_boundary_queries_no_throw(), test_construct_from_array(), test_construct_from_dynlist(), test_construct_from_init_list(), test_construct_from_vector(), test_construct_uniform(), test_copy_assignment(), test_double_product(), test_double_sum(), test_exception_l_greater_than_r(), test_exception_r_out_of_range(), test_get_equals_point_query(), test_int_limits(), test_known_product_array(), test_known_sum_array(), test_move_assignment(), test_negative_values(), test_non_power_of_two_sizes(), test_perf_queries(), test_power_of_two_sizes(), test_prefix_sum_consistency(), test_self_copy_assignment(), test_self_swap(), test_single_element_product(), test_single_element_sum(), test_sliding_window(), test_sorted_ascending(), test_sorted_descending(), test_splitting_composability(), test_splitting_product(), test_stress_double_sum(), test_stress_exhaustive_small(), test_stress_point_queries(), test_stress_product_small(), test_stress_sum_large(), test_stress_sum_small(), test_string_concatenation(), test_string_stress(), test_swap(), test_two_elements(), test_xor_known(), and test_xor_stress().

◆ size()

template<typename T , class Op >

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

inlineconstexprnoexcept

Number of logical elements.

Definition at line 382 of file tpl_disjoint_sparse_table.H.

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

Referenced by test_copy_assignment(), test_move_assignment(), test_non_power_of_two_sizes(), test_perf_build(), test_perf_build_large(), test_power_of_two_sizes(), test_self_copy_assignment(), test_self_swap(), test_single_element_sum(), and test_swap().

◆ swap()

template<typename T , class Op >

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

inlinenoexcept

Swap this table with other in O(1).

Definition at line 406 of file tpl_disjoint_sparse_table.H.

References Aleph::Gen_Disjoint_Sparse_Table< T, Op >::data, Aleph::Gen_Disjoint_Sparse_Table< T, Op >::levels, Aleph::maps(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::n, Aleph::Gen_Disjoint_Sparse_Table< T, Op >::op, and Aleph::Gen_Disjoint_Sparse_Table< T, Op >::table.

Referenced by test_self_swap(), and test_swap().

◆ values()

template<typename T , class Op >

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

inline

Reconstruct all original values into an Array.

O(n).

Definition at line 397 of file tpl_disjoint_sparse_table.H.

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

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

Member Data Documentation

◆ data

template<typename T , class Op >

Array<T> Aleph::Gen_Disjoint_Sparse_Table< T, Op >::data

private

Definition at line 158 of file tpl_disjoint_sparse_table.H.

Referenced by Aleph::Gen_Disjoint_Sparse_Table< T, Op >::build(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::fill_data(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::fill_data_from_aleph_it(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::get(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::query(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::swap(), and Aleph::Gen_Disjoint_Sparse_Table< T, Op >::values().

◆ levels

template<typename T , class Op >

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

private

Definition at line 161 of file tpl_disjoint_sparse_table.H.

Referenced by Aleph::Gen_Disjoint_Sparse_Table< T, Op >::build(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::num_levels(), and Aleph::Gen_Disjoint_Sparse_Table< T, Op >::swap().

◆ n

◆ op

template<typename T , class Op >

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

private

Definition at line 163 of file tpl_disjoint_sparse_table.H.

Referenced by Aleph::Gen_Disjoint_Sparse_Table< T, Op >::build(), Aleph::Gen_Disjoint_Sparse_Table< T, Op >::query(), and Aleph::Gen_Disjoint_Sparse_Table< T, Op >::swap().

◆ table

template<typename T , class Op >

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

private

Definition at line 159 of file tpl_disjoint_sparse_table.H.

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

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

tpl_disjoint_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_Disjoint_Sparse_Table() [1/7]

◆ Gen_Disjoint_Sparse_Table() [2/7]

◆ Gen_Disjoint_Sparse_Table() [3/7]

◆ Gen_Disjoint_Sparse_Table() [4/7]

◆ Gen_Disjoint_Sparse_Table() [5/7]

◆ Gen_Disjoint_Sparse_Table() [6/7]

◆ Gen_Disjoint_Sparse_Table() [7/7]

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ build()

◆ compute_levels()

◆ fill_data()

◆ fill_data_from_aleph_it()

◆ get()

◆ is_empty()

◆ num_levels()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ query()

◆ size()

◆ swap()

◆ values()

Member Data Documentation

◆ data

◆ levels

◆ n

◆ op

◆ table