Quad tree search sitemanager.cc

/*
 * 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