#include "StdAfx.h"
#include "Q_Routing_Policy.h"
#include "Q_Routing_QRoutingPolicy.h"
#include <math.h>

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

QRoutingPolicy::~QRoutingPolicy()
{
}

void QRoutingPolicy::Init()
{
	// build the extra data for each router
	// for each router there will be list of all routers in the network, for each neighbor 
	RouterListIterator router_iterator , inner_router_iterator;
	network->InitRouterListIterator( router_iterator );
	network->InitRouterListIterator( inner_router_iterator );	
	
	// build the extra data
	for( router_iterator.Begin() ; !router_iterator.IsEnd() ; router_iterator++ )
	{
		QRoutingExtraData * extra_data = new QRoutingExtraData(router_iterator.GetRouter());

		extra_data->SetRoutersNum( network->GetRouterNum() );
		
		for( inner_router_iterator.Begin() ; !inner_router_iterator.IsEnd() ; inner_router_iterator++ )
			extra_data->AddRouter( inner_router_iterator.GetRouter() );
		
		router_iterator.GetRouter()->SetExtraData( extra_data );	
	}

}	

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

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

bool QRoutingPolicy::OneStep( Router & router , Packet ** packet ) const
{
	QRoutingExtraData & extra_data = *(QRoutingExtraData*)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 , (*packet)->last_router );

	ASSERT( next_hop );
	
	bool is_success = router.GetConnection( *next_hop ).PutOnePacket( *next_hop , *packet );
//	if( !is_success )
//		return false;

	const double factor = 0.05;
	double time = ((QRoutingExtraData*)next_hop->GetExtraData())->GetExpectedTime( (*packet)->destination ) + next_hop->GetLoad();
	double buffer_t = router.GetLoad();
	Connection & connection = router.GetConnection( *next_hop );
	double connection_t = ( connection.GetA() == *next_hop ) ? connection.GetLoadToA() : connection.GetLoadToB();
	if( !is_success )
		time = PACKET_DUMP_PRICE;
	double curr_Q = extra_data.GetExpectedTime( (*packet)->destination , next_hop );
	double delta_Q = factor * ( buffer_t + connection_t + time - curr_Q );  

//	if( delta_Q > 0 && !( curr_Q == time ) )
//		time = ((QRoutingExtraData*)next_hop->GetExtraData())->GetExpectedTime( (*packet)->destination );

	double new_Q = curr_Q + delta_Q;
	if( new_Q > PACKET_DUMP_PRICE )
		new_Q = PACKET_DUMP_PRICE;

	extra_data.Update( (*packet)->destination , next_hop , new_Q ); 

	return is_success;
}


///////////////////////////////
// extra data class
QRoutingExtraData::QRoutingExtraData( Router * parent_par )
{
	entries_num = 0;
	routers_num = 0;
	routers_list = 0;

	parent = parent_par;

	neighbor_num = 0;
	neighbor_list = 0;
}

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

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

void QRoutingExtraData::SetRoutersNum( int routers_num_par )
{
	Clear();
	
	neighbor_num = parent->GetConnectionNum();

	routers_num = routers_num_par;
	entries_num = routers_num * neighbor_num;
	routers_list = new Entry[ entries_num ];

	neighbor_list = new RouterPointer[ neighbor_num ];
	for( int i =0 ; i<neighbor_num ; i++ )
	{
		Connection & connection = parent->GetConnection(i);
		if( connection.GetA() == *parent )
			neighbor_list[i] = &connection.GetB();
		else
			neighbor_list[i] = &connection.GetA();
	}
}

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

	assert( index < entries_num );

	for( int i=0 ; i<neighbor_num ; i++ )
	{
		routers_list[index + i].destination		= router;
		routers_list[index + i].neighbor		= neighbor_list[i];	
		if( *parent == *router)
			routers_list[index + i].expected_time	= 0;
		else if ( *neighbor_list[i] == *router )
			routers_list[index + i].expected_time	= 1;
		else
			routers_list[index + i].expected_time	= PACKET_DUMP_PRICE;
	}
}

Router * QRoutingExtraData::GetNextHop( Router * packet_destination , Router * packet_last_router )
{
	// compute the greedy policy
	int min_index = -1;
	double bset_for_now;// = GetRouterEntry( packet_destination , min_index )->expected_time; 
	for( int i=0 ; i< neighbor_num ; i++ )
	{	
		// for each router there must be atlest 2 neighbors, so we dont want to send packet to the place where she come from
		if( packet_last_router && packet_last_router->GetPosition() ==  neighbor_list[i]->GetPosition() )
			continue;

		double load = (double)neighbor_list[i]->GetLoad() / neighbor_list[i]->GetCapacity(); 
		double factor = pow( (1.0 / (1.001 - load)) , 2 );
		double new_suqest = factor * GetRouterEntry( packet_destination , i )->expected_time;
		if( min_index == -1 || 
			new_suqest < bset_for_now || 
			(new_suqest == bset_for_now && rand() < (RAND_MAX/2) ) )
		{
			bset_for_now = new_suqest;
			min_index = i;
		}
	}
	
	// give epsilon chance to the others routres
	static double epsilon = Q_ROUTING_EPSILON;
	if( neighbor_num > 2 ) // if neighbor_num==2, then we have to send the packet to the router from which the packet didnt came
	{
		if( (double)rand() / RAND_MAX < epsilon || bset_for_now == PACKET_DUMP_PRICE )
			min_index = rand() % neighbor_num;
	}

	return neighbor_list[min_index];
}

void QRoutingExtraData::Update( Router * destination ,
								Router * neighbor ,
								double new_expected_time )
{
	Entry * entry = GetRouterEntry( destination , neighbor );
	
	assert( entry  );
	
	entry->expected_time = new_expected_time;
}

double QRoutingExtraData::GetExpectedTime( Router * destination , Router * neighbor ) const
{
	if( *destination == *parent )
		return 0.0;

	Entry * entry = GetRouterEntry( destination , neighbor );
	assert( entry );
	return entry->expected_time;
}

double QRoutingExtraData::GetExpectedTime( Router * destination ) const
{
	double answer = GetExpectedTime( destination , neighbor_list[0] );
	for( int i=1 ; i< neighbor_num ; i++ )
	{
		double expected_time = GetExpectedTime( destination , neighbor_list[i] );
		if( expected_time < answer )
			answer = expected_time;
	}

	return answer;
}

QRoutingExtraData::Entry * QRoutingExtraData::GetRouterEntry( Router * destination , unsigned int neighbor_index ) const
{
	unsigned int index =0;
	while( index < entries_num && 
		   routers_list[index].destination != destination )
		index += neighbor_num;

	assert( index + neighbor_index < entries_num );

	return &routers_list[index + neighbor_index];
}

QRoutingExtraData::Entry * QRoutingExtraData::GetRouterEntry( Router * destination ,Router * neighbor ) const
{
	unsigned int index =0;
	while( index < entries_num && 
		   routers_list[index].destination != destination )
		index += neighbor_num;

	assert( index < entries_num );

	while( index < entries_num && 
		   routers_list[index].neighbor != neighbor )
		index++;

	assert( index < entries_num );

	return &routers_list[index];
}