/*  Header file for Math 3012:  Applied Combinatorics  

    Updated:  January 25, 2007            */

/*  Declarations   */

int test_reflexive(int **P, int n);
int test_antisymmetric(int **P, int n);
int test_transitive(int **P, int n);
int test_poset (int **P, int n);
void create_linear_ext(int **P, int *L, int n);
int test_intorder (int **P, int n);
int minimal_interval_rep(int **P, int *LEP, int *REP, int n);
void sort_segment(int *s, int i1, int i2);
void sort_labels_by_weights(int *s, int *w, int i1, int i2);
void merge_segments(int *s, int i1, int i2, int i3);
void merge_segments_by_weights(int *s, int *w, int i1, int i2, int i3);

/*  Definitions  */

int test_reflexive(int **P, int n) {
  int i;
  for (i = 1; i <= n; i++) {
    if (P[i][i] != 1) {
      return(0);
    }
  }
  return(1);
}

int test_antisymmetric(int **P, int n) {
  int i, j;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      if ((i != j) && (P[i][j] == 1) && (P[j][i] == 1)) {
        return(0);
      }
    }
  }
  return(1);
}

int test_transitive(int **P, int n) {
  int i, j,k;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      for (k = 1; k <= n; k++) {
        if ((P[i][j] == 1) && (P[j][k] == 1) && (P[i][k] == 0)) {
          return(0);
        }
      }
    }
  }
  return(1);
}

int test_poset(int **P, int n) {
  return((test_reflexive(P,n))*(test_antisymmetric(P,n))*(test_transitive(P,n)));
}

void create_linear_ext(int **P, int *L, int n) {
  int i,j,k;

  int no_remaining;
  int no_minimals;
  int *R;         /*  array of elements not yet inserted  */
  int *Save_R;         /*  dummy array to store R  */
  int *M;         /*  indicates whether entry is minimal  */
  
  R = (int *)malloc((n+2)*sizeof(int));
  if (R == NULL) {
    printf("Failed to allocate memory for R.\n");
    exit(1);
  }

  Save_R = (int *)malloc((n+2)*sizeof(int));
  if (Save_R == NULL) {
    printf("Failed to allocate memory for Save_R.\n");
    exit(1);
  }

  M = (int *)malloc((n+2)*sizeof(int));
  if (M == NULL) {
    printf("Failed to allocate memory for M.\n");
    exit(1);
  }

  for (i = 0; i <= n; i++) {
    R[i] = i;
    Save_R[i] = i; 
    M[i] = 1;
  }

  no_remaining = n;
   
  while (no_remaining >= 1) {
      
    no_minimals = 0;
    for (i = 1; i <= no_remaining; i++) {
      M[i] = 1;
      for (j = 1; j <= no_remaining; j++) {
      
        if ((i != j) && (P[R[j]][R[i]] == 1)) { 
          M[i] = 0;
          // j = no_remaining;
        }
      }
      if (M[i] == 1) {
        no_minimals++;
        L[n-no_remaining+no_minimals] = R[i];
      }
    }
    j = 0;
    for (i = 1; i <= no_remaining; i++) {  
      if (M[i] == 0) {
        j++;
        R[j] = Save_R[i];
      }
    }
    no_remaining = no_remaining- no_minimals; 
    for (i = 1; i <= no_remaining; i++) {  
      Save_R[i] = R[i];
    } 
  }
}

int test_intorder (int **P, int n) {

  /*  return 0 if no and 1 if yes  */ 

  int i,j,k; 
  int below_i, below_j;

  for (i = 1; i < n; i++) {
    for (j = i+1; j <= n; j++) {
      below_i = 0;
      below_j = 0;
      for (k = 1; k <= n; k++) {
        if ((k != i) && (P[k][i] == 1) && (P[k][j] == 0)) {
          below_i = k;
        }
        if ((k != j) && (P[k][j] == 1) && (P[k][i] == 0)) {
          below_j = k;
        }
      }
      if(below_i != 0 && below_j != 0) {
        return(0);
      }
    }
  }
  return(1);
}

int minimal_interval_rep(int **P, int *LEP, int *REP, int n) {

  int i,j,k; 

  int no_endpoints;   /*  integer end points of representation  */
  int downset_size;  
  int upset_size;   
  int save_int;   
  int below_i;
  int below_j;
  int good_so_far;


  int *D;     /*  Counts the size of the down sets */
  int *U;     /*  Counts the size of the up sets */
  int *L;     /*  Used to store D and U  */
  int *sizeof_downset;  
  int *sizeof_upset;

  D = (int *) malloc((n+1)*sizeof(int));

  if (D == NULL) {
    printf("Unable to allocate memory for D.\n");
    exit(1);
  }

  U = (int *) malloc((n+1)*sizeof(int));

  if (U == NULL) {
    printf("Unable to allocate memory for U.\n");
    exit(1);
  }

  L = (int *) malloc((n+1)*sizeof(int));

  if (L == NULL) {
    printf("Unable to allocate memory for L.\n");
    exit(1);
  }

  sizeof_downset = (int *) malloc((n+1)*sizeof(int));

  if (sizeof_downset == NULL) {
    printf("Unable to allocate memory for sizeof_downset.\n");
    exit(1);
  }

  sizeof_upset = (int *) malloc((n+1)*sizeof(int));

  if (sizeof_upset == NULL) {
    printf("Unable to allocate memory for sizeof_upset.\n");
    exit(1);
  }

  for (i = 1; i <= n; i++) {
    D[i] = 0;
    U[i] = 0;
  }

  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      if (i != j && P[i][j] == 1) { 
        U[i] = 1 + U[i];
        D[j] = 1 + D[j];
      }
    }
  } 

  for (i = 1; i <= n; i++) {
    L[i] = D[i];
  }

  sort_segment(L, 1, n); 
 
  no_endpoints = 1;
  downset_size = 0;
  sizeof_downset[1] = 0;

  for(i = 2; i <= n; i++) {
    if(L[i] > downset_size) {
      downset_size = L[i];
      no_endpoints++;
      sizeof_downset[no_endpoints] = downset_size;
    }
  }

  for (i = 1; i <= n; i++) {
    L[i] = U[i];
  }

  sort_segment(L, 1, n); 

  upset_size = 0;
  sizeof_upset[1]=0;
  no_endpoints = 1;

  for(i = 1; i <= n; i++) {
    if(L[i] > upset_size) {
      upset_size = L[i];
      no_endpoints++;
      sizeof_upset[no_endpoints] = upset_size;
    }
  }
  
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= no_endpoints; j++) {
      if(D[i] == sizeof_downset[j]) {
         LEP[i] = j;
      }
      if(U[i] == sizeof_upset[j]) {
         REP[i] = no_endpoints+1-j;
      }
    }
  }
  return(no_endpoints);
}

void sort_segment(int *s, int i1, int i2) {
  int j1, j2, j3;
  int k;
  if (i1 < 0 || i1 > i2) {
    printf("Error: Bad values for sort_segment call.\n");
    exit(1);
  }
  if (i1 == i2) {
    return;
  } 
  else {
    k = (i1 + i2)/2;
    sort_segment(s, i1, k);
    sort_segment(s, k+1, i2);
    merge_segments(s, i1, k, i2);
  }
}
  
void sort_labels_by_weights(int *s, int *w, int i1, int i2) {
  int j1, j2, j3;
  int k;
  if (i1 < 0 || i1 > i2) {
    printf("Error 0: Bad values for sort_labels_by_weights call.\n");
    exit(1);
  }
  if (i1 == i2) {
    return;
  } 
  else {
    k = (i1 + i2)/2;
    sort_labels_by_weights(s, w, i1, k);
    sort_labels_by_weights(s, w, k+1, i2);
    merge_segments_by_weights(s, w, i1, k, i2);
  }
}

void merge_segments(int *s, int i1, int i2, int i3) {
  int j1 = i1;
  int j2 = i2 + 1;
  int j3 = 0; 


  long* temp_s = malloc(5+sizeof(long)*(i3-i1));
  while ((j1 <=  i2)  && (j2 <= i3)) {
    if (s[j1] <= s[j2]) {
      temp_s[j3++] = s[j1++];
    }
    else { 
      temp_s[j3++] = s[j2++];
    }
  }
  while (j1 <= i2) {
    temp_s[j3++] = s[j1++];
  }
  while (j2 <= i3) {
    temp_s[j3++] = s[j2++];
  }
  for (j3 = 0; j3 <= i3 - i1; j3++) {
    s[i1+j3] = temp_s[j3];
  }
  free(temp_s);
  return;
}

void merge_segments_by_weights(int *s, int *w, int i1, int i2, int i3) {
  int j1 = i1;
  int j2 = i2 + 1;
  int j3 = 0;

  long* temp_s = malloc(5+sizeof(long)*(i3-i1));
  while ((j1 <=  i2)  && (j2 <= i3)) {
    if (w[s[j1]] <= w[s[j2]]) {
      temp_s[j3++] = s[j1++];
    }
    else {
      temp_s[j3++] = s[j2++];
    }
  }
  while (j1 <= i2) {
    temp_s[j3++] = s[j1++];
  }
  while (j2 <= i3) {
    temp_s[j3++] = s[j2++];
  }
  for (j3 = 0; j3 <= i3 - i1; j3++) {
    s[i1+j3] = temp_s[j3];
  }
  free(temp_s);
  return;
}