OrderedQueue.hpp

Go to the documentation of this file.

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

namespace Pothos {
namespace Util {

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

    OrderedQueue(const size_t capacity);

    bool empty(void) const;

    template <typename U>
    void push(U &&elem, const size_t index);

    const T &front(void) const;

    T &front(void);

    void pop(void);

    size_t capacity(void) const;

private:
    size_t _indexToAck;
    std::vector<std::pair<T, bool>> _pushedElems;
    Pothos::Util::RingDeque<T> _readyElems;
    inline void _wrapIndex(void)
    {
        if (++_indexToAck == _pushedElems.size()) _indexToAck = 0;
    }
};

template <typename T>
OrderedQueue<T>::OrderedQueue(void):
    _indexToAck(0)
{
    return;
}

template <typename T>
OrderedQueue<T>::OrderedQueue(const size_t capacity):
    _indexToAck(0),
    _pushedElems(capacity, std::make_pair(T(), false)),
    _readyElems(capacity)
{
    return;
}

template <typename T>
bool OrderedQueue<T>::empty(void) const
{
    return _readyElems.empty();
}

template <typename T>
template <typename U>
void OrderedQueue<T>::push(U &&elem, const size_t index)
{
    //element was pushed in order, go directly to the queue
    if (index == _indexToAck)
    {
        assert(not _readyElems.full());
        _readyElems.push_back(std::forward<U>(elem));

        //increment for the next pushed element
        _wrapIndex();
    }

    //store the element into its position
    else
    {
        assert(index < _pushedElems.size());
        _pushedElems[index].first = std::forward<U>(elem);
        _pushedElems[index].second = true;
    }

    //look for pushed elements -- but in order
    while (_pushedElems[_indexToAck].second)
    {
        //move the element into the queue
        assert(not _readyElems.full());
        _readyElems.push_back(std::move(_pushedElems[_indexToAck].first));
        _pushedElems[_indexToAck].second = false;

        //increment for the next pushed element
        _wrapIndex();
    }
}

template <typename T>
const T &OrderedQueue<T>::front(void) const
{
    return _readyElems.front();
}

template <typename T>
T &OrderedQueue<T>::front(void)
{
    return _readyElems.front();
}

template <typename T>
void OrderedQueue<T>::pop(void)
{
    _readyElems.pop_front();
}

template <typename T>
size_t OrderedQueue<T>::capacity(void) const
{
    return _readyElems.capacity();
}

} //namespace Util
} //namespace Pothos