Line data    Source code

       1             : // The libMesh Finite Element Library.
       2             : // Copyright (C) 2002-2025 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
       3             : 
       4             : // This library is free software; you can redistribute it and/or
       5             : // modify it under the terms of the GNU Lesser General Public
       6             : // License as published by the Free Software Foundation; either
       7             : // version 2.1 of the License, or (at your option) any later version.
       8             : 
       9             : // This library is distributed in the hope that it will be useful,
      10             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      12             : // Lesser General Public License for more details.
      13             : 
      14             : // You should have received a copy of the GNU Lesser General Public
      15             : // License along with this library; if not, write to the Free Software
      16             : // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
      17             : 
      18             : 
      19             : #ifndef LIBMESH_PARALLEL_BIN_SORTER_H
      20             : #define LIBMESH_PARALLEL_BIN_SORTER_H
      21             : 
      22             : // This class contains all the functionality for bin sorting
      23             : // Templated on the type of keys you will be sorting and the
      24             : // type of iterator you will be using.
      25             : 
      26             : // libMesh includes
      27             : #include "libmesh/libmesh_common.h" // cast_int
      28             : #include "libmesh/parallel_object.h"
      29             : 
      30             : // C++ includes
      31             : #include <vector>
      32             : #include <iterator>
      33             : 
      34             : namespace libMesh
      35             : {
      36             : 
      37             : namespace Parallel
      38             : {
      39             : 
      40             : /**
      41             :  * Perform a parallel sort using a bin-sort method.
      42             :  *
      43             :  * \author Benjamin S. Kirk
      44             :  * \author John W. Peterson
      45             :  * \date 2007
      46             :  * \brief Parallel bin sorting object.
      47             :  */
      48             : template <typename KeyType, typename IdxType=unsigned int>
      49      682713 : class BinSorter : public ParallelObject
      50             : {
      51             :   // the type of iterator we will be using is inferred from KeyType
      52             :   typedef typename std::vector<KeyType>::const_iterator IterType;
      53             : 
      54             : public:
      55             : 
      56             :   // Constructor
      57             :   explicit
      58             :   BinSorter (const Parallel::Communicator & comm,
      59             :              const std::vector<KeyType> & d);
      60             : 
      61             :   /**
      62             :    * The actual function which sorts the data into
      63             :    * nbins.  Currently based on the global min and
      64             :    * max which you must provide e.g. by using MPI.
      65             :    */
      66             :   void binsort (const IdxType nbins,
      67             :                 KeyType max,
      68             :                 KeyType min);
      69             : 
      70             :   /**
      71             :    * \returns The size of bin b as an unsigned int.
      72             :    */
      73             :   IdxType sizeof_bin (const IdxType bin) const;
      74             : 
      75             : 
      76             : private:
      77             : 
      78             :   const std::vector<KeyType> & data;
      79             :   std::vector<IterType>       bin_iters;   // Iterators to the bin boundaries
      80             :                                            //  in data
      81             : };
      82             : 
      83             : 
      84             : 
      85             : //--------------------------------------------------------------------------
      86             : template <typename KeyType, typename IdxType>
      87             : inline
      88       30460 : IdxType BinSorter<KeyType,IdxType>::sizeof_bin (const IdxType bin) const
      89             : {
      90       30460 :   libmesh_assert_less ((bin+1), bin_iters.size());
      91             : 
      92             :   // The size of the bin is defined by the distance between
      93             :   // its bounding iterators
      94             :   return cast_int<IdxType>
      95     7217431 :     (std::distance (bin_iters[bin], bin_iters[bin+1]));
      96             : }
      97             : 
      98             : }
      99             : 
     100             : } // namespace libMesh
     101             : 
     102             : #endif // LIBMESH_PARALLEL_BIN_SORTER_H