#include "StdAfx.h"
#include "Q_Routing_Policy.h"
#include "Q_Routing_BellmanFordPolicy.h"

BellmanFordPolicy::BellmanFordPolicy( Network * network )
	: Policy( network )
{
	Init();
}

BellmanFordPolicy::~BellmanFordPolicy()
{
}

void BellmanFordPolicy::Init()
{
	RouterListIterator router_iterator;
	network->InitRouterListIterator( router_iterator );
	RouterListIterator inner_router_iterator;
	network->InitRouterListIterator( inner_router_iterator );

	// build the extra data for each router
	// for each router there will be list of all routers in the network
	
	// build the extra data
	for( router_iterator.Begin() ; !router_iterator.IsEnd() ; router_iterator++ )
	{
		BellmanFordExtraData * extra_data = new BellmanFordExtraData;

		extra_data->SetRoutersNum( network->GetRouterNum() );
		
		for( inner_router_iterator.Begin() ; !inner_router_iterator.IsEnd() ; inner_router_iterator++ )
			extra_data->AddRouter( inner_router_iterator.GetRouter() );
		
		// init the distination to my self to 0
		extra_data->SetNextHop( router_iterator.GetRouter() , router_iterator.GetRouter() , 0 ); 	

		router_iterator.GetRouter()->SetExtraData( extra_data );	
	}

	// find the shortest path
	for( unsigned int i=0 ; i<network->GetRouterNum() ; i++ )
	{
		// for each router
		for( router_iterator.Begin() ; !router_iterator.IsEnd() ; router_iterator++ )
		{
			Router * router = router_iterator.GetRouter();
			// for each neighbour
			for( int j=0 ; j<router->GetConnectionNum() ; j++ )
			{
				Connection & connection = router->GetConnection(j);
				Router & neighbour = connection.GetA() == *router ? connection.GetB() : connection.GetA();
				// try to improve next hop for each destination
				BellmanFordExtraData * router_extra_data = (BellmanFordExtraData*)router->GetExtraData();
				BellmanFordExtraData * neighbour_extra_data = (BellmanFordExtraData*)neighbour.GetExtraData();
				for( inner_router_iterator.Begin() ; !inner_router_iterator.IsEnd() ; inner_router_iterator++ )
				{
					Router * destination = inner_router_iterator.GetRouter();
					int neighbour_dist = neighbour_extra_data->GetNextHopDistance( destination );
					int router_dist = router_extra_data->GetNextHopDistance( destination );
					if( router_dist > neighbour_dist + 1 )
					{
						router_extra_data->SetNextHop( destination , &neighbour , neighbour_dist+1 ); 	
					}
				}
			}
		}
	}

	
/*  // TEST distances
	if( network->GetRouterNum() > 0 )
	{
		Router & base = network->GetRouter( 3 , 3 );
		for( i=3 ; i<6 ; i++ )
			for( int j=3 ; j<6 ; j++ )
			{
				BellmanFordExtraData * r = (BellmanFordExtraData *)network->GetRouter( i , j ).GetExtraData();
				int dist = r->GetNextHopDistance( &base );
				if( dist == -9 )
					return;	
			}
	}
*/

}	

void BellmanFordPolicy::Reset()
{
	throw( "not impliment yet" );	
}

void BellmanFordPolicy::NetworkChange()
{
	Init();
}

bool BellmanFordPolicy::OneStep( Router & router , Packet ** packet ) const
{
	BellmanFordExtraData & extra_data = *(BellmanFordExtraData*)router.GetExtraData();
	*packet = router.GetNextPacketToRoute();
	if( *packet == 0 )
		return true;
	// check if packet reach her destination
	if( *(*packet)->destination == router )
		return true;
	
	Router * next_hop = extra_data.GetNextHop( (*packet)->destination );
	ASSERT( next_hop );
	return router.GetConnection( *next_hop ).PutOnePacket( *next_hop , *packet );
}


///////////////////////////////
// extra data class
BellmanFordExtraData::BellmanFordExtraData()
{
	entries_num = 0;
	routers_list = 0;
}

BellmanFordExtraData::~BellmanFordExtraData()
{
	Clear();
}

void BellmanFordExtraData::Clear()
{
	if( routers_list )
	{
		delete[] routers_list;
		routers_list = 0;
		entries_num = 0;
	}
}

void BellmanFordExtraData::SetRoutersNum( int routers_num )
{
	Clear();
	
	entries_num = routers_num;
	routers_list = new Entry[ entries_num ];
}

void BellmanFordExtraData::AddRouter( Router * router )
{
	int index =0;
	while( index < entries_num &&
		   routers_list[index].destination_router != 0 )
		index++;

	assert( index < entries_num );

	routers_list[index].destination_router = router;
}

Router * BellmanFordExtraData::GetNextHop( Router * packet_destination )
{
	return GetRouterEntry( packet_destination )->next_hop;
}

int BellmanFordExtraData::GetNextHopDistance( Router * packet_destination )
{
	return GetRouterEntry( packet_destination )->distance;
}

void BellmanFordExtraData::SetNextHop( Router * destination ,
									   Router * new_next_hop ,
									   int distance )
{
	GetRouterEntry( destination )->next_hop = new_next_hop;
	GetRouterEntry( destination )->distance = distance;
}

BellmanFordExtraData::Entry * BellmanFordExtraData::GetRouterEntry( Router * destination )
{
	int index =0;
	while( index < entries_num && 
		   routers_list[index].destination_router != destination )
		index++;

	assert( index < entries_num );

	return &routers_list[index];
}