pixie::rmq::utils::SuccinctIncreasingStack Class Reference

Construction-only stack for monotonically increasing integer keys. More...

#include <succinct_monotone_stack.h>

Public Member Functions
	SuccinctIncreasingStack (std::size_t capacity)
bool	empty () const
	Whether the logical stack is empty.
std::size_t	top () const
	Return the current top key.
void	push (std::size_t key)
	Push a key larger than the current top key.
void	pop ()
	Remove the current top key.

Detailed Description

Construction-only stack for monotonically increasing integer keys.

The stack stores the currently live keys in 64-bit blocks and keeps compact summary bitsets for non-empty blocks. It is intended for Cartesian-tree construction passes where pushed keys are strictly increasing. Under that precondition the logical stack top is the largest stored key.

The helper keeps construction memory succinct in the worst case: an input of capacity keys uses one bit per key plus about 1/64 extra summary bits, instead of one full index per live stack entry. It does not own or inspect input values and deliberately does not define the Cartesian-tree tie rule; callers keep their existing pop predicate.

Member Function Documentation

pop()

void pixie::rmq::utils::SuccinctIncreasingStack::pop ( )

inline

Remove the current top key.

Precondition

The stack is not empty.

push()

void pixie::rmq::utils::SuccinctIncreasingStack::push ( std::size_t key )

inline

Push a key larger than the current top key.

Keys are expected to be pushed in strictly increasing order over the lifetime of this stack. The assertion checks the live top, which is the only ordering constraint needed by this bitset representation.

top()

std::size_t pixie::rmq::utils::SuccinctIncreasingStack::top ( ) const

inline

Return the current top key.

Precondition

The stack is not empty.

---

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

• include/pixie/rmq/utils/succinct_monotone_stack.h