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

ecs_vec_real_tri.c

/*============================================================================
 *  Définitions des fonctions
 *   associées à la structure `ecs_vec_real_t' décrivant un vecteur indexé
 *   réel et réalisant des fonctionnalités 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 associe au fichier courant
 *----------------------------------------------------------------------------*/

#include "ecs_vec_real_tri.h"


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

#include "ecs_vec_real_priv.h"


/*============================================================================
 *                       Prototypes de fonctions privees
 *============================================================================*/

/*----------------------------------------------------------------------------
 *    Fonction de descente d'un arbre binaire pour le tri lexicographique
 *  d'un vecteur `ecs_vec_real_t' de réels (voir ecs_vec_real__trie)
 *----------------------------------------------------------------------------*/

static void ecs_loc_vec_real__desc_arbre
(
  size_t      elem_pas,  /* --> Pas des éléments                              */
  ecs_real_t  *elem_tab, /* --> Table de définition des éléments              */
                         /*     Dimension : elem_tab[sz_table]                */
  ecs_real_t  tolerance, /* --> Tolérance                                     */
  size_t      ltree,     /* --> Niveau de l'arbre binaire à descendre         */
  size_t      ntree,     /* --> Taille de l'arbre binaire à descendre         */

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


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

/*----------------------------------------------------------------------------
 *    Fonction de tri lexicographique d'une table de listes de réels.
 *  La liste n'est pas modifiée directement, mais on construit une table de
 *  renumérotation, afin de pouvoir appliquer cette rénumerotation à 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.
 *----------------------------------------------------------------------------*/

void ecs_vec_real__trie
(
 const ecs_vec_real_t *const this_vec  , /* --> Indexe des reels à trier      */
       ecs_tab_int_t  *const vect_renum, /* <-> Tableau de renumérotation     */
 const ecs_real_t            tolerance   /* --> Tolérance                     */
)
{
  ecs_int_t i, i_save;


  /*xxxxxxxxxxxxxxxxxxxxxxxxxxx Instructions xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx*/


  /* creation de l'arbre binaire vect_renum->val[vect_renum->nbr] */

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

    ecs_loc_vec_real__desc_arbre(this_vec->pos_pas,
                                 this_vec->val_tab,
                                 tolerance,
                                 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_real__desc_arbre(this_vec->pos_pas,
                                 this_vec->val_tab,
                                 tolerance,
                                 0,
                                 i,
                                 vect_renum->val);
  }

}


/*----------------------------------------------------------------------------
 *  Fonction qui trie un vecteur de reels en renvoyant le vecteur trié
 *----------------------------------------------------------------------------*/

void ecs_vec_real__trie_et_renvoie
(
 const ecs_vec_real_t *const this_vec       , /* --> Réels à trier            */
       ecs_vec_real_t *const vec_trie       , /* <-- Réels triés              */
       ecs_tab_int_t  *const vect_renum_pos , /* <-> Renum. des positions     */
 const ecs_real_t            tolerance        /* --> Tolérance                */
)
{

  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_vec_real__trie(this_vec      ,
                     vect_renum_pos,
                     tolerance     ) ;

  cpt_val = 0 ;

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

  vec_trie->pos_pas = this_vec->pos_pas ;


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

    pos_nbr_val = this_vec->pos_pas ;

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

      vec_trie->val_tab[cpt_val++] =
        this_vec->val_tab[this_vec->pos_pas*(vect_renum_pos->val[ipos])+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' :                    */
  /*  a 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'un vecteur `ecs_vec_real_t' de réels (voir ecs_vec_real__trie)
 *----------------------------------------------------------------------------*/

static void ecs_loc_vec_real__desc_arbre
(
  size_t      elem_pas,  /* --> Pas des éléments                              */
  ecs_real_t  *elem_tab, /* --> Table de définition des éléments              */
                         /*     Dimension : elem_tab[sz_table]                */
  ecs_real_t  tolerance, /* --> Tolérance                                     */
  size_t      ltree,     /* --> Niveau de l'arbre binaire à descendre         */
  size_t      ntree,     /* --> Taille de l'arbre binaire à descendre         */

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

  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);
      isup = 0;
      for (i = 0, e1 = elem_pas*p1, e2 = elem_pas*p2;
           (i < elem_pas) &&
             ECS_ABS(*(elem_tab+e1) - *(elem_tab+e2)) < tolerance ;
           i++, e1++, e2++)
        ;

      if (i < elem_pas)
        isup = (*(elem_tab+e1) > *(elem_tab+e2)) ? 1 : 0;

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

    if (ktree >= ntree) break;

    /* isup faux si elem_ord[ltree] < elem_ord[ktree] */
    p1 = i_save;
    p2 = *(elem_ord+ktree);
    isup = 0 ;
    for (i = 0 , e1 = elem_pas*p1, e2 = elem_pas*p2 ;
         (i < elem_pas) &&
           (ECS_ABS(*(elem_tab+e1) - *(elem_tab+e2)) < tolerance) ;
         i++, e1++, e2++)
      ;


    if (i < elem_pas)
      isup = (*(elem_tab+e1) < *(elem_tab+e2)) ? 0 : 1;

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

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

  *(elem_ord+ltree) = i_save;

  return;
}


Generated by  Doxygen 1.6.0   Back to index