Quad tree search skiplists.cc
Revision as of 20:41, 3 July 2016 by Maintenance script (talk)
/* * 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