/* Copyright (c) 2019, Anthony Latorre <tlatorre at uchicago>
 *
 * This program is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or (at your option)
 * any later version.

 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
 * more details.

 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <https://www.gnu.org/licenses/>.
 */

#include <stdlib.h>
#include "sort.h"

typedef struct fargsort_element {
    double value;
    size_t index;
} fargsort_element;

typedef struct argsort_element {
    int value;
    size_t index;
} argsort_element;

int fargsort_compare(const void *a, const void *b)
{
    const double da = ((fargsort_element *) a)->value;
    const double db = ((fargsort_element *) b)->value;

    return (da > db) - (da < db);
}

int argsort_compare(const void *a, const void *b)
{
    const int da = ((argsort_element *) a)->value;
    const int db = ((argsort_element *) b)->value;

    return (da > db) - (da < db);
}

void fargsort(double *base, size_t num, size_t *index_array)
{
    /* Returns the indices that would sort the array `base`. */
    size_t i;
    fargsort_element *array;

    array = (fargsort_element *) malloc(num*sizeof(fargsort_element));

    for (i = 0; i < num; i++) {
        array[i].value = base[i];
        array[i].index = i;
    }

    qsort(array, num, sizeof(fargsort_element), fargsort_compare);

    for (i = 0; i < num; i++) {
        index_array[i] = array[i].index;
    }

    free(array);
}

void argsort(int *base, size_t num, size_t *index_array)
{
    /* Returns the indices that would sort the array `base`. */
    size_t i;
    argsort_element *array;

    array = (argsort_element *) malloc(num*sizeof(argsort_element));

    for (i = 0; i < num; i++) {
        array[i].value = base[i];
        array[i].index = i;
    }

    qsort(array, num, sizeof(argsort_element), argsort_compare);

    for (i = 0; i < num; i++) {
        index_array[i] = array[i].index;
    }

    free(array);
}