 |
Shadowrun: Awakened 29 September 2011 - Build 871
|
|
Shadowrun: Awakened 29 September 2011 - Build 871
|
#include <DS_LinkedList.h>
Inheritance diagram for DataStructures::LinkedList< LinkedListType >:Public Member Functions | |
| LinkedList () | |
| LinkedList (const LinkedList &original_copy) | |
| LinkedList & | operator++ () |
| LinkedList & | operator++ (int) |
| LinkedList & | operator-- () |
| LinkedList & | operator-- (int) |
| bool | operator= (const LinkedList< LinkedListType > &original_copy) |
| ~LinkedList () | |
Private Member Functions | |
| LinkedList | Merge (LinkedList L1, LinkedList L2) |
| LinkedList | Mergesort (const LinkedList &L) |
Definition at line 212 of file DS_LinkedList.h.
| DataStructures::LinkedList< LinkedListType >::LinkedList | ( | ) | [inline] |
Definition at line 216 of file DS_LinkedList.h.
{}
| DataStructures::LinkedList< LinkedListType >::LinkedList | ( | const LinkedList< LinkedListType > & | original_copy | ) |
Definition at line 360 of file DS_LinkedList.h.
References _FILE_AND_LINE_, DataStructures::CircularLinkedList< CircularLinkedListType >::list_size, DataStructures::CircularLinkedList< CircularLinkedListType >::position, and DataStructures::CircularLinkedList< CircularLinkedListType >::root.
{
typename LinkedList::node * original_copy_pointer, *last, *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 LinkedList::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 LinkedList::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 LinkedList::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;
}
}
| DataStructures::LinkedList< LinkedListType >::~LinkedList | ( | ) |
Definition at line 354 of file DS_LinkedList.h.
{
this->Clear();
}
| LinkedList< LinkedListType > DataStructures::LinkedList< LinkedListType >::Merge | ( | LinkedList< LinkedListType > | L1, |
| LinkedList< LinkedListType > | L2 | ||
| ) | [private] |
Definition at line 1147 of file DS_LinkedList.h.
References DataStructures::CircularLinkedList< LinkedListType >::Add(), DataStructures::CircularLinkedList< CircularLinkedListType >::Del(), DataStructures::CircularLinkedList< CircularLinkedListType >::position, and DataStructures::CircularLinkedList< CircularLinkedListType >::root.
{
LinkedList<LinkedListType> X;
LinkedListType element;
L1.position = L1.root;
L2.position = L2.root;
// While neither list is empty
while ( ( L1.LinkedList_size != 0 ) && ( L2.LinkedList_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 );
}
// Add the remaining list to X
if ( L1.LinkedList_size != 0 )
X.concatenate( L1 );
else
X.concatenate( L2 );
return X;
}
| LinkedList< LinkedListType > DataStructures::LinkedList< LinkedListType >::Mergesort | ( | const LinkedList< LinkedListType > & | L | ) | [private] |
Definition at line 1110 of file DS_LinkedList.h.
References DataStructures::CircularLinkedList< LinkedListType >::Add(), DataStructures::CircularLinkedList< LinkedListType >::list_size, and DataStructures::CircularLinkedList< CircularLinkedListType >::root.
{
unsigned int counter;
typename LinkedList::node* location;
LinkedList<LinkedListType> L1;
LinkedList<LinkedListType> L2;
location = L.root;
// Split the list into two equal size sublists, L1 and L2
for ( counter = 0; counter < L.LinkedList_size / 2; counter++ )
{
// L1.add (*(location->item));
L1.Add ( location->item );
location = location->next;
}
for ( ;counter < L.LinkedList_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 );
}
| LinkedList< LinkedListType > & DataStructures::LinkedList< LinkedListType >::operator++ | ( | int | ) |
Reimplemented from DataStructures::CircularLinkedList< LinkedListType >.
Definition at line 1212 of file DS_LinkedList.h.
{
return this->operator++();
}
| LinkedList< LinkedListType > & DataStructures::LinkedList< LinkedListType >::operator++ | ( | ) |
Reimplemented from DataStructures::CircularLinkedList< LinkedListType >.
Definition at line 1191 of file DS_LinkedList.h.
| LinkedList< LinkedListType > & DataStructures::LinkedList< LinkedListType >::operator-- | ( | ) |
Reimplemented from DataStructures::CircularLinkedList< LinkedListType >.
Definition at line 1219 of file DS_LinkedList.h.
| LinkedList< LinkedListType > & DataStructures::LinkedList< LinkedListType >::operator-- | ( | int | ) |
Reimplemented from DataStructures::CircularLinkedList< LinkedListType >.
Definition at line 1241 of file DS_LinkedList.h.
{
return this->operator--();
}
| bool DataStructures::LinkedList< LinkedListType >::operator= | ( | const LinkedList< LinkedListType > & | original_copy | ) |
Definition at line 249 of file DS_LinkedList.h.
References _FILE_AND_LINE_, DataStructures::CircularLinkedList< LinkedListType >::list_size, DataStructures::CircularLinkedList< LinkedListType >::position, and DataStructures::CircularLinkedList< LinkedListType >::root.
{
typename LinkedList::node * original_copy_pointer, *last, *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 LinkedList::node>( _FILE_AND_LINE_ );
// root->item = RakNet::OP_NEW<LinkedListType>( _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 LinkedList::node>( _FILE_AND_LINE_ );
// root->item = RakNet::OP_NEW<LinkedListType>( _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 LinkedList::node>( _FILE_AND_LINE_ );
// position->item = RakNet::OP_NEW<LinkedListType>( _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;
}
Copyright © 2007-2010 by The Shadowrun: Awakened Team. This work is licensed under the GNU Lesser General Public License 3.
 |