Stack.h

Go to the documentation of this file.

#pragma once
 
#include <stdint.h>
#include <stddef.h>
#include <initializer_list>
 
namespace daisy
{
template <typename T>
class StackBase
{
  protected:
    StackBase(T* buffer, size_t bufferSize)
    : buffer_(buffer), bufferSize_(bufferSize), bufferHead_(0)
    {
    }
 
    StackBase(T*                       buffer,
              size_t                   bufferSize,
              std::initializer_list<T> valuesToAdd)
    : buffer_(buffer), bufferSize_(bufferSize), bufferHead_(0)
    {
        PushBack(valuesToAdd);
    }
 
  public:
    StackBase<T>& operator=(const StackBase<T>& other)
    {
        bufferHead_ = 0;
        if(!other.IsEmpty())
        {
            const auto numCopy = (other.GetNumElements() < bufferSize_)
                                     ? other.GetNumElements()
                                     : bufferSize_;
            for(size_t i = 0; i < numCopy; i++)
                buffer_[i] = other[i];
            bufferHead_ = other.GetNumElements();
        }
        return *this;
    }
 
    ~StackBase() {}
 
    bool PushBack(const T& elementToAdd)
    {
        if(!IsFull())
        {
            buffer_[bufferHead_++] = elementToAdd;
            return true;
        }
        return false;
    }
 
    int PushBack(std::initializer_list<T> valuesToAdd)
    {
        int numAdded = 0;
        for(const auto& v : valuesToAdd)
        {
            if(IsFull())
                return numAdded;
 
            PushBack(v);
            numAdded++;
        }
        return numAdded;
    }
 
    T PopBack()
    {
        if(IsEmpty())
            return T();
        else
        {
            return buffer_[--bufferHead_];
        }
    }
 
    void Clear() { bufferHead_ = 0; }
 
    T& operator[](uint32_t idx) { return buffer_[idx]; }
    const T& operator[](uint32_t idx) const { return buffer_[idx]; }
 
    bool Remove(uint32_t idx)
    {
        if(idx >= bufferHead_)
            return false;
 
        for(uint32_t i = idx; i < bufferHead_ - 1; i++)
        {
            buffer_[i] = buffer_[i + 1];
        }
        bufferHead_--;
        return true;
    }
 
    int RemoveAllEqualTo(const T& element)
    {
        int numRemoved = 0;
        int idx        = bufferHead_ - 1;
        while(idx >= 0)
        {
            if(buffer_[idx] == element)
            {
                numRemoved++;
                Remove(idx);
                // was that the last element?
                if(decltype(bufferHead_)(idx) == bufferHead_)
                    idx--;
            }
            else
                idx--;
        }
        return numRemoved;
    }
 
    bool Insert(uint32_t idx, const T& item)
    {
        if(bufferHead_ >= bufferSize_)
            return false;
        if(idx > bufferHead_)
            return false;
        if(idx == bufferHead_)
        {
            buffer_[bufferHead_++] = item;
            return true;
        }
 
        for(uint32_t i = bufferHead_ - 1; i >= idx; i--)
        {
            buffer_[i + 1] = buffer_[i];
        }
        buffer_[idx] = item;
        bufferHead_++;
        return true;
    }
 
    bool Contains(const T& element)
    {
        int idx = bufferHead_ - 1;
        while(idx >= 0)
        {
            if(buffer_[idx] == element)
                return true;
            idx--;
        }
        return false;
    }
 
    size_t CountEqualTo(const T& element)
    {
        size_t result = 0;
        int    idx    = bufferHead_ - 1;
        while(idx >= 0)
        {
            if(buffer_[idx] == element)
                result++;
            idx--;
        }
        return result;
    }
 
    bool IsEmpty() const { return bufferHead_ == 0; }
 
    bool IsFull() const { return bufferHead_ == bufferSize_; }
 
    size_t GetNumElements() const { return bufferHead_; }
 
    size_t GetCapacity() const { return bufferSize_; }
 
  private:
    T*           buffer_;
    const size_t bufferSize_;
    size_t       bufferHead_;
};
 
template <typename T, size_t capacity>
class Stack : public StackBase<T>
{
  public:
    Stack() : StackBase<T>(buffer_, capacity) {}
 
    explicit Stack(std::initializer_list<T> valuesToAdd)
    : StackBase<T>(buffer_, capacity, valuesToAdd)
    {
    }
 
    template <size_t otherCapacity>
    Stack(const Stack<T, otherCapacity>& other)
    : StackBase<T>(buffer_, capacity)
    {
        *this = other;
    }
 
    template <size_t otherCapacity>
    Stack<T, capacity>& operator=(const Stack<T, otherCapacity>& other)
    {
        StackBase<T>::operator=(other);
        return *this;
    }
 
  private:
    T buffer_[capacity];
};
 
} // namespace daisy