path: root/LibOVR/Src/Kernel/OVR_Deque.h

/************************************************************************************

Filename    :   OVR_Deque.h
Content     :   Deque container
Created     :   Nov. 15, 2013
Authors     :   Dov Katz

Copyright   :   Copyright 2014 Oculus VR, Inc. All Rights reserved.

Licensed under the Oculus VR Rift SDK License Version 3.1 (the "License"); 
you may not use the Oculus VR Rift SDK except in compliance with the License, 
which is provided at the time of installation or download, or which 
otherwise accompanies this software in either electronic or hard copy form.

You may obtain a copy of the License at

http://www.oculusvr.com/licenses/LICENSE-3.1 

Unless required by applicable law or agreed to in writing, the Oculus VR SDK 
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

*************************************************************************************/

#ifndef OVR_Deque_h
#define OVR_Deque_h

#include "OVR_ContainerAllocator.h"

namespace OVR{ 

template <class Elem, class Allocator = ContainerAllocator<Elem> >
class Deque
{
public:
    enum
    {
        DefaultCapacity = 500
    };

    Deque(int capacity = DefaultCapacity);
    virtual ~Deque(void);

    virtual void         PushBack   (const Elem &Item);    // Adds Item to the end
    virtual void         PushFront  (const Elem &Item);    // Adds Item to the beginning
    virtual Elem         PopBack    (void);                // Removes Item from the end
    virtual Elem         PopFront   (void);                // Removes Item from the beginning
    virtual const Elem&  PeekBack   (int count = 0) const; // Returns count-th Item from the end
    virtual const Elem&  PeekFront  (int count = 0) const; // Returns count-th Item from the beginning

	virtual inline size_t GetSize    (void)          const; // Returns Number of Elements
	OVR_FORCE_INLINE int GetSizeI   (void)          const
	{
		return (int)GetSize();
	}
    virtual inline size_t GetCapacity(void)          const; // Returns the maximum possible number of elements
    virtual void         Clear      (void);				   // Remove all elements
    virtual inline bool  IsEmpty    ()              const;
    virtual inline bool  IsFull     ()              const;

protected:
    Elem        *Data;          // The actual Data array
    const int   Capacity;       // Deque capacity
    int         Beginning;      // Index of the first element
    int         End;            // Index of the next after last element

    // Instead of calculating the number of elements, using this variable
    // is much more convenient.
    int         ElemCount;

private:
    Deque&      operator= (const Deque& q) { }; // forbidden
    Deque(const Deque<Elem, Allocator> &OtherDeque) { };
};

template <class Elem, class Allocator = ContainerAllocator<Elem> >
class InPlaceMutableDeque : public Deque<Elem, Allocator>
{
    typedef Deque<Elem, Allocator> BaseType;

public:
    InPlaceMutableDeque( int capacity = BaseType::DefaultCapacity ) : BaseType( capacity ) {}
	virtual ~InPlaceMutableDeque() {};

    using BaseType::PeekBack;
    using BaseType::PeekFront;
	virtual Elem& PeekBack  (int count = 0); // Returns count-th Item from the end
	virtual Elem& PeekFront (int count = 0); // Returns count-th Item from the beginning
};

// Same as Deque, but allows to write more elements than maximum capacity
// Old elements are lost as they are overwritten with the new ones
template <class Elem, class Allocator = ContainerAllocator<Elem> >
class CircularBuffer : public InPlaceMutableDeque<Elem, Allocator>
{
    typedef InPlaceMutableDeque<Elem, Allocator> BaseType;

public:
    CircularBuffer(int MaxSize = BaseType::DefaultCapacity) : BaseType(MaxSize) { };

    // The following methods are inline as a workaround for a VS bug causing erroneous C4505 warnings
    // See: http://stackoverflow.com/questions/3051992/compiler-warning-at-c-template-base-class
    inline virtual void PushBack  (const Elem &Item);    // Adds Item to the end, overwriting the oldest element at the beginning if necessary
    inline virtual void PushFront (const Elem &Item);    // Adds Item to the beginning, overwriting the oldest element at the end if necessary
};

//----------------------------------------------------------------------------------

// Deque Constructor function
template <class Elem, class Allocator>
Deque<Elem, Allocator>::Deque(int capacity) :
Capacity( capacity ), Beginning(0), End(0), ElemCount(0)
{
    Data = (Elem*) Allocator::Alloc(Capacity * sizeof(Elem));
}

// Deque Destructor function
template <class Elem, class Allocator>
Deque<Elem, Allocator>::~Deque(void)
{
    Clear();
    Allocator::Free(Data);
}

template <class Elem, class Allocator>
void Deque<Elem, Allocator>::Clear()
{
    if (!IsEmpty())
    {
        if (Beginning < End)
        {
            // no wrap-around
            Allocator::DestructArray(Data + Beginning, End - Beginning);
        }
        else
        {
            // wrap-around
            Allocator::DestructArray(Data + Beginning, Capacity - Beginning);
            Allocator::DestructArray(Data, End);
        }
    }
    
    Beginning = 0;
    End       = 0;
    ElemCount = 0;
}

// Push functions
template <class Elem, class Allocator>
void Deque<Elem, Allocator>::PushBack(const Elem &Item)
{
    // Error Check: Make sure we aren't  
    // exceeding our maximum storage space
    OVR_ASSERT( ElemCount < Capacity );

    Allocator::Construct(Data + End, Item);
    ++End;
    ++ElemCount;

    // Check for wrap-around
    if (End >= Capacity)
        End -= Capacity;
}

template <class Elem, class Allocator>
void Deque<Elem, Allocator>::PushFront(const Elem &Item)
{
    // Error Check: Make sure we aren't  
    // exceeding our maximum storage space
    OVR_ASSERT( ElemCount < Capacity );

    --Beginning;
    // Check for wrap-around
    if (Beginning < 0)
        Beginning += Capacity;

    Allocator::Construct(Data + Beginning, Item);
    ++ElemCount;
}

// Pop functions
template <class Elem, class Allocator>
Elem Deque<Elem, Allocator>::PopFront(void)
{
    // Error Check: Make sure we aren't reading from an empty Deque
    OVR_ASSERT( ElemCount > 0 );

	Elem ReturnValue = Data[ Beginning ];
    Allocator::Destruct(Data + Beginning);

	++Beginning;
    --ElemCount;

    // Check for wrap-around
    if (Beginning >= Capacity)
        Beginning -= Capacity;

    return ReturnValue;
}

template <class Elem, class Allocator>
Elem Deque<Elem, Allocator>::PopBack(void)
{
    // Error Check: Make sure we aren't reading from an empty Deque
    OVR_ASSERT( ElemCount > 0 );

    --End;
    --ElemCount;

    // Check for wrap-around
    if (End < 0)
        End += Capacity;

    Elem ReturnValue = Data[ End ];
    Allocator::Destruct(Data + End);

    return ReturnValue;
}

// Peek functions
template <class Elem, class Allocator>
const Elem& Deque<Elem, Allocator>::PeekFront(int count) const
{
    // Error Check: Make sure we aren't reading from an empty Deque
    OVR_ASSERT( ElemCount > count );

    int idx = Beginning + count;
    if (idx >= Capacity)
        idx -= Capacity;
    return Data[ idx ];
}

template <class Elem, class Allocator>
const Elem& Deque<Elem, Allocator>::PeekBack(int count) const
{
    // Error Check: Make sure we aren't reading from an empty Deque
    OVR_ASSERT( ElemCount > count );

    int idx = End - count - 1;
    if (idx < 0)
        idx += Capacity;
    return Data[ idx ];
}

// Mutable Peek functions
template <class Elem, class Allocator>
Elem& InPlaceMutableDeque<Elem, Allocator>::PeekFront(int count)
{
    // Error Check: Make sure we aren't reading from an empty Deque
    OVR_ASSERT( BaseType::ElemCount > count );

    int idx = BaseType::Beginning + count;
    if (idx >= BaseType::Capacity)
        idx -= BaseType::Capacity;
    return BaseType::Data[ idx ];
}

template <class Elem, class Allocator>
Elem& InPlaceMutableDeque<Elem, Allocator>::PeekBack(int count)
{
    // Error Check: Make sure we aren't reading from an empty Deque
    OVR_ASSERT( BaseType::ElemCount > count );

    int idx = BaseType::End - count - 1;
    if (idx < 0)
        idx += BaseType::Capacity;
    return BaseType::Data[ idx ];
}

template <class Elem, class Allocator>
inline size_t Deque<Elem, Allocator>::GetCapacity(void) const
{
    return Capacity;
}

template <class Elem, class Allocator>
inline size_t Deque<Elem, Allocator>::GetSize(void) const
{
    return ElemCount;
}

template <class Elem, class Allocator>
inline bool Deque<Elem, Allocator>::IsEmpty(void) const
{
    return ElemCount == 0;
}

template <class Elem, class Allocator>
inline bool Deque<Elem, Allocator>::IsFull(void) const
{
    return ElemCount == Capacity;
}

// ******* CircularBuffer<Elem> *******
// Push functions
template <class Elem, class Allocator>
void CircularBuffer<Elem, Allocator>::PushBack(const Elem &Item)
{
    if (this->IsFull())
        this->PopFront();
    BaseType::PushBack(Item);
}

template <class Elem, class Allocator>
void CircularBuffer<Elem, Allocator>::PushFront(const Elem &Item)
{
    if (this->IsFull())
        this->PopBack();
    BaseType::PushFront(Item);
}

};   

#endif