#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Sorting criteria */
#define START_TIME 0
#define END_TIME 1
#define INT_LENGTH 2
#define CONFLICT_CNT 3

/* Parameters for generation of random intervals */
#define MAX_START 1000
#define MAX_LENGTH 100

typedef struct {
   unsigned int start; /* the left end */
   unsigned int end;   /* the right end */
   unsigned int nc;    /* number of conflicts, may be stored externally */
} interval;

/* Randomly generate n intervals, and return the list so produced */
interval *genIntervals ( unsigned int n )
{
   interval *A;
   unsigned i, j;

   if (n == 0) return NULL;
   A = (interval *)malloc(n * sizeof(interval));
   for (i=0; i<n; ++i) {
      A[i].start = rand() % MAX_START;
      A[i].end = A[i].start + 1 + rand() % MAX_LENGTH;

      /* Locate the conflicts with the intervals generated so far */
      A[i].nc = 0;
      for (j=0; j<i; ++j) {
         if ((A[j].start < A[i].end) && (A[j].end > A[i].start)) {
            ++(A[i].nc); ++(A[j].nc);
         }
      }
   }
   return A;
}

/* Linear-time merge function. flag indicates with respect to what we want
   to sort. */
void merge ( interval *A1, unsigned int n1, interval *A2, unsigned int n2, int flag )
{
   int i1, i2, i;
   interval *B;

   B = (interval *)malloc((n1+n2) * sizeof(interval));
   i1 = i2 = i = 0;

   if (flag == START_TIME) {
      while ((i1 < n1) || (i2 < n2)) {
         if (i1 >= n1) B[i++] = A2[i2++];
         else if (i2 >= n2) B[i++] = A1[i1++];
         else if (A1[i1].start <= A2[i2].start) B[i++] = A1[i1++];
         else B[i++] = A2[i2++];
      }
   } else if (flag == END_TIME) {
      while ((i1 < n1) || (i2 < n2)) {
         if (i1 >= n1) B[i++] = A2[i2++];
         else if (i2 >= n2) B[i++] = A1[i1++];
         else if (A1[i1].end <= A2[i2].end) B[i++] = A1[i1++];
         else B[i++] = A2[i2++];
      }
   } else if (flag == INT_LENGTH) {
      while ((i1 < n1) || (i2 < n2)) {
         if (i1 >= n1) B[i++] = A2[i2++];
         else if (i2 >= n2) B[i++] = A1[i1++];
         else if ((A1[i1].end - A1[i1].start) <= (A2[i2].end - A2[i2].start)) B[i++] = A1[i1++];
         else B[i++] = A2[i2++];
      }
   } else if (flag == CONFLICT_CNT) {
      while ((i1 < n1) || (i2 < n2)) {
         if (i1 >= n1) B[i++] = A2[i2++];
         else if (i2 >= n2) B[i++] = A1[i1++];
         else if (A1[i1].nc <= A2[i2].nc) B[i++] = A1[i1++];
         else B[i++] = A2[i2++];
      }
   } else {
      fprintf(stderr, "*** Error in merge(): Unknown sorting criterion\n");
      free(B);
      exit(1);
   }

   for (i=0; i<n1+n2; ++i) A1[i] = B[i];
   free(B);
}

/* Recursive merge function */
void mergeSort ( interval *A, unsigned int n, int flag )
{
   unsigned int n1, n2;

   if (n <= 1) return;
   n1 = (n >> 1); n2 = n - n1;
   mergeSort(A,n1,flag);
   mergeSort(A+n1,n2,flag);
   merge(A,n1,A+n1,n2,flag);
}

/* Print the list of intervals in the format
   [left_end, right_end](no_of_conflicts) for each */
void printIntervals ( interval *A, unsigned int n )
{
   int i;

   for (i=0; i<n; ++i) {
      printf("[%4u,%4u](%2u) ", A[i].start, A[i].end, A[i].nc);
      if (i % 5 == 4) printf("\n");
   }
   if (i % 5) printf("\n");
}

/* This is the scheduler function. flag indicates what scheduling policy we
   plan to follow. */
void schedule ( interval *A, unsigned int n, int flag )
{
   unsigned i, j, k, util;
   interval *S;

   if (n == 0) return;

   /* S will store the scheduled intervals. Its maximum size will be n. */
   S = (interval *)malloc(n * sizeof(interval));

   /* Always schedule the first interval */
   S[0] = A[0]; i = j = 1;

   if ((flag == START_TIME) || (flag == END_TIME)) {
      while (1) {
         /* Find the first compatible interval after A[i] */
         while ((i < n) && (A[i].start < S[j-1].end)) ++i;

         /* Break if no remaining intervals are compatible */
         if (i >= n) break;

         /* Otherwise store the first compatible interval and continue */
         S[j++] = A[i++];
      }
   } else if ((flag == INT_LENGTH) || (flag == CONFLICT_CNT)) {
      while (1) {
         if (i >= n) break;

         /* Find out whether A[i] has a conflict with any of the intervals
           selected so far */
         k = 0;
         while (k < j) {
            if ((A[i].start >= S[k].end) || (A[i].end <= S[k].start)) ++k;
            else break;
         }

         /* In case no conflicts are found, include A[i] in S */
         if (k == j) S[j++] = A[i];

         /* Increment i in any case */
         ++i;
      }
   } else {
      fprintf(stderr, "*** Error in schedule(): Unknown sorting criterion\n");
      free(S);
      exit(2);
   }

   printf("--- Total number of intervals selected = %u\n", j);
   printIntervals(S,j);

   /* Simple loop to compute the total utilization by the intervals in S */
   util= 0; for (i=0; i<j; ++i) util += (S[i].end - S[i].start);
   printf("Total utilization = %u\n", util);

   /* Clean memory before leaving */
   free(S);
}

int main ( int argc, char *argv[] )
{
   unsigned int n;
   interval *A;

   srand((unsigned int)time(NULL));
   if (argc > 1) n = atoi(argv[1]); else scanf("%u",&n);
   A = genIntervals(n); printIntervals(A,n);

   printf("\n+++ Schedule 1: Earliest start time first\n");
   mergeSort(A,n,START_TIME); printIntervals(A,n);
   schedule(A,n,START_TIME);

   printf("\n+++ Schedule 2: Earliest finish time first\n");
   mergeSort(A,n,END_TIME); printIntervals(A,n);
   schedule(A,n,END_TIME);

   printf("\n+++ Schedule 3: Shortest first\n");
   mergeSort(A,n,INT_LENGTH); printIntervals(A,n);
   schedule(A,n,INT_LENGTH);

   printf("\n+++ Schedule 4: Least conflict first\n");
   mergeSort(A,n,CONFLICT_CNT); printIntervals(A,n);
   schedule(A,n,CONFLICT_CNT);

   exit(0);
}