#include <FenwickFixedL.hpp>

Inheritance diagram for sux::util::FenwickFixedL< BOUND, AT >:

Public Member Functions
	FenwickFixedL ()

	FenwickFixedL (uint64_t sequence[], size_t size)

virtual uint64_t	prefix (size_t idx)

virtual void	add (size_t idx, int64_t inc)

virtual size_t	find (uint64_t *val)

virtual size_t	compFind (uint64_t *val)

virtual void	push (uint64_t val)

virtual void	pop ()

virtual void	grow (size_t space)

virtual void	reserve (size_t space)

virtual void	trim (size_t space)

virtual void	resize (size_t space)

virtual void	size (size_t space)

virtual size_t	size () const

virtual size_t	bitCount () const

virtual size_t	find (uint64_t *val)=0

size_t	find (uint64_t val)

virtual size_t	compFind (uint64_t *val)=0

size_t	compFind (uint64_t val)

void	trimToFit ()

Public Member Functions inherited from sux::util::SearchablePrefixSums
virtual	~SearchablePrefixSums ()=default

size_t	find (uint64_t val)

size_t	compFind (uint64_t val)

Public Member Functions inherited from sux::util::Expandable
void	trimToFit ()

Static Public Attributes
static constexpr size_t	BOUNDSIZE = ceil_log2_plus1(BOUND)

Protected Attributes
Vector< uint64_t, AT >	Tree [64]

size_t	Levels

size_t	Size

Friends
std::ostream &	operator<< (std::ostream &os, const FenwickFixedL< BOUND, AT > &ft)

std::istream &	operator>> (std::istream &is, FenwickFixedL< BOUND, AT > &ft)

Detailed Description

template<size_t BOUND, AllocType AT = MALLOC>
class sux::util::FenwickFixedL< BOUND, AT >

A standard (fixed-size) Fenwick tree in level-order layout.

Template Parameters

BOUND	maximum representable value (at most the maximum value of a `uint64_t`).
AT	a type of memory allocation out of AllocType.

Constructor & Destructor Documentation

◆ FenwickFixedL() [1/2]

template<size_t BOUND, AllocType AT = MALLOC>

sux::util::FenwickFixedL< BOUND, AT >::FenwickFixedL ( )

inline

Creates a new instance with no values (empty tree).

◆ FenwickFixedL() [2/2]

template<size_t BOUND, AllocType AT = MALLOC>

sux::util::FenwickFixedL< BOUND, AT >::FenwickFixedL	(	uint64_t	sequence[],
		size_t	size
	)

inline

Creates a new instance with given vector of values.

Note that the provided sequence is read at construction time but it will not be referenced afterwards.

Parameters

sequence	a sequence of nonnegative integers smaller than or equal to the template parameter `BOUND`.
size	the number of elements in the sequence.

Member Function Documentation

◆ add()

template<size_t BOUND, AllocType AT = MALLOC>

virtual void sux::util::FenwickFixedL< BOUND, AT >::add	(	size_t	idx,
		int64_t	c
	)

inlinevirtual

Increment an element of the sequence (not the tree).

Parameters

idx	index of the element.
c	value to sum.

You are allowed to use negative values for the increment, but elements of of the sequence must remain all nonnegative.

Implements sux::util::SearchablePrefixSums.

◆ bitCount()

template<size_t BOUND, AllocType AT = MALLOC>

virtual size_t sux::util::FenwickFixedL< BOUND, AT >::bitCount ( ) const

inlinevirtual

Returns an estimate of the size (in bits) of this structure.

Implements sux::util::SearchablePrefixSums.

◆ compFind() [1/3]

template<size_t BOUND, AllocType AT = MALLOC>

virtual size_t sux::util::FenwickFixedL< BOUND, AT >::compFind ( uint64_t * val )

inlinevirtual

Search the length of the longest prefix whose complemented sum is less than or equal to a given bound.

Parameters

val	bound for the complemented prefix sum.

If val is an l-value reference its value will be replaced with the excess, that is, the difference between val and the complemented longest prefix sum described above.

This method returns zero if there are no prefixes whose complemented sum is greater or equal to val.

Implements sux::util::SearchablePrefixSums.

◆ compFind() [2/3]

template<size_t BOUND, AllocType AT = MALLOC>

virtual size_t sux::util::SearchablePrefixSums::compFind

Search the length of the longest prefix whose complemented sum is less than or equal to a given bound.

Parameters

val	bound for the complemented prefix sum.

If val is an l-value reference its value will be replaced with the excess, that is, the difference between val and the complemented longest prefix sum described above.

This method returns zero if there are no prefixes whose complemented sum is greater or equal to val.

◆ compFind() [3/3]

template<size_t BOUND, AllocType AT = MALLOC>

size_t sux::util::SearchablePrefixSums::compFind

inline

◆ find() [1/3]

template<size_t BOUND, AllocType AT = MALLOC>

virtual size_t sux::util::FenwickFixedL< BOUND, AT >::find ( uint64_t * val )

inlinevirtual

Search the length of the longest prefix whose sum is less than or equal to a given bound.

Parameters

val	bound for the prefix sum.

If val is an l-value reference its value will be replaced with the excess, that is, the difference between val and the longest prefix sum described above.

This method returns zero if there are no prefixes whose sum is greater or equal to val.

Implements sux::util::SearchablePrefixSums.

◆ find() [2/3]

template<size_t BOUND, AllocType AT = MALLOC>

virtual size_t sux::util::SearchablePrefixSums::find

Search the length of the longest prefix whose sum is less than or equal to a given bound.

Parameters

val	bound for the prefix sum.

If val is an l-value reference its value will be replaced with the excess, that is, the difference between val and the longest prefix sum described above.

This method returns zero if there are no prefixes whose sum is greater or equal to val.

◆ find() [3/3]

template<size_t BOUND, AllocType AT = MALLOC>

size_t sux::util::SearchablePrefixSums::find

inline

◆ grow()

template<size_t BOUND, AllocType AT = MALLOC>

virtual void sux::util::FenwickFixedL< BOUND, AT >::grow ( size_t capacity )

inlinevirtual

Enlarges this expandable so that it can contain a given number of elements, plus possibly extra space.

If the current capacity is sufficient, nothing happens. Otherwise, the expandable is enlarged, usually to the maximum between the provided capacity and 50% more than the current capacity.

Parameters

capacity the desired new capacity.

Implements sux::util::Expandable.

◆ pop()

template<size_t BOUND, AllocType AT = MALLOC>

virtual void sux::util::FenwickFixedL< BOUND, AT >::pop ( )

inlinevirtual

Remove the last value of the sequence.

This method does not release the allocated space.

Implements sux::util::SearchablePrefixSums.

◆ prefix()

template<size_t BOUND, AllocType AT = MALLOC>

virtual uint64_t sux::util::FenwickFixedL< BOUND, AT >::prefix ( size_t length )

inlinevirtual

Compute the prefix sum.

Parameters

length length of the prefix sum (from 0 to size(), included).

Returns: the sum of the elements in the range (0 .. length].

Implements sux::util::SearchablePrefixSums.

◆ push()

template<size_t BOUND, AllocType AT = MALLOC>

virtual void sux::util::FenwickFixedL< BOUND, AT >::push ( uint64_t val )

inlinevirtual

Append a value to the sequence

Parameters

val	value to append.

Append a new value to the sequence and update the tree.

Implements sux::util::SearchablePrefixSums.

◆ reserve()

template<size_t BOUND, AllocType AT = MALLOC>

virtual void sux::util::FenwickFixedL< BOUND, AT >::reserve ( size_t capacity )

inlinevirtual

Enlarges this expandable so that it can contain a given number of elements without memory reallocation.

If the current capacity is sufficient, nothing happens. Otherwise, the expandable is enlarged to the provided capacity.

Parameters

capacity the desired new capacity.

Implements sux::util::Expandable.

◆ resize()

template<size_t BOUND, AllocType AT = MALLOC>

virtual void sux::util::FenwickFixedL< BOUND, AT >::resize ( size_t size )

inlinevirtual

Changes the expandable size to the given value.

If the argument is smaller than or equal to the current size, there is no memory reallocation. Otherwise, reallocation happens with grow().

Parameters

size	the desired new size.

Implements sux::util::Expandable.

◆ size() [1/2]

template<size_t BOUND, AllocType AT = MALLOC>

virtual size_t sux::util::FenwickFixedL< BOUND, AT >::size ( ) const

inlinevirtual

Returns the number of elements in this expandable.

Implements sux::util::Expandable.

◆ size() [2/2]

template<size_t BOUND, AllocType AT = MALLOC>

virtual void sux::util::FenwickFixedL< BOUND, AT >::size ( size_t size )

inlinevirtual

Changes the expandable size and capacity to the given value.

Parameters

size	the desired new size and capacity.

Implements sux::util::Expandable.

◆ trim()

template<size_t BOUND, AllocType AT = MALLOC>

virtual void sux::util::FenwickFixedL< BOUND, AT >::trim ( size_t capacity )

inlinevirtual

Trims the data structure to the given capacity

provided it is larger than the current size.

Parameters

capacity the new desired capacity.

Implements sux::util::Expandable.

◆ trimToFit()

template<size_t BOUND, AllocType AT = MALLOC>

void sux::util::Expandable::trimToFit

inline

Trims the the memory allocated so that size and capacity are the same.

Friends And Related Function Documentation

◆ operator<<

template<size_t BOUND, AllocType AT = MALLOC>

std::ostream& operator<<	(	std::ostream &	os,
		const FenwickFixedL< BOUND, AT > &	ft
	)

friend

◆ operator>>

template<size_t BOUND, AllocType AT = MALLOC>

std::istream& operator>>	(	std::istream &	is,
		FenwickFixedL< BOUND, AT > &	ft
	)

friend

Member Data Documentation

◆ BOUNDSIZE

template<size_t BOUND, AllocType AT = MALLOC>

constexpr size_t sux::util::FenwickFixedL< BOUND, AT >::BOUNDSIZE = ceil_log2_plus1(BOUND)

staticconstexpr

◆ Levels

template<size_t BOUND, AllocType AT = MALLOC>

size_t sux::util::FenwickFixedL< BOUND, AT >::Levels

protected

◆ Size

template<size_t BOUND, AllocType AT = MALLOC>

size_t sux::util::FenwickFixedL< BOUND, AT >::Size

protected

◆ Tree

template<size_t BOUND, AllocType AT = MALLOC>

Vector<uint64_t, AT> sux::util::FenwickFixedL< BOUND, AT >::Tree[64]

protected

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

sux/util/FenwickFixedL.hpp

Public Member Functions

Static Public Attributes

Protected Attributes

Friends

Detailed Description

template<size_t BOUND, AllocType AT = MALLOC> class sux::util::FenwickFixedL< BOUND, AT >

Constructor & Destructor Documentation

◆ FenwickFixedL() [1/2]

◆ FenwickFixedL() [2/2]

Member Function Documentation

◆ add()

◆ bitCount()

◆ compFind() [1/3]

◆ compFind() [2/3]

◆ compFind() [3/3]

◆ find() [1/3]

◆ find() [2/3]

◆ find() [3/3]

◆ grow()

◆ pop()

◆ prefix()

◆ push()

◆ reserve()

◆ resize()

◆ size() [1/2]

◆ size() [2/2]

◆ trim()

◆ trimToFit()

Friends And Related Function Documentation

◆ operator<<

◆ operator>>

Member Data Documentation

◆ BOUNDSIZE

◆ Levels

◆ Size

◆ Tree

template<size_t BOUND, AllocType AT = MALLOC>
class sux::util::FenwickFixedL< BOUND, AT >