/*============================================================================
 * Functions related to the ordering of local arrays of global numbers and
 * calculation of global ranks in parallel mode.
 *============================================================================*/

/*
  This file is part of the "Finite Volume Mesh" library, intended to provide
  finite volume mesh and associated fields I/O and manipulation services.

  Copyright (C) 2004-2005  EDF

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.

  This library 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
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/

/*----------------------------------------------------------------------------
 * Standard C library headers
 *----------------------------------------------------------------------------*/

#include <assert.h>
#include <stdio.h>

/*----------------------------------------------------------------------------
 * BFT library headers
 *----------------------------------------------------------------------------*/

#include <bft_mem.h>
#include <bft_printf.h>

/*----------------------------------------------------------------------------
 *  Local headers
 *----------------------------------------------------------------------------*/

#include <fvm_config_defs.h>
#include <fvm_defs.h>
#include <fvm_parall.h>

/*----------------------------------------------------------------------------
 *  Header for the current file
 *----------------------------------------------------------------------------*/

#include <fvm_order.h>

/*----------------------------------------------------------------------------*/

#ifdef __cplusplus
extern "C" {
#if 0
} /* Fake brace to force back Emacs auto-indentation back to column 0 */
#endif
#endif /* __cplusplus */

/*============================================================================
 * Local structure definitions
 *============================================================================*/

/*=============================================================================
 * Private function definitions
 *============================================================================*/

/*----------------------------------------------------------------------------
 * Descend binary tree for the ordering of a fvm_gnum (integer) array.
 *
 * parameters:
 *   number    <-- pointer to numbers of entities that should be ordered.
 *                 (if NULL, a default 1 to n numbering is considered)
 *   level     <-- level of the binary tree to descend
 *   nb_ent    <-- number of entities in the binary tree to descend
 *   order     <-> ordering array
 *----------------------------------------------------------------------------*/

inline static void
_fvm_order_gnum_descend_tree(const fvm_gnum_t  number[],
                             size_t            level,
                             const size_t      nb_ent,
                             fvm_lnum_t        order[])
{
  size_t i_save, i1, i2, lv_cur;

  i_save = (size_t)(order[level]);

  while (level <= (nb_ent/2)) {

    lv_cur = (2*level) + 1;

    if (lv_cur < nb_ent - 1) {

      i1 = (size_t)(order[lv_cur+1]);
      i2 = (size_t)(order[lv_cur]);

      if (number[i1] > number[i2]) lv_cur++;
    }

    if (lv_cur >= nb_ent) break;

    i1 = i_save;
    i2 = (size_t)(order[lv_cur]);

    if (number[i1] >= number[i2]) break;

    order[level] = order[lv_cur];
    level = lv_cur;

  }

  order[level] = i_save;
}

/*----------------------------------------------------------------------------
 * Order an array of global numbers.
 *
 * parameters:
 *   number   <-- array of entity numbers (if NULL, a default 1 to n
 *                numbering is considered)
 *   order    <-- pre-allocated ordering table
 *   nb_ent   <-- number of entities considered
 *----------------------------------------------------------------------------*/

static void
_fvm_order_local(const fvm_gnum_t  number[],
                 fvm_lnum_t        order[],
                 const size_t      nb_ent)
{
  size_t i;
  fvm_lnum_t o_save;

  /* Initialize ordering array */

  for (i = 0 ; i < nb_ent ; i++)
    order[i] = i;

  if (nb_ent < 2)
    return;

  /* Create binary tree */

  i = (nb_ent / 2) ;
  do {
    i--;
    _fvm_order_gnum_descend_tree(number, i, nb_ent, order);
  } while (i > 0);

  /* Sort binary tree */

  for (i = nb_ent - 1 ; i > 0 ; i--) {
    o_save   = order[0];
    order[0] = order[i];
    order[i] = o_save;
    _fvm_order_gnum_descend_tree(number, 0, i, order);
  }
}

/*=============================================================================
 * Public function definitions
 *============================================================================*/

/*----------------------------------------------------------------------------
 * Test if an array of global numbers is ordered.
 *
 * parameters:
 *   list     <-- optional list (1 to n numbering) of selected entities
 *                (or NULL if all nb_ent are selected). This list may
 *                contain element numbers in any order
 *   number   <-- array of all entity numbers (number of entity i
 *                given by number[i] or number[list[i] - 1]) if list exists
 *                (if NULL, a default 1 to n numbering is considered)
 *   nb_ent   <-- number of entities considered
 *
 * returns:
 *   1 if ordered, 0 otherwise.
 *----------------------------------------------------------------------------*/

int
fvm_order_local_test(const fvm_lnum_t  list[],
                     const fvm_gnum_t  number[],
                     const size_t      nb_ent)
{
  size_t i = 0;

  /* If numbering is explicit */

  if (number != NULL) {

    if (list != NULL) {
      for (i = 1 ; i < nb_ent ; i++) {
        if (number[list[i] - 1] < number[list[i-1] - 1])
          break;
      }
    }
    else {
      for (i = 1 ; i < nb_ent ; i++) {
        if (number[i] < number[i-1])
          break;
      }
    }

  /* If numbering is implicit */

  }
  else {

    if (list != NULL) {
      for (i = 1 ; i < nb_ent ; i++) {
        if (list[i] < list[i-1])
          break;
      }
    }
    else
      i = nb_ent;
  }

  if (i == nb_ent || nb_ent == 0)
    return 1;
  else
    return 0;
}

/*----------------------------------------------------------------------------
 * Return an ordering table associated with an array of global numbers.
 *
 * parameters:
 *   list     <-- optional list (1 to n numbering) of selected entities
 *                (or NULL if all nb_ent are selected). This list may
 *                contain element numbers in any order
 *   number   <-- array of all entity numbers (number of entity i
 *                given by number[i] or number[list[i] - 1]) if list exists
 *                (if NULL, a default 1 to n numbering is considered)
 *   nb_ent   <-- number of entities considered
 *
 * returns:
 *   pointer to list of nb_ent entities (0 to n-1 numbering) ordered by
 *   increasing associated number. The calling code is responsible for
 *   freeing this array when it is not needed anymore.
 *----------------------------------------------------------------------------*/

fvm_lnum_t *
fvm_order_local(const fvm_lnum_t  list[],
                const fvm_gnum_t  number[],
                const size_t      nb_ent)
{
  fvm_lnum_t *order;

  BFT_MALLOC(order, nb_ent, fvm_lnum_t);

  fvm_order_local_allocated(list,
                            number,
                            order,
                            nb_ent);

  return order;
}

/*----------------------------------------------------------------------------
 * Compute an ordering table associated with an array of global numbers.
 *
 * parameters:
 *   list     <-- optional list (1 to n numbering) of selected entities
 *                (or NULL if all nb_ent are selected). This list may
 *                contain element numbers in any order
 *   number   <-- array of all entity numbers (number of entity i
 *                given by number[i] or number[list[i] - 1]) if list exists
 *                (if NULL, a default 1 to n numbering is considered)
 *   order    --> pointer to pre-allocated ordering table
 *   nb_ent   <-- number of entities considered
 *----------------------------------------------------------------------------*/

void
fvm_order_local_allocated(const fvm_lnum_t  list[],
                          const fvm_gnum_t  number[],
                          fvm_lnum_t        order[],
                          const size_t      nb_ent)
{
  size_t i;
  fvm_gnum_t *number_list;

  /* Explicit numbering */

  if (number != NULL) {

    if (list != NULL) {
      BFT_MALLOC(number_list, nb_ent, fvm_gnum_t);
      for (i = 0 ; i < nb_ent ; i++)
        number_list[i] = number[list[i] - 1];
      _fvm_order_local(number_list,
                       order,
                       nb_ent);
      BFT_FREE(number_list);
    }
    else
      _fvm_order_local(number,
                       order,
                       nb_ent);

  }

  /* Implicit numbering */

  else {

    BFT_MALLOC(number_list, nb_ent, fvm_gnum_t);
    if (list != NULL) {
      for (i = 0 ; i < nb_ent ; i++)
        number_list[i] = (fvm_gnum_t)(list[i]);
    }
    else {
      for (i = 0 ; i < nb_ent ; i++)
        number_list[i] = (fvm_gnum_t)(i + 1);
    }
    _fvm_order_local(number_list,
                     order,
                     nb_ent);
    BFT_FREE(number_list);

  }

}

/*----------------------------------------------------------------------------
 * Build local renumbering array based on ordering of entities.
 *
 * parameters:
 *   order    <-- 0 to n-1 ordering of entities by increasing attribute
 *   nb_ent   <-- number of entities considered
 *   base     <-- renumbering starting number (typically 0 or 1)
 *
 * returns:
 *   pointer to renumbering array (0 to n-1 numbering) indicating the new
 *   index of renumbered entities; The calling code is responsible for
 *   freeing this array when it is not needed anymore
 *----------------------------------------------------------------------------*/

fvm_lnum_t *
fvm_order_local_renumbering(const fvm_lnum_t  order[],
                            const size_t      nb_ent)
{
  size_t i;
  fvm_lnum_t *number;

  if (nb_ent < 1)
    return NULL;

  assert(order != NULL);

  BFT_MALLOC(number, nb_ent, fvm_lnum_t);

#if defined(DEBUG) && !defined(NDEBUG)
  /* Initialize with "impossible" number (so as to have a reproducible
     and detectable error in the renumbering array in case of
     incorrect order[] values) */
  for (i = 0 ; i < nb_ent ; i++)
    number[i] = - 1;
#endif

  /* Populate renumbering array */

  for (i = 0 ; i < nb_ent ; i++)
    number[order[i]] = i;

#if defined(DEBUG) && !defined(NDEBUG)
  /* Check renumbering array */
  for (i = 0 ; i < nb_ent ; i++)
    assert(number[i] >= 0);
#endif

  return number;
}

/*----------------------------------------------------------------------------*/

#ifdef __cplusplus
}
#endif /* __cplusplus */