Deque.h

#pragma once
 
#include <Foundation/Algorithm/Sorting.h>
#include <Foundation/Containers/Implementation/ArrayIterator.h>
#include <Foundation/Memory/Allocator.h>
#include <Foundation/Memory/AllocatorWrapper.h>
 
#ifndef plInvalidIndex
#  define plInvalidIndex 0xFFFFFFFF
#endif
 
template <typename T, bool Construct>
class plDequeBase
{
protected:
  explicit plDequeBase(plAllocator* pAllocator); // [tested]
 
  plDequeBase(const plDequeBase<T, Construct>& rhs, plAllocator* pAllocator); // [tested]
 
  plDequeBase(plDequeBase<T, Construct>&& rhs, plAllocator* pAllocator); // [tested]
 
  ~plDequeBase(); // [tested]
 
  void operator=(const plDequeBase<T, Construct>& rhs); // [tested]
 
  void operator=(plDequeBase<T, Construct>&& rhs); // [tested]
 
public:
  void Clear(); // [tested]
 
  void Reserve(plUInt32 uiCount); // [tested]
 
  void Compact(); // [tested]
 
  void Swap(plDequeBase<T, Construct>& other); // [tested]
 
  void SetCount(plUInt32 uiCount); // [tested]
 
  template <typename = void>                    // Template is used to only conditionally compile this function in when it is actually used.
  void SetCountUninitialized(plUInt32 uiCount); // [tested]
 
  void EnsureCount(plUInt32 uiCount); // [tested]
 
  T& operator[](plUInt32 uiIndex); // [tested]
 
  const T& operator[](plUInt32 uiIndex) const; // [tested]
 
  T& ExpandAndGetRef(); // [tested]
 
  void PushBack(); // [tested]
 
  void PushBack(const T& element); // [tested]
 
  void PushBack(T&& value); // [tested]
 
  void PopBack(plUInt32 uiElements = 1); // [tested]
 
  void PushFront(const T& element); // [tested]
 
  void PushFront(T&& element); // [tested]
 
  void PushFront(); // [tested]
 
  void PopFront(plUInt32 uiElements = 1); // [tested]
 
  bool IsEmpty() const; // [tested]
 
  plUInt32 GetCount() const; // [tested]
 
  const T& PeekFront() const; // [tested]
 
  T& PeekFront(); // [tested]
 
  const T& PeekBack() const; // [tested]
 
  T& PeekBack(); // [tested]
 
  bool Contains(const T& value) const; // [tested]
 
  plUInt32 IndexOf(const T& value, plUInt32 uiStartIndex = 0) const; // [tested]
 
  plUInt32 LastIndexOf(const T& value, plUInt32 uiStartIndex = plInvalidIndex) const; // [tested]
 
  void RemoveAtAndSwap(plUInt32 uiIndex); // [tested]
 
  void RemoveAtAndCopy(plUInt32 uiIndex); // [tested]
 
  bool RemoveAndCopy(const T& value); // [tested]
 
  bool RemoveAndSwap(const T& value); // [tested]
 
  void InsertAt(plUInt32 uiIndex, const T& value); // [tested]
 
  template <typename Comparer>
  void Sort(const Comparer& comparer); // [tested]
 
  void Sort(); // [tested]
 
  plAllocator* GetAllocator() const { return m_pAllocator; }
 
  using const_iterator = const_iterator_base<plDequeBase<T, Construct>, T, false>;
  using const_reverse_iterator = const_iterator_base<plDequeBase<T, Construct>, T, true>;
  using iterator = iterator_base<plDequeBase<T, Construct>, T, false>;
  using reverse_iterator = iterator_base<plDequeBase<T, Construct>, T, true>;
 
  plUInt32 GetContiguousRange(plUInt32 uiStartIndex) const; // [tested]
 
  bool operator==(const plDequeBase<T, Construct>& rhs) const; // [tested]
 
  PL_ADD_DEFAULT_OPERATOR_NOTEQUAL(const plDequeBase<T, Construct>&);
 
  plUInt64 GetHeapMemoryUsage() const; // [tested]
 
private:
  void Constructor(plAllocator* pAllocator);
 
  void CompactIndexArray(plUInt32 uiMinChunksToKeep);
 
  void MoveIndexChunksLeft(plUInt32 uiChunkDiff);
 
  void MoveIndexChunksRight(plUInt32 uiChunkDiff);
 
  plUInt32 GetFirstUsedChunk() const;
 
  plUInt32 GetLastUsedChunk(plUInt32 uiAtSize) const;
 
  plUInt32 GetLastUsedChunk() const;
 
  plUInt32 GetRequiredChunks(plUInt32 uiAtSize) const;
 
  void DeallocateUnusedChunks(plUInt32 uiMaxChunks);
 
  void ResetReduceSizeCounter();
 
  void ReduceSize(plInt32 iReduction);
 
  plUInt32 GetCurMaxCount() const;
 
  T* GetUnusedChunk();
 
  T& ElementAt(plUInt32 uiIndex);
 
  void DeallocateAll();
 
  plAllocator* m_pAllocator;
  T** m_pChunks;                
  plUInt32 m_uiChunks;          
  plUInt32 m_uiFirstElement;    
  plUInt32 m_uiCount;           
  plUInt32 m_uiAllocatedChunks; 
  plInt32 m_iReduceSizeTimer;   
  plUInt32 m_uiMaxCount;        
 
#if PL_ENABLED(PL_COMPILE_FOR_DEBUG)
  plUInt32 m_uiChunkSize; // needed for debugger visualization
#endif
};
 
template <typename T, typename AllocatorWrapper = plDefaultAllocatorWrapper, bool Construct = true>
class plDeque : public plDequeBase<T, Construct>
{
public:
  plDeque();
  plDeque(plAllocator* pAllocator);
 
  plDeque(const plDeque<T, AllocatorWrapper, Construct>& other);
  plDeque(const plDequeBase<T, Construct>& other);
 
  plDeque(plDeque<T, AllocatorWrapper, Construct>&& other);
  plDeque(plDequeBase<T, Construct>&& other);
 
  void operator=(const plDeque<T, AllocatorWrapper, Construct>& rhs);
  void operator=(const plDequeBase<T, Construct>& rhs);
 
  void operator=(plDeque<T, AllocatorWrapper, Construct>&& rhs);
  void operator=(plDequeBase<T, Construct>&& rhs);
};
 
template <typename T, bool Construct>
typename plDequeBase<T, Construct>::iterator begin(plDequeBase<T, Construct>& ref_container)
{
  return typename plDequeBase<T, Construct>::iterator(ref_container, (size_t)0);
}
 
template <typename T, bool Construct>
typename plDequeBase<T, Construct>::const_iterator begin(const plDequeBase<T, Construct>& container)
{
  return typename plDequeBase<T, Construct>::const_iterator(container, (size_t)0);
}
 
template <typename T, bool Construct>
typename plDequeBase<T, Construct>::const_iterator cbegin(const plDequeBase<T, Construct>& container)
{
  return typename plDequeBase<T, Construct>::const_iterator(container, (size_t)0);
}
 
template <typename T, bool Construct>
typename plDequeBase<T, Construct>::reverse_iterator rbegin(plDequeBase<T, Construct>& ref_container)
{
  return typename plDequeBase<T, Construct>::reverse_iterator(ref_container, (size_t)0);
}
 
template <typename T, bool Construct>
typename plDequeBase<T, Construct>::const_reverse_iterator rbegin(const plDequeBase<T, Construct>& container)
{
  return typename plDequeBase<T, Construct>::const_reverse_iterator(container, (size_t)0);
}
 
template <typename T, bool Construct>
typename plDequeBase<T, Construct>::const_reverse_iterator crbegin(const plDequeBase<T, Construct>& container)
{
  return typename plDequeBase<T, Construct>::const_reverse_iterator(container, (size_t)0);
}
 
template <typename T, bool Construct>
typename plDequeBase<T, Construct>::iterator end(plDequeBase<T, Construct>& ref_container)
{
  return typename plDequeBase<T, Construct>::iterator(ref_container, (size_t)ref_container.GetCount());
}
 
template <typename T, bool Construct>
typename plDequeBase<T, Construct>::const_iterator end(const plDequeBase<T, Construct>& container)
{
  return typename plDequeBase<T, Construct>::const_iterator(container, (size_t)container.GetCount());
}
 
template <typename T, bool Construct>
typename plDequeBase<T, Construct>::const_iterator cend(const plDequeBase<T, Construct>& container)
{
  return typename plDequeBase<T, Construct>::const_iterator(container, (size_t)container.GetCount());
}
 
template <typename T, bool Construct>
typename plDequeBase<T, Construct>::reverse_iterator rend(plDequeBase<T, Construct>& ref_container)
{
  return typename plDequeBase<T, Construct>::reverse_iterator(ref_container, (size_t)ref_container.GetCount());
}
 
template <typename T, bool Construct>
typename plDequeBase<T, Construct>::const_reverse_iterator rend(const plDequeBase<T, Construct>& container)
{
  return typename plDequeBase<T, Construct>::const_reverse_iterator(container, (size_t)container.GetCount());
}
 
template <typename T, bool Construct>
typename plDequeBase<T, Construct>::const_reverse_iterator crend(const plDequeBase<T, Construct>& container)
{
  return typename plDequeBase<T, Construct>::const_reverse_iterator(container, (size_t)container.GetCount());
}
 
#include <Foundation/Containers/Implementation/Deque_inl.h>