Sunday, December 12, 2010

Schwartzian transform used in a C Program

If you are looking for an in depth explanation of the Schwartzian transform with an example, please refer to my earlier post - Schwartzian Transform Explained

I was getting bored and asked a friend to give me something interesting to code in C. He being who he is, told me to write an implementation of the Schwartzian Transform (henceforth referred to as ST) in C. During the process of writing that program, I realized how Perl makes us focus on the problem at hand rather than the nuances of the language. This post aims provide the source and explain it.

The source is uploaded here - schwartz.c

Now that the (fo|sou)rce is with you, I shall explain the main() function because all the other functions are called from main() and their body is easy to understand once you know their purpose in the main(). Or rather, their main() purpose. :)

int main() {
    emp* emp_ptr_arr[MAXEMP];
    build_emp_list(emp_ptr_arr, MAXEMP);
    print_emp_list(emp_ptr_arr, MAXEMP);
    /* 
      map { [$_, $_->get_salary] } 
      @employees
    */
    store_sal_emp_ds* store_sal_emp_ds_ptr_arr[MAXEMP];
    build_store_sal_emp_ds(emp_ptr_arr, store_sal_emp_ds_ptr_arr, MAXEMP);
    /* 
      sort { $a->[1] &br;=> $b->[1] } 
      map { [$_, $_->get_salary] } 
      @employees
    */
    qsort(store_sal_emp_ds_ptr_arr, MAXEMP, sizeof(store_sal_emp_ds*), salary_comparator);
    /*
      @sorted_emp = map { $_->[0] } 
                    sort { $a->[1] &br;=> $b->[1] } 
                    map { [$_, $_->get_salary] } 
                    @employees
    */
    emp* sorted_emp_ptr_arr[MAXEMP];
    build_emp_list_frm_store_sal_emp_ds(store_sal_emp_ds_ptr_arr, sorted_emp_ptr_arr, MAXEMP);
    printf("----------------------------\n");
    print_emp_list(sorted_emp_ptr_arr, MAXEMP);
    return(0);
}


line 02      : Declare an array which will hold the employees.

line 03-04 : Build a sample dataset for this program and print it.

line 05-10: Build the intermediate data structure which will hold the employee
                instances as well as the salary for each employee. (the one time
                storing part)

line 11-16: Sort the intermediate data structure

line 17-24: Extract what is needed from the intermediate data structure -
                the employee struct instances

line 25-xx: Print the sorted array of employee struct instances.

As you can see, you need a separate function to simulate each cascade of the map-sort-map construct in C. I haven't benchmarked this code against a simple sorting but I think the effort that goes into building the intermediate data structure, sorting it and extracting what is required in the above code would be costlier just sorting the employee instances directly. (Open to speculation)

No comments: