nuclear@0: /************************************************************************************
nuclear@0: 
nuclear@0: Filename    :   OVR_Deque.h
nuclear@0: Content     :   Deque container
nuclear@0: Created     :   Nov. 15, 2013
nuclear@0: Authors     :   Dov Katz
nuclear@0: 
nuclear@0: Copyright   :   Copyright 2014 Oculus VR, LLC All Rights reserved.
nuclear@0: 
nuclear@0: Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License"); 
nuclear@0: you may not use the Oculus VR Rift SDK except in compliance with the License, 
nuclear@0: which is provided at the time of installation or download, or which 
nuclear@0: otherwise accompanies this software in either electronic or hard copy form.
nuclear@0: 
nuclear@0: You may obtain a copy of the License at
nuclear@0: 
nuclear@0: http://www.oculusvr.com/licenses/LICENSE-3.2 
nuclear@0: 
nuclear@0: Unless required by applicable law or agreed to in writing, the Oculus VR SDK 
nuclear@0: distributed under the License is distributed on an "AS IS" BASIS,
nuclear@0: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
nuclear@0: See the License for the specific language governing permissions and
nuclear@0: limitations under the License.
nuclear@0: 
nuclear@0: *************************************************************************************/
nuclear@0: 
nuclear@0: #ifndef OVR_Deque_h
nuclear@0: #define OVR_Deque_h
nuclear@0: 
nuclear@0: #include "OVR_ContainerAllocator.h"
nuclear@0: 
nuclear@0: namespace OVR{ 
nuclear@0: 
nuclear@0: template <class Elem, class Allocator = ContainerAllocator<Elem> >
nuclear@0: class Deque
nuclear@0: {
nuclear@0: public:
nuclear@0:     enum
nuclear@0:     {
nuclear@0:         DefaultCapacity = 500
nuclear@0:     };
nuclear@0: 
nuclear@0:     Deque(int capacity = DefaultCapacity);
nuclear@0:     virtual ~Deque(void);
nuclear@0: 
nuclear@0:     virtual void         PushBack   (const Elem &Item);    // Adds Item to the end
nuclear@0:     virtual void         PushFront  (const Elem &Item);    // Adds Item to the beginning
nuclear@0:     virtual Elem         PopBack    (void);                // Removes Item from the end
nuclear@0:     virtual Elem         PopFront   (void);                // Removes Item from the beginning
nuclear@0:     virtual const Elem&  PeekBack   (int count = 0) const; // Returns count-th Item from the end
nuclear@0:     virtual const Elem&  PeekFront  (int count = 0) const; // Returns count-th Item from the beginning
nuclear@0: 
nuclear@0: 	virtual inline size_t GetSize    (void)          const; // Returns Number of Elements
nuclear@0: 	OVR_FORCE_INLINE int GetSizeI   (void)          const
nuclear@0: 	{
nuclear@0: 		return (int)GetSize();
nuclear@0: 	}
nuclear@0:     virtual inline size_t GetCapacity(void)          const; // Returns the maximum possible number of elements
nuclear@0:     virtual void         Clear      (void);				   // Remove all elements
nuclear@0:     virtual inline bool  IsEmpty    ()              const;
nuclear@0:     virtual inline bool  IsFull     ()              const;
nuclear@0: 
nuclear@0: protected:
nuclear@0:     Elem        *Data;          // The actual Data array
nuclear@0:     const int   Capacity;       // Deque capacity
nuclear@0:     int         Beginning;      // Index of the first element
nuclear@0:     int         End;            // Index of the next after last element
nuclear@0: 
nuclear@0:     // Instead of calculating the number of elements, using this variable
nuclear@0:     // is much more convenient.
nuclear@0:     int         ElemCount;
nuclear@0: 
nuclear@0: private:
nuclear@0:     OVR_NON_COPYABLE(Deque);
nuclear@0: };
nuclear@0: 
nuclear@0: template <class Elem, class Allocator = ContainerAllocator<Elem> >
nuclear@0: class InPlaceMutableDeque : public Deque<Elem, Allocator>
nuclear@0: {
nuclear@0:     typedef Deque<Elem, Allocator> BaseType;
nuclear@0: 
nuclear@0: public:
nuclear@0:     InPlaceMutableDeque( int capacity = BaseType::DefaultCapacity ) : BaseType( capacity ) {}
nuclear@0: 	virtual ~InPlaceMutableDeque() {};
nuclear@0: 
nuclear@0:     using BaseType::PeekBack;
nuclear@0:     using BaseType::PeekFront;
nuclear@0: 	virtual Elem& PeekBack  (int count = 0); // Returns count-th Item from the end
nuclear@0: 	virtual Elem& PeekFront (int count = 0); // Returns count-th Item from the beginning
nuclear@0: };
nuclear@0: 
nuclear@0: // Same as Deque, but allows to write more elements than maximum capacity
nuclear@0: // Old elements are lost as they are overwritten with the new ones
nuclear@0: template <class Elem, class Allocator = ContainerAllocator<Elem> >
nuclear@0: class CircularBuffer : public InPlaceMutableDeque<Elem, Allocator>
nuclear@0: {
nuclear@0:     typedef InPlaceMutableDeque<Elem, Allocator> BaseType;
nuclear@0: 
nuclear@0: public:
nuclear@0:     CircularBuffer(int MaxSize = BaseType::DefaultCapacity) : BaseType(MaxSize) { };
nuclear@0:     virtual ~CircularBuffer(){}
nuclear@0: 
nuclear@0:     // The following methods are inline as a workaround for a VS bug causing erroneous C4505 warnings
nuclear@0:     // See: http://stackoverflow.com/questions/3051992/compiler-warning-at-c-template-base-class
nuclear@0:     inline virtual void PushBack  (const Elem &Item);    // Adds Item to the end, overwriting the oldest element at the beginning if necessary
nuclear@0:     inline virtual void PushFront (const Elem &Item);    // Adds Item to the beginning, overwriting the oldest element at the end if necessary
nuclear@0: };
nuclear@0: 
nuclear@0: //----------------------------------------------------------------------------------
nuclear@0: 
nuclear@0: // Deque Constructor function
nuclear@0: template <class Elem, class Allocator>
nuclear@0: Deque<Elem, Allocator>::Deque(int capacity) :
nuclear@0: Capacity( capacity ), Beginning(0), End(0), ElemCount(0)
nuclear@0: {
nuclear@0:     Data = (Elem*) Allocator::Alloc(Capacity * sizeof(Elem));
nuclear@0: }
nuclear@0: 
nuclear@0: // Deque Destructor function
nuclear@0: template <class Elem, class Allocator>
nuclear@0: Deque<Elem, Allocator>::~Deque(void)
nuclear@0: {
nuclear@0:     Clear();
nuclear@0:     Allocator::Free(Data);
nuclear@0: }
nuclear@0: 
nuclear@0: template <class Elem, class Allocator>
nuclear@0: void Deque<Elem, Allocator>::Clear()
nuclear@0: {
nuclear@0:     if (!IsEmpty())
nuclear@0:     {
nuclear@0:         if (Beginning < End)
nuclear@0:         {
nuclear@0:             // no wrap-around
nuclear@0:             Allocator::DestructArray(Data + Beginning, End - Beginning);
nuclear@0:         }
nuclear@0:         else
nuclear@0:         {
nuclear@0:             // wrap-around
nuclear@0:             Allocator::DestructArray(Data + Beginning, Capacity - Beginning);
nuclear@0:             Allocator::DestructArray(Data, End);
nuclear@0:         }
nuclear@0:     }
nuclear@0:     
nuclear@0:     Beginning = 0;
nuclear@0:     End       = 0;
nuclear@0:     ElemCount = 0;
nuclear@0: }
nuclear@0: 
nuclear@0: // Push functions
nuclear@0: template <class Elem, class Allocator>
nuclear@0: void Deque<Elem, Allocator>::PushBack(const Elem &Item)
nuclear@0: {
nuclear@0:     // Error Check: Make sure we aren't  
nuclear@0:     // exceeding our maximum storage space
nuclear@0:     OVR_ASSERT( ElemCount < Capacity );
nuclear@0: 
nuclear@0:     Allocator::Construct(Data + End, Item);
nuclear@0:     ++End;
nuclear@0:     ++ElemCount;
nuclear@0: 
nuclear@0:     // Check for wrap-around
nuclear@0:     if (End >= Capacity)
nuclear@0:         End -= Capacity;
nuclear@0: }
nuclear@0: 
nuclear@0: template <class Elem, class Allocator>
nuclear@0: void Deque<Elem, Allocator>::PushFront(const Elem &Item)
nuclear@0: {
nuclear@0:     // Error Check: Make sure we aren't  
nuclear@0:     // exceeding our maximum storage space
nuclear@0:     OVR_ASSERT( ElemCount < Capacity );
nuclear@0: 
nuclear@0:     --Beginning;
nuclear@0:     // Check for wrap-around
nuclear@0:     if (Beginning < 0)
nuclear@0:         Beginning += Capacity;
nuclear@0: 
nuclear@0:     Allocator::Construct(Data + Beginning, Item);
nuclear@0:     ++ElemCount;
nuclear@0: }
nuclear@0: 
nuclear@0: // Pop functions
nuclear@0: template <class Elem, class Allocator>
nuclear@0: Elem Deque<Elem, Allocator>::PopFront(void)
nuclear@0: {
nuclear@0:     // Error Check: Make sure we aren't reading from an empty Deque
nuclear@0:     OVR_ASSERT( ElemCount > 0 );
nuclear@0: 
nuclear@0: 	Elem ReturnValue = Data[ Beginning ];
nuclear@0:     Allocator::Destruct(Data + Beginning);
nuclear@0: 
nuclear@0: 	++Beginning;
nuclear@0:     --ElemCount;
nuclear@0: 
nuclear@0:     // Check for wrap-around
nuclear@0:     if (Beginning >= Capacity)
nuclear@0:         Beginning -= Capacity;
nuclear@0: 
nuclear@0:     return ReturnValue;
nuclear@0: }
nuclear@0: 
nuclear@0: template <class Elem, class Allocator>
nuclear@0: Elem Deque<Elem, Allocator>::PopBack(void)
nuclear@0: {
nuclear@0:     // Error Check: Make sure we aren't reading from an empty Deque
nuclear@0:     OVR_ASSERT( ElemCount > 0 );
nuclear@0: 
nuclear@0:     --End;
nuclear@0:     --ElemCount;
nuclear@0: 
nuclear@0:     // Check for wrap-around
nuclear@0:     if (End < 0)
nuclear@0:         End += Capacity;
nuclear@0: 
nuclear@0:     Elem ReturnValue = Data[ End ];
nuclear@0:     Allocator::Destruct(Data + End);
nuclear@0: 
nuclear@0:     return ReturnValue;
nuclear@0: }
nuclear@0: 
nuclear@0: // Peek functions
nuclear@0: template <class Elem, class Allocator>
nuclear@0: const Elem& Deque<Elem, Allocator>::PeekFront(int count) const
nuclear@0: {
nuclear@0:     // Error Check: Make sure we aren't reading from an empty Deque
nuclear@0:     OVR_ASSERT( ElemCount > count );
nuclear@0: 
nuclear@0:     int idx = Beginning + count;
nuclear@0:     if (idx >= Capacity)
nuclear@0:         idx -= Capacity;
nuclear@0:     return Data[ idx ];
nuclear@0: }
nuclear@0: 
nuclear@0: template <class Elem, class Allocator>
nuclear@0: const Elem& Deque<Elem, Allocator>::PeekBack(int count) const
nuclear@0: {
nuclear@0:     // Error Check: Make sure we aren't reading from an empty Deque
nuclear@0:     OVR_ASSERT( ElemCount > count );
nuclear@0: 
nuclear@0:     int idx = End - count - 1;
nuclear@0:     if (idx < 0)
nuclear@0:         idx += Capacity;
nuclear@0:     return Data[ idx ];
nuclear@0: }
nuclear@0: 
nuclear@0: // Mutable Peek functions
nuclear@0: template <class Elem, class Allocator>
nuclear@0: Elem& InPlaceMutableDeque<Elem, Allocator>::PeekFront(int count)
nuclear@0: {
nuclear@0:     // Error Check: Make sure we aren't reading from an empty Deque
nuclear@0:     OVR_ASSERT( BaseType::ElemCount > count );
nuclear@0: 
nuclear@0:     int idx = BaseType::Beginning + count;
nuclear@0:     if (idx >= BaseType::Capacity)
nuclear@0:         idx -= BaseType::Capacity;
nuclear@0:     return BaseType::Data[ idx ];
nuclear@0: }
nuclear@0: 
nuclear@0: template <class Elem, class Allocator>
nuclear@0: Elem& InPlaceMutableDeque<Elem, Allocator>::PeekBack(int count)
nuclear@0: {
nuclear@0:     // Error Check: Make sure we aren't reading from an empty Deque
nuclear@0:     OVR_ASSERT( BaseType::ElemCount > count );
nuclear@0: 
nuclear@0:     int idx = BaseType::End - count - 1;
nuclear@0:     if (idx < 0)
nuclear@0:         idx += BaseType::Capacity;
nuclear@0:     return BaseType::Data[ idx ];
nuclear@0: }
nuclear@0: 
nuclear@0: template <class Elem, class Allocator>
nuclear@0: inline size_t Deque<Elem, Allocator>::GetCapacity(void) const
nuclear@0: {
nuclear@0:     return Capacity;
nuclear@0: }
nuclear@0: 
nuclear@0: template <class Elem, class Allocator>
nuclear@0: inline size_t Deque<Elem, Allocator>::GetSize(void) const
nuclear@0: {
nuclear@0:     return ElemCount;
nuclear@0: }
nuclear@0: 
nuclear@0: template <class Elem, class Allocator>
nuclear@0: inline bool Deque<Elem, Allocator>::IsEmpty(void) const
nuclear@0: {
nuclear@0:     return ElemCount == 0;
nuclear@0: }
nuclear@0: 
nuclear@0: template <class Elem, class Allocator>
nuclear@0: inline bool Deque<Elem, Allocator>::IsFull(void) const
nuclear@0: {
nuclear@0:     return ElemCount == Capacity;
nuclear@0: }
nuclear@0: 
nuclear@0: // ******* CircularBuffer<Elem> *******
nuclear@0: // Push functions
nuclear@0: template <class Elem, class Allocator>
nuclear@0: void CircularBuffer<Elem, Allocator>::PushBack(const Elem &Item)
nuclear@0: {
nuclear@0:     if (this->IsFull())
nuclear@0:         this->PopFront();
nuclear@0:     BaseType::PushBack(Item);
nuclear@0: }
nuclear@0: 
nuclear@0: template <class Elem, class Allocator>
nuclear@0: void CircularBuffer<Elem, Allocator>::PushFront(const Elem &Item)
nuclear@0: {
nuclear@0:     if (this->IsFull())
nuclear@0:         this->PopBack();
nuclear@0:     BaseType::PushFront(Item);
nuclear@0: }
nuclear@0: 
nuclear@0: };   
nuclear@0: 
nuclear@0: #endif