/*-----------------------------------------------------------------------------
 *				HTBLA-Leonding
 *-----------------------------------------------------------------------------
 * Exercise Number: S07
 * Title:			Insertion sort implementation
 * Author:			Marc Tismonar
 *-----------------------------------------------------------------------------
 * Description:
 * Implements the insertion sort algorithm
 *-----------------------------------------------------------------------------
*/

#include "insertion_sort_binary_search.h"
#include "binary_search.h"

/**
 * Sorts the given list according to the insertion sort algorithm using binary.
 * 
 * @param list The list to be sorted.
 * @param criterion The pointer to the function that implements the sorting criterion.
 * That function accepts two integer parameters and returns a boolean value.
 */
void insertion_sort_binsearch_list(IntList list, criterion_fn criterion) {
    if (!list_is_valid(list) || criterion == 0) {
        return;
    }
    
    int size = list_get_size(list);
    if (size <= 1) {
        return;
    }
    
    for (int i = 1; i < size; i++) {
        int current = list_get_at(list, i);
        
        IntList temp = list_obtain();
        for (int k = 0; k < i; k++) {
            list_insert(temp, list_get_at(list, k));
        }
        
        int pos = binary_search_list_limited(temp, i, criterion, current);
        
        if (pos < 0) {
            pos = -pos;
        }
        
        if (pos < i) {
            list_remove_at(list, i);
            list_insert_at(list, pos, current);
        }
        
        list_release(&temp);
    }
}

/**
 * Sorts the given array according to the insertion sort algorithm using binary search.
 * 
 * @param array The array to be sorted.
 * @param length The length of the array.
 * @param criterion The pointer to the function that implements the sorting criterion.
 * That function accepts two integer parameters and returns a boolean value.
 */
void insertion_sort_binsearch_array(int array[], int length, criterion_fn criterion) {

}