(Circular) Linked List ADT (Doubly Linked Pointer to Node Style) - More...

#include <DS_LinkedList.h>

Inheritance diagram for DataStructures::CircularLinkedList< CircularLinkedListType >:

Classes
struct	node
Public Member Functions
CircularLinkedListType &	Add (const CircularLinkedListType &input)
void	Beginning (void)
	CircularLinkedList ()
	CircularLinkedList (const CircularLinkedList &original_copy)
void	Clear (void)
void	Concatenate (const CircularLinkedList &L)
void	Del (void)
void	End (void)
bool	Find (const CircularLinkedListType &input)
void	Insert (const CircularLinkedListType &input)
bool	IsIn (const CircularLinkedListType &input)
CircularLinkedList &	operator++ ()
CircularLinkedList &	operator++ (int)
CircularLinkedList &	operator-- (int)
CircularLinkedList &	operator-- ()
bool	operator= (const CircularLinkedList &original_copy)
CircularLinkedListType &	Peek (void)
CircularLinkedListType	Pop (void)
void	Replace (const CircularLinkedListType &input)
unsigned int	Size (void)
void	Sort (void)
	~CircularLinkedList ()
Protected Member Functions
node *	FindPointer (const CircularLinkedListType &input)
Protected Attributes
unsigned int	list_size
node *	position
node *	root
Private Member Functions
CircularLinkedList	Merge (CircularLinkedList L1, CircularLinkedList L2)
CircularLinkedList	Mergesort (const CircularLinkedList &L)

Detailed Description

template<class CircularLinkedListType>
class DataStructures::CircularLinkedList< CircularLinkedListType >

By Kevin Jenkins (http://www.rakkar.org) Initilize with the following command LinkedList<TYPE> OR CircularLinkedList<Type>

Has the following member functions

size: returns number of elements in the linked list
insert(item): inserts item at the current position in the LinkedList.
add(item): inserts item after the current position in the LinkedList. Does not increment the position
replace(item): replaces the element at the current position item.
peek: returns the element at the current position
pop: returns the element at the current position and deletes it
del: deletes the current element. Does nothing for an empty list.
clear: empties the LinkedList and returns storage
bool IsInitem): Does a linear search for item. Does not set the position to it, only returns true on item found, false otherwise
bool find(item): Does a linear search for item and sets the current position to point to it if and only if the item is found. Returns true on item found, false otherwise
sort: Sorts the elements of the list with a mergesort and sets the current pointer to the first element
concatenate(list L): This appends L to the current list
++(prefix): moves the pointer one element up in the list and returns the appropriate copy of the element in the list
--(prefix): moves the pointer one element back in the list and returns the appropriate copy of the element in the list
beginning - moves the pointer to the start of the list. For circular linked lists this is first 'position' created. You should call this after the sort function to read the first value.
end - moves the pointer to the end of the list. For circular linked lists this is one less than the first 'position' created The assignment and copy constructor operators are defined

Note:: 1. LinkedList and CircularLinkedList are exactly the same except LinkedList won't let you wrap around the root and lets you jump to two positions relative to the root/ 2. Postfix ++ and -- can be used but simply call the prefix versions.

EXAMPLE:

 LinkedList<int> A;  // Creates a Linked List of integers called A
 CircularLinkedList<int> B;  // Creates a Circular Linked List of 
          // integers called B

 A.Insert(20);  // Adds 20 to A.  A: 20 - current is 20
 A.Insert(5);  // Adds 5 to A.  A: 5 20 - current is 5
 A.Insert(1);  // Adds 1 to A.  A: 1 5 20 - current is 1

 A.IsIn1); // returns true
 A.IsIn200); // returns false
 A.Find(5);  // returns true and sets current to 5
 A.Peek();  // returns 5
 A.Find(1);  // returns true and sets current to 1

 (++A).Peek();  // Returns 5
 A.Peek(); // Returns 5

 A.Replace(10);  // Replaces 5 with 10.
 A.Peek();  // Returns 10

 A.Beginning();  // Current points to the beginning of the list at 1

 (++A).Peek();  // Returns 5
 A.Peek();  // Returns 10

 A.Del();  // Deletes 10.  Current points to the next element, which is 20
 A.Peek();  // Returns 20
 
 A.Beginning();  // Current points to the beginning of the list at 1

 (++A).Peek();  // Returns 5
 A.Peek();  // Returns 20

 A.Clear(_FILE_AND_LINE_);  // Deletes all nodes in A

 A.Insert(5);  // A: 5 - current is 5
 A.Insert(6); // A: 6 5 - current is 6
 A.Insert(7); // A: 7 6 5 - current is 7

 A.Clear(_FILE_AND_LINE_);
 B.Clear(_FILE_AND_LINE_);

 B.Add(10);
 B.Add(20);
 B.Add(30);
 B.Add(5);
 B.Add(2);
 B.Add(25);
 // Sorts the numbers in the list and sets the current pointer to the 
 // first element
 B.sort();  

 // Postfix ++ just calls the prefix version and has no functional 
 // difference.
 B.Peek();  // Returns 2
 B++;
 B.Peek();  // Returns 5
 B++;
 B.Peek();  // Returns 10
 B++;
 B.Peek();  // Returns 20
 B++;
 B.Peek();  // Returns 25
 B++;
 B.Peek();  // Returns 30

Definition at line 146 of file DS_LinkedList.h.

Constructor & Destructor Documentation

template<class CircularLinkedListType >

DataStructures::CircularLinkedList< CircularLinkedListType >::CircularLinkedList ( )

Definition at line 340 of file DS_LinkedList.h.

    {
        this->root = 0;
        this->position = 0;
        this->list_size = 0;
    }

template<class CircularLinkedListType >

DataStructures::CircularLinkedList< CircularLinkedListType >::~CircularLinkedList ( )

Definition at line 348 of file DS_LinkedList.h.

    {
        this->Clear();
    }

template<class CircularLinkedListType >

DataStructures::CircularLinkedList< CircularLinkedListType >::CircularLinkedList ( const CircularLinkedList< CircularLinkedListType > & original_copy )

Definition at line 442 of file DS_LinkedList.h.

References _FILE_AND_LINE_, DataStructures::CircularLinkedList< CircularLinkedListType >::node::item, DataStructures::CircularLinkedList< CircularLinkedListType >::list_size, DataStructures::CircularLinkedList< CircularLinkedListType >::node::next, DataStructures::CircularLinkedList< CircularLinkedListType >::position, DataStructures::CircularLinkedList< CircularLinkedListType >::node::previous, and DataStructures::CircularLinkedList< CircularLinkedListType >::root.

    {
        node * original_copy_pointer;
        node *last;
        node *save_position;

        if ( original_copy.list_size == 0 )
        {
            this->root = 0;
            this->position = 0;
            this->list_size = 0;
            return ;
        }

        else
            if ( original_copy.list_size == 1 )
            {
                this->root = RakNet::OP_NEW<typename CircularLinkedList::node>( _FILE_AND_LINE_ );
                // root->item = RakNet::OP_NEW<CircularLinkedListType>( _FILE_AND_LINE_ );
                this->root->next = this->root;
                this->root->previous = this->root;
                this->list_size = 1;
                this->position = this->root;
                // *(root->item) = *((original_copy.root)->item);
                this->root->item = original_copy.root->item;
            }

            else
            {
                // Setup the first part of the root node
                original_copy_pointer = original_copy.root;
                this->root = RakNet::OP_NEW<typename CircularLinkedList::node>( _FILE_AND_LINE_ );
                // root->item = RakNet::OP_NEW<CircularLinkedListType>( _FILE_AND_LINE_ );
                this->position = this->root;
                // *(root->item)=*((original_copy.root)->item);
                this->root->item = original_copy.root->item;

                if ( original_copy_pointer == original_copy.position )
                    save_position = this->position;

                do
                {


                    // Save the current element
                    last = this->position;

                    // Point to the next node in the source list
                    original_copy_pointer = original_copy_pointer->next;

                    // Create a new node and point position to it
                    this->position = RakNet::OP_NEW<typename CircularLinkedList::node>( _FILE_AND_LINE_ );
                    // position->item = RakNet::OP_NEW<CircularLinkedListType>( _FILE_AND_LINE_ );

                    // Copy the item to the new node
                    // *(position->item)=*(original_copy_pointer->item);
                    this->position->item = original_copy_pointer->item;

                    if ( original_copy_pointer == original_copy.position )
                        save_position = position;

                    // Set the previous pointer for the new node
                    ( this->position->previous ) = last;

                    // Set the next pointer for the old node to the new node
                    ( last->next ) = this->position;

                }

                while ( ( original_copy_pointer->next ) != ( original_copy.root ) );

                // Complete the circle.  Set the next pointer of the newest node to the root and the previous pointer of the root to the newest node
                this->position->next = this->root;

                this->root->previous = position;

                this->list_size = original_copy.list_size;

                this->position = save_position;
            }
    }

Member Function Documentation

template<class CircularLinkedListType>

CircularLinkedListType & DataStructures::CircularLinkedList< CircularLinkedListType >::Add ( const CircularLinkedListType & input )

Definition at line 694 of file DS_LinkedList.h.

References _FILE_AND_LINE_, DataStructures::CircularLinkedList< CircularLinkedListType >::node::item, DataStructures::CircularLinkedList< CircularLinkedListType >::node::next, and DataStructures::CircularLinkedList< CircularLinkedListType >::node::previous.

Referenced by DataStructures::CircularLinkedList< CircularLinkedListType >::Merge(), and DataStructures::CircularLinkedList< CircularLinkedListType >::Mergesort().

    {
        node * new_node;

        if ( this->list_size == 0 )
        {
            this->root = RakNet::OP_NEW<typename CircularLinkedList::node>( _FILE_AND_LINE_ );
            // root->item = RakNet::OP_NEW<CircularLinkedListType>( _FILE_AND_LINE_ );
            // *(root->item)=input;
            this->root->item = input;
            this->root->next = this->root;
            this->root->previous = this->root;
            this->list_size = 1;
            this->position = this->root;
            // return *(position->item);
            return this->position->item;
        }

        else
            if ( list_size == 1 )
            {
                this->position = RakNet::OP_NEW<typename CircularLinkedList::node>( _FILE_AND_LINE_ );
                // position->item = RakNet::OP_NEW<CircularLinkedListType>( _FILE_AND_LINE_ );
                this->root->next = this->position;
                this->root->previous = this->position;
                this->position->previous = this->root;
                this->position->next = this->root;
                // *(position->item)=input;
                this->position->item = input;
                this->list_size = 2;
                this->position = this->root; // Don't move the position from the root
                // return *(position->item);
                return this->position->item;
            }

            else
            {
                /*

                   B
                   |
                A --- C

                new_node=B
                position=A
                position->next=C

                Note that the order of the following statements is important  */

                new_node = RakNet::OP_NEW<typename CircularLinkedList::node>( _FILE_AND_LINE_ );
                // new_node->item = RakNet::OP_NEW<CircularLinkedListType>( _FILE_AND_LINE_ );

                // *(new_node->item)=input;
                new_node->item = input;

                // Point last of B to A
                new_node->previous = this->position;

                // Point next of B to C
                new_node->next = ( this->position->next );

                // Point last of C to B
                ( this->position->next ) ->previous = new_node;

                // Point next of A to B
                ( this->position->next ) = new_node;

                // Increase the recorded size of the list by one
                this->list_size++;

                // return *(new_node->item);
                return new_node->item;
            }
    }

template<class CircularLinkedListType >

void DataStructures::CircularLinkedList< CircularLinkedListType >::Beginning ( void ) [inline]

Definition at line 235 of file DS_LinkedList.h.

    {
        if ( this->root )
            this->position = this->root;
    }

template<class CircularLinkedListType >

void DataStructures::CircularLinkedList< CircularLinkedListType >::Clear ( void )

Definition at line 952 of file DS_LinkedList.h.

References _FILE_AND_LINE_, DataStructures::CircularLinkedList< CircularLinkedListType >::node::next, and RakNet::OP_DELETE().

    {
        if ( this->list_size == 0 )
            return ;
        else
            if ( this->list_size == 1 )  // {RakNet::OP_DELETE(root->item); RakNet::OP_DELETE(root, _FILE_AND_LINE_);}
            {
                RakNet::OP_DELETE(this->root, _FILE_AND_LINE_);
            }

            else
            {
                node* current;
                node* temp;

                current = this->root;

                do
                {
                    temp = current;
                    current = current->next;
                    // RakNet::OP_DELETE(temp->item, _FILE_AND_LINE_);
                    RakNet::OP_DELETE(temp, _FILE_AND_LINE_);
                }

                while ( current != this->root );
            }

            this->list_size = 0;
            this->root = 0;
            this->position = 0;
    }

template<class CircularLinkedListType >

void DataStructures::CircularLinkedList< CircularLinkedListType >::Concatenate ( const CircularLinkedList< CircularLinkedListType > & L ) [inline]

Definition at line 986 of file DS_LinkedList.h.

References cat::Atomic::Add(), DataStructures::CircularLinkedList< CircularLinkedListType >::node::item, L, DataStructures::CircularLinkedList< CircularLinkedListType >::list_size, DataStructures::CircularLinkedList< CircularLinkedListType >::node::next, DataStructures::CircularLinkedList< CircularLinkedListType >::node::previous, and DataStructures::CircularLinkedList< CircularLinkedListType >::root.

Referenced by DataStructures::CircularLinkedList< CircularLinkedListType >::Merge().

    {
        unsigned int counter;
        node* ptr;

        if ( L.list_size == 0 )
            return ;

        if ( this->list_size == 0 )
            * this = L;

        ptr = L.root;

        this->position = this->root->previous;

        // Cycle through each element in L and add it to the current list
        for ( counter = 0; counter < L.list_size; counter++ )
        {
            // Add item after the current item pointed to
            // add(*(ptr->item));

            Add ( ptr->item );

            // Update pointers.  Moving ptr keeps the current pointer at the end of the list since the add function does not move the pointer
            ptr = ptr->next;

            this->position = this->position->next;
        }
    }

template<class CircularLinkedListType >

void DataStructures::CircularLinkedList< CircularLinkedListType >::Del ( void )

Definition at line 778 of file DS_LinkedList.h.

References _FILE_AND_LINE_, DataStructures::CircularLinkedList< CircularLinkedListType >::node::next, and RakNet::OP_DELETE().

Referenced by DataStructures::LinkedList< LinkedListType >::Merge(), and DataStructures::CircularLinkedList< CircularLinkedListType >::Merge().

    {
        node * new_position;

        if ( this->list_size == 0 )
            return ;

        else
            if ( this->list_size == 1 )
            {
                // RakNet::OP_DELETE(root->item, _FILE_AND_LINE_);
                RakNet::OP_DELETE(this->root, _FILE_AND_LINE_);
                this->root = this->position = 0;
                this->list_size = 0;
            }

            else
            {
                ( this->position->previous ) ->next = this->position->next;
                ( this->position->next ) ->previous = this->position->previous;
                new_position = this->position->next;

                if ( this->position == this->root )
                    this->root = new_position;

                // RakNet::OP_DELETE(position->item, _FILE_AND_LINE_);
                RakNet::OP_DELETE(this->position, _FILE_AND_LINE_);

                this->position = new_position;

                this->list_size--;
            }
    }

template<class CircularLinkedListType >

void DataStructures::CircularLinkedList< CircularLinkedListType >::End ( void ) [inline]

Definition at line 242 of file DS_LinkedList.h.

    {
        if ( this->root )
            this->position = this->root->previous;
    }

template<class CircularLinkedListType>

bool DataStructures::CircularLinkedList< CircularLinkedListType >::Find ( const CircularLinkedListType & input )

Definition at line 829 of file DS_LinkedList.h.

    {
        node * return_value;

        return_value = FindPointer( input );

        if ( return_value != 0 )
        {
            this->position = return_value;
            return true;
        }

        else
            return false; // Can't find the item don't do anything
    }

template<class CircularLinkedListType>

CircularLinkedList< CircularLinkedListType >::node * DataStructures::CircularLinkedList< CircularLinkedListType >::FindPointer ( const CircularLinkedListType & input ) [protected]

Definition at line 846 of file DS_LinkedList.h.

References DataStructures::CircularLinkedList< CircularLinkedListType >::node::item, and DataStructures::CircularLinkedList< CircularLinkedListType >::node::next.

    {
        node * current;

        if ( this->list_size == 0 )
            return 0;

        current = this->root;

        // Search for the item starting from the root node and incrementing the pointer after every check
        // If you wind up pointing at the root again you looped around the list so didn't find the item, in which case return 0
        do
        {
            // if (*(current->item) == input) return current;

            if ( current->item == input )
                return current;

            current = current->next;
        }

        while ( current != this->root );

        return 0;

    }

template<class CircularLinkedListType>

void DataStructures::CircularLinkedList< CircularLinkedListType >::Insert ( const CircularLinkedListType & input )

Definition at line 617 of file DS_LinkedList.h.

References _FILE_AND_LINE_, DataStructures::CircularLinkedList< CircularLinkedListType >::node::item, DataStructures::CircularLinkedList< CircularLinkedListType >::node::next, and DataStructures::CircularLinkedList< CircularLinkedListType >::node::previous.

    {
        node * new_node;

        if ( list_size == 0 )
        {
            this->root = RakNet::OP_NEW<typename CircularLinkedList::node>( _FILE_AND_LINE_ );
            // root->item = RakNet::OP_NEW<CircularLinkedListType>( _FILE_AND_LINE_ );
            //*(root->item)=input;
            this->root->item = input;
            this->root->next = this->root;
            this->root->previous = this->root;
            this->list_size = 1;
            this->position = this->root;
        }

        else
            if ( list_size == 1 )
            {
                this->position = RakNet::OP_NEW<typename CircularLinkedList::node>( _FILE_AND_LINE_ );
                // position->item = RakNet::OP_NEW<CircularLinkedListType>( _FILE_AND_LINE_ );
                this->root->next = this->position;
                this->root->previous = this->position;
                this->position->previous = this->root;
                this->position->next = this->root;
                // *(position->item)=input;
                this->position->item = input;
                this->root = this->position; // Since we're inserting into a 1 element list the old root is now the second item
                this->list_size = 2;
            }

            else
            {
                /*

                B
                |
                A --- C

                position->previous=A
                new_node=B
                position=C

                Note that the order of the following statements is important  */

                new_node = RakNet::OP_NEW<typename CircularLinkedList::node>( _FILE_AND_LINE_ );
                // new_node->item = RakNet::OP_NEW<CircularLinkedListType>( _FILE_AND_LINE_ );

                // *(new_node->item)=input;
                new_node->item = input;

                // Point next of A to B
                ( this->position->previous ) ->next = new_node;

                // Point last of B to A
                new_node->previous = this->position->previous;

                // Point last of C to B
                this->position->previous = new_node;

                // Point next of B to C
                new_node->next = this->position;

                // Since the root pointer is bound to a node rather than an index this moves it back if you insert an element at the root

                if ( this->position == this->root )
                {
                    this->root = new_node;
                    this->position = this->root;
                }

                // Increase the recorded size of the list by one
                this->list_size++;
            }
    }

template<class CircularLinkedListType>

bool DataStructures::CircularLinkedList< CircularLinkedListType >::IsIn ( const CircularLinkedListType & input )

Definition at line 813 of file DS_LinkedList.h.

    {
        node * return_value, *old_position;

        old_position = this->position;

        return_value = FindPointer( input );
        this->position = old_position;

        if ( return_value != 0 )
            return true;
        else
            return false; // Can't find the item don't do anything
    }

template<class CircularLinkedListType >

CircularLinkedList< CircularLinkedListType > DataStructures::CircularLinkedList< CircularLinkedListType >::Merge	(	CircularLinkedList< CircularLinkedListType >	L1,
		CircularLinkedList< CircularLinkedListType >	L2
	)		`[private]`

Definition at line 1066 of file DS_LinkedList.h.

References DataStructures::CircularLinkedList< CircularLinkedListType >::Add(), DataStructures::CircularLinkedList< CircularLinkedListType >::Concatenate(), DataStructures::CircularLinkedList< CircularLinkedListType >::Del(), DataStructures::CircularLinkedList< CircularLinkedListType >::list_size, DataStructures::CircularLinkedList< CircularLinkedListType >::position, and DataStructures::CircularLinkedList< CircularLinkedListType >::root.

    {
        CircularLinkedList<CircularLinkedListType> X;
        CircularLinkedListType element;
        L1.position = L1.root;
        L2.position = L2.root;

        // While neither list is empty

        while ( ( L1.list_size != 0 ) && ( L2.list_size != 0 ) )
        {
            // Compare the first items of L1 and L2
            // Remove the smaller of the two items from the list

            if ( ( ( L1.root ) ->item ) < ( ( L2.root ) ->item ) )
                // if ((*((L1.root)->item)) < (*((L2.root)->item)))
            {
                // element = *((L1.root)->item);
                element = ( L1.root ) ->item;
                L1.Del();
            }
            else
            {
                // element = *((L2.root)->item);
                element = ( L2.root ) ->item;
                L2.Del();
            }

            // Add this item to the end of X
            X.Add( element );

            X++;
        }

        // Add the remaining list to X
        if ( L1.list_size != 0 )
            X.Concatenate( L1 );
        else
            X.Concatenate( L2 );

        return X;
    }

template<class CircularLinkedListType >

CircularLinkedList< CircularLinkedListType > DataStructures::CircularLinkedList< CircularLinkedListType >::Mergesort ( const CircularLinkedList< CircularLinkedListType > & L ) [private]

Definition at line 1029 of file DS_LinkedList.h.

References DataStructures::CircularLinkedList< CircularLinkedListType >::Add(), DataStructures::CircularLinkedList< CircularLinkedListType >::node::item, DataStructures::CircularLinkedList< CircularLinkedListType >::list_size, DataStructures::CircularLinkedList< CircularLinkedListType >::node::next, and DataStructures::CircularLinkedList< CircularLinkedListType >::root.

    {
        unsigned int counter;
        node* location;
        CircularLinkedList<CircularLinkedListType> L1;
        CircularLinkedList<CircularLinkedListType> L2;

        location = L.root;

        // Split the list into two equal size sublists, L1 and L2

        for ( counter = 0; counter < L.list_size / 2; counter++ )
        {
            // L1.add (*(location->item));
            L1.Add ( location->item );
            location = location->next;
        }

        for ( ;counter < L.list_size; counter++ )
        {
            // L2.Add(*(location->item));
            L2.Add ( location->item );
            location = location->next;
        }

        // Recursively sort the sublists
        if ( L1.list_size > 1 )
            L1 = Mergesort( L1 );

        if ( L2.list_size > 1 )
            L2 = Mergesort( L2 );

        // Merge the two sublists
        return Merge( L1, L2 );
    }

template<class CircularLinkedListType >

CircularLinkedList< CircularLinkedListType > & DataStructures::CircularLinkedList< CircularLinkedListType >::operator++ ( )

Reimplemented in DataStructures::LinkedList< LinkedListType >, and DataStructures::LinkedList< QueueType >.

Definition at line 897 of file DS_LinkedList.h.

    {
        if ( this->list_size != 0 )
            position = position->next;

        return *this;
    }

template<class CircularLinkedListType >

CircularLinkedList< CircularLinkedListType > & DataStructures::CircularLinkedList< CircularLinkedListType >::operator++ ( int )

Reimplemented in DataStructures::LinkedList< LinkedListType >, and DataStructures::LinkedList< QueueType >.

Definition at line 918 of file DS_LinkedList.h.

    {
        return this->operator++();
    }

template<class CircularLinkedListType >

CircularLinkedList< CircularLinkedListType > & DataStructures::CircularLinkedList< CircularLinkedListType >::operator-- ( int )

Reimplemented in DataStructures::LinkedList< LinkedListType >, and DataStructures::LinkedList< QueueType >.

Definition at line 946 of file DS_LinkedList.h.

    {
        return this->operator--();
    }

template<class CircularLinkedListType >

CircularLinkedList< CircularLinkedListType > & DataStructures::CircularLinkedList< CircularLinkedListType >::operator-- ( )

Reimplemented in DataStructures::LinkedList< LinkedListType >, and DataStructures::LinkedList< QueueType >.

Definition at line 925 of file DS_LinkedList.h.

    {
        if ( this->list_size != 0 )
            this->position = this->position->previous;

        return *this;
    }

template<class CircularLinkedListType >

bool DataStructures::CircularLinkedList< CircularLinkedListType >::operator= ( const CircularLinkedList< CircularLinkedListType > & original_copy )

Definition at line 528 of file DS_LinkedList.h.

References _FILE_AND_LINE_, DataStructures::CircularLinkedList< CircularLinkedListType >::node::item, DataStructures::CircularLinkedList< CircularLinkedListType >::list_size, DataStructures::CircularLinkedList< CircularLinkedListType >::node::next, DataStructures::CircularLinkedList< CircularLinkedListType >::position, DataStructures::CircularLinkedList< CircularLinkedListType >::node::previous, and DataStructures::CircularLinkedList< CircularLinkedListType >::root.

    {
        node * original_copy_pointer;
        node *last;
        node *save_position;

        if ( ( &original_copy ) != this )
        {

            this->Clear();


            if ( original_copy.list_size == 0 )
            {
                this->root = 0;
                this->position = 0;
                this->list_size = 0;
            }

            else
                if ( original_copy.list_size == 1 )
                {
                    this->root = RakNet::OP_NEW<typename CircularLinkedList::node>( _FILE_AND_LINE_ );
                    // root->item = RakNet::OP_NEW<CircularLinkedListType>( _FILE_AND_LINE_ );
                    this->root->next = this->root;
                    this->root->previous = this->root;
                    this->list_size = 1;
                    this->position = this->root;
                    // *(root->item)=*((original_copy.root)->item);
                    this->root->item = original_copy.root->item;
                }

                else
                {
                    // Setup the first part of the root node
                    original_copy_pointer = original_copy.root;
                    this->root = RakNet::OP_NEW<typename CircularLinkedList::node>( _FILE_AND_LINE_ );
                    // root->item = RakNet::OP_NEW<CircularLinkedListType>( _FILE_AND_LINE_ );
                    this->position = this->root;
                    // *(root->item)=*((original_copy.root)->item);
                    this->root->item = original_copy.root->item;

                    if ( original_copy_pointer == original_copy.position )
                        save_position = this->position;

                    do
                    {
                        // Save the current element
                        last = this->position;

                        // Point to the next node in the source list
                        original_copy_pointer = original_copy_pointer->next;

                        // Create a new node and point position to it
                        this->position = RakNet::OP_NEW<typename CircularLinkedList::node>( _FILE_AND_LINE_ );
                        // position->item = RakNet::OP_NEW<CircularLinkedListType>( _FILE_AND_LINE_ );

                        // Copy the item to the new node
                        // *(position->item)=*(original_copy_pointer->item);
                        this->position->item = original_copy_pointer->item;

                        if ( original_copy_pointer == original_copy.position )
                            save_position = this->position;

                        // Set the previous pointer for the new node
                        ( this->position->previous ) = last;

                        // Set the next pointer for the old node to the new node
                        ( last->next ) = this->position;

                    }

                    while ( ( original_copy_pointer->next ) != ( original_copy.root ) );

                    // Complete the circle.  Set the next pointer of the newest node to the root and the previous pointer of the root to the newest node
                    this->position->next = this->root;

                    this->root->previous = this->position;

                    this->list_size = original_copy.list_size;

                    this->position = save_position;
                }
        }

        return true;
    }

template<class CircularLinkedListType >

CircularLinkedListType & DataStructures::CircularLinkedList< CircularLinkedListType >::Peek ( void ) [inline]

Definition at line 880 of file DS_LinkedList.h.

    {
        // return *(position->item);
        return this->position->item;
    }

template<class CircularLinkedListType >

CircularLinkedListType DataStructures::CircularLinkedList< CircularLinkedListType >::Pop ( void )

Definition at line 887 of file DS_LinkedList.h.

    {
        CircularLinkedListType element;
        element = Peek();
        Del();
        return CircularLinkedListType( element ); // return temporary
    }

template<class CircularLinkedListType>

void DataStructures::CircularLinkedList< CircularLinkedListType >::Replace ( const CircularLinkedListType & input ) [inline]

Definition at line 770 of file DS_LinkedList.h.

    {
        if ( this->list_size > 0 )
            // *(position->item)=input;
            this->position->item = input;
    }

template<class CircularLinkedListType >

unsigned int DataStructures::CircularLinkedList< CircularLinkedListType >::Size ( void ) [inline]

Definition at line 874 of file DS_LinkedList.h.

    {
        return this->list_size;
    }

template<class CircularLinkedListType >

void DataStructures::CircularLinkedList< CircularLinkedListType >::Sort ( void ) [inline]

Definition at line 1017 of file DS_LinkedList.h.

    {
        if ( this->list_size <= 1 )
            return ;

        // Call equal operator to assign result of mergesort to current object
        *this = Mergesort( *this );

        this->position = this->root;
    }

Member Data Documentation

template<class CircularLinkedListType>

unsigned int DataStructures::CircularLinkedList< CircularLinkedListType >::list_size [protected]

Definition at line 196 of file DS_LinkedList.h.

Referenced by DataStructures::CircularLinkedList< CircularLinkedListType >::CircularLinkedList(), DataStructures::CircularLinkedList< CircularLinkedListType >::Concatenate(), DataStructures::LinkedList< LinkedListType >::LinkedList(), DataStructures::CircularLinkedList< CircularLinkedListType >::Merge(), DataStructures::CircularLinkedList< CircularLinkedListType >::Mergesort(), and DataStructures::CircularLinkedList< CircularLinkedListType >::operator=().

template<class CircularLinkedListType>

node* DataStructures::CircularLinkedList< CircularLinkedListType >::position [protected]

Definition at line 200 of file DS_LinkedList.h.

Referenced by DataStructures::CircularLinkedList< CircularLinkedListType >::CircularLinkedList(), DataStructures::LinkedList< LinkedListType >::LinkedList(), DataStructures::LinkedList< LinkedListType >::Merge(), DataStructures::CircularLinkedList< CircularLinkedListType >::Merge(), and DataStructures::CircularLinkedList< CircularLinkedListType >::operator=().

template<class CircularLinkedListType>

node* DataStructures::CircularLinkedList< CircularLinkedListType >::root [protected]

Definition at line 198 of file DS_LinkedList.h.

Referenced by DataStructures::CircularLinkedList< CircularLinkedListType >::CircularLinkedList(), DataStructures::CircularLinkedList< CircularLinkedListType >::Concatenate(), DataStructures::LinkedList< LinkedListType >::LinkedList(), DataStructures::LinkedList< LinkedListType >::Merge(), DataStructures::CircularLinkedList< CircularLinkedListType >::Merge(), DataStructures::LinkedList< LinkedListType >::Mergesort(), DataStructures::CircularLinkedList< CircularLinkedListType >::Mergesort(), and DataStructures::CircularLinkedList< CircularLinkedListType >::operator=().

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

DS_LinkedList.h

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

template<class CircularLinkedListType> class DataStructures::CircularLinkedList< CircularLinkedListType >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class CircularLinkedListType>
class DataStructures::CircularLinkedList< CircularLinkedListType >