Logo Search packages:      
Sourcecode: ecs version File versions  Download package

ecs_vec_int_tri.c

/*============================================================================
 *  Définitions des fonctions
 *   associées à la structure `ecs_vec_int_t' décrivant un vecteur indexé entier
 *   et réalisant des fonctionnalités de tri
 *
 *  Fonctions utilitaires de tri
 *============================================================================*/

/*
  This file is part of the Code_Saturne Preprocessor, element of the
  Code_Saturne CFD tool.

  Copyright (C) 1999-2007 EDF S.A., France

  contact: saturne-support@edf.fr

  The Code_Saturne Preprocessor 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 2 of
  the License, or (at your option) any later version.

  The Code_Saturne Preprocessor 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 the Code_Saturne Preprocessor; if not, write to the
  Free Software Foundation, Inc.,
  51 Franklin St, Fifth Floor,
  Boston, MA  02110-1301  USA
*/


/*============================================================================
 *                                 Visibilité
 *============================================================================*/

/*----------------------------------------------------------------------------
 *  Fichiers `include' librairie standard C ou BFT
 *----------------------------------------------------------------------------*/

#include <assert.h>

#include <bft_mem.h>


/*----------------------------------------------------------------------------
 *  Fichiers `include' visibles du  paquetage global "Utilitaire"
 *----------------------------------------------------------------------------*/

#include "ecs_def.h"


/*----------------------------------------------------------------------------
 *  Fichiers `include' visibles des paquetages visibles
 *----------------------------------------------------------------------------*/


/*----------------------------------------------------------------------------
 *  Fichiers `include' visibles du  paquetage courant
 *----------------------------------------------------------------------------*/


/*----------------------------------------------------------------------------
 *  Fichier  `include' du  paquetage courant associé au fichier courant
 *----------------------------------------------------------------------------*/

#include "ecs_vec_int_tri.h"


/*----------------------------------------------------------------------------
 *  Fichiers `include' prives   du  paquetage courant
 *----------------------------------------------------------------------------*/

#include "ecs_vec_int_priv.h"


/*============================================================================
 *                       Prototypes de fonctions privées
 *============================================================================*/

/*----------------------------------------------------------------------------
 *    Fonction de descente d'un arbre binaire pour le tri lexicographique
 *  d'une table de listes d'entiers (voir ecs_int_table_ord).
 *----------------------------------------------------------------------------*/

static void ecs_loc_vec_int__desc_arbre
(
 const ecs_size_t *const pos_tab , /* --> Position d'un élément dans la table */
                                   /*     Dimension : pos_tab[nb_tot_elems+1] */
 const ecs_int_t *const val_tab  , /* --> Table de définition des éléments    */
                                   /*     Dimension : val_tab[sz_table]       */
       size_t           ltree    , /* --> Niveau arbre binaire à descendre    */
       size_t           ntree    , /* --> Taille arbre binaire a descendre    */

       ecs_int_t *const elem_ord   /* <-> Liste à trier des éléms. considérés */
                                   /*     Dimension : elem_ord[nbr_renum]     */
);


/*----------------------------------------------------------------------------
 *    Fonction de tri lexicographique d'une table de listes d'entiers.
 *  La liste n'est pas modifiée directement, mais on construit une table de
 *  renumérotation, afin de pouvoir appliquer cette renumérotation à d'autres
 *  tableaux dépendant de la table.
 *
 *    Le tri utilisé est de type "heapsort", de complexité O(nlog(n)). Les
 *  éléments sont rangés en ordre croissant.
 *
 *    Pour accéder au k-ième élément ordonné de la table,
 *  on utilisera la position :
 *              elem_pos[elem_ord[k - 1] - 1] du tableau elem_table[].
 *----------------------------------------------------------------------------*/

static void ecs_loc_vec_int__trie
(
 const ecs_vec_int_t  *const this_vec  , /* --> Indexe des entiers à trier    */
       ecs_tab_int_t  *const vect_renum  /* <-> Tableau de renumérotation     */
) ;


/*============================================================================
 *                             Fonctions publiques
 *============================================================================*/

/*----------------------------------------------------------------------------
 *  Fonction qui trie un vecteur d'entiers en renvoyant le vecteur trié
 *
 *  --------------------------------------------------------------------------
 *
 *  Suite de l'exemple précédent :
 *  ============================
 *
 *  Cette fonction renvoie, en plus, le vecteur trié :
 *  ------------------------------------------------
 *
 *                        .---..---..---..---.---.---..---.---..---.---.
 *  vec_trie->val_tab     | 2 || 4 || 4 || 5 | 2 | 6 || 5 | 3 || 5 | 9 |
 *                        `---'`---'`---'`---'---'---'`---'---'`---'---'
 *                          0    1    2    3   4   5    6   7    8   9
 *                        `-,-'`-,-'`-,-'`-----,-----'`---,---'`---,---'
 *       Ancien  numéro :   7    2    4        3          1        5
 *       Nouveau numéro :   1    2    3        4          5        6
 *
 *
 *                        .---.---.---.---.---.---.---.
 *  vec_trie->pos_tab     | 1 | 2 | 3 | 4 | 7 | 9 | 11|
 *                        `---'---'---'---'---'---'---'
 *                          0   1   2   3   4   5   6
 *
 *----------------------------------------------------------------------------*/

void ecs_vec_int__trie_et_renvoie
(
 const ecs_vec_int_t *const this_vec       , /* --> Entiers à trier           */
       ecs_vec_int_t *const vec_trie       , /* <-- Entiers triés             */
       ecs_tab_int_t *const vect_renum_pos   /* <-> Renumérotation positions  */
)
{

  size_t      pos_nbr_val ;
  size_t      ival    ;
  size_t      ipos    ;
  size_t      cpt_val ;
  ecs_int_t * vect_renum_pos_val ;


  /*xxxxxxxxxxxxxxxxxxxxxxxxxxx Instructions xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx*/


  ecs_loc_vec_int__trie(this_vec,
                        vect_renum_pos) ;

  cpt_val = 0 ;

  vec_trie->pos_nbr = vect_renum_pos->nbr + 1 ;

  vec_trie->pos_tab[0] = 1 ;


  for (ipos = 0 ; ipos < vect_renum_pos->nbr ; ipos++) {

    pos_nbr_val
      = this_vec->pos_tab[vect_renum_pos->val[ipos] + 1]
      - this_vec->pos_tab[vect_renum_pos->val[ipos]]     ;

    vec_trie->pos_tab[ipos + 1] = vec_trie->pos_tab[ipos] + pos_nbr_val ;

    for (ival = 0 ; ival < pos_nbr_val ; ival++) {

      vec_trie->val_tab[cpt_val++] =
        this_vec->val_tab[this_vec->pos_tab[vect_renum_pos->val[ipos]]-1+ival] ;

    }

  }

  /* `vect_renum_pos' prend pour indice les indices nouveaux,       */
  /*  et ses valeurs contiennent les indices anciens correspondants */
  /* On inverse le contenu de `vect_renum_pos' :                    */
  /*  à chaque indice ancien, `vect_renum_pos' donne la valeur      */
  /*  du nouvel indice                                              */

  BFT_MALLOC(vect_renum_pos_val, vect_renum_pos->nbr, ecs_int_t) ;

  for (ival = 0 ; ival < vect_renum_pos->nbr ; ival++)
    vect_renum_pos_val[ival] = vect_renum_pos->val[ival] ;

  for (ival = 0 ; ival < vect_renum_pos->nbr ; ival++)
    vect_renum_pos->val[vect_renum_pos_val[ival]] = ival ;

  BFT_FREE(vect_renum_pos_val) ;


}


/*============================================================================
 *                              Fonctions privées
 *============================================================================*/

/*----------------------------------------------------------------------------
 *    Fonction de descente d'un arbre binaire pour le tri lexicographique
 *  d'une table de listes d'entiers (voir ecs_int_table_ord).
 *----------------------------------------------------------------------------*/

static void ecs_loc_vec_int__desc_arbre
(
 const ecs_size_t *const pos_tab , /* --> Position d'un élément dans la table */
                                   /*     Dimension : pos_tab[nb_tot_elems+1] */
 const ecs_int_t *const val_tab  , /* --> Table de définition des éléments    */
                                   /*     Dimension : val_tab[sz_table]       */
       size_t           ltree    , /* --> Niveau arbre binaire à descendre    */
       size_t           ntree    , /* --> Taille arbre binaire a descendre    */

       ecs_int_t *const elem_ord   /* <-> Liste à trier des éléms. considérés */
                                   /*     Dimension : elem_ord[nbr_renum]     */
)
{
  size_t    ktree;
  size_t    p1, p2, l1, l2, i, i_save;
  size_t    e1, e2 ;
  int     isup;


  /*xxxxxxxxxxxxxxxxxxxxxxxxxxx Instructions xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx*/


  i_save = *(elem_ord+ltree);

  while (ltree <= (ntree/2)) {

    ktree = (2*ltree)+1;

    if (ktree < ntree - 1) {

      /* isup vrai si elem_ord[ktree+1] > elem_ord[ktree] */
      p1 = *(elem_ord+ktree+1);
      p2 = *(elem_ord+ktree);
      l1 = *(pos_tab+p1+1) - *(pos_tab+p1);
      l2 = *(pos_tab+p2+1) - *(pos_tab+p2);
      isup = (l1 > l2) ? 1 : 0;
      for (i = 0, e1 = *(pos_tab+p1) - 1, e2 = *(pos_tab+p2) - 1;
           (i < l1) && (i < l2)
             && (*(val_tab+e1) == *(val_tab+e2));
           i++, e1++, e2++)
        ;
      if ((i < l1) && (i < l2))
        isup = (*(val_tab+e1) > *(val_tab+e2)) ? 1 : 0;

      /* si isup vrai, on incremente ktree */
      if (isup) ktree++;
    }

    if (ktree >= ntree) break;

    /* isup faux si elem_ord[ltree] (initial) < elem_ord[ktree] */
    p1 = i_save;
    p2 = *(elem_ord+ktree);
    l1 = *(pos_tab+p1+1) - *(pos_tab+p1);
    l2 = *(pos_tab+p2+1) - *(pos_tab+p2);
    isup = (l1 < l2) ? 0 : 1;
    for (i = 0, e1 = *(pos_tab+p1) - 1, e2 = *(pos_tab+p2) - 1;
         (i < l1) && (i < l2) &&
           (*(val_tab+e1) == *(val_tab+e2));
         i++, e1++, e2++)
      ;
    if ((i < l1) && (i < l2))
      isup = (*(val_tab+e1) < *(val_tab+e2)) ? 0 : 1;

    /* si isup vrai */
    if (isup) break;

    *(elem_ord+ltree) = *(elem_ord+ktree);
    ltree = ktree;
  }

  *(elem_ord+ltree) = i_save;

}


/*----------------------------------------------------------------------------
 *    Fonction de tri lexicographique d'une table de listes d'entiers.
 *  La liste n'est pas modifiée directement, mais on construit une table de
 *  renumérotation, afin de pouvoir appliquer cette renumérotation à d'autres
 *  tableaux dépendant de la table.
 *
 *    Le tri utilisé est de type "heapsort", de complexité O(nlog(n)). Les
 *  éléments sont rangés en ordre croissant.
 *
 *    Pour accéder au k-ième élément ordonné de la table,
 *  on utilisera la position :
 *              elem_pos[elem_ord[k - 1] - 1] du tableau elem_table[].
 *
 * ----------------------------------------------------------------------------
 *
 *  Exemple : (pour des tables de valeurs entières)
 *  =======
 *
 *  Supposons 7 éléments définis par des sommets de numéros 1,2,3,4,5,6,9
 *   comme suit :
 *
 *                        .---.---..---..---.---.---..---..---.---..---..---.
 *  this_vec->val_tab     | 5 | 3 || 4 || 5 | 2 | 6 || 4 || 5 | 9 || 1 || 2 |
 *                        `---'---'`---'`---'---'---'`---'`---'---'`---'`---'
 *                          0   1    2    3   4   5    6    7   8    9    10
 *                        `---.---'`-.-'`-----.-----'`-.-'`---.---'`-.-'`-.-'
 *  Numéro de l'élément :     1      2        3        4      5      6    7
 *
 *
 *                        .---.---.---.---.---.---.---.---.
 *  this_vec->pos_tab     | 1 | 3 | 4 | 7 | 8 | 10| 11| 12|
 *                        `---'---'---'---'---'---'---'---'
 *                          0   1   2   3   4   5   6   7
 *
 *
 *
 *  On veut trier les 6 éléments 1,2,3,4,5,7
 *  ----------------------------------------
 *
 *
 *                        .---.---.---.---.---.---.
 *  vect_renum            | 0 | 1 | 2 | 3 | 4 | 6 |
 *                        `---'---'---'---'---'---'
 *                          0   1   2   3   4   5
 *
 *
 *  La liste trieé étant :
 *  --------------------
 *                        .---..---..---..---..---.---.---..---.---..---.---.
 *                        | 1 || 2 || 4 || 4 || 5 | 2 | 6 || 5 | 3 || 5 | 9 |
 *                        `---'`---'`---'`---'`---'---'---'`---'---'`---'---'
 *                        `-.-'`-.-'`-.-'`-.-'`-----.-----'`---.---'`---.---'
 *       Ancien  numéro :   6    7    2    4        3          1        5
 *       Nouveau numéro :   1    2    3    4        5          6        7
 *
 *
 *
 *  on obtient pour résultat :
 *  ------------------------
 *
 *
 *                        .---.---.---.---.---.---.
 *  vect_renum            | 6 | 1 | 3 | 2 | 0 | 4 |
 *                        `---'---'---'---'---'---'
 *                          0   1   2   3   4   5
 *
 *----------------------------------------------------------------------------*/

static void ecs_loc_vec_int__trie
(
 const ecs_vec_int_t  *const this_vec  , /* --> Indexe des entiers à trier    */
       ecs_tab_int_t  *const vect_renum  /* <-> Tableau de renumérotation     */
)
{

  ecs_int_t i, i_save;


  /*xxxxxxxxxxxxxxxxxxxxxxxxxxx Instructions xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx*/


  /* création de l'arbre binaire vec_renum->val_tab[vect_renum->nbr] */

  for (i = (vect_renum->nbr / 2) - 1 ; i >= 0 ; i--) {

    ecs_loc_vec_int__desc_arbre (this_vec->pos_tab,
                                 this_vec->val_tab,
                                 i,
                                 vect_renum->nbr,
                                 vect_renum->val);

  }


  /* tri de l'arbre binaire */

  for (i = vect_renum->nbr - 1 ; i > 0 ; i--) {

    i_save                 = *(vect_renum->val    ) ;
    *(vect_renum->val    ) = *(vect_renum->val + i) ;
    *(vect_renum->val + i) = i_save                 ;


    ecs_loc_vec_int__desc_arbre (this_vec->pos_tab,
                                 this_vec->val_tab,
                                 0,
                                 i,
                                 vect_renum->val);

  }


}


Generated by  Doxygen 1.6.0   Back to index