#include <stdio.h>
#include <string.h>


//Global structure for the node used in the program
typedef struct node {

                int label;  //label that tells the node number in the network
                int pass;   //Number of passes, counter
                int flagu;  //flag to determine if the node is used
                int ncost[7][2];//bidimensional table for this ex, cost|via(NODE)
                struct node *next; //pointer to link nodes in the list

                }Node;


//Global table used for the costs(weight) of travelling from node to node
int table[7][7];



//Function to create a new network for the dijkstra modified algorithm
Node *new_network(void)
{

  Node *head; //head pointer for the list
  int i,j; //indexes for the neighbor array


  head=(Node *)malloc(sizeof(Node)); //allocating memory for the first node (root)
  head->next=NULL; //will be given by the simulator
  head->flagu=1; //default value of not used in probabilistic routing algorithm
  head->label=1; //default starting node;
  head->pass=1; //to indicate the actual node is the root for dijkstra loop
  //initializing head node's neighbor cost matrix

  for(i=0;i<7;i++)
    for(j=0;j<2;j++)
      head->ncost[i][j]=999;


  //initializing head node neighbors

   head->ncost[0][0]=0; //source node
   head->ncost[0][1]=1; //via source node
   head->ncost[1][0]=999;//cost of getting to neighbor (initial values)
   head->ncost[1][1]=2;//via this node (initial values)
   head->ncost[3][0]=999;//cost to neighbor 4
   head->ncost[3][1]=4;//via neighbor 4
   //head->ncost[6][0]=5;  remove later only for debugging
   //head->ncost[6][1]=7;


   printf("             Neighbors----> ");
   printf("\n Cost \n");
  for(i=0;i<7;i++)
    {for(j=0;j<1;j++)
       printf("%d %d \n",head->ncost[i][j],head->ncost[i][j+1]);}


  return(head);
}


//Function to insert nodes in the network
//The nodes will be binded in the link and linked between them through a link table
//This functions recieves the head of the list, the name of the node and the cost table(initial)

Node *add_node (Node *head, int label, int ncostin[7][2])
{

  int x; //index
  int i,j; //indexes for initialing node array
  Node *start; //head pointer to move in list
  Node *temp; //temporary pointer for new node


  start=head;
  while ( (start->next) !=NULL)
    start=start->next;

  temp=(Node *)malloc(sizeof(Node));
  start->next=temp;

  temp->label=label;
  temp->flagu=1; //first initialization to remove from viewed list
  temp->next=NULL;
  temp->pass=1;

  //Initializing neighbor array
  for(i=0;i<7;i++)
    for(j=0;j<2;j++)
      temp->ncost[i][j]=999;

    for(i=0;i<7;i++)
      for(j=0;j<2;j++)
        temp->ncost[i][j]=ncostin[i][j];



  return(head);

  }


//Function to display the routing or probabilistic table at each node
//The inputs are the head of the list and the node you want to show
void display(Node *head, int label)
{

  Node *temp;
  int i,j;


   temp=head;//preserving head pointer


   while( (temp->next)!=NULL)
   {
     //printf("temp %d label %d\n",temp->label,label);
     if( (temp->label)==label)
     {
       printf("             via (neighbor node)----> ");
       printf("\n Cost \n");
       for(i=0;i<7;i++)
        for(j=0;j<1;j++)
         printf("%d %d \n",temp->ncost[i][j],temp->ncost[i][j+1]);

         temp=temp->next;
      }
      else
        if((temp->next)!=NULL)

            temp=temp->next;
   }

}


//This function is to create the global matrix of costs for the nodes.

int init_table()
{
  int i,j;  //temporal indexes

  //Table initialization
  //Costs will be set to a maximum(broken link) of 999
    for(i=0;i<7;i++)
    for(j=0;j<7;j++)
      table[i][j]=999;

  //Initializing same vector distances(cost) (from node 1 to 1 , 2 to 2 etc.)
    for(i=0;i<7;i++)
    table[i][i]=0;


   //Neighbor initialization (declares the costs for the neighbors)

   table[0][1]=2;//Node 1
   table[0][3]=1;
   table[1][3]=3;//Node 2
   table[1][4]=10;
   table[2][0]=4;//Node 3
   table[2][5]=5;
   table[3][2]=2;//Node 4
   table[3][4]=2;
   table[3][5]=8;
   table[3][6]=4;
   table[4][6]=6;//Node 5
   table[6][5]=1;//Node 7

      //Displaying table for test

  printf("                     Destination\n");
  printf("Source                       \n");

  for(i=0;i<7;i++)
    {
      for(j=0;j<7;j++)
        printf("%d   ", table[i][j]);
      printf("\n");



    }
  }

//This function calculates the cost of travelling from one node to another
//from the values stored in the cost table.
//This function recieves the source and destination node

int cost (int source, int destination)
{
  int s,d;  //temporary locations for source and destination
  int output; //variable to store and send the cost

  s=(source-1);
  d=(destination-1);
  output=table[s][d];
  //printf("COST %d\n",output);
  return(output);

}

int in_list(int node, int u[7])
{
  int i,j,x;//indexers
  int output;//variable to tell if node is in unvisited list

  output=0;
  for (x=0;x<7;x++)
  {
    if(node==u[x])
      output=1;
   }
   //printf("Node %d, output (in list) %d\n",node,output);
  return(output);
}

//Function to find the minimum values from the probabilistic tables.
//to determine the shortest path to follow for the dijkstra algorithm
//It recieves the actual node the algorithm is on and the Unvisited node list

int find_min(Node *actual, int u[7])
{
   int x,i,j,output;//temporary registers and indexes
   int temp, temp2;//indexers
   int out;//final ouput it gives the next node to process
   int k; //for checking elements in the unvisited U list
   int ban1,ban2;//flags for unused integers

   i=0;
   j=1;


   x=0;
   while(x<7)

   {

       ban1=in_list(actual->ncost[i][1],u);
       ban2=in_list(actual->ncost[j][1],u);
       //printf("BAN1 %d Ban2 %d\n",ban1,ban2);


       temp=actual->ncost[i][0];
       temp2=actual->ncost[j][0];

       //printf("TEMP %d TEMP2 %d nodet1 %d node t2 %d\n",temp,temp2,actual->ncost[i][1],actual->ncost[j][1]);


       if (temp<temp2)
        {
          if (ban1)
           {
            output=i;
            j++;
           }
           else
           {
            i++;
            j++;
           }


        }
        else
          {

            if(ban2)
              {
                output=temp2;
                i=j;
                j++;
              }
            else
            j++;
          }
        x++;
      }


    out=actual->ncost[output][1];
    printf("The next node is %d with x coord %d and cost %d\n",out,output,actual->ncost[output][0]);
   return(output);

}

//Function to calculate the minimum values from two numbers, it recieves them.


int min(int a, int b)
{
  int output;//for minimun vector

  if(a<b)
    output=a;
  else
    output=b;

  return(output);
}

//Function to calculate the direct routes, (node to node links) of the network
//This function recieves the network head node and modifies the routing tables
//of the entire network, but only the direct connections.
//This functions is one of the functions that compose the dijkstra's
//Modified routing algorithm

void direct_route (Node *head)

{
  int U[7];//temporary unvisited vectors for dijkstra
  Node *start,*pthead, *temp2; //temporary copies of the head of list pointer
  int x,i,j; //indexers
  int getindex;//gets index for the next node of ncost table
  int nnode; //next node to go to
  int test;

  int distance; //to calculate new values for cost in functions

  start=head; //baking up head pointer for node displacement
  pthead=head;  //baking up head pointer
  //temp2=head; //for node comparison
  //temp2=temp2->next;//for node comparison

  //Creating Unvisited node list
  for(i=0;i<7;i++)
    U[i]=i+1;
  //printf("NODEO %d \n",U[6]);

  /*DEBUGGIN ONLY
  start=start->next->next->next->next->next->next;
  printf ("IVI hola soy nodo %d\n",start->label);
  getindex=find_min(start,U);//tells us the x coord in the ncost table for lookup
  nnode=start->ncost[getindex][1]; //the node to visit
  printf("ahora voy al nodo %d\n",nnode);*/

 x=0;
 while(x<7)
 {
  //finding node to go to
  getindex=find_min(start,U);//tells us the x coord in the ncost table for lookup
  nnode=start->ncost[getindex][1]; //the node to visit
  printf("NEXT IVI NODE %d\n",nnode);
  //---------------NEW---------------------------

  while( !(start->label==nnode))
    start=start->next;

  //reserved for loop--------------------------------------------------------


  //removing node from unvisited vectors list
  for(i=0;i<7;i++)
    {
      if(U[i]==nnode)
        U[i]=-1;
     printf("NODES %d\n",U[i]);//test material
     }


   //calculating preparing for next node and recalculating costs

     for(i=0;i<7;i++)
     { //printf("start %d label %d\n",start->ncost[i][1],start->label);
       if( (start->ncost[i][1]!=start->label)&&(start->ncost[i][1]!=999))
         {
           distance=min(start->ncost[i][0],cost(start->label,start->ncost[i][1]));
           printf("NEw distance is %d, for node %d to node %d\n",distance,start->label,start->ncost[i][1]);
           start->ncost[i][0]=distance;
           //printf("estes es %d\n",start->ncost[i][1]);
         }
     }

     x++;

     //security measure to move from nodes
     //finding node to go to
     start=pthead;
     getindex=find_min(start,U);//tells us the x coord in the ncost table for lookup
     nnode=start->ncost[getindex][1]; //the node to visit
     //printf("IIVIVIVIVI NNDOE %d\n\n",nnode);
     while( (nnode==999)&&(start->next!=NULL))
       {
         printf("In node %d,",start->label);
         start=start->next;
         printf(" going to node %d\n",start->label);

         getindex=find_min(start,U);//tells us the x coord in the ncost table for lookup
         nnode=start->ncost[getindex][1]; //the node to visit
        }

  //loop ends-------------------------------------------------------------------------------

 }
}




int main(void)
{

  Node *ptr_head;
  int i,j, ncost[7][2];
  Node *test;
  int prueba;



  ptr_head=new_network();


  //Adding nodes to network

  //Node 2
  //initializing neighbors
  for(i=0;i<7;i++)
    for(j=0;j<2;j++)
      ncost[i][j]=999;
  ncost[1][0]=0;
  ncost[1][1]=2;
  ncost[3][0]=999;
  ncost[3][1]=4;
  ncost[4][0]=999;
  ncost[4][1]=5;
  ptr_head=add_node(ptr_head,2,ncost);
  //Node 3
  //initializing neighbors
  for(i=0;i<7;i++)
    for(j=0;j<2;j++)
      ncost[i][j]=999;
  ncost[2][0]=0;
  ncost[2][1]=3;
  ncost[0][0]=999;
  ncost[0][1]=1;
  ncost[5][0]=999;
  ncost[5][1]=6;
  ptr_head=add_node(ptr_head,3,ncost);
//Node 4
//initializing neighbors
  for(i=0;i<7;i++)
    for(j=0;j<2;j++)
      ncost[i][j]=999;
  ncost[3][0]=0;
  ncost[3][1]=4;
  ncost[2][0]=999;
  ncost[2][1]=3;
  ncost[4][0]=999;
  ncost[4][1]=5;
  ncost[5][0]=999;
  ncost[5][1]=6;
  ncost[6][0]=999;
  ncost[6][1]=7;
 ptr_head=add_node(ptr_head,4,ncost);
//Node 5
//initializing neighbors
  for(i=0;i<7;i++)
    for(j=0;j<2;j++)
      ncost[i][j]=999;
  ncost[4][0]=0;
  ncost[4][1]=5;
  ncost[6][0]=999;
  ncost[6][1]=7;
  ptr_head=add_node(ptr_head,5,ncost);
//Node 6
//initializing neighbors
  for(i=0;i<7;i++)
    for(j=0;j<2;j++)
      ncost[i][j]=999;
  ncost[5][0]=0;
  ncost[5][1]=6;
  ptr_head=add_node(ptr_head,6,ncost);
//Node 7
//initializing neighbors
  for(i=0;i<7;i++)
    for(j=0;j<2;j++)
      ncost[i][j]=999;
  ncost[6][0]=0;
  ncost[6][1]=7;
  ncost[5][0]=999;
  ncost[5][1]=6;
  ptr_head=add_node(ptr_head,7,ncost);
//Creating node 8 for ending list node
//Node 8
//initializing neighbors
  for(i=0;i<7;i++)
    for(j=0;j<2;j++)
      ncost[i][j]=999;

   // ncost[7][0]=0;
   // ncost[7][1]=8;
  ptr_head=add_node(ptr_head,8,ncost);


  display(ptr_head,2);
  display(ptr_head,3);
  display(ptr_head,4);
  display(ptr_head,5);
  display(ptr_head,6);
  display(ptr_head,7);
  init_table();
  //cost(3,6); //for going from node 3 to node 6 the cost
 //direct_route();
 test=ptr_head;

 direct_route(ptr_head);
 display(ptr_head,1);
 display(ptr_head,2);
  display(ptr_head,3);
  display(ptr_head,4);
  display(ptr_head,5);
  display(ptr_head,6);
  display(ptr_head,7);


}