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

namespace OVR{ 

template <class 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 UPInt GetSize    (void)          const; // Returns Number of Elements
    virtual inline UPInt 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> &OtherDeque) { };
};

template <class Elem>
class InPlaceMutableDeque : public Deque<Elem>
{
public:
    InPlaceMutableDeque( int capacity = Deque<Elem>::DefaultCapacity ) : Deque<Elem>( capacity ) {}
	virtual ~InPlaceMutableDeque() {};

    using Deque<Elem>::PeekBack;
    using Deque<Elem>::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 CircularBuffer : public InPlaceMutableDeque<Elem>
{
public:
    CircularBuffer(int MaxSize = Deque<Elem>::DefaultCapacity) : InPlaceMutableDeque<Elem>(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>
Deque<Elem>::Deque(int capacity) :
Capacity( capacity ), Beginning(0), End(0), ElemCount(0)
{
    Data = (Elem*) OVR_ALLOC(Capacity * sizeof(Elem));
    ConstructArray<Elem>(Data, Capacity);
}

// Deque Destructor function
template <class Elem>
Deque<Elem>::~Deque(void)
{
    DestructArray<Elem>(Data, Capacity);
    OVR_FREE(Data);
}

template <class Elem>
void Deque<Elem>::Clear()
{
    Beginning = 0;
    End       = 0;
    ElemCount = 0;

    DestructArray<Elem>(Data, Capacity);
    ConstructArray<Elem>(Data, Capacity);
}

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

    Data[ End++ ] = Item;
    ++ElemCount;

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

template <class Elem>
void Deque<Elem>::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;

    Data[ Beginning ] = Item;
    ++ElemCount;
}

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

	Elem ReturnValue = Data[ Beginning ];
    Destruct<Elem>(&Data[ Beginning ]);
    Construct<Elem>(&Data[ Beginning ]);

	++Beginning;
    --ElemCount;

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

    return ReturnValue;
}

template <class Elem>
Elem Deque<Elem>::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 ];
    Destruct<Elem>(&Data[ End ]);
    Construct<Elem>(&Data[ End ]);

    return ReturnValue;
}

// Peek functions
template <class Elem>
const Elem& Deque<Elem>::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>
const Elem& Deque<Elem>::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>
Elem& InPlaceMutableDeque<Elem>::PeekFront(int count)
{
    // Error Check: Make sure we aren't reading from an empty Deque
    OVR_ASSERT( Deque<Elem>::ElemCount > count );

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

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

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

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

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

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

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

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

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

};   

#endif