/*
 * Copyright (c) 1996 Tomi Pasanen <tpasanen@cs.utu.fi>
 * All rights reserved.
 */

#include <stdio.h>
#include <stdlib.h>
#include "defmerge.h"

/*********************************************************************
 */
void merge_f(TYPE X[], int m, int n, TYPE B[], int (*f)(TYPE *, TYPE *))
{
  int k = 0, i = 0, j = m;
  
  while (k < m && j < (m + n)) {
    add_comparisons(1);
    add_assignments(1);
    if (f(&X[ k ], &X[ j ]) <= 0)   /* X[k]<=X[j]) */
      B[ i++ ] = X[ k++ ];
    else
      B[ i++ ] = X[ j++ ];
  }
  
  if (j >= (m + n)) {
    while (k < m) {
      add_assignments(1);
      B[ i++ ] = X[ k++ ];
    }
  }
  else {
    while (j < (m + n)) {
      add_assignments(1);
      B[ i++ ] = X[ j++ ];
    }
  }

}


/*********************************************************************
 * Non-recursive merge sort
 */
void mergesort_f(TYPE A[], int left, int rigth, int (*f)(TYPE *, TYPE *))
{
  int i, cursor, left1, rigth1, left2, rigth2,
  nelements = rigth - left + 1,
  size = 1,
  runs = nelements / size + ((nelements % size) ? 1 : 0),
  in_original = 1;
  TYPE *B, *T;

  B = (TYPE *)malloc(nelements*sizeof(TYPE));
  if (B == NULL) {
    printf("Out of memory?\n");
    exit(1);
  }
  while (size < nelements) {
    cursor = left;
    for (i = 1; i <= (runs / 2); ++i) {
      left1 = cursor;
      left2 = left1 + size;
      rigth1 = left2 - 1;
      rigth2 = (((rigth1 + size) > rigth) ? rigth : rigth1 + size);
      merge_f(&A[ cursor ], rigth1 - left1 + 1, rigth2 - left2 + 1, &B[ cursor ], f);
      cursor += (rigth2 - left1 + 1);
    }
    if ((runs % 2) == 1) {
      add_assignments((rigth - cursor + 1)); 
      for (i = cursor; i <= rigth; ++i)
	B[ i ] = A[ i ];
    }

    /* let's switch the merging areas */
    in_original = (in_original + 1) % 2;
    T = A;
    A = B;
    B = T;
    
    size = size << 1;
    runs = nelements / size + ((nelements % size) ? 1: 0);
  }

  if (in_original == 0) { /* if items are in B */
    add_assignments(nelements); 
    for (i = left; i <= rigth; ++i)
      B[ i ] = A[ i ];
  }
  A = B;
}