#include<stdio.h>
#include<unistd.h>
#include<stdlib.h>
#include<math.h>


typedef double Time ;

#define SIMTIME 5000    // Far too small
#define BSIZE 24000
#define tau 1.0

#define PD  1e-1    // 100 ns in microseconds
#define R   1e-2    // 10 ns
#define EQSize 500

#define MYX 7
#define MYY 7

#define MU 5   //  time is microseconds

#define ARRIVAL 1
#define STARTSEND 2
#define ENDSEND 3

struct IP {
    int x ; // coordinates x.y
    int y ;
} ;

struct Router {
    struct IP ip ;
    char OB[5][BSIZE] ; // OB[4] is Ethernet
    int OBptr[5] ;
    Time LFree[4] ;
    int lost ;
    int arrived ;
} Router77 ;

//  Every event deals with a packet, so I encoded events inside packet
//  descriptions.
struct Packet {
    struct IP source , dest ;
    int length ;
//  The following are event decriptors
    struct IP where ;
    int NextEvent ;
    Time when ;
    int link ;
    Time Sstart ;
    Time Send ;
} ;

    int last = 0 ;
    struct Packet *EQ[EQSize] ;

void Insert( struct Packet * , int , Time ) ;
struct Packet *Delete() ;
char *Show( int ) ;


void Insert( struct Packet *P , int Type , Time when )
{
    if( last + 1 == EQSize ) {
        printf( "EQ overflow Type=%d Time=%lf\n" , Type , when ) ;
        exit( -1 ) ;
    } else {
        P->NextEvent = Type ;
        P->when = when ;
        EQ[last++] = P ;
//        printf( "Inserted event %s to occur at time %lf\n"
//        , Show( EQ[last-1]->NextEvent ) , EQ[last-1]->when ) ;
//        fflush(stdout ) ;
    }
}

struct Packet *Delete()
{
    int min ;
    int i ;
    struct Packet *P ;
    if( last == 0 )
        return NULL ;
//    printf( "EQ: " ) ;
//    for( i = 0 ; i < last ; i++ )
//        printf( " %lf" , EQ[i]->when ) ;
//    printf( "\n" ) ;
    min = 0 ;
    for( i = 1 ; i < last ; i++ )
        if( EQ[i]->when < EQ[min]->when )
            min = i ;
//    printf( "Deleting event %s to occur at time %lf\n"
//        , Show( EQ[min]->NextEvent ) , EQ[min]->when ) ;
//    fflush(stdout ) ;
    P = EQ[min] ;
    EQ[min] = EQ[--last] ;
    return P ;
}

//  Thie following function is not correct for a multi-router simulator
struct Packet *Create( struct Router *MyRouter , Time Now )
{
    int x , y ;
    struct Packet *p ;

    printf( "You cannot use this function as is\n" ) ;
    p = (struct Packet *) malloc( sizeof( struct Packet ) ) ;
    if( p == NULL ) {
        printf( "malloc failed\n" ) ;
        exit( -1 ) ;
    }
    p->source.x = MyRouter->ip.x + random()%3 - 1 ;
    p->source.y = MyRouter->ip.y + random()%3 - 1 ;
    do {
        x = MyRouter->ip.x + random()%3 - 1 ;
        y = MyRouter->ip.x + random()%3 - 1 ;
    } while( x == p->source.x && y == p->source.y ) ;
    p->dest.x = x ;
    p->dest.y = y ;
    p->length = 1 + random() % 4800 ;
//    printf( "Creating packet (%d.%d)-->(%d.%d) of length %d\n"
//    , p->source.x , p->source.y , p->dest.x , p->dest.y , p->length ) ;
    return p ;
}

char *Show( int E )
{
    switch( E ) {
    case ARRIVAL:   return "Arrival" ;
    case STARTSEND: return "Start send" ;
    case ENDSEND:   return "End send" ;
    }
}

//  The following function does not agree with the assignment
//  specification
Time IA( )
{
    printf( "You cannot use this function as is\n" ) ;
    return -tau * MU * log( drand48() ) ;
}

int PickLink( struct Router *MyRouter , struct Packet *P )
{
    if( P->dest.x == MyRouter->ip.x && P->dest.y == MyRouter->ip.y )
        return 4 ;
    else if( P->dest.x == MyRouter->ip.x )
        return 2 * (P->dest.y > MyRouter->ip.y) ;
    else if( P->dest.y == MyRouter->ip.y )
        return 1 + 2 * (P->dest.x > MyRouter->ip.x) ;
    else if( P->dest.x > MyRouter->ip.x ) {  // up+right
        if( MyRouter->OBptr[2] < MyRouter->OBptr[3] )   // 2 has more room
            return 2 ;
        else if( MyRouter->OBptr[2] > MyRouter->OBptr[3] )
            return 3 ;
        else
            return 2 + random() % 2 ;
    } else {        // down+left
        if( MyRouter->OBptr[0] < MyRouter->OBptr[1] )   // 0 has more room
            return 0 ;
        else if( MyRouter->OBptr[0] > MyRouter->OBptr[1] )
            return 1 ;
        else
            return  random() % 2 ;
    }       
}

void simulate( struct Router *MyRouter )
{
    Time Now ;
    struct Packet *P ;
    int i ;

    Now = 0 ;
    Insert( Create( MyRouter , Now  ) , ARRIVAL , Now  ) ;
    while( (P = Delete()) != NULL ) {
        Now = P->when ;
//  Use in this place:
      if( Now > SIMTIME ) break ;
//  as one way of ending simulation
        printf( "Event %s at time %lf: " , Show(P->NextEvent) , Now ) ;
        printf( "packet (%d.%d)-->(%d.%d) of length %d\n"
            , P->source.x , P->source.y , P->dest.x , P->dest.y , P->length ) ;
        fflush( stdout ) ;
        switch( P->NextEvent ) {
        case ARRIVAL:
            P->where.x = MyRouter->ip.x ;
            P->where.y = MyRouter->ip.y ;
//  Use in this place:
//      if( Now < SIMTIME ) 
//  as another way of ending simulation
                Insert( Create( MyRouter , Now ) , ARRIVAL , Now + IA() ) ;
            P->link = PickLink( MyRouter , P ) ;
            if( P->link == 4 ) {
                MyRouter->arrived++ ;
                printf( "Link 4: packet to local destination removed (%d)\n"
                    , MyRouter->arrived ) ;
                free( P ) ;
            } else if( MyRouter->OBptr[P->link] + P->length > BSIZE ) {
                MyRouter->lost++ ;
                printf( "Packet dropped (lost=%d)\n" , MyRouter->lost ) ;
                free( P ) ;
            } else {
                MyRouter->OBptr[P->link] += P->length ;
                printf( "Link %d: packet buffered. New length=%d\n"
                    , P->link , MyRouter->OBptr[P->link] ) ;
                if( MyRouter->LFree[P->link] < Now )
                    MyRouter->LFree[P->link] = Now ;
                P->Sstart = MyRouter->LFree[P->link] ;
                P->Send = P->Sstart + P->length * R ;
                Insert( P , STARTSEND , P->Sstart ) ;
                MyRouter->LFree[P->link] += P->length * R ;
            }
            break ;
        case STARTSEND:
            printf( "Link %d: transmission start at time %lf\n"
                    , P->link , Now ) ;
            Insert( P , ENDSEND , P->Send ) ;
            break ;
        case ENDSEND:
            MyRouter->OBptr[P->link] -= P->length ;
            printf( "Link %d: transmission end at time %lf (new length=%d)\n"
                    , P->link , Now , MyRouter->OBptr[P->link] ) ;
            free( P ) ;
            break ;
        }
    }
    printf( "End of simulation: lost=%d arrived at 7.7=%d\n"
        , MyRouter->lost , MyRouter->arrived ) ;
    printf( "Buffer space in use: " ) ;
// Will always be 0 with the second method of ending simulation
    for( i = 0 ; i < 4 ; i++ )
        printf( " %d" , MyRouter->OBptr[i] ) ;
    printf( "\n" ) ;
}

void initialise(struct Router *MyRouter )
{
    int i ;
    srand48( getpid() ) ;
    srandom( getpid() ) ;
    MyRouter->ip.x = MYX ;
    MyRouter->ip.y = MYY ;
    for( i = 0 ; i < 4 ; i++ ) {
        MyRouter->OBptr[i] = 0 ;  // Nothing in buffers
        MyRouter->LFree[i] = 0 ;  // No delay to start transmitting
        MyRouter->lost = 0 ;
        MyRouter->arrived = 0 ;
    }
    
}

main()
{
    initialise( &Router77 ) ;
    simulate( &Router77 ) ;
}