RingDeque.hpp

Go to the documentation of this file.

#pragma once
#include <Pothos/Config.hpp>
#include <cstdlib> //size_t
#include <utility> //forward
#include <vector>
#include <cassert>

namespace Pothos {
namespace Util {

template <typename T>
class RingDeque
{
public:
    RingDeque(void);

    RingDeque(const size_t capacity);

    const T &operator[](const size_t offset) const;

    T &operator[](const size_t offset);

    template <typename U>
    void push_front(U &&elem);

    template <typename... Args>
    T &emplace_front(Args&&... args);

    void pop_front(void);

    const T &front(void) const;

    T &front(void);

    template <typename U>
    void push_back(U &&elem);

    template <typename... Args>
    T &emplace_back(Args&&... args);

    void pop_back(void);

    const T &back(void) const;

    T &back(void);

    bool empty(void) const;

    bool full(void) const;

    size_t size(void) const;

    size_t capacity(void) const;

    void set_capacity(const size_t capacity);

    void clear(void);

private:
    size_t _frontIndex;
    size_t _backIndex;
    size_t _numElements;
    std::vector<T> _container;
};

template <typename T>
RingDeque<T>::RingDeque(void):
    _frontIndex(0),
    _backIndex(0),
    _numElements(0),
    _container(1)
{
    return;
}

template <typename T>
RingDeque<T>::RingDeque(const size_t capacity):
    _frontIndex(0),
    _backIndex(capacity-1),
    _numElements(0),
    _container(capacity)
{
    assert(capacity > 0);
}

template <typename T>
const T &RingDeque<T>::operator[](const size_t offset) const
{
    return _container[(_frontIndex + offset) % _container.size()];
}

template <typename T>
T &RingDeque<T>::operator[](const size_t offset)
{
    return _container[(_frontIndex + offset) % _container.size()];
}

template <typename T>
template <typename U>
void RingDeque<T>::push_front(U &&elem)
{
    assert(not this->full());
    _frontIndex = size_t(_frontIndex + _container.size() - 1) % _container.size();
    _container[_frontIndex] = std::forward<U>(elem);
    _numElements++;
}

template <typename T>
template <typename... Args>
T &RingDeque<T>::emplace_front(Args&&... args)
{
    assert(not this->full());
    _frontIndex = size_t(_frontIndex + _container.size() - 1) % _container.size();
    _container[_frontIndex] = T(std::forward<Args>(args)...);
    _numElements++;
    return _container[_frontIndex];
}

template <typename T>
void RingDeque<T>::pop_front(void)
{
    assert(not this->empty());
    assert(_frontIndex < _container.size());
    _container[_frontIndex] = T();
    _frontIndex = size_t(_frontIndex + 1) % _container.size();
    _numElements--;
}

template <typename T>
const T &RingDeque<T>::front(void) const
{
    assert(not this->empty());
    assert(_frontIndex < _container.size());
    return _container[_frontIndex];
}

template <typename T>
T &RingDeque<T>::front(void)
{
    assert(not this->empty());
    assert(_frontIndex < _container.size());
    return _container[_frontIndex];
}

template <typename T>
template <typename U>
void RingDeque<T>::push_back(U &&elem)
{
    assert(not this->full());
    _backIndex = size_t(_backIndex + 1) % _container.size();
    _container[_backIndex] = std::forward<U>(elem);
    _numElements++;
}

template <typename T>
template <typename... Args>
T &RingDeque<T>::emplace_back(Args&&... args)
{
    assert(not this->full());
    _backIndex = size_t(_backIndex + 1) % _container.size();
    _container[_backIndex] = T(std::forward<Args>(args)...);
    _numElements++;
    return _container[_backIndex];
}

template <typename T>
void RingDeque<T>::pop_back(void)
{
    assert(not this->empty());
    assert(_backIndex < _container.size());
    _container[_backIndex] = T();
    _backIndex = size_t(_backIndex + _container.size() - 1) % _container.size();
    _numElements--;
}

template <typename T>
const T &RingDeque<T>::back(void) const
{
    assert(not this->empty());
    assert(_backIndex < _container.size());
    return _container[_backIndex];
}

template <typename T>
T &RingDeque<T>::back(void)
{
    assert(not this->empty());
    assert(_backIndex < _container.size());
    return _container[_backIndex];
}

template <typename T>
bool RingDeque<T>::empty(void) const
{
    return _numElements == 0;
}

template <typename T>
bool RingDeque<T>::full(void) const
{
    return _numElements == _container.size();
}

template <typename T>
size_t RingDeque<T>::size(void) const
{
    return _numElements;
}

template <typename T>
size_t RingDeque<T>::capacity(void) const
{
    return _container.size();
}

template <typename T>
void RingDeque<T>::set_capacity(const size_t capacity)
{
    if (_numElements > capacity) return;
    std::vector<T> _newContainer(capacity);
    for (size_t i = 0; i < _numElements; i++)
    {
        _newContainer[i] = _container[(_frontIndex+i) % _container.size()];
    }
    _container = _newContainer;
    _frontIndex = 0;
    _backIndex = (_numElements + capacity - 1) % capacity;
}

template <typename T>
void RingDeque<T>::clear(void)
{
    while (not this->empty())
    {
        this->pop_front();
    }
}

} //namespace Util
} //namespace Pothos