#include <stdio.h>
#include <malloc.h>

#include "aloca.h"
#include "sbtools.h"
#include "sbd.h"
#include "sodl.h"
#include "longest.h"
#include "active.h"

/*
 *
  */


SORT_DESCENDING(long solution_number,
     long *the_order ,
     long *keep_makespans )
{ long i , j ;
  long *sorted ;
  long point ;
  long biggest ; 

  sorted = (long *) calloc((100),sizeof(long)) ;
  for (i=0;i<=solution_number;i++) sorted[i] = 0 ; 
  for (i=1;i<=solution_number;i++)  { /* find the smallest makespan */
     biggest = ((long) RAND_MAXI) ;  
     for (j=1;j<=solution_number;j++) {
        if ( sorted[j] == 0 ){
          if (keep_makespans[j] < biggest) {
            point = j ; 
            biggest = keep_makespans[j] ; 
              }
          }
      }
   the_order[i] = point; 
   sorted[point] = 1 ; 
   }
 free(sorted) ; 
}


/* ******************************************************************* */
/** This procedure Generates an active schedule for the Job           **/
/** Shop Scheduling Problem.                                          **/
/* ******************************************************************* */

/* use the most work remaining dispatching rule */

ACTIVE_SCHEDULE( /* number of runs for the randomized active schedule 
                          */
                long run_it ,
                long m , 
     long my_jobs ,
     long oper ,
     long *jobpred ,
     long *macpred , 
     long *jobsucc , 
     long *macsucc , 
     long finishing ,
     long  MKSP_GUESS , 
     long *which_job ,
     long *machine_sched ,
     long *releases ,
     long *tails ,
     long *operations , 
     long *processing_time ,
     long *which_machine ,
     long *actdeadline ,
     long *moddeadline , 
     long *actrelease ,
     long *pdc , 
     long *scs ,
     long *LIST ,
     long *POS ,
     long *machine_total ,
     long *position )
{
 long i , j ;
 long mksp ; 
 long kk ;
 long best_makespan ; /* best upper bound from the randomized dispatching
                        rules */
 long jsele ; 
 long mstar , phistar ;
 long jstar ; 
 long phik ; 
 long toper ; 
 long solution_number ;  
 long SELECTED ; 
 long maxcompl ; 
 long jobi , mwrdr , jnext ;
 long tcand ;
 
 long candidates [ 1000 ] ; 
 long pointe[ MAXJOBIS ] ; 
 long machtime[ MAXMACHINES ] ; 
 long labl[ MAXOPER ] ;
 long the_order [ 1000 ] , keep_makespans [ 10000 ] ;
 long labelled_list [ MAXOPER ] ; 

 long LONGEST_PATH() ; 
 double aa , cbefore , cweight , tweight , y ; 
 double weights [ 100 ] ; 
 double random_number() ; 

 long MAX_METHODS ; /* number of dispathing rules implemented here*/
 long iter_without_imprv ; 
 long max_iter_no_imprv ; 
 long method ;  /* dispatching rules: 
               0 : Most Work Remaining
               1 : Longest Processing Time 
               2 : Shortest Processing Time
               */

/* STARTTIME(1) ;  */

 best_makespan = ((long) RAND_MAXI) ; 
 method = 0 ; /* start with the MWKR dispatching rule */
 
 iter_without_imprv = 0 ; 
 max_iter_no_imprv = 30 ; /* maximum iterations without 
                             improvements, change method 
                             if you reach this iterations */

 MAX_METHODS = 2 ; 
 
 for (kk=0; kk < run_it ; kk++) {
   for (i=1;i <= m ; i++) {
     DELETE_MACHINE(i,
                    machine_sched,
                    pdc,
                    scs,
                    machine_total,
                    finishing,
                    macpred,
                    macsucc) ; 
   }

 mksp = LONGEST_PATH(m,
                     my_jobs,
                     oper,
                     finishing,
                     jobpred,
                     jobsucc,
                     macpred,
                     macsucc,
                     MKSP_GUESS,
                     machine_sched,
                     actrelease,
                     releases,
                     tails,
                     moddeadline,
                     actdeadline,
                     processing_time,
                     operations,
                     pdc,
                     scs,
                     LIST,
                     POS,
                     machine_total,
                     labelled_list,
                     0);

 maxcompl = 0 ; 
 for (i=1;i<=m;i++)  { 
    machine_total[i] = 0 ; 
    machtime[i]      = 0 ; 
   }
 for (i=1;i<=my_jobs;i++) pointe[i] = 1 ; 
 for (i=0;i<=oper+1;i++)  {
   releases[i] = 0 ;
   labl[i] = 0 ;
   tails[i] = 0 ;  
 } 

 for (i=1;i<=my_jobs;i++) {
  for (j=operations[i]-1;j>=1;j--)  { 
    jobi = job_operations[i][j] ;
    jnext = job_operations[i][j+1] ; 
    tails[jobi] = tails[jnext] + processing_time[jnext] ;      
  }
}

 toper = 0 ; 
 while ( toper < oper )    { 

    /* find among all the aviable operations the one with  */
    /* the minimum phi[k] : be the earliest time that      */
    /* the operation k could be finished;                  */
    /* also find machine M(*) ;                            */

     phistar = ((long)  RAND_MAXI) ; 
     for (i=1;i<=my_jobs;i++)    { 
       if (pointe[i] <= operations[i])    {
        jobi = job_operations[i][pointe[i]] ; 
        phik = releases[jobi] + processing_time[jobi] ; 
        if (phik < phistar)  { 
          phistar = phik ; 
          mstar   = which_machine[jobi] ; 
        }
      }
     }
     
      /* choose an operation j in M(*) such that */
      /* releases[j] < phistar                   */

     mwrdr = 0 ; 
     tcand = 0 ;
     for (i=1;i<=my_jobs;i++) {
       if (pointe[i] <= operations[i])  {
         jobi = job_operations[i][pointe[i]]; 
         if (releases[jobi] < phistar) {
           tcand++ ; 
           candidates [ tcand ] = jobi ; 
           if (method == 0) { /* most work remaining */
             keep_makespans [ tcand ] = tails [ jobi ] ; 
           }
           if ((method == 1) ||
               (method == 2)) { 
             /* 
              * longest processing time or shortest processing time 
              */
             keep_makespans [ tcand ] = processing_time [ jobi ] ; 
           }
         }
       }
     }

     solution_number = tcand ; 
     SORT_DESCENDING(solution_number,
                     the_order,
                     keep_makespans) ; 

     if (method == 2) {
       aa = 1.0 ; 
       for (i=1 ; i <= solution_number; i++)  { 
         j = the_order[i] ; 
         aa = 2.0 * aa ; 
         weights[j] = (1.0 /  aa) ; 
       }
     }
     else {
       aa = 1.0 ; 
       for (i=solution_number;i>=1;i--)  { 
         j = the_order[i] ; 
         aa = 2.0 * aa ; 
         weights[j] = (1.0 /  aa) ; 
       }
     }

     tweight = 0.0 ;
     for (i=1;i<=tcand;i++) tweight = tweight + weights[i] ; 
     for (i=1;i<=tcand;i++) weights[i] = (weights[i] /  tweight) ; 
     
     /* normalization */

   tweight = 0.0 ;
   for (i=1;i<=tcand;i++) tweight = tweight + weights[i] ; 
/*
   num = rand() ; 
   y   = num / RAND_MAX ; 
*/

     y=random_number() ; 
   y =  y * tweight ; 
   cweight = 0.0 ;
   SELECTED = 0 ;  
   for (i=1;i<=tcand;i++)  { 
        cbefore = cweight ;
        cweight = cweight + weights[i] ;  
         if ((cbefore <= y) && (y <= cweight))  {
             SELECTED = i ; 
             i = tcand + 100 ;
           }
      }

     if (SELECTED == 0) printf("WHY !!!!!!!!!!!!!!!! \n") ;  
     jobi = candidates[SELECTED] ; 
     mstar = which_machine[jobi] ; 
     jstar = which_job[jobi] ; 
     jsele = jobi ; 


         /* add this in the machine M(*)                          */
         /* add the  counter for the job that is affected         */
         /* modify the operation is after the operation selected. */
       
     machine_total[mstar] = machine_total[mstar] + 1 ; 
     machine_operations[mstar][machine_total[mstar]] = jsele ; 
     pointe[jstar] = pointe[jstar] + 1 ; 
     jobi  = job_operations[jstar][pointe[jstar]] ;
     if (releases[jobi] < releases[jsele] + processing_time[jsele] )  { 
       releases[jobi] = releases[jsele] + processing_time[jsele] ; }
     if (maxcompl < releases[jsele] + processing_time[jsele])  {
       maxcompl = releases[jsele] + processing_time[jsele] ; }

     machtime[mstar] = releases[jsele] + processing_time[jsele] ; 
     labl[jsele] = 1 ; 
     for (i=1;i<=oper;i++)  {
       if ((labl[i] == 0 ) && (which_machine[i] == which_machine[jsele]))  {
         if (releases[i] < (releases[jsele]+processing_time[jsele])) 
           releases[i] = releases[jsele] + processing_time[jsele] ;
       }
     }
     toper = toper + 1 ; 
   }

 for (i=1;i<=m;i++) machine_sched[i] = 1 ; 
 SEQUENCE_FIXED_MACHINES(machine_sched,
                         machine_total,
                         position,
                         m,
                         finishing,
                         macpred,
                         macsucc) ; 

 mksp = LONGEST_PATH(m,
                     my_jobs,
                     oper,
                     finishing,
                     jobpred,
                     jobsucc,
                     macpred,
                     macsucc,
                     MKSP_GUESS,
                     machine_sched,
                     actrelease,
                     releases,
                     tails,
                     moddeadline,
                     actdeadline,
                     processing_time,
                     operations,
                     pdc,
                     scs,
                     LIST,
                     POS,
                     machine_total,
                     labelled_list,
                     0);
 
   if (mksp < best_makespan) {
     best_makespan = mksp ; 
     iter_without_imprv = 0 ; 
   }
   else { iter_without_imprv++ ; }
   if (iter_without_imprv > max_iter_no_imprv) {
/*
     printf("Change method , current method = %ld , best upper bound %ld\n",
            method,best_makespan) ; 
*/

     iter_without_imprv = 0 ; 
     method++ ; 
     if (method > MAX_METHODS) method = 0 ;
   }

#ifdef ALL_RESULTS
 printf("MWKR Makespan = %ld \n",mksp) ;  
#endif

 }
 
 printf("Best Makespan = %ld \n",best_makespan) ; 

/* STOPTIME(1) ;  */
 printf("Number of Runs = %ld \n",run_it) ; 
/* printf("Cpu time in seconds = %f\n",(((double) (USERTIME(1))) / 1000.0)) ;
*/
 

}