A queue implemented as an array with a read and write index.

#include <DS_Queue.h>

Inheritance diagram for DataStructures::Queue< queue_type >:

Public Member Functions
unsigned int	AllocationSize (void) const
void	Clear (const char *file, unsigned int line)
void	ClearAndForceAllocation (int size, const char *file, unsigned int line)
void	Compress (const char *file, unsigned int line)
bool	Find (queue_type q)
bool	IsEmpty (void) const
bool	operator= (const Queue &original_copy)
queue_type &	operator[] (unsigned int position) const
queue_type	Peek (void) const
queue_type	PeekTail (void) const
queue_type	Pop (void)
queue_type	PopDeref (void)
void	Push (const queue_type &input, const char *file, unsigned int line)
void	PushAtHead (const queue_type &input, unsigned index, const char *file, unsigned int line)
	Queue ()
	Queue (Queue &original_copy)
void	RemoveAtIndex (unsigned int position)
unsigned int	Size (void) const
	~Queue ()
Private Attributes
unsigned int	allocation_size
queue_type *	array
unsigned int	head
unsigned int	tail

Detailed Description

template<class queue_type>
class DataStructures::Queue< queue_type >

Definition at line 24 of file DS_Queue.h.

Constructor & Destructor Documentation

template<class queue_type >

DataStructures::Queue< queue_type >::Queue ( )

Definition at line 78 of file DS_Queue.h.

    {
        //allocation_size = 16;
        //array = RakNet::OP_NEW_ARRAY<queue_type>(allocation_size, _FILE_AND_LINE_ );
        allocation_size = 0;
        array=0;
        head = 0;
        tail = 0;
    }

template<class queue_type >

DataStructures::Queue< queue_type >::~Queue ( )

Definition at line 89 of file DS_Queue.h.

References _FILE_AND_LINE_, and RakNet::OP_DELETE_ARRAY().

    {
        if (allocation_size>0)
            RakNet::OP_DELETE_ARRAY(array, _FILE_AND_LINE_);
    }

template<class queue_type >

DataStructures::Queue< queue_type >::Queue ( Queue< queue_type > & original_copy )

Definition at line 245 of file DS_Queue.h.

References _FILE_AND_LINE_, DataStructures::Queue< queue_type >::allocation_size, DataStructures::Queue< queue_type >::array, DataStructures::Queue< queue_type >::head, and DataStructures::Queue< queue_type >::Size().

    {
        // Allocate memory for copy

        if ( original_copy.Size() == 0 )
        {
            allocation_size = 0;
        }

        else
        {
            array = RakNet::OP_NEW_ARRAY<queue_type >( original_copy.Size() + 1 , _FILE_AND_LINE_ );

            for ( unsigned int counter = 0; counter < original_copy.Size(); ++counter )
                array[ counter ] = original_copy.array[ ( original_copy.head + counter ) % ( original_copy.allocation_size ) ];

            head = 0;

            tail = original_copy.Size();

            allocation_size = original_copy.Size() + 1;
        }
    }

Member Function Documentation

template<class queue_type >

unsigned int DataStructures::Queue< queue_type >::AllocationSize ( void ) const [inline]

Definition at line 72 of file DS_Queue.h.

    {
        return allocation_size;
    }

template<class queue_type >

void DataStructures::Queue< queue_type >::Clear	(	const char *	file,
		unsigned int	line
	)		`[inline]`

Definition at line 301 of file DS_Queue.h.

References RakNet::OP_DELETE_ARRAY().

    {
        if ( allocation_size == 0 )
            return ;

        if (allocation_size > 32)
        {
            RakNet::OP_DELETE_ARRAY(array, file, line);
            allocation_size = 0;
        }

        head = 0;
        tail = 0;
    }

template<class queue_type >

void DataStructures::Queue< queue_type >::ClearAndForceAllocation	(	int	size,
		const char *	file,
		unsigned int	line
	)

Definition at line 362 of file DS_Queue.h.

References RakNet::OP_DELETE_ARRAY().

    {
        RakNet::OP_DELETE_ARRAY(array, file, line);
        if (size>0)
            array = RakNet::OP_NEW_ARRAY<queue_type>(size, file, line );
        else
            array=0;
        allocation_size = size;
        head = 0;
        tail = 0;
    }

template<class queue_type >

void DataStructures::Queue< queue_type >::Compress	(	const char *	file,
		unsigned int	line
	)

Definition at line 317 of file DS_Queue.h.

References RakNet::OP_DELETE_ARRAY().

    {
        queue_type* new_array;
        unsigned int newAllocationSize;
        if (allocation_size==0)
            return;

        newAllocationSize=1;
        while (newAllocationSize <= Size())
            newAllocationSize<<=1; // Must be a better way to do this but I'm too dumb to figure it out quickly :)

        new_array = RakNet::OP_NEW_ARRAY<queue_type >(newAllocationSize, file, line );

        for (unsigned int counter=0; counter < Size(); ++counter)
            new_array[counter] = array[(head + counter)%(allocation_size)];

        tail=Size();
        allocation_size=newAllocationSize;
        head=0;

        // Delete the old array and move the pointer to the new array
        RakNet::OP_DELETE_ARRAY(array, file, line);
        array=new_array;
    }

template<class queue_type>

bool DataStructures::Queue< queue_type >::Find ( queue_type q )

Definition at line 343 of file DS_Queue.h.

    {
        if ( allocation_size == 0 )
            return false;

        unsigned int counter = head;

        while ( counter != tail )
        {
            if ( array[ counter ] == q )
                return true;

            counter = ( counter + 1 ) % allocation_size;
        }

        return false;
    }

template<class queue_type >

bool DataStructures::Queue< queue_type >::IsEmpty ( void ) const [inline]

Definition at line 66 of file DS_Queue.h.

    {
        return head==tail;
    }

template<class queue_type >

bool DataStructures::Queue< queue_type >::operator= ( const Queue< queue_type > & original_copy )

Definition at line 270 of file DS_Queue.h.

References _FILE_AND_LINE_, DataStructures::Queue< queue_type >::allocation_size, DataStructures::Queue< queue_type >::array, DataStructures::Queue< queue_type >::head, and DataStructures::Queue< queue_type >::Size().

    {
        if ( ( &original_copy ) == this )
            return false;

        Clear(_FILE_AND_LINE_);

        // Allocate memory for copy
        if ( original_copy.Size() == 0 )
        {
            allocation_size = 0;
        }

        else
        {
            array = RakNet::OP_NEW_ARRAY<queue_type >( original_copy.Size() + 1 , _FILE_AND_LINE_ );

            for ( unsigned int counter = 0; counter < original_copy.Size(); ++counter )
                array[ counter ] = original_copy.array[ ( original_copy.head + counter ) % ( original_copy.allocation_size ) ];

            head = 0;

            tail = original_copy.Size();

            allocation_size = original_copy.Size() + 1;
        }

        return true;
    }

template<class queue_type >

queue_type & DataStructures::Queue< queue_type >::operator[] ( unsigned int position ) const [inline]

Definition at line 375 of file DS_Queue.h.

References RakAssert.

    {
#ifdef _DEBUG
        RakAssert( position < Size() );
#endif
        //return array[(head + position) % allocation_size];

        if ( head + position >= allocation_size )
            return array[ head + position - allocation_size ];
        else
            return array[ head + position ];
    }

template<class queue_type >

queue_type DataStructures::Queue< queue_type >::Peek ( void ) const [inline]

Definition at line 175 of file DS_Queue.h.

References RakAssert.

    {
#ifdef _DEBUG
        RakAssert( head != tail );
#endif

        return ( queue_type ) array[ head ];
    }

template<class queue_type >

queue_type DataStructures::Queue< queue_type >::PeekTail ( void ) const [inline]

Definition at line 185 of file DS_Queue.h.

References RakAssert.

        {
#ifdef _DEBUG
            RakAssert( head != tail );
#endif
            if (tail!=0)
                return ( queue_type ) array[ tail-1 ];
            else
                return ( queue_type ) array[ allocation_size-1 ];
        }

template<class queue_type >

queue_type DataStructures::Queue< queue_type >::Pop ( void ) [inline]

Definition at line 96 of file DS_Queue.h.

References RakAssert.

Referenced by DataStructures::BPlusTree< KeyType, DataType, order >::FreePages(), DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetShortestPath(), DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetSpanningTree(), DataStructures::Tree< TreeType >::LevelOrderTraversal(), DataStructures::BPlusTree< KeyType, DataType, order >::PrintGraph(), and DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::RemoveNode().

    {
#ifdef _DEBUG
        RakAssert( head != tail);
#endif
        //head=(head+1) % allocation_size;

        if ( ++head == allocation_size )
            head = 0;

        if ( head == 0 )
            return ( queue_type ) array[ allocation_size -1 ];

        return ( queue_type ) array[ head -1 ];
    }

template<class queue_type >

queue_type DataStructures::Queue< queue_type >::PopDeref ( void ) [inline]

Definition at line 113 of file DS_Queue.h.

        {
            if ( ++head == allocation_size )
                head = 0;

            queue_type q;
            if ( head == 0 )
            {
                q=array[ allocation_size -1 ];
                array[ allocation_size -1 ]=0;
                return q;
            }

            q=array[ head -1 ];
            array[ head -1 ]=0;
            return q;
        }

template<class queue_type>

void DataStructures::Queue< queue_type >::Push	(	const queue_type &	input,
		const char *	file,
		unsigned int	line
	)

Definition at line 197 of file DS_Queue.h.

References RakNet::OP_DELETE_ARRAY(), and RakAssert.

Referenced by DataStructures::BPlusTree< KeyType, DataType, order >::FreePages(), DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetSpanningTree(), DataStructures::Tree< TreeType >::LevelOrderTraversal(), DataStructures::BPlusTree< KeyType, DataType, order >::PrintGraph(), RakNet::BPSTracker::Push1(), DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::PushAtHead(), and DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::RemoveNode().

    {
        if ( allocation_size == 0 )
        {
            array = RakNet::OP_NEW_ARRAY<queue_type>(16, file, line );
            head = 0;
            tail = 1;
            array[ 0 ] = input;
            allocation_size = 16;
            return ;
        }

        array[ tail++ ] = input;

        if ( tail == allocation_size )
            tail = 0;

        if ( tail == head )
        {
            //  unsigned int index=tail;

            // Need to allocate more memory.
            queue_type * new_array;
            new_array = RakNet::OP_NEW_ARRAY<queue_type>(allocation_size * 2, file, line );
#ifdef _DEBUG
            RakAssert( new_array );
#endif
            if (new_array==0)
                return;

            for ( unsigned int counter = 0; counter < allocation_size; ++counter )
                new_array[ counter ] = array[ ( head + counter ) % ( allocation_size ) ];

            head = 0;

            tail = allocation_size;

            allocation_size *= 2;

            // Delete the old array and move the pointer to the new array
            RakNet::OP_DELETE_ARRAY(array, file, line);

            array = new_array;
        }

    }

template<class queue_type>

void DataStructures::Queue< queue_type >::PushAtHead	(	const queue_type &	input,
		unsigned	index,
		const char *	file,
		unsigned int	line
	)

Definition at line 132 of file DS_Queue.h.

References RakAssert.

Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetShortestPath(), and DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::PushAtHead().

    {
        RakAssert(index <= Size());

        // Just force a reallocation, will be overwritten
        Push(input, file, line );

        if (Size()==1)
            return;

        unsigned writeIndex, readIndex, trueWriteIndex, trueReadIndex;
        writeIndex=Size()-1;
        readIndex=writeIndex-1;
        while (readIndex >= index)
        {
            if ( head + writeIndex >= allocation_size )
                trueWriteIndex = head + writeIndex - allocation_size;
            else
                trueWriteIndex = head + writeIndex;

            if ( head + readIndex >= allocation_size )
                trueReadIndex = head + readIndex - allocation_size;
            else
                trueReadIndex = head + readIndex;

            array[trueWriteIndex]=array[trueReadIndex];

            if (readIndex==0)
                break;
            writeIndex--;
            readIndex--;
        }

        if ( head + index >= allocation_size )
            trueWriteIndex = head + index - allocation_size;
        else
            trueWriteIndex = head + index;

        array[trueWriteIndex]=input;
    }

template<class queue_type >

void DataStructures::Queue< queue_type >::RemoveAtIndex ( unsigned int position )

Definition at line 389 of file DS_Queue.h.

References RakAssert.

Referenced by DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::Pop().

    {
#ifdef _DEBUG
        RakAssert( position < Size() );
        RakAssert( head != tail );
#endif

        if ( head == tail || position >= Size() )
            return ;

        unsigned int index;

        unsigned int next;

        //index  = (head + position) % allocation_size;
        if ( head + position >= allocation_size )
            index = head + position - allocation_size;
        else
            index = head + position;

        //next = (index + 1) % allocation_size;
        next = index + 1;

        if ( next == allocation_size )
            next = 0;

        while ( next != tail )
        {
            // Overwrite the previous element
            array[ index ] = array[ next ];
            index = next;
            //next = (next + 1) % allocation_size;

            if ( ++next == allocation_size )
                next = 0;
        }

        // Move the tail back
        if ( tail == 0 )
            tail = allocation_size - 1;
        else
            --tail;
    }

template<class queue_type >

unsigned int DataStructures::Queue< queue_type >::Size ( void ) const [inline]

Definition at line 57 of file DS_Queue.h.

    {
        if ( head <= tail )
            return tail -head;
        else
            return allocation_size -head + tail;
    }

Member Data Documentation

template<class queue_type>

unsigned int DataStructures::Queue< queue_type >::allocation_size [private]

Definition at line 52 of file DS_Queue.h.

Referenced by DataStructures::Queue< queue_type >::operator=(), and DataStructures::Queue< queue_type >::Queue().

template<class queue_type>

queue_type* DataStructures::Queue< queue_type >::array [private]

Definition at line 49 of file DS_Queue.h.

Referenced by DataStructures::Queue< queue_type >::operator=(), and DataStructures::Queue< queue_type >::Queue().

template<class queue_type>

unsigned int DataStructures::Queue< queue_type >::head [private]

Definition at line 50 of file DS_Queue.h.

Referenced by DataStructures::Queue< queue_type >::operator=(), and DataStructures::Queue< queue_type >::Queue().

template<class queue_type>

unsigned int DataStructures::Queue< queue_type >::tail [private]

Definition at line 51 of file DS_Queue.h.

The documentation for this class was generated from the following file:

DS_Queue.h

Public Member Functions

Private Attributes

Detailed Description

template<class queue_type> class DataStructures::Queue< queue_type >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class queue_type>
class DataStructures::Queue< queue_type >