BitonicSort.h

// -*- tab-width: 2; indent-tabs-mode: nil; coding: utf-8-with-signature -*-
//-----------------------------------------------------------------------------
// Copyright 2000-2025 CEA (www.cea.fr) IFPEN (www.ifpenergiesnouvelles.com)
// See the top-level COPYRIGHT file for details.
// SPDX-License-Identifier: Apache-2.0
//-----------------------------------------------------------------------------
/*---------------------------------------------------------------------------*/
/* BitonicSort.h                                               (C) 2000-2025 */
/*                                                                           */
/* Algorithme de tri bi-tonique parallèle.                                   */
/*---------------------------------------------------------------------------*/
#ifndef ARCANE_CORE_PARALLEL_BITONICSORT_H
#define ARCANE_CORE_PARALLEL_BITONICSORT_H
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
#include "arcane/utils/TraceAccessor.h"
#include "arcane/utils/UniqueArray.h"
 
#include "arcane/core/IParallelSort.h"
#include "arcane/core/IParallelMng.h"
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
namespace Arcane::Parallel
{
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
template <typename KeyType>
class BitonicSortDefaultTraits
{
 public:
 
  static bool compareLess(const KeyType& k1, const KeyType& k2)
  {
    return k1 < k2;
  }
  static Request send(IParallelMng* pm, Int32 rank, ConstArrayView<KeyType> values)
  {
    return pm->send(values, rank, false);
  }
  static Request recv(IParallelMng* pm, Int32 rank, ArrayView<KeyType> values)
  {
    return pm->recv(values, rank, false);
  }
  static KeyType maxValue()
  {
    //return ARCANE_INTEGER_MAX-1;
    return std::numeric_limits<KeyType>::max();
  }
  // Indique si la clé est valide. Elle doit être invalide si k==maxValue()
  static bool isValid(const KeyType& k)
  {
    return k != maxValue();
  }
};
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/

template <typename KeyType, typename KeyTypeTraits = BitonicSortDefaultTraits<KeyType>>
class BitonicSort
: public TraceAccessor
, public IParallelSort<KeyType>
{
 public:
 
  explicit BitonicSort(IParallelMng* parallel_mng);
  explicit BitonicSort(IParallelMng* parallel_mng, const KeyTypeTraits& traits);
 
 public:

  inline void sort(ConstArrayView<KeyType> keys) override;

  ConstArrayView<KeyType> keys() const override { return m_keys; }

  Int32ConstArrayView keyRanks() const override { return m_key_ranks; }

  Int32ConstArrayView keyIndexes() const override { return m_key_indexes; }
 
 public:
 
  void setNeedIndexAndRank(bool want_index_and_rank)
  {
    m_want_index_and_rank = want_index_and_rank;
  }
 
 private:
 
  void _mergeLevels(Int32 begin, Int32 size);
  void _mergeProcessors(Int32 proc1, Int32 proc2);
  void _separator(Int32 begin, Int32 size);
  void _localHeapSort();
 
 private:

  UniqueArray<KeyType> m_keys;
  UniqueArray<Int32> m_key_ranks;
  UniqueArray<Int32> m_key_indexes;
  IParallelMng* m_parallel_mng = nullptr;
  Int64 m_init_size = 0;
  Int64 m_size = 0;

  bool m_want_index_and_rank = true;

  Integer m_nb_merge = 0;
 
  KeyTypeTraits m_traits;
 
 private:
 
  void _init(ConstArrayView<KeyType> keys);
};
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
} // namespace Arcane::Parallel
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
#endif