Sux
Public Member Functions | Static Public Attributes | Protected Attributes | Friends | List of all members
sux::util::FenwickBitF< BOUND, AT > Class Template Reference

#include <FenwickBitF.hpp>

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

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
BOUNDmaximum representable value (at most the maximum value of a uint64_t).
ATa 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
sequencea sequence of nonnegative integers smaller than or equal to the template parameter BOUND.
sizethe 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
idxindex of the element.
cvalue 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
valbound 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
valbound 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
valbound 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
valbound 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
capacitythe 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
lengthlength 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
valvalue 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
capacitythe 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
sizethe 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
sizethe 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
capacitythe 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: