comprstack.h

Go to the documentation of this file.

 
#include "elementa/license.inc"
#include "elementa/checks.inc"
 
#ifndef ELEMENTA_ADTS_COMPRESSEDSTACK_H
#define ELEMENTA_ADTS_COMPRESSEDSTACK_H
 
#include <stack>
#include "elementa/base/exceptions.h"
 
#include "elementa/base/debugging.h"
 
 
namespace elementa
{
 
namespace adts
{
 
/* ***************************************************************************
 
    Template class: CSHolder
    
*******************************************************************************/
 
 
template <class Obj>
struct CSHolder final
{
    const bool interesting; 
    union HeldData
    {
        size_t howmanyunint; 
        Obj object; 
 
        HeldData(void):howmanyunint{1} {}
        HeldData(const Obj & o):object{o} {}
        HeldData(Obj && o):object{std::move(o)} {}
 
        ~HeldData(void) {}
    } held; 
 
 
    CSHolder(void): interesting{false}, held{} {}
 
    CSHolder(const Obj & o): interesting{true}, held{o} {}
 
    CSHolder(const CSHolder &) = delete;
    CSHolder(CSHolder &&) = delete;
    CSHolder & operator=(const CSHolder &) = delete;
    CSHolder & operator=(CSHolder &&) = delete;
 
    ~CSHolder(void) {}
 
};
 
 
/* ***************************************************************************
 
    Template class: ComprStack
    
*******************************************************************************/
 
 
template <class Obj>
class ComprStack: public std::stack<CSHolder<Obj>>
{
 public:
 
    using Base = std::stack<CSHolder<Obj>>;
 
    using Base::Base;
 
 
 
    double comprRatio(void) const noexcept;
 
    bool empty() const
        { return(Base::empty()); }
 
    typename Base::size_type size(void) const 
        { return(size_); }
 
    void push(void);
 
    void push(const Obj & o);
 
    void push(Obj && o);
 
    void pop(void);
 
 
    const CSHolder<Obj> & top(void) const;
 
 
 private:
 
    typename Base::size_type size_{0};
 
};
 
 
 
/* ===========================================================================
 
        ========== IMPLEMENTATION OF TEMPLATES ==========
 
============================================================================= */
 
 
/* ***************************************************************************
 
    Template class: ComprStack
    
*******************************************************************************/
 
template <class Obj>
double ComprStack<Obj>::comprRatio(void) const noexcept
{
    if (Base::size() <= 1) return(1.0);
    return(static_cast<double>(size()-Base::size()) / 
           static_cast<double>(size()));
}
 
template <class Obj>
void ComprStack<Obj>::push(void)    
{ELE_CODE_TRACE_OFF;
 
    if ( (Base::empty())||(top().interesting) ) Base::emplace(); 
    else ++(const_cast<typename Base::reference>(Base::top()).
            held.howmanyunint);
    ++size_;
    ELE_CODE_TRACE({},"Pushed un-interesting element in stack."
              " Stack acc size = " << size() << 
              " (in memory: " << Base::size() << ")");
}
 
template <class Obj>
void ComprStack<Obj>::push(const Obj & o) 
{ELE_CODE_TRACE_OFF;
 
    Base::emplace(o); 
    ++size_; 
    ELE_CODE_TRACE({},"Pushed interesting element in stack."
              " Stack acc size = " << size() << 
              " (in memory: " << Base::size() << ")");
}
 
template <class Obj>
void ComprStack<Obj>::push(Obj && o)
{ELE_CODE_TRACE_OFF;
 
    Base::emplace(std::move(o)); 
    ++size_; 
    ELE_CODE_TRACE({},"Moved interesting element into stack."
              " Stack acc size = " << size() << 
              " (in memory: " << Base::size() << ")");
}
 
template <class Obj>
void ComprStack<Obj>::pop(void)
{ELE_CODE_TRACE_OFF;
 
    if (!top().interesting)
    {
        ELE_CODE_TRACE({},"Popping un-interesting element from stack");
        --(const_cast<typename Base::reference>(top()).held.howmanyunint);
        if (Base::top().held.howmanyunint == 0) Base::pop();
    }
    else
    {
        ELE_CODE_TRACE({},"Popping interesting element from stack");
        Base::pop();
    }
    --size_;
}
 
template <class Obj>
const CSHolder<Obj> & ComprStack<Obj>::top(void) const
{
    if (empty()) ELE_CODE_INVSTATE("No top in empty stack");
    return(Base::top());
}
 
 // ComprStack
 
 
} // end adts namespace
 
} // end elementa namespace
 
 
#endif