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 <vector>
#include <cassert>

namespace Pothos {
namespace Util {

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

    OrderedQueue(const size_t capacity);

    bool empty(void) const;

    void push(const T &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<T> _pushedElems;
    std::vector<bool> _pushedElemsFlag;
    Pothos::Util::RingDeque<T> _readyElems;
};

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

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

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

template <typename T>
void OrderedQueue<T>::push(const T &elem, const size_t index)
{
    //store the element into its position
    assert(index < _pushedElems.size());
    _pushedElems[index] = elem;
    _pushedElemsFlag[index] = true;

    //look for pushed elements -- but in order
    while (_pushedElemsFlag[_indexToAck])
    {
        //move the element into the queue
        assert(not _readyElems.full());
        _readyElems.push_back(_pushedElems[_indexToAck]);
        _pushedElems[_indexToAck] = T(); //clear reference
        _pushedElemsFlag[_indexToAck] = false;

        //increment for the next pushed element
        if (++_indexToAck == _pushedElems.size()) _indexToAck = 0;
    }
}

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