Compressed Stack

Description

---

  A stack that compresses all non-interesting elements and only
  stores explicitly those that are interesting.

Author

Juan-Antonio Fernandez-Madrigal. http://jafma.net

Date

2019

Copyright

Copyright (c), Individual contributors, see AUTHORS file. This program is free for non-commercial uses. For the rest, contact the AUTHORS. Please include a mention in your programs to the main developer and the web page of the library.

Collaboration diagram for Compressed Stack:

Classes
struct	elementa::adts::CSHolder< Obj >
	Holder for elements in a compressed stack. More...
class	elementa::adts::ComprStack< Obj >
	A compressed stack that only stores some objects and not others. More...

Functions
double	elementa::adts::ComprStack< Obj >::comprRatio (void) const noexcept
	Return the compression ratio in [0,1]. More...
void	elementa::adts::ComprStack< Obj >::push (void)
	Push an un-interesting element without storing anything. More...
void	elementa::adts::ComprStack< Obj >::push (const Obj &o)
	Push a new interesting element. More...
void	elementa::adts::ComprStack< Obj >::push (Obj &&o)
	Push a new interesting element, stealing it from the arg. More...
void	elementa::adts::ComprStack< Obj >::pop (void)
	Pop an element from stack. More...
const CSHolder< Obj > &	elementa::adts::ComprStack< Obj >::top (void) const
	Consult the top. More...

---

Class Documentation

elementa::adts::CSHolder

struct elementa::adts::CSHolder

template<class Obj>
struct elementa::adts::CSHolder< Obj >

Holder for elements in a compressed stack.

Template Parameters

Obj	is the class of the elements in the compressed stack. It must be default-constructible and copyable.

Definition at line 51 of file comprstack.h.

Collaboration diagram for elementa::adts::CSHolder< Obj >:

Public Attributes
const bool	interesting
	TRUE if it holds an interesting element. More...
union elementa::adts::CSHolder::HeldData	held
	Data held by the holder.
Public Member Functions
	CSHolder (void)
	Construct an un-interesting element. More...
	CSHolder (const Obj &o)
	Construct an interesting element. More...
	CSHolder (const CSHolder &)=delete
	CSHolder (CSHolder &&)=delete
CSHolder &	operator= (const CSHolder &)=delete
CSHolder &	operator= (CSHolder &&)=delete

Constructor & Destructor Documentation

CSHolder() [1/2]

template<class Obj >

elementa::adts::CSHolder< Obj >::CSHolder ( void  )

inline

Construct an un-interesting element.

Definition at line 68 of file comprstack.h.

CSHolder() [2/2]

template<class Obj >

elementa::adts::CSHolder< Obj >::CSHolder ( const Obj &  o )

inline

Construct an interesting element.

Definition at line 71 of file comprstack.h.

~CSHolder()

template<class Obj >

elementa::adts::CSHolder< Obj >::~CSHolder ( void  )

inline

Definition at line 78 of file comprstack.h.

Member Data Documentation

interesting

template<class Obj >

const bool elementa::adts::CSHolder< Obj >::interesting

TRUE if it holds an interesting element.

Definition at line 53 of file comprstack.h.

elementa::adts::ComprStack

class elementa::adts::ComprStack

template<class Obj>
class elementa::adts::ComprStack< Obj >

A compressed stack that only stores some objects and not others.

Template Parameters

Obj	is the kind of objects stored.

Definition at line 92 of file comprstack.h.

Inheritance diagram for elementa::adts::ComprStack< Obj >:

Collaboration diagram for elementa::adts::ComprStack< Obj >:

Public Types
using	Base = std::stack< CSHolder< Obj > >
	Shortcut. More...
Public Attributes
T	elements
	STL member.
Public Member Functions
double	comprRatio (void) const noexcept
	Return the compression ratio in [0,1]. More...
bool	empty () const
Base::size_type	size (void) const
	Return the total size of the stack by counting all, not compressed. More...
void	push (void)
	Push an un-interesting element without storing anything. More...
void	push (const Obj &o)
	Push a new interesting element. More...
void	push (Obj &&o)
	Push a new interesting element, stealing it from the arg. More...
void	pop (void)
	Pop an element from stack. More...
const CSHolder< Obj > &	top (void) const
	Consult the top. More...

Member Typedef Documentation

Base

template<class Obj >

using elementa::adts::ComprStack< Obj >::Base = std::stack<CSHolder<Obj> >

Shortcut.

Definition at line 97 of file comprstack.h.

Member Function Documentation

empty()

template<class Obj >

bool elementa::adts::ComprStack< Obj >::empty ( ) const

inline

Definition at line 108 of file comprstack.h.

size()

template<class Obj >

Base::size_type elementa::adts::ComprStack< Obj >::size ( void  ) const

inline

Return the total size of the stack by counting all, not compressed.

Definition at line 112 of file comprstack.h.

Function Documentation

comprRatio()

template<class Obj >

double elementa::adts::ComprStack< Obj >::comprRatio ( void  ) const

noexcept

#include <elementa/adts/comprstack.h>

Return the compression ratio in [0,1].

0 indicates no compression; 1 complete compression (cannot compress any more).

Definition at line 155 of file comprstack.h.

push() [1/3]

template<class Obj >

void elementa::adts::ComprStack< Obj >::push

(

void

)

#include <elementa/adts/comprstack.h>

Push an un-interesting element without storing anything.

Definition at line 163 of file comprstack.h.

References ELE_CODE_TRACE_OFF.

push() [2/3]

template<class Obj >

void elementa::adts::ComprStack< Obj >::push

(

const Obj &

o

)

#include <elementa/adts/comprstack.h>

Push a new interesting element.

Definition at line 176 of file comprstack.h.

References ELE_CODE_TRACE_OFF.

push() [3/3]

template<class Obj >

void elementa::adts::ComprStack< Obj >::push

(

Obj &&

o

)

#include <elementa/adts/comprstack.h>

Push a new interesting element, stealing it from the arg.

Definition at line 187 of file comprstack.h.

References ELE_CODE_TRACE_OFF.

pop()

template<class Obj >

void elementa::adts::ComprStack< Obj >::pop

(

void

)

#include <elementa/adts/comprstack.h>

Pop an element from stack.

Definition at line 198 of file comprstack.h.

References ELE_CODE_TRACE_OFF.

top()

template<class Obj >

const CSHolder< Obj > & elementa::adts::ComprStack< Obj >::top

(

void

)

const

#include <elementa/adts/comprstack.h>

Consult the top.

Only not modifiable version for not compromising the consistency of the internal count of elements.

Definition at line 216 of file comprstack.h.

References ELE_CODE_INVSTATE.