sux::util::FenwickBitF< BOUND, AT > Class Template Reference

#include <FenwickBitF.hpp>

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

Public Member Functions
	FenwickBitF ()
	FenwickBitF (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	trimToFit ()
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)
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)
static constexpr size_t	STARTING_OFFSET = 1
static constexpr size_t	END_PADDING = 56

Protected Attributes
Vector< uint8_t, AT >	Tree
size_t	Size

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

Detailed Description

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

A bit-compressed Fenwick tree in classical 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

FenwickBitF() [1/2]

template<size_t BOUND, AllocType AT = MALLOC>

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

inline

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

FenwickBitF() [2/2]

template<size_t BOUND, AllocType AT = MALLOC>

sux::util::FenwickBitF< BOUND, AT >::FenwickBitF ( 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::FenwickBitF< 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::FenwickBitF< 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::FenwickBitF< 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::FenwickBitF< 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::FenwickBitF< 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::FenwickBitF< 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::FenwickBitF< 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::FenwickBitF< 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::FenwickBitF< 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::FenwickBitF< 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::FenwickBitF< 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::FenwickBitF< 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::FenwickBitF< 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>

virtual void sux::util::FenwickBitF< BOUND, AT >::trimToFit ( )

inlinevirtual

Friends And Related Function Documentation

operator<<

template<size_t BOUND, AllocType AT = MALLOC>

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

friend

operator>>

template<size_t BOUND, AllocType AT = MALLOC>

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

friend

Member Data Documentation

BOUNDSIZE

template<size_t BOUND, AllocType AT = MALLOC>

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

staticconstexpr

END_PADDING

template<size_t BOUND, AllocType AT = MALLOC>

constexpr size_t sux::util::FenwickBitF< BOUND, AT >::END_PADDING = 56

staticconstexpr

Size

template<size_t BOUND, AllocType AT = MALLOC>

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

protected

STARTING_OFFSET

template<size_t BOUND, AllocType AT = MALLOC>

constexpr size_t sux::util::FenwickBitF< BOUND, AT >::STARTING_OFFSET = 1

staticconstexpr

Tree

template<size_t BOUND, AllocType AT = MALLOC>

Vector<uint8_t, AT> sux::util::FenwickBitF< BOUND, AT >::Tree

protected

---

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

• sux/util/FenwickBitF.hpp