FixedIndexQueue.h

Go to the documentation of this file.

#pragma once
#include "../Memory/MemoryBuffer.h"
#include "../BitTwiddling/PowerOfTwo.h"
 
#include <type_traits>
#include <cassert>
 
namespace Cogs
{
  namespace Collections
  {
 
    template<typename Element, typename IndexBaseType>
    class FixedIndexQueue
    {
      typedef typename std::make_signed<IndexBaseType>::type SignedIndexType;
    public:
      typedef typename std::make_unsigned<IndexBaseType>::type IndexType;
 
      FixedIndexQueue() { storage.resize(capacity(), false); }
 
      const IndexType capacity() const { return sizeMask + 1u; }
 
      IndexType empty() const
      {
        IndexType frontOffsetWrap = frontOffset & sizeMask;
        IndexType backOffsetWrap = backOffset & sizeMask;
        return frontOffsetWrap == backOffsetWrap;
      }
 
      IndexType count() const
      {
        IndexType frontOffsetWrap = frontOffset & sizeMask;
        IndexType backOffsetWrap = backOffset & sizeMask;
        return backOffsetWrap - frontOffsetWrap + (backOffsetWrap < frontOffsetWrap ? capacity() : static_cast<IndexType>(0));
      }
 
      void clear()
      {
        offsetToFixedIndexShift += backOffset;
        frontOffset = 0;
        backOffset = 0;
      }
 
      void reset()
      {
        frontOffset = 0;
        backOffset = 0;
        offsetToFixedIndexShift = 0;
      }
 
      void shrink()
      {
        IndexType sizeL2New = static_cast<IndexType>(roundUpToPowerOfTwoShift(count() + 1u));
        if (sizeL2New == sizeL2) return;
 
        resize(sizeL2New);
      }
 
      void pushBack(Element e)
      {
        if (noCapacity()) grow();
 
        storage[backOffset & sizeMask] = e;
        backOffset++;
      }
 
      void pushFront(Element e)
      {
        if (noCapacity()) grow();
 
        frontOffset--;
        storage[frontOffset & sizeMask] = e;
      }
 
      void popFront()
      {
        if (empty()) {
          assert(false && "queue is empty");
          return;
        }
        frontOffset++;
      }
 
      Element& operator[](IndexType fixedIndex)
      {
        assert(empty() == false);
        assert(0 <= static_cast<SignedIndexType>(fixedIndex - frontIndex()));
        assert(static_cast<SignedIndexType>(fixedIndex - backIndex()) <= 0);
        IndexType offset = fixedIndex - offsetToFixedIndexShift;
        return storage[offset & sizeMask];
      }
 
      const Element& operator[](IndexType fixedIndex) const
      {
        assert(empty() == false);
        assert(0 <= static_cast<SignedIndexType>(fixedIndex - frontIndex()));
        assert(static_cast<SignedIndexType>(fixedIndex - backIndex()) <= 0);
        IndexType offset = fixedIndex - offsetToFixedIndexShift;
        return storage[offset & sizeMask];
      }
 
      Element& front() { assert(empty() == false); return storage[frontOffset & sizeMask]; }
 
      const Element& front() const { assert(empty() == false); return storage[frontOffset & sizeMask]; }
 
      Element& back() { assert(empty() == false); return storage[(backOffset - IndexType(1)) & sizeMask]; }
 
      const Element& back() const { assert(empty() == false); return storage[(backOffset - IndexType(1)) & sizeMask]; }
 
      IndexType frontIndex() const { assert(empty() == false); return frontOffset + offsetToFixedIndexShift; }
 
      IndexType backIndex() const { assert(empty() == false); return backOffset - IndexType(1) + offsetToFixedIndexShift; }
 
      bool validIndex(uint32_t fixedIndex) const
      {
        if (empty()) return false;
        // Correct as long as distance is less than SignedIndexType::Max.
        if (static_cast<SignedIndexType>(fixedIndex - frontIndex()) < 0) return false;
        if (0 < static_cast<SignedIndexType>(fixedIndex - backIndex())) return false;
        return true;
      }
 
    private:
      IndexType sizeL2 = 0;       // size is 1<<0 = 1.
      IndexType sizeMask = 0;
      IndexType frontOffset = 0;
      IndexType backOffset = 0;
      IndexType offsetToFixedIndexShift = 0;
      Cogs::Memory::TypedBuffer<Element> storage;
 
      bool noCapacity() const { return ((frontOffset & sizeMask) == ((backOffset + 1) & sizeMask)); }
 
      void grow()
      {
        IndexType sizeL2New = sizeL2 + 1u;
        IndexType sizeNew = (1u << sizeL2New);
        assert(capacity() < sizeNew); // Check if we grow beyond domain of representation.
        resize(sizeL2New);
      }
 
      void resize(IndexType sizeL2New)
      {
        IndexType sizeNew = 1u << sizeL2New;
        assert(isPowerOfTwo(sizeNew));
 
        IndexType N = count();
        assert(N < sizeNew);
 
        Cogs::Memory::TypedBuffer<Element> storageNew(sizeNew);
        for (uint32_t i = 0; i < N; i++) {
          storageNew[i] = storage[(frontOffset + i) & sizeMask];
        }
        offsetToFixedIndexShift += frontOffset;
        frontOffset = 0;
        backOffset = N;
 
        sizeL2 = sizeL2New;
        sizeMask = sizeNew - 1u;
        storage.swap(storageNew);
      }
 
    };
 
  }
}