/* ----------------- */
/* --- nrsort1.c --- */
/* ----------------- */

/*
 * Copyright (c) 2000-2014, Lionel Lacassagne, All rights reserved
 * Univ Paris Sud XI, CNRS
 *
 * Distributed under the Boost Software License, Version 1.0
 * see accompanying file LICENSE.txt or copy it at
 * http://www.boost.org/LICENSE_1_0.txt
 */


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

#include "mypredef.h"
#include "nrtype.h"
#include "nrdef.h"
#include "nrmacro.h"
#include "nrkernel.h"

#include "nrset1.h"
#include "nrsort1.h"


#undef extractnz_boundaries_type_vector
#define extractnz_boundaries_type_vector(t) \
void short_name(t,extractnz_boundaries_,vector)(t * v, int32_t nl, int32_t nh, int32_t * nlnz, int32_t * nhnz) \
{                                      \
    int32_t left = nl;                 \
    int32_t right = nh;                \
    while (!v[left] && left <= nh) {   \
        left++;                        \
    }                                  \
    while (!v[right] && right >= nl) { \
        right--;                       \
    }                                  \
    *nlnz = left;                      \
    *nhnz = right;                     \
}


extractnz_boundaries_type_vector(int8_t);
extractnz_boundaries_type_vector(uint8_t);
extractnz_boundaries_type_vector(int16_t);
extractnz_boundaries_type_vector(uint16_t);
extractnz_boundaries_type_vector(int32_t);
extractnz_boundaries_type_vector(uint32_t);
extractnz_boundaries_type_vector(int64_t);
extractnz_boundaries_type_vector(uint64_t);
extractnz_boundaries_type_vector(float);
extractnz_boundaries_type_vector(double);



void sort_index_f64vector_selection(double * key, int32_t nl, int32_t nh, int32_t * index)
{
    int32_t pos, tmp;
    double x, min;

    for (int32_t i = nl; i<=nh; i++) {
        index[i] = i - nl;
    }

    for (int32_t i = nl; i < nh; i++) {
        min = key[i];
        pos = i;
        for (int32_t j = i + 1; j <= nh; j++) {
            x = key[j];
            if (x < min) {
                min = x;
                pos = j;
            }
        }
        key[pos] = key[i];
        key[i]   = min;

        tmp        = index[i];
        index[i]   = index[pos];
        index[pos] = tmp;
    }
}

void sort_index_ivector_selection_min(int32_t * key, int32_t nl, int32_t nh, int32_t * index)
{
    int32_t pos, tmp;
    int32_t x, min;

    for (int32_t i = nl; i <= nh; i++) {
        index[i] = i;
    }

    for (int32_t i = nl; i < nh; i++) {
        min = key[i];
        pos = i;
        for (int32_t j = i + 1; j <= nh; j++) {
            x = key[j];
            if (x < min) {
                min = x;
                pos = j;
            }
        }
        key[pos] = key[i];
        key[i]   = min;

        tmp        = index[i];
        index[i]   = index[pos];
        index[pos] = tmp;
    }
}

void sort_index_ivector_selection_max(int32_t * key, int32_t nl, int32_t nh, int32_t * index)
{
    int32_t pos, tmp;
    int32_t x, max;

    for (int32_t i = nl; i <= nh; i++) {
        index[i] = i;
    }

    for (int32_t i = nl; i < nh; i++) {
        max = key[i];
        pos = i;
        for (int32_t j = i + 1; j <= nh; j++) {
            x = key[j];
            if (x > max) {
                max = x;
                pos = j;
            }
        }
        key[pos] = key[i];
        key[i]   = max;

        tmp        = index[i];
        index[i]   = index[pos];
        index[pos] = tmp;
    }
}

void sort_index_vector_selection_min(float * key, int32_t nl, int32_t nh, int32_t * index)
{
    int32_t pos, tmp;
    float x, min;

    for (int32_t i = nl; i <= nh; i++) {
        index[i] = i;
    }

    for (int32_t i = nl; i < nh; i++) {
        min = key[i];
        pos = i;
        for (int32_t j = i + 1; j <= nh; j++) {
            x = key[j];
            if (x < min) {
                min = x;
                pos = j;
            }
        }
        key[pos] = key[i];
        key[i]   = min;

        tmp        = index[i];
        index[i]   = index[pos];
        index[pos] = tmp;
    }
}

void sort_index_vector_selection_max(float * key, int32_t nl, int32_t nh, int32_t * index)
{
    int32_t pos, tmp;
    float x, max;

    for (int32_t i = nl; i <= nh; i++) {
        index[i] = i;
    }

    for (int32_t i = nl; i < nh; i++) {
        max = key[i];
        pos = i;
        for (int32_t j = i + 1; j <= nh; j++) {
            x = key[j];
            if (x > max) {
                max = x;
                pos = j;
            }
        }
        key[pos] = key[i];
        key[i]   = max;

        tmp        = index[i];
        index[i]   = index[pos];
        index[pos] = tmp;
    }
}

void sort_index_vector_selection_kmin(float * key, int32_t nl, int32_t nh, int32_t * index, int32_t k)
{
    /*
     * ATTENTION, le tableau index DOIT etre initialise
     * @QM : pourquoi est-ce commenté alors ?
     */
    int32_t pos, tmp, il, ih;
    float x, min;

    il = nl;
    ih = il + k;

    /*
    for(int32_t i = il; i <= ih; i++) {
        index[i] = i - il;
    }
    */

    for (int32_t i = il; i < ih; i++) {
        min = key[i];
        pos = i;
        for (int32_t j = i + 1; j <= nh; j++) {
            x = key[j];
            if (x < min) {
                min = x;
                pos = j;
            }
        }
        key[pos] = key[i];
        key[i]   = min;

        tmp        = index[i];
        index[i]   = index[pos];
        index[pos] = tmp;
    }
}

void sort_index_ivector_selection_kmin(int32_t * key, int32_t nl, int32_t nh, int32_t * index, int32_t k)
{
    /*
     * ATTENTION, le tableau index DOIT etre initialise
     */
    int32_t pos, tmp, il, ih;
    int32_t x, min;

    il = nl;
    ih = il + k;

    /*
    for(int32_t i = il; i <= ih; i++) {
        index[i] = i - il;
    }
    */

    for (int32_t i = il; i < ih; i++) {
        min = key[i];
        pos = i;
        for (int32_t j = i + 1; j <= nh; j++) {
            x = key[j];
            if (x < min) {
                min = x;
                pos = j;
            }
        }
        key[pos] = key[i];
        key[i]   = min;

        tmp        = index[i];
        index[i]   = index[pos];
        index[pos] = tmp;
    }
}

void sort_index_vector_selection_kmax(float * key, int32_t nl, int32_t nh, int32_t * index, int32_t k)
{
    /*
     * ATTENTION, le tableau index DOIT etre initialise
     */
    int32_t pos, tmp, il, ih;
    float x, max;

    il = nl;
    ih = il + k;

    /*
    for (int32_t i = il; i <= ih; i++) {
        index[i] = i - il;
    }
    */

    for (int32_t i = il; i < ih; i++) {
        max = key[i];
        pos = i;
        for (int32_t j = i + 1; j <= nh; j++) {
            x = key[j];
            if (x > max) {
                max = x;
                pos = j;
            }
        }
        key[pos] = key[i];
        key[i]   = max;

        tmp        = index[i];
        index[i]   = index[pos];
        index[pos] = tmp;
    }
}

void sort_index_ivector_selection_kmax(int32_t * key, int32_t nl, int32_t nh, int32_t * index, int32_t k)
{
    /*
     * ATTENTION, le tableau index DOIT etre initialise
     */
    int32_t pos, tmp, il, ih;
    int32_t x, max;

    il = nl;
    ih = il + k;

    /*
    for (int32_t i = i l; i <= ih; i++) {
        index[i] = i - il;
    }
    */

    for (int32_t i = il; i < ih; i++) {
        max = key[i];
        pos = i;
        for (int32_t j = i + 1; j <= nh; j++) {
            x = key[j];
            if (x > max) {
                max = x;
                pos = j;
            }
        }
        key[pos] = key[i];
        key[i]   = max;

        tmp        = index[i];
        index[i]   = index[pos];
        index[pos] = tmp;
    }
}


void sort_bvector_selection_min(int8_t * v, int32_t nl, int32_t nh)
{
    int8_t x, min;
    int32_t pos;

    for (int32_t i = nl; i < nh; i++) {
        min = v[i];
        pos = i;
        for (int32_t j = i + 1; j <= nh; j++) {
            x = v[j];
            if (x < min) {
                min = x;
                pos = j;
            }
        }
        v[pos] = v[i];
        v[i]   = min;
    }
}

int8_t select_bvector(int8_t * v, int32_t nl, int32_t nh, int32_t k)
{
    int32_t il, ih;
    int8_t x, min, pos;

    il = nl;
    ih = il + k;

    for (int32_t i = il; i < ih; i++) {
        min = v[i];
        pos = i;
        for (int32_t j = i + 1; j <= nh; j++) {
            x = v[j];
            if (x < min) {
                min = x;
                pos = j;
            }
        }
        v[pos] = v[i];
        v[i]   = min;
    }
    return v[ih];
}

rgb8 select_rgb8vector(rgb8 * v, int32_t nl, int32_t nh, int32_t k)
{
    int32_t il, ih;
    int32_t rpos, gpos, bpos;

    rgb8 xi, xj;
    int8_t r, g, b;
    int8_t rmin, gmin, bmin;

    il = nl;
    ih = il + k;

    for (int32_t i = il; i < ih; i++) {
        xi = v[i];
        rmin = xi.r;
        gmin = xi.g;
        bmin = xi.b;
        rpos = gpos = bpos = i;

        for (int32_t j = i + 1; j <= nh; j++) {
            xj = v[j];
            r = xj.r;
            g = xj.g;
            b = xj.b;
            if (r < rmin) {
                rmin = r;
                rpos = j;
            }
            if (g < gmin) {
                gmin = r;
                gpos = j;
            }
            if (b < bmin) {
                bmin = r;
                bpos = j;
            }
        }
        v[rpos].r = v[i].r;
        v[i].r = rmin;
        v[rpos].g = v[i].g;
        v[i].g = gmin;
        v[rpos].b = v[i].b;
        v[i].b = bmin;
    }
    return v[ih];
}

// Local Variables:
// tab-width: 4
// c-basic-offset: 4
// c-file-offsets:((innamespace . 0)(inline-open . 0))
// indent-tabs-mode: nil
// End:

// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4