|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#ifndef COMMONTOOLS_RECOALGOS_FQUEUE_H
#define COMMONTOOLS_RECOALGOS_FQUEUE_H
#include <vector>
template <class T>
class FQueue {
public:
FQueue() {
theSize = 0;
theFront = 0;
theTail = 0;
theCapacity = 0;
}
FQueue(unsigned int initialCapacity) {
theBuffer.resize(initialCapacity);
theSize = 0;
theFront = 0;
theTail = 0;
theCapacity = initialCapacity;
}
unsigned int size() const { return theSize; }
bool empty() const { return theSize == 0; }
T front() const { return theBuffer[theFront]; }
T& tail() { return theBuffer[theTail]; }
constexpr unsigned int wrapIndex(unsigned int i) { return i & (theBuffer.size() - 1); }
void push_back(const T& value) {
if (theSize >= theCapacity) {
theBuffer.resize(theCapacity * 2);
if (theFront != 0) {
std::copy(theBuffer.begin(), theBuffer.begin() + theTail, theBuffer.begin() + theCapacity);
theTail += theSize;
} else {
theTail += theCapacity;
}
theCapacity *= 2;
}
theBuffer[theTail] = value;
theTail = wrapIndex(theTail + 1);
theSize++;
}
void pop_front() {
if (theSize > 0) {
theFront = wrapIndex(theFront + 1);
theSize--;
}
}
void pop_front(const unsigned int numberOfElementsToPop) {
unsigned int elementsToErase = theSize > numberOfElementsToPop ? numberOfElementsToPop : theSize;
theSize -= elementsToErase;
theFront = wrapIndex(theFront + elementsToErase);
}
void reserve(unsigned int capacity) { theBuffer.reserve(capacity); }
T& operator[](unsigned int index) { return theBuffer[wrapIndex(theFront + index)]; }
void clear() {
theBuffer.clear();
theSize = 0;
theFront = 0;
theTail = 0;
}
private:
unsigned int theSize;
unsigned int theFront;
unsigned int theTail;
std::vector<T> theBuffer;
unsigned int theCapacity;
};
#endif
|