Pothos  0.2.1-g9f04573d
The Pothos dataflow programming software suite
 All Classes Namespaces Files Functions Variables Typedefs Friends Macros
OrderedQueue.hpp
Go to the documentation of this file.
1 
12 #pragma once
13 #include <Pothos/Config.hpp>
15 #include <cstdlib> //size_t
16 
17 #include <vector>
18 #include <cassert>
19 
20 namespace Pothos {
21 namespace Util {
22 
27 template <typename T>
29 {
30 public:
32  OrderedQueue(void);
33 
35  OrderedQueue(const size_t capacity);
36 
42  bool empty(void) const;
43 
49  void push(const T &elem, const size_t index);
50 
54  const T &front(void) const;
55 
59  T &front(void);
60 
64  void pop(void);
65 
67  size_t capacity(void) const;
68 
69 private:
70  size_t _indexToAck;
71  std::vector<T> _pushedElems;
72  std::vector<bool> _pushedElemsFlag;
73  Pothos::Util::RingDeque<T> _readyElems;
74 };
75 
76 template <typename T>
78  _indexToAck(0)
79 {
80  return;
81 }
82 
83 template <typename T>
84 OrderedQueue<T>::OrderedQueue(const size_t capacity):
85  _indexToAck(0),
86  _pushedElems(capacity),
87  _pushedElemsFlag(capacity, false),
88  _readyElems(capacity)
89 {
90  return;
91 }
92 
93 template <typename T>
94 bool OrderedQueue<T>::empty(void) const
95 {
96  return _readyElems.empty();
97 }
98 
99 template <typename T>
100 void OrderedQueue<T>::push(const T &elem, const size_t index)
101 {
102  //store the element into its position
103  assert(index < _pushedElems.size());
104  _pushedElems[index] = elem;
105  _pushedElemsFlag[index] = true;
106 
107  //look for pushed elements -- but in order
108  while (_pushedElemsFlag[_indexToAck])
109  {
110  //move the element into the queue
111  assert(not _readyElems.full());
112  _readyElems.push_back(_pushedElems[_indexToAck]);
113  _pushedElems[_indexToAck] = T(); //clear reference
114  _pushedElemsFlag[_indexToAck] = false;
115 
116  //increment for the next pushed element
117  if (++_indexToAck == _pushedElems.size()) _indexToAck = 0;
118  }
119 }
120 
121 template <typename T>
122 const T &OrderedQueue<T>::front(void) const
123 {
124  return _readyElems.front();
125 }
126 
127 template <typename T>
129 {
130  return _readyElems.front();
131 }
132 
133 template <typename T>
135 {
136  _readyElems.pop_front();
137 }
138 
139 template <typename T>
140 size_t OrderedQueue<T>::capacity(void) const
141 {
142  return _readyElems.capacity();
143 }
144 
145 } //namespace Util
146 } //namespace Pothos
const T & front(void) const
Definition: OrderedQueue.hpp:122
void push(const T &elem, const size_t index)
Definition: OrderedQueue.hpp:100
size_t capacity(void) const
How many elements can be stored?
Definition: OrderedQueue.hpp:140
bool empty(void) const
Definition: OrderedQueue.hpp:94
Definition: RingDeque.hpp:28
void pop(void)
Definition: OrderedQueue.hpp:134
Definition: OrderedQueue.hpp:28
OrderedQueue(void)
Construct a size-zero ordered queue.
Definition: OrderedQueue.hpp:77