Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2021-02-14 12:50:02

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