/*
* Jesse B. Dooley
* Date: November 1,1999
* For: CMSC 420-0201 Fall 1999
* Prof. Michelle Hugue
* Title: Part 2: Minimum Spanning Tree and Nearest Neighbors
* Module: SlipLists.cpp
*/
#ifndef SKIPLISTS_CPP
#define SKIPLISTS_CPP
#define Levels 10
#define MaxNumberOfLevels (Levels) /* Maximum level of the list (1 more than the number of levels in the list) */
#define MaxLevel (MaxNumberOfLevels-1)
#include <time.h>
#include "site.cc"
#include "List.cc"
#include <string>
class SkipLists {
struct nodeStructure
{
site key;
nodeStructure* forward[MaxNumberOfLevels]; /* variable sized array of forward pointers */
};
nodeStructure header; /* header node */
int size_int;
bool IsEven( int i )
{
div_t result;
result = div( i, 2 );
return (!result.rem );
} // IsEven
void initNode( nodeStructure* nS )
{
for(int i=0; i< MaxNumberOfLevels; i++)
nS->forward[i] = NULL;
}
short LEVEL( nodeStructure* nS )
{
short Return_short = 0;
for(int i=0; i< MaxNumberOfLevels; i++)
if( nS->forward[i] == NULL )
Return_short++;
return Return_short;
} // LEVEL
public:
SkipLists()
{
size_int = 0;
initNode( &header );
}
SkipLists( const SkipLists &S )
{
// copy the nodes
nodeStructure* q;
nodeStructure* p = S.header.forward[0];
while(p != NULL)
{
q = p->forward[0];
insert( p->key ); // just insert the node
p = q; // advance the pointer
} // while
}
~SkipLists()
{
nodeStructure* q;
nodeStructure* p = header.forward[0];
while(p != NULL)
{
q = p->forward[0];
delete p;
p = q;
} // while
size_int = 0;
initNode( &header );
} // ~SkipLists
bool empty()
{
return (header.forward[0] == NULL );
} // empty
void erase()
{
nodeStructure* q;
nodeStructure* p = header.forward[0];
while(p != NULL)
{
q = p->forward[0];
delete p;
p = q;
} // while
size_int = 0;
initNode( &header );
} // erase
int randomLevel()
{// return a distribution between 0 and 10
double Random_double = 0.0;
time_t L;
time_t R;
R = time( &L );
struct tm* TempTime_p = NULL;
TempTime_p = localtime( &R );
Random_double += (double) TempTime_p->tm_sec / rand();
Random_double += (double) TempTime_p->tm_min / rand();
Random_double += (double) TempTime_p->tm_hour / rand();
Random_double += (double) TempTime_p->tm_mday / rand();
Random_double += (double) TempTime_p->tm_mon / rand();
Random_double += (double) TempTime_p->tm_year / rand();
Random_double += (double) TempTime_p->tm_wday / rand();
Random_double += (double) TempTime_p->tm_yday / rand();
Random_double += (double) TempTime_p->tm_isdst / rand();
Random_double *= 1000;
int Hold = Random_double;
Random_double -= Hold;
if( Random_double <= 0.01 )
return 0;
if( Random_double <= 0.02 )
return 1;
if( Random_double <= 0.06 )
return 2;
if( Random_double <= 0.12 )
return 3;
if( Random_double <= 0.24 )
return 4;
if( Random_double <= 0.48 )
return 5;
if( Random_double <= 0.768 )
return 6;
if( Random_double <= 0.8192 )
return 7;
if( Random_double <= 0.92 )
return 8;
return 9;
} // randomLevel
void insert( site key) // allows duplicates
{
nodeStructure *update[MaxNumberOfLevels]; // hold the preceding pointers
nodeStructure *p = &header;
nodeStructure *q = NULL;
int k = MaxLevel; // which level we are on
for( int i = 0; i < MaxNumberOfLevels; i++ )
update[i] = NULL;
do // find the insertion point
{
while( (q = p->forward[k]) && q->key < key)
p = q;
update[k] = p;
} while( --k >= 0 );
// No duplicates!
if( q && q->key == key)
{
return;
}
// create the new node
k = randomLevel();
int S = k;
q = new nodeStructure;
// initialize the pointer array
initNode( q );
q->key = key;
do
{
p = update[k];
q->forward[k] = p->forward[k];
p->forward[k] = q;
} while(--k>=0);
size_int++;
cout << " with SkipLists level " << S << endl;
cout << " Other sites at this level." << endl;
PRINT_LEVEL( S );
} // insert
/*
bool deletenode( site key )
{
int k,m;
nodeStructure* update[MaxLevel];
nodeStructure* p,q;
p = &header;
k = m = level;
do
{
while( (q = p->forward[k]) && (q->key < key) )
p = q;
update[k] = p;
}while( --k >= 0 );
if( q->key == key)
{
for(k=0; k<=m && (p=update[k])->forward[k] == q; k++)
p->forward[k] = q->forward[k];
delete q;
while( header->forward[m] == NULL && m > 0 )
m--;
level = m;
size_int--;
return(true);
}
else
return(false);
} // delete
*/
site* find( site P )
{
return find( P.name() );
}
site* find( string name_string )
{
nodeStructure *p = &header; // point to the header
nodeStructure *q = NULL;
int k = MaxLevel; // which level we are on or MaxLevel
do while((q = p->forward[k]) && q->key.name() < name_string )
p = q;
while( --k >=0 );
// Found It!
if( q && q->key.name() == name_string )
{
return &q->key;
}
return NULL;
} // search
int size()
{
return size_int;
} // size
List<site> GetTypeList( char C )
{
List<site> Return_path;
nodeStructure* p = header.forward[0];
if( empty() )
return Return_path;
while ( p != NULL )
{
if( p->key.type() == C )
Return_path.AddToList( p->key );
p = p->forward[0];
} // while
return Return_path;
} // GetTypeList
List<site> GetFactoryList( )
{
List<site> Return_path;
nodeStructure* p = header.forward[0];
if( empty() )
return Return_path;
while ( p != NULL )
{
if( p->key.type() == 'F' )
Return_path.AddToList( p->key );
p = p->forward[0];
} // while
return Return_path;
} // GetFactoryList
void PRINT_LEVEL( short S )
{
if( S < 0 || S > MaxLevel )
return;
nodeStructure* p = header.forward[S];
if( empty() )
{
cout << "The List is empty." << endl;
return;
}
while ( p != NULL )
{
if( p->forward[S] && p->forward[S+1] == NULL )
{
p->key.OutPut();
cout << endl;
}
p = p->forward[S];
} // while
} // PRINT_LEVEL
void OutPut()
{
nodeStructure* q;
nodeStructure* p = header.forward[0];
if( empty() )
{
cout << "The List is empty." << endl;
return;
}
while ( p != NULL )
{
p->key.OutPut();
cout << endl;
q = p->forward[0];
p = q;
} // while
} // OutPut
List<site> GetResourceList()
{
List<site> Return_path;
nodeStructure* p = header.forward[0];
if( empty() )
return Return_path;
while ( p != NULL )
{
// 'F' is a factory
if( p->key.type() != 'F' )
Return_path.AddToList( p->key );
p = p->forward[0];
} // while
return Return_path;
} // GetResourceList
void SetVisited( string Site_string, bool visited_bool )
{
site* S = find( Site_string );
if( S != NULL )
S->visited( visited_bool );
} // GetAdjacentList
bool WasVisited( string Site_string )
{
site* S = find( Site_string );
if( S != NULL )
return S->visited();
return false;
} // WasVisited
void SET_VISITED( bool T )
{
nodeStructure* p = header.forward[0];
while ( p != NULL )
{
p->key.visited( T );
p = p->forward[0];
} // while
} // ResetVisited
List<string> getnames()
{
nodeStructure* p = header.forward[0];
List<string> B;
while ( p != NULL )
{
B.AddToList( p->key.name() );
p = p->forward[0];
} // while
return B;
} // EdgeCount
void LIST_SITES()
{
// Grab the base names first
// 'L' - lab |
// 'B' - barrack | base type
// 'S' - supply, |
// 'P' - power |
// 'M' - mineral | raw material type
cout << "List of base sites:" << endl;
LIST_BASE_SITES();
cout << "List of raw material sites:" << endl;
LIST_MATERIAL_SITES();
}
void LIST_BASE_SITES()
{
nodeStructure* p = header.forward[0];
while ( p != NULL )
{
if( p->key.material() == false )
p->key.OutPut();
p = p->forward[0];
} // while
}
void LIST_MATERIAL_SITES()
{
nodeStructure* p = header.forward[0];
while ( p != NULL )
{
if( p->key.material() )
p->key.OutPut();
p = p->forward[0];
} // while
}
}; // SkipLists.cpp
#endif
