sux::util::SearchablePrefixSums Class Reference

#include <SearchablePrefixSums.hpp>

Inheritance diagram for sux::util::SearchablePrefixSums:

Public Member Functions
virtual	~SearchablePrefixSums ()=default
virtual uint64_t	prefix (size_t length)=0
virtual void	add (size_t idx, int64_t c)=0
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)
virtual void	push (uint64_t val)=0
virtual void	pop ()=0
virtual size_t	size () const =0
virtual size_t	bitCount () const =0

Detailed Description

An interface for classes implementing searchable prefix sums.

A searchable prefix-sums data structure maintains a list of nonnegative values and makes it possible to compute sum of prefixes and find the length of the longest prefix sum smaller than or equal to a given bound.

Indices into the list start (oddly) from 1 and end at size(), included, because the typical implementation is by a Fenwick tree, for which indexing from 1 is natural.

An implementation of SearchablePrefixSums should be serializable and deserializable with:

• friend std::ostream &operator<<(std::ostream &os, const SearchablePrefixSums &ft);
• friend std::istream &operator>>(std::istream &is, SearchablePrefixSums &ft);

Constructor & Destructor Documentation

~SearchablePrefixSums()

virtual sux::util::SearchablePrefixSums::~SearchablePrefixSums ( )

virtualdefault

Member Function Documentation

add()

virtual void sux::util::SearchablePrefixSums::add ( size_t  idx, int64_t  c  )

pure virtual

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.

Implemented in sux::util::FenwickByteL< BOUND, AT >, sux::util::FenwickBitL< BOUND, AT >, sux::util::FenwickFixedL< BOUND, AT >, sux::util::FenwickByteF< BOUND, AT >, sux::util::FenwickBitF< BOUND, AT >, and sux::util::FenwickFixedF< BOUND, AT >.

bitCount()

virtual size_t sux::util::SearchablePrefixSums::bitCount ( ) const

pure virtual

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

Implemented in sux::util::FenwickByteL< BOUND, AT >, sux::util::FenwickBitL< BOUND, AT >, sux::util::FenwickFixedL< BOUND, AT >, sux::util::FenwickByteF< BOUND, AT >, sux::util::FenwickBitF< BOUND, AT >, and sux::util::FenwickFixedF< BOUND, AT >.

compFind() [1/2]

virtual size_t sux::util::SearchablePrefixSums::compFind ( uint64_t *  val )

pure virtual

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.

Implemented in sux::util::FenwickByteL< BOUND, AT >, sux::util::FenwickBitL< BOUND, AT >, sux::util::FenwickFixedL< BOUND, AT >, sux::util::FenwickByteF< BOUND, AT >, sux::util::FenwickBitF< BOUND, AT >, and sux::util::FenwickFixedF< BOUND, AT >.

compFind() [2/2]

size_t sux::util::SearchablePrefixSums::compFind ( uint64_t  val )

inline

find() [1/2]

virtual size_t sux::util::SearchablePrefixSums::find ( uint64_t *  val )

pure virtual

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.

Implemented in sux::util::FenwickByteL< BOUND, AT >, sux::util::FenwickBitL< BOUND, AT >, sux::util::FenwickFixedL< BOUND, AT >, sux::util::FenwickByteF< BOUND, AT >, sux::util::FenwickBitF< BOUND, AT >, and sux::util::FenwickFixedF< BOUND, AT >.

find() [2/2]

size_t sux::util::SearchablePrefixSums::find ( uint64_t  val )

inline

pop()

virtual void sux::util::SearchablePrefixSums::pop ( )

pure virtual

Remove the last value of the sequence.

This method does not release the allocated space.

Implemented in sux::util::FenwickByteL< BOUND, AT >, sux::util::FenwickBitL< BOUND, AT >, sux::util::FenwickFixedL< BOUND, AT >, sux::util::FenwickByteF< BOUND, AT >, sux::util::FenwickBitF< BOUND, AT >, and sux::util::FenwickFixedF< BOUND, AT >.

prefix()

virtual uint64_t sux::util::SearchablePrefixSums::prefix ( size_t  length )

pure virtual

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].

Implemented in sux::util::FenwickBitL< BOUND, AT >, sux::util::FenwickByteL< BOUND, AT >, sux::util::FenwickFixedL< BOUND, AT >, sux::util::FenwickByteF< BOUND, AT >, sux::util::FenwickBitF< BOUND, AT >, and sux::util::FenwickFixedF< BOUND, AT >.

push()

virtual void sux::util::SearchablePrefixSums::push ( uint64_t  val )

pure virtual

Append a value to the sequence

Parameters

val	value to append.

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

Implemented in sux::util::FenwickByteL< BOUND, AT >, sux::util::FenwickBitL< BOUND, AT >, sux::util::FenwickFixedL< BOUND, AT >, sux::util::FenwickBitF< BOUND, AT >, sux::util::FenwickByteF< BOUND, AT >, and sux::util::FenwickFixedF< BOUND, AT >.

size()

virtual size_t sux::util::SearchablePrefixSums::size ( ) const

pure virtual

Returns the length of the sequence (i.e., the size of the tree).

Implemented in sux::util::FenwickByteL< BOUND, AT >, sux::util::FenwickBitL< BOUND, AT >, sux::util::FenwickFixedL< BOUND, AT >, sux::util::FenwickByteF< BOUND, AT >, sux::util::FenwickBitF< BOUND, AT >, and sux::util::FenwickFixedF< BOUND, AT >.

---

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

• sux/util/SearchablePrefixSums.hpp