HT_TANGXONG.C

HT_TANGXONG.C

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

// Compile: 
// Cross compile on Linux:
// open-watcom.owcc-dos -bdos -o HT_HEART.EXE HT_TANGXONG.C
// On openwatcom on DOS:
// wcl386 HT_TANGXONG.C

void addToSortedArray(int * arr_len, int *arr, int el) {
    int lower, upper, guess;
    int i;
    if (*arr_len == 0 || el < arr[0]) {
        //printf("Add %d at beginning\n", el);
        for (i = *arr_len; i > 0; i--) {
            arr[i] = arr[i-1];
        }
        arr[0] = el;
        *arr_len = (*arr_len)+1;
        return;
    }
    
    if (el > arr[(*arr_len) - 1]) {
        //printf("Add %d at end\n", el);
        arr[(*arr_len)] = el;
        *arr_len = (*arr_len)+1;
        return;
    }
    
    lower = 0;
    upper = (*arr_len);
    guess = (lower + upper)  / 2;
    //printf("Guess = %d val = %d\n", guess, arr[guess]);
    
    while (! ( el >= arr[guess] && el <= arr[guess + 1] )) {
        if (el < arr[guess]) {
            upper = guess;
        } else {
            lower = guess;
        }
        guess = (lower + upper)  / 2;
        //printf("Guess = %d val = %d\n", guess, arr[guess]);
    }
    
    guess++;
    
    //printf("Add %d at position %d\n", el, guess);
        
    for (i = *arr_len; i > guess; i--) {
        arr[i] = arr[i-1];
    }
    
    arr[guess] =  el;
    
    (*arr_len)++;
    
    return;
}

void removeOnce(int * arr_len, int *arr, int el) {
    int lower, upper, guess;
    int i;
    
    lower = 0;
    upper = (*arr_len);
    guess = (lower + upper)  / 2;
    //printf("Guess = %d val = %d\n", guess, arr[guess]);
    
    while ( arr[guess] != el ) {
        if (arr[guess] > el) {
            upper = guess;
        } else {
            lower = guess;
        }
        guess = (lower + upper)  / 2;
        //printf("Guess = %d val = %d\n", guess, arr[guess]);
    }
    
    //printf("Remove %d at position %d val = %d\n", el, guess, arr[guess]);
    
    for (i = guess; i < *arr_len - 1; i++) {
        arr[i] = arr[i+1];
    }
    * arr_len = * arr_len  - 1;
}

int twiceMedian(int c, int*m) {
    if (c % 2 == 1) {
        return 2 * m[ (c-1) /2 ];
    } else {
        return m [ c / 2] + m [ c / 2 - 1 ];
    }
}

void print_arr(int arr_len, int * arr) {
    int i;
    printf("Array dump [%2d]: ", arr_len);
    for (i = 0 ; i < arr_len; i++) {
        printf("[%2d] %2d  ", i, arr[i]);
    }
    printf("\n");
}

int test() {
    
  
  
  int test_arr[]  = { 0, 55, 82, 168, 180 };
  int test_arr_len = 5;
  
  print_arr(test_arr_len, test_arr);
  addToSortedArray(&test_arr_len, test_arr, 41);
  print_arr(test_arr_len, test_arr);
  return 0;
  
  
  print_arr(test_arr_len, test_arr);
  
  removeOnce(&test_arr_len, test_arr, 12);
  
  print_arr(test_arr_len, test_arr);
  
  addToSortedArray(&test_arr_len, test_arr, 15);
  
  print_arr(test_arr_len, test_arr);
  
  addToSortedArray(&test_arr_len, test_arr, 22);
  
  print_arr(test_arr_len, test_arr);
  
  addToSortedArray(&test_arr_len, test_arr, 0);
  
  print_arr(test_arr_len, test_arr);
  
  removeOnce(&test_arr_len, test_arr, 0);
  
  print_arr(test_arr_len, test_arr);
  
  removeOnce(&test_arr_len, test_arr, 22);
  
  print_arr(test_arr_len, test_arr);
  
  removeOnce(&test_arr_len, test_arr, 10);
  
  print_arr(test_arr_len, test_arr);
  
  removeOnce(&test_arr_len, test_arr, 20);
  print_arr(test_arr_len, test_arr);
  
  removeOnce(&test_arr_len, test_arr, 8);
  print_arr(test_arr_len, test_arr);
  
  removeOnce(&test_arr_len, test_arr, 2);
  print_arr(test_arr_len, test_arr);
  
  return 0 ;
}

int tangXongCount(int measurement_count, int* measurement, int d) {
  int * lookback;
  int lookback_len;
  int ret;
  int i, j;
  
  
  ret = 0;
  lookback_len = 0;

  lookback = (int*)(malloc(d * sizeof(int)));
  
  for (i = 0 ; i < d;  i++) {
      addToSortedArray(&lookback_len, lookback, measurement[i]);
  }
  
  for (i = d; i < measurement_count; i++) {
      if (measurement[i] >= twiceMedian(d, lookback)) {
          ret ++;
      }
      removeOnce(&lookback_len, lookback, measurement[i - d]);
      addToSortedArray(&lookback_len, lookback, measurement[i]);
  }
  
  return ret;
}




int main(int argc, char *argv[])
{
    
    FILE *fptr = NULL;
    int measurement_count;
    int d;
    int* measurement;   
    int i;    
    int result;
    
    if (argc <= 1) {
        printf("Usage: %s INPUT.TXT\n", argv[0]);
        printf("INPUT is the input sequence\n");
        exit(EXIT_FAILURE);
    }
 
    fptr = fopen(argv[1], "r");
    
    fscanf(fptr, "%d", &measurement_count);
    fscanf(fptr, "%d", &d);
    
    measurement = (int*) malloc(measurement_count * sizeof(int));

    for (i = 0; i < measurement_count; i++) {
        fscanf(fptr, "%d", measurement + i);
    }

    result = tangXongCount(measurement_count, measurement, d);

    printf("%d\n", result);

    fclose(fptr);

    return 0;
}