Quad tree search sitemanager.cc
Revision as of 20:41, 3 July 2016 by Maintenance script (talk)
/* * sitemanager handles a */ #ifndef SITEMANAGER_CC #define SITEMANAGER_CC #include "TemasBase.h" #include <algorithm> #include "List.cc" #include "site.cc" #include "route.cc" //#include "avl_tree_site.cc" #include "route.cc" #include "SkipLists.cc" using namespace std; class sitemanager { SkipLists Site_map; List<string> Site_Name_List; List<route> routes_List; List<route> MST_List; // SkipLists Q_SkipLists; int calcaxis( string yaxis ) { return atoi( yaxis.data() ); } // calcaxis int GrabBaseRoutes() {// grab lowest base route in ascii order int Return_int = INT_MAX; Site_Name_List.begin(); for( int i = 0; i < Site_Name_List.size(); i++ ) { site* S_p = search((*Site_Name_List.getcurrent())); int Temp_int = SiteIndex( S_p ); // there are no routes between material and base sites so just test once. if(( MATERIAL_SITE( S_p ) == false ) && (Return_int > Temp_int ) && (S_p->visited() == false) ) { Return_int = Temp_int; } Site_Name_List.next(); } return Return_int; } // GrabBaseRoutes //Prim's MST Algorithm // Compute a minimal-cost spanning tree void Prim( int s ) { // Find shortest route by taking successive shortest edges // until the finish is reached. // Use these like queues double D[ MaxSites ]; // weights I have so far site* V[ MaxSites ]; // sites visited. NULL, havent gotten there yet // D[s] = 0 and V[s] = 0 int index = 0; // initialize everything for( index = 0; index < MaxSites; index++ ) { D[index] = DBL_MAX; V[index] = NULL; } D[s] = 0.0; // step through the sites for( index = 0; index < Site_map.size(); index++ ) { int v = minVertex( D ); // closest unvisited vertex to s if( D[v] == DBL_MAX ) return; // remaining vertices unreachable setMark( v, true ); if( v != s ) AddEdgetoMST( V[v], v ); List<route*> Edge = GetAdjacentList( search( IndexSite( v ) ) ); Edge.begin(); for( int index2 = 0; index2 < Edge.size(); index2++ ) { int EdgeEnd = INT_MAX; if( (*Edge.getcurrent())->StartSite() == search(IndexSite(v)) ) EdgeEnd = SiteIndex((*Edge.getcurrent())->FinishSite()); else EdgeEnd = SiteIndex((*Edge.getcurrent())->StartSite()); // if( D[G.v2(w)] > G.weight(w) ) if( D[EdgeEnd] > (*Edge.getcurrent())->getweight() ) { D[EdgeEnd] = (*Edge.getcurrent())->getweight(); // Update distance V[EdgeEnd] = search(IndexSite(v)); // Update who it came from } Edge.next(); } } // for route list } // Prim int minVertex( double D[MaxSites] ) { int v = MaxSites; int i = 0; for( i = 0; i < Site_map.size(); i++ ) if( getMark(i) == false ){ v = i; break; } for( i = 0; i < Site_map.size(); i++ ) if( getMark(i) == false && (D[i] < D[v])){ v = i; } return v; } // minVertex List<route*> GetAdjacentList( site* S_p ) {// All routes connecting S_p that haven't been visited List<route*> E_list; routes_List.begin(); for(int i = 0; i < routes_List.size(); i++ ) { if( (routes_List.getcurrent()->StartSite() == S_p && routes_List.getcurrent()->FinishSite()->visited() == false ) || ( routes_List.getcurrent()->FinishSite() == S_p && routes_List.getcurrent()->StartSite()->visited() == false ) ) E_list.AddToList( (route*) routes_List.getcurrent() ); routes_List.next(); } return E_list; } // GetAdjacentList int SiteIndex( site* S_p ) { int Return_int = INT_MAX; if( S_p == NULL ) return Return_int; Site_Name_List.begin(); for(int i = 0; i < Site_Name_List.size(); i++ ) { if( (*Site_Name_List.getcurrent()) == S_p->name() ) return i; Site_Name_List.next(); } return Return_int; } // SiteIndex string IndexSite( int v ) { string S_p; Site_Name_List.begin(); for(int i = 0; i < Site_Name_List.size(); i++ ) { if( i == v ) return (*Site_Name_List.getcurrent()); Site_Name_List.next(); } return S_p; } // SiteIndex void setMark( int v, bool T ) { site* S = search( IndexSite( v ) ); if( S ) S->visited( T ); } // setMark bool getMark( int v ) { site* S = search( IndexSite( v ) ); return S->visited(); } // getMark void AddEdgetoMST( site* s, int v ) { if( s == NULL ) return; site* A = search( IndexSite( v ) ); routes_List.begin(); for( int i = 0; i < routes_List.size(); i++ ) { if( ((*routes_List.getcurrent()).StartSite() == A && (*routes_List.getcurrent()).FinishSite() == s ) || ((*routes_List.getcurrent()).StartSite() == s && (*routes_List.getcurrent()).FinishSite() == A ) ) { MST_List.AddToList( (*routes_List.getcurrent()) ); break; } routes_List.next(); } } // AddEdgetoMST public: sitemanager(){} sitemanager(const sitemanager &S) { Site_map = S.Site_map; routes_List = S.routes_List; Site_Name_List = S.Site_Name_List; MST_List = S.MST_List; } ~sitemanager(){} bool addsite( string Name_string, string Xaxis_string, string Yaxis_string, string type_string ) { site Temp_site; if( search( Name_string ) ) { cout << "ERROR, site not created" << endl; return false; } try { int X_axis = calcaxis( Xaxis_string ); int Y_axis = calcaxis( Yaxis_string ); Temp_site.name( Name_string ); Temp_site.xaxis( X_axis ); Temp_site.yaxis( Y_axis ); Temp_site.type( type_string[0] ); } catch( BadAxisException e ) { cout << e.what(); return false; } catch( BadSiteNameException e ) { cout << e.what(); return false; } catch( BadTypeException e ) { cout << e.what(); return false; } Site_map.insert( Temp_site ); Site_Name_List += Temp_site.name(); return true; } // addsite void erase() { Site_map.erase(); routes_List.erase(); Site_Name_List.erase(); } // erase int size() { return Site_map.size(); } // size bool MATERIAL_SITE( site* S_p ) { if( S_p == NULL ) return false; return S_p->material(); } void LIST_SITES() { Site_map.LIST_SITES(); } route* create_route( string name1_string, string name2_string ) { site* site1_p = search( name1_string ); site* site2_p = search( name2_string ); // see if the sites exist if( site1_p == NULL || site2_p == NULL ) { if( site1_p == NULL ) cout << "ERROR: Site " << name1_string << " does not exist." << endl; if( site2_p == NULL ) cout << "ERROR: Site " << name2_string << " does not exist." << endl; return NULL; } // Check for material site if( (MATERIAL_SITE( site1_p ) && MATERIAL_SITE( site2_p ) == false) || (MATERIAL_SITE( site1_p ) == false && MATERIAL_SITE( site2_p ) ) ) { cout << "ERROR: Raw material sites can not have external routes." << endl; return NULL; } route R; R.make( site1_p, site2_p ); if( routes_List.find( R ) ) return NULL; else { routes_List.AddToList( R ); routes_List.find( R ); return (route*) routes_List.getcurrent(); } } // create_route route* GetRoute( string name_string ) { routes_List.begin(); for( int itr = 0; itr < routes_List.size(); itr++ ) { if( *(*routes_List.getcurrent()).StartSite() == name_string ) return (route*) routes_List.getcurrent(); routes_List.next(); } return NULL; } // GetRoute int GetRouteCount() { return routes_List.size(); } // GetRouteCount int GetBaseRouteCount() { int Return_int = 0; routes_List.begin(); for( int itr = 0; itr < routes_List.size(); itr++ ) { if( (*routes_List.getcurrent()).StartSite()->type() == 'B' || (*routes_List.getcurrent()).StartSite()->type() == 'L' || (*routes_List.getcurrent()).StartSite()->type() == 'S' ) Return_int++; routes_List.next(); } return Return_int; } // GetRoute void EraseRoute( route* R ) { if( routes_List.find( *R )) routes_List.pop_current(); } // GetRoute void EraseRoute() { routes_List.erase(); } // GetRoute // Type methods List<site*> GetTypeList( char C_char ) { List<site*> Q; Site_Name_List.begin(); for( int itr = 0; itr < Site_Name_List.size(); itr++ ) { site* S = Site_map.find( *Site_Name_List.getcurrent() ); if( S->type() == C_char ) Q += S; Site_Name_List.next(); } return Q; } bool IsSiteInGraph( string Site_string ) { routes_List.begin(); for( int itr = 0; itr < routes_List.size(); itr++ ) { if( (*routes_List.getcurrent()).StartSite()->name() == Site_string || (*routes_List.getcurrent()).FinishSite()->name() == Site_string) return true; routes_List.next(); } return false; } bool search( site S ) { if( Site_map.find(S) ) return true; else return false; } // search site* search( string name_string ) { site P; P.name( name_string ); site* S = NULL; S = Site_map.find(P); return S; } // search // overloads void operator=( const sitemanager &S ) { Site_map = S.Site_map; routes_List = S.routes_List; } // = void PrintRoutes() { if( routes_List.empty() ) return; cout << "List of routes:" << endl; routes_List.begin(); for( int itr = 0; itr < routes_List.size(); itr++ ) { (*routes_List.getcurrent()).OutPut(); cout << endl; routes_List.next(); } if( routes_List.empty() ) cout << "There are no routes in the pm1quadtree." << endl; } // PRINT_ROUTES() void PM_MST() { Site_map.SET_VISITED( false ); int L = GrabBaseRoutes(); weight W; W.setweight( 0.0 ); short Component_short = 0; while( L < INT_MAX ) // always one base site left { Prim( L ); if( MST_List.empty() == false ) { Component_short++; // next batch cout << "List of routes in Component #" << Component_short << endl; MST_List.begin(); for(int i = 0; i < MST_List.size(); i++ ) { (*MST_List.getcurrent()).OutPut(); W.add( (*MST_List.getcurrent()).getweight() ); cout << endl; MST_List.next(); } cout << "Total length is "; W.OutPut(); cout << endl << endl; } MST_List.erase(); W.setweight( 0.0 ); L = GrabBaseRoutes(); // grab the next batch } //cout << endl; cout << "Total # of connected components is " << Component_short << endl; Site_map.SET_VISITED( false ); } // PM_MST void OutPut() { cout << "List of sites:" << endl; Site_map.OutPut(); } // OutPut: generic output routine void RADIUS_POLYGONS( List<string> S_List ) { if( S_List.empty() ) return; List<string> T_List = S_List; S_List.begin(); for( int i = 0; i < S_List.size(); i++ ) { T_List.begin(); for( int j = 0; j < T_List.size(); j++ ) { routes_List.begin(); for( int k = 0; k < routes_List.size(); k++ ) { if( (*routes_List.getcurrent()).StartName() == (*S_List.getcurrent()) && (*routes_List.getcurrent()).FinishName() == (*T_List.getcurrent()) ) { (*routes_List.getcurrent()).OutPut(); cout << endl; } routes_List.next(); } T_List.next(); } S_List.next(); } } }; #endif // sitemanager.cc