File indexing completed on 2024-04-06 12:01:08
0001 #ifndef COMMONTOOLS_RECOALGOS_FQUEUE_H
0002 #define COMMONTOOLS_RECOALGOS_FQUEUE_H
0003
0004 #include <vector>
0005
0006 template <class T>
0007 class FQueue {
0008 public:
0009 FQueue() {
0010 theSize = 0;
0011 theFront = 0;
0012 theTail = 0;
0013 theCapacity = 0;
0014 }
0015
0016 FQueue(unsigned int initialCapacity) {
0017 theBuffer.resize(initialCapacity);
0018 theSize = 0;
0019 theFront = 0;
0020 theTail = 0;
0021 theCapacity = initialCapacity;
0022 }
0023
0024 unsigned int size() const { return theSize; }
0025
0026 bool empty() const { return theSize == 0; }
0027
0028 T front() const { return theBuffer[theFront]; }
0029
0030 T& tail() { return theBuffer[theTail]; }
0031
0032 constexpr unsigned int wrapIndex(unsigned int i) { return i & (theBuffer.size() - 1); }
0033
0034 void push_back(const T& value) {
0035 if (theSize >= theCapacity) {
0036 theBuffer.resize(theCapacity * 2);
0037 if (theFront != 0) {
0038 std::copy(theBuffer.begin(), theBuffer.begin() + theTail, theBuffer.begin() + theCapacity);
0039
0040 theTail += theSize;
0041
0042 } else {
0043 theTail += theCapacity;
0044 }
0045 theCapacity *= 2;
0046 }
0047 theBuffer[theTail] = value;
0048 theTail = wrapIndex(theTail + 1);
0049 theSize++;
0050 }
0051
0052 void pop_front() {
0053 if (theSize > 0) {
0054 theFront = wrapIndex(theFront + 1);
0055 theSize--;
0056 }
0057 }
0058
0059 void pop_front(const unsigned int numberOfElementsToPop) {
0060 unsigned int elementsToErase = theSize > numberOfElementsToPop ? numberOfElementsToPop : theSize;
0061 theSize -= elementsToErase;
0062 theFront = wrapIndex(theFront + elementsToErase);
0063 }
0064
0065 void reserve(unsigned int capacity) { theBuffer.reserve(capacity); }
0066
0067 T& operator[](unsigned int index) { return theBuffer[wrapIndex(theFront + index)]; }
0068
0069 void clear() {
0070 theBuffer.clear();
0071 theSize = 0;
0072 theFront = 0;
0073 theTail = 0;
0074 }
0075
0076 private:
0077 unsigned int theSize;
0078 unsigned int theFront;
0079 unsigned int theTail;
0080 std::vector<T> theBuffer;
0081 unsigned int theCapacity;
0082 };
0083
0084 #endif
