/* ----------------- */
/* --- nrsort2.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 "nrset2.h"

#include "nrsort1.h"
#include "nrsort2.h"


#undef extractnz_boundaries_type_matrix
#define extractnz_boundaries_type_matrix(t) \
void short_name(t,extractnz_boundaries_,matrix)(t ** m, int32_t nrl, int32_t nrh, int32_t ncl, int32_t nch, int32_t * nclnz, int32_t * nchnz) \
{                                                                                                         \
    int32_t a, b;                                                                                         \
    int32_t left, right;                                                                                  \
    short_name(t,extractnz_boundaries_,vector)(m[nrl], ncl, nch, &left, &right); /* premier intervalle */ \
    for (int32_t i = nrl + 1; i <= nrh; i++) {                                                            \
        short_name(t,extractnz_boundaries_,vector)(m[i], ncl, nch, &a, &b);                               \
        if (a < left) {                                                                                   \
            left = a; /* agrandissement de l'intervalle SI necessaire (et non le contraire) */            \
        }                                                                                                 \
        if (b > right) {                                                                                  \
            right = b;                                                                                    \
        }                                                                                                 \
    }                                                                                                     \
    *nclnz = left;                                                                                        \
    *nchnz = right;                                                                                       \
}

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



void sort_si32matrix_selection2(int32_t ** m, int32_t nl, int32_t nh)
{
    /*
     * sort an matrix of int32_t with the selection algorithm
     * the key is supposed to be in row 1
     * the flag associated, in row 0
     */
    int32_t x, min, pos, tmp;

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

        tmp       = m[0][i];
        m[0][i]   = m[0][pos];
        m[0][pos] = tmp;
    }
}

void sort_si32matrix_leftpart_selection2(int32_t ** m, int32_t nl, int32_t nh, int32_t len)
{
    /*
     * sort an matrix of int32_t with the selection algorithm
     * the key is supposed to be in row 1
     * the flag associated, in row 0
     * the sort is performed only on the len first items
     * for selecting the len first smallest values (for Tracking algo)
     */
    int32_t x, min, pos, tmp;
    int32_t ih = nl + len - 1;
    int32_t * X;
    int32_t * F;

    F = m[0];
    X = m[1];

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

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

void sort_f64matrix_selection(double * m, int32_t nl, int32_t nh)
{
    int32_t pos;
    float64 x, min;

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

void sort_si32matrix_selection(int32_t ** m, int32_t nrl, int32_t nrh, int32_t ncl, int32_t nch, int32_t nrow)
{
    /*
     * sort an matrix of int32_t with the selection algorithm
     * the key is supposed to be in row nrow
     */
    int32_t x, min, pos, tmp;

    for (int32_t i = ncl; i < nch; i++) {
        min = m[nrow][i];
        pos = i;
        for (int32_t j = i + 1; j <= nch; j++) {
            x = m[nrow][j];
            if (x < min) {
                min = x;
                pos = j;
            }
        }

        // big swap
        for (int32_t k = nrl; k <= nrh; k++) {
            tmp = m[k][i];
            m[k][i] = m[k][pos];
            m[k][pos] = tmp;
        }
    }
}

void sortv_si32matrix_selection_min(int32_t ** m, int32_t nrl, int32_t nrh, int32_t ncl, int32_t nch, int32_t nc)
{
    /*
     * sort an matrix of int, with the selection algorithm.
     * the key is in column nc
     * the sort is performed, by doing a purmutation on the lines,
     * instead of copying the lines.
     */

    int32_t x, min, pos;
    int32_t * ptr;

    for (int32_t i = nrl; i < nrh; i++) {
        min = m[i][nc];
        pos = i;
        for (int32_t j = i + 1; j <= nrh; j++) {
            x = m[j][nc];
            if (x < min) {
                min = x;
                pos = j;
            }
        }

        /* permutation des pointeurs de ligne de la matrice */
        ptr    = m[i];
        m[i]   = m[pos];
        m[pos] = ptr;
    }
}

void sortv_si32matrix_selection_kmin(int32_t ** m, int32_t nrl, int32_t nrh, int32_t ncl, int32_t nch, int32_t nc, int32_t k)
{
    /*
     * sort an matrix of int, with the selection algorithm.
     * the key is in column nc
     * the sort is performed, by doing a purmutation on the lines,
     * instead of copying the lines.
     */
    int32_t il = nrl;
    int32_t ih = nrl + k;

    int32_t x, min, pos;
    int32_t * ptr;

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

        /* permutation des pointeurs de ligne de la matrice */
        ptr    = m[i];
        m[i]   = m[pos];
        m[pos] = ptr;

    }
}

void sortv_si32matrix_selection_max(int32_t ** m, int32_t nrl, int32_t nrh, int32_t ncl, int32_t nch, int32_t nc)
{
    /*
     * sort an matrix of int, with the selection algorithm.
     * from max to min
     * the key is in column nc
     * the sort is performed, by doing a purmutation on the lines,
     * instead of copying the lines.
     */

    int32_t x, max, pos;
    int32_t * ptr;

    for (int32_t i = nrl; i < nrh; i++) {
        max = m[i][nc];
        pos = i;
        for (int32_t j = i + 1; j <= nrh; j++) {
            x = m[j][nc];
            if (x > max) {
                max = x;
                pos = j;
            }
        }

        /* permutation des pointeurs de ligne de la matrice */
        ptr    = m[i];
        m[i]   = m[pos];
        m[pos] = ptr;
    }
}

void sortv_si32matrix_selection_kmax(int32_t ** m, int32_t nrl, int32_t nrh, int32_t ncl, int32_t nch, int32_t nc, int32_t k)
{
    /*
     * sort an matrix of int, with the selection algorithm.
     * from max to min
     * the key is in column nc
     * the sort is performed, by doing a purmutation on the lines,
     * instead of copying the lines.
     */
    int32_t x, max, pos;
    int32_t * ptr;

    for (int32_t i = nrl; i < nrh; i++) {
        max = m[i][nc];
        pos = i;
        for (int32_t j = i + 1; j <= nrh; j++) {
            x = m[j][nc];
            if (x > max) {
                max = x;
                pos = j;
            }
        }

        /* permutation des pointeurs de ligne de la matrice */
        ptr    = m[i];
        m[i]   = m[pos];
        m[pos] = ptr;
    }
}

void sort_index_si32matrix_selection_kmin(int32_t ** key, int32_t nrl, int32_t nrh, int32_t ncl, int32_t nch, int32_t ** index, int32_t k)
{
    set_si32matrix_j(index, nrl,nrh, ncl,nch);
    for (int32_t i = nrl; i <= nrh; i++) {
        sort_index_ivector_selection_kmin(key[i], ncl, nch, index[i], k);
    }
}

void sort_index_si32matrix_selection_kmax(int32_t ** key, int32_t nrl, int32_t nrh, int32_t ncl, int32_t nch, int32_t ** index, int32_t k)
{
    set_si32matrix_j(index, nrl,nrh, ncl,nch);
    for (int32_t i = nrl; i <= nrh; i++) {
        sort_index_ivector_selection_kmax(key[i], ncl, nch, index[i], k);
    }
}

void sortv_index_imatrix_selection_max(int ** key, int32_t nrl, int32_t nrh, int32_t ncl, int32_t nch, int32_t * index, int32_t nc)
{
    int32_t pos, tmp, il, ih;
    int32_t x, max;
    int32_t * ptr;

    il = nrl;
    ih = nrh;

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

    for (int32_t i = il; i < ih; i++) {
        max = key[i][nc];
        pos = i;
        for (int32_t j = i + 1; j <= nrh; j++) {
            x = key[j][nc];
            if (x > max) {
                max = x;
                pos = j;
            }
        }
        /* permutation des pointeurs de ligne de la matrice */
        ptr      = key[i];
        key[i]   = key[pos];
        key[pos] = ptr;

        /* permutation des indices de l'index */
        tmp        = index[i];
        index[i]   = index[pos];
        index[pos] = tmp;
    }
}

void sortv_index_imatrix_selection_min(int32_t ** key, int32_t nrl, int32_t nrh, int32_t ncl, int32_t nch, int32_t * index, int32_t nc)
{
    int32_t pos, tmp, il, ih;
    int32_t x, min;
    int32_t * ptr;

    il = nrl;
    ih = nrh;

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

    for (int32_t i = il; i < ih; i++) {
        min = key[i][nc];
        pos = i;
        for (int32_t j = i + 1; j <= nrh; j++) {
            x = key[j][nc];
            if (x < min) {
                min = x;
                pos = j;
            }
        }
        /* permutation des pointeurs de ligne de la matrice */
        ptr      = key[i];
        key[i]   = key[pos];
        key[pos] = ptr;

        /* permutation des indices de l'index */
        tmp        = index[i];
        index[i]   = index[pos];
        index[pos] = tmp;
    }
}


// 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