Array based implementation of a list. More...

#include <DS_List.h>

Public Member Functions
void	Clear (bool doNotDeallocateSmallBlocks, const char *file, unsigned int line)
	Clear the list.
void	Compress (const char *file, unsigned int line)
	Frees overallocated members, to use the minimum memory necessary.
list_type &	Get (const unsigned int position) const
	Access an element by its index in the array.
unsigned int	GetIndexOf (const list_type &input) const
	Returns the index of the specified item or MAX_UNSIGNED_LONG if not found.
void	Insert (const list_type &input, const unsigned int position, const char *file, unsigned int line)
	Insert an element at position position in the list.
void	Insert (const list_type &input, const char *file, unsigned int line)
	Insert at the end of the list.
	List ()
	Default constructor.
	List (const List &original_copy)
	Copy constructor.
List &	operator= (const List &original_copy)
	Assign one list to another.
list_type &	operator[] (const unsigned int position) const
	Access an element by its index in the array.
list_type &	Pop (void)
	Pop an element from the end of the stack.
void	Preallocate (unsigned countNeeded, const char *file, unsigned int line)
	Preallocate the list, so it needs fewer reallocations at runtime.
void	Push (const list_type &input, const char *file, unsigned int line)
	Push an element at the end of the stack.
void	RemoveAtIndex (const unsigned int position)
	Delete the element at position position.
void	RemoveAtIndexFast (const unsigned int position)
	Delete the element at position position.
void	RemoveFromEnd (const unsigned num=1)
	Delete the element at the end of the list.
void	Replace (const list_type &input, const list_type filler, const unsigned int position, const char *file, unsigned int line)
	Replace the value at position by input.
void	Replace (const list_type &input)
	Replace the last element of the list by input.
unsigned int	Size (void) const
	~List ()
Private Attributes
unsigned int	allocation_size
	Size of array.
unsigned int	list_size
	Number of elements in the list.
list_type *	listArray
	An array of user values.

Detailed Description

template<class list_type>
class DataStructures::List< list_type >

Note:: ONLY USE THIS FOR SHALLOW COPIES. I don't bother with operator= to improve performance.

Definition at line 29 of file DS_List.h.

Constructor & Destructor Documentation

template<class list_type >

DataStructures::List< list_type >::List ( )

Definition at line 129 of file DS_List.h.

    {
        allocation_size = 0;
        listArray = 0;
        list_size = 0;
    }

template<class list_type >

DataStructures::List< list_type >::~List ( )

Definition at line 137 of file DS_List.h.

References _FILE_AND_LINE_, and RakNet::OP_DELETE_ARRAY().

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

template<class list_type >

DataStructures::List< list_type >::List ( const List< list_type > & original_copy )

Parameters:

[in] original_copy The list to duplicate

Definition at line 145 of file DS_List.h.

References _FILE_AND_LINE_, DataStructures::List< list_type >::list_size, and DataStructures::List< list_type >::listArray.

    {
        // Allocate memory for copy

        if ( original_copy.list_size == 0 )
        {
            list_size = 0;
            allocation_size = 0;
        }
        else
        {
            listArray = RakNet::OP_NEW_ARRAY<list_type >( original_copy.list_size , _FILE_AND_LINE_ );

            for ( unsigned int counter = 0; counter < original_copy.list_size; ++counter )
                listArray[ counter ] = original_copy.listArray[ counter ];

            // Don't call constructors, assignment operators, etc.
            //memcpy(listArray, original_copy.listArray, original_copy.list_size*sizeof(list_type));

            list_size = allocation_size = original_copy.list_size;
        }
    }

Member Function Documentation

template<class list_type >

void DataStructures::List< list_type >::Clear	(	bool	doNotDeallocateSmallBlocks,
		const char *	file,
		unsigned int	line
	)

Definition at line 444 of file DS_List.h.

References RakNet::OP_DELETE_ARRAY().

Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetShortestPath().

    {
        if ( allocation_size == 0 )
            return;

        if (allocation_size>512 || doNotDeallocateSmallBlocks==false)
        {
            RakNet::OP_DELETE_ARRAY(listArray, file, line);
            allocation_size = 0;
            listArray = 0;
        }
        list_size = 0;
    }

template<class list_type >

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

Attention:: This is a slow operation

Definition at line 459 of file DS_List.h.

References RakNet::OP_DELETE_ARRAY().

    {
        list_type * new_array;

        if ( allocation_size == 0 )
            return ;

        new_array = RakNet::OP_NEW_ARRAY<list_type >( allocation_size , file, line );

        // copy old array over
        for ( unsigned int counter = 0; counter < list_size; ++counter )
            new_array[ counter ] = listArray[ counter ];

        // Don't call constructors, assignment operators, etc.
        //memcpy(new_array, listArray, list_size*sizeof(list_type));

        // set old array to point to the newly allocated array
        RakNet::OP_DELETE_ARRAY(listArray, file, line);

        listArray = new_array;
    }

template<class list_type >

list_type & DataStructures::List< list_type >::Get ( const unsigned int position ) const [inline]

Parameters:

[in] position The index into the array.

Returns:: The element at position position.

Definition at line 214 of file DS_List.h.

        {
            return listArray[ position ];
        }

template<class list_type>

unsigned int DataStructures::List< list_type >::GetIndexOf ( const list_type & input ) const

Parameters:

[in] input The element to check for

Returns:: The index or position of input in the list.

Return values:

MAX_UNSIGNED_LONG	The object is not in the list
[Integer]	The index of the element in the list

Definition at line 428 of file DS_List.h.

References MAX_UNSIGNED_LONG.

    {
        for ( unsigned int i = 0; i < list_size; ++i )
            if ( listArray[ i ] == input )
                return i;

        return MAX_UNSIGNED_LONG;
    }

template<class list_type>

void DataStructures::List< list_type >::Insert	(	const list_type &	input,
		const unsigned int	position,
		const char *	file,
		unsigned int	line
	)

Parameters:

[in]	input	The new element.
[in]	position	The position of the new element.

Definition at line 236 of file DS_List.h.

References RakNet::OP_DELETE_ARRAY(), and RakAssert.

Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetShortestPath(), DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetSpanningTree(), and DataStructures::Tree< TreeType >::LevelOrderTraversal().

    {
#ifdef _DEBUG
        if (position>list_size)
        {
            RakAssert( position <= list_size );
        }
#endif

        // Reallocate list if necessary
        if ( list_size == allocation_size )
        {
            // allocate twice the currently allocated memory
            list_type * new_array;

            if ( allocation_size == 0 )
                allocation_size = 16;
            else
                allocation_size *= 2;

            new_array = RakNet::OP_NEW_ARRAY<list_type >( allocation_size , file, line );

            // copy old array over
            for ( unsigned int counter = 0; counter < list_size; ++counter )
                new_array[ counter ] = listArray[ counter ];

            // Don't call constructors, assignment operators, etc.
            //memcpy(new_array, listArray, list_size*sizeof(list_type));

            // set old array to point to the newly allocated and twice as large array
            RakNet::OP_DELETE_ARRAY(listArray, file, line);

            listArray = new_array;
        }

        // Move the elements in the list to make room
        for ( unsigned int counter = list_size; counter != position; counter-- )
            listArray[ counter ] = listArray[ counter - 1 ];

        // Don't call constructors, assignment operators, etc.
        //memmove(listArray+position+1, listArray+position, (list_size-position)*sizeof(list_type));

        // Insert the new item at the correct spot
        listArray[ position ] = input;

        ++list_size;

    }

template<class list_type>

void DataStructures::List< list_type >::Insert	(	const list_type &	input,
		const char *	file,
		unsigned int	line
	)

Parameters:

[in] input The new element.

Definition at line 287 of file DS_List.h.

References RakNet::OP_DELETE_ARRAY().

    {
        // Reallocate list if necessary

        if ( list_size == allocation_size )
        {
            // allocate twice the currently allocated memory
            list_type * new_array;

            if ( allocation_size == 0 )
                allocation_size = 16;
            else
                allocation_size *= 2;

            new_array = RakNet::OP_NEW_ARRAY<list_type >( allocation_size , file, line );

            if (listArray)
            {
                // copy old array over
                    for ( unsigned int counter = 0; counter < list_size; ++counter )
                        new_array[ counter ] = listArray[ counter ];

                // Don't call constructors, assignment operators, etc.
                //memcpy(new_array, listArray, list_size*sizeof(list_type));

                // set old array to point to the newly allocated and twice as large array
                RakNet::OP_DELETE_ARRAY(listArray, file, line);
            }
            
            listArray = new_array;
        }

        // Insert the new item at the correct spot
        listArray[ list_size ] = input;

        ++list_size;
    }

template<class list_type >

List< list_type > & DataStructures::List< list_type >::operator= ( const List< list_type > & original_copy )

Definition at line 169 of file DS_List.h.

References _FILE_AND_LINE_, DataStructures::List< list_type >::list_size, and DataStructures::List< list_type >::listArray.

    {
        if ( ( &original_copy ) != this )
        {
            Clear( false, _FILE_AND_LINE_ );

            // Allocate memory for copy

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

            else
            {
                listArray = RakNet::OP_NEW_ARRAY<list_type >( original_copy.list_size , _FILE_AND_LINE_ );

                for ( unsigned int counter = 0; counter < original_copy.list_size; ++counter )
                    listArray[ counter ] = original_copy.listArray[ counter ];
                // Don't call constructors, assignment operators, etc.
                //memcpy(listArray, original_copy.listArray, original_copy.list_size*sizeof(list_type));

                list_size = allocation_size = original_copy.list_size;
            }
        }

        return *this;
    }

template<class list_type >

list_type & DataStructures::List< list_type >::operator[] ( const unsigned int position ) const [inline]

Parameters:

[in] position The index into the array.

Returns:: The element at position position.

Definition at line 201 of file DS_List.h.

References RakAssert.

        {
        #ifdef _DEBUG
            if (position>=list_size)
            {
                RakAssert ( position < list_size );
            }
        #endif
            return listArray[ position ];
        }

template<class list_type >

list_type & DataStructures::List< list_type >::Pop ( void ) [inline]

Precondition:: Size()>0

Returns:: The element at the end.

Definition at line 226 of file DS_List.h.

References RakAssert.

        {
#ifdef _DEBUG
            RakAssert(list_size>0);
#endif
            --list_size;
            return listArray[list_size];
        }

template<class list_type >

void DataStructures::List< list_type >::Preallocate	(	unsigned	countNeeded,
		const char *	file,
		unsigned int	line
	)

Definition at line 482 of file DS_List.h.

References RakNet::OP_DELETE_ARRAY().

    {
        unsigned amountToAllocate = allocation_size;
        if (allocation_size==0)
            amountToAllocate=16;
        while (amountToAllocate < countNeeded)
            amountToAllocate<<=1;

        if ( allocation_size < amountToAllocate)
        {
            // allocate twice the currently allocated memory
            list_type * new_array;

            allocation_size=amountToAllocate;

            new_array = RakNet::OP_NEW_ARRAY< list_type >( allocation_size , file, line );

            if (listArray)
            {
                // copy old array over
                for ( unsigned int counter = 0; counter < list_size; ++counter )
                    new_array[ counter ] = listArray[ counter ];

                // Don't call constructors, assignment operators, etc.
                //memcpy(new_array, listArray, list_size*sizeof(list_type));

                // set old array to point to the newly allocated and twice as large array
                RakNet::OP_DELETE_ARRAY(listArray, file, line);
            }

            listArray = new_array;
        }
    }

template<class list_type>

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

Parameters:

[in] input The new element.

Definition at line 220 of file DS_List.h.

Referenced by RakNet::VariableListDeltaTracker::WriteVar().

        {
            Insert(input, file, line);
        }

template<class list_type >

void DataStructures::List< list_type >::RemoveAtIndex ( const unsigned int position )

Parameters:

[in] position The index of the element to delete

Definition at line 381 of file DS_List.h.

References RakAssert.

    {
#ifdef _DEBUG
        if (position >= list_size)
        {
            RakAssert( position < list_size );
            return;
        }
#endif

        if ( position < list_size )
        {
            // Compress the array
            for ( unsigned int counter = position; counter < list_size - 1 ; ++counter )
            listArray[ counter ] = listArray[ counter + 1 ];
            // Don't call constructors, assignment operators, etc.
            // memmove(listArray+position, listArray+position+1, (list_size-1-position) * sizeof(list_type));

            RemoveFromEnd();
        }
    }

template<class list_type >

void DataStructures::List< list_type >::RemoveAtIndexFast ( const unsigned int position )

Note:: - swaps middle with end of list, only use if list order does not matter

Parameters:

[in] position The index of the element to delete

Definition at line 404 of file DS_List.h.

References RakAssert.

        {
#ifdef _DEBUG
            if (position >= list_size)
            {
                RakAssert( position < list_size );
                return;
            }
#endif
            --list_size;
            listArray[position]=listArray[list_size];
        }

template<class list_type >

void DataStructures::List< list_type >::RemoveFromEnd ( const unsigned num = 1 ) [inline]

Definition at line 418 of file DS_List.h.

References RakAssert.

    {
        // Delete the last elements on the list.  No compression needed
#ifdef _DEBUG
        RakAssert(list_size>=num);
#endif
        list_size-=num;
    }

template<class list_type>

void DataStructures::List< list_type >::Replace	(	const list_type &	input,
		const list_type	filler,
		const unsigned int	position,
		const char *	file,
		unsigned int	line
	)		`[inline]`

If the size of the list is less than position, it increase the capacity of the list and fill slot with filler.

Parameters:

[in]	input	The element to replace at position position.
[in]	filler	The element use to fill new allocated capacity.
[in]	position	The position of input in the list.

Definition at line 326 of file DS_List.h.

References RakNet::OP_DELETE_ARRAY(), and RakAssert.

    {
        if ( ( list_size > 0 ) && ( position < list_size ) )
        {
            // Direct replacement
            listArray[ position ] = input;
        }
        else
        {
            if ( position >= allocation_size )
            {
                // Reallocate the list to size position and fill in blanks with filler
                list_type * new_array;
                allocation_size = position + 1;

                new_array = RakNet::OP_NEW_ARRAY<list_type >( allocation_size , file, line );

                // copy old array over

                for ( unsigned int counter = 0; counter < list_size; ++counter )
                    new_array[ counter ] = listArray[ counter ];

                // Don't call constructors, assignment operators, etc.
                //memcpy(new_array, listArray, list_size*sizeof(list_type));

                // set old array to point to the newly allocated array
                RakNet::OP_DELETE_ARRAY(listArray, file, line);

                listArray = new_array;
            }

            // Fill in holes with filler
            while ( list_size < position )
                listArray[ list_size++ ] = filler;

            // Fill in the last element with the new item
            listArray[ list_size++ ] = input;

#ifdef _DEBUG

            RakAssert( list_size == position + 1 );

#endif

        }
    }

template<class list_type>

void DataStructures::List< list_type >::Replace ( const list_type & input ) [inline]

Parameters:

[in] input The element used to replace the last element.

Definition at line 374 of file DS_List.h.

    {
        if ( list_size > 0 )
            listArray[ list_size - 1 ] = input;
    }

template<class list_type >

unsigned int DataStructures::List< list_type >::Size ( void ) const [inline]

Returns:: The number of elements in the list

Definition at line 438 of file DS_List.h.

Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetSpanningTree(), RakNet::VariableListDeltaTracker::IsPastEndOfList(), DataStructures::Tree< TreeType >::LevelOrderTraversal(), and RakNet::VariableListDeltaTracker::WriteVar().

    {
        return list_size;
    }

Member Data Documentation

template<class list_type>

unsigned int DataStructures::List< list_type >::allocation_size [private]

Definition at line 126 of file DS_List.h.

template<class list_type>

unsigned int DataStructures::List< list_type >::list_size [private]

Definition at line 123 of file DS_List.h.

Referenced by DataStructures::List< list_type >::List(), and DataStructures::List< list_type >::operator=().

template<class list_type>

list_type* DataStructures::List< list_type >::listArray [private]

Definition at line 120 of file DS_List.h.

Referenced by DataStructures::List< list_type >::List(), and DataStructures::List< list_type >::operator=().

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

DS_List.h

Public Member Functions

Private Attributes

Detailed Description

template<class list_type> class DataStructures::List< list_type >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class list_type>
class DataStructures::List< list_type >