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_HISTOGRAM_H
      20             : #define LIBMESH_PARALLEL_HISTOGRAM_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             : 
      27             : // C++ includes
      28             : #include "libmesh/libmesh_common.h" // for libmesh_assert()
      29             : #include "libmesh/parallel_object.h"
      30             : 
      31             : // Local includes
      32             : #include <vector>
      33             : #include <iterator>
      34             : 
      35             : namespace libMesh
      36             : {
      37             : 
      38             : namespace Parallel
      39             : {
      40             : 
      41             : /**
      42             :  * Defines a histogram to be used in parallel in conjunction with
      43             :  * a \p BinSorter.
      44             :  *
      45             :  * \author Benjamin S. Kirk
      46             :  * \author John W. Peterson
      47             :  * \date 2007
      48             :  * \brief Used in conjunction with a BinSorter for parallel sorting.
      49             :  */
      50             : template <typename KeyType, typename IdxType=unsigned int>
      51             : class Histogram : public ParallelObject
      52             : {
      53             :   // The type of iterator we will be using is inferred from KeyType
      54             :   typedef typename std::vector<KeyType>::const_iterator IterType;
      55             : 
      56             : public:
      57             : 
      58             :   /**
      59             :    * Constructor.
      60             :    */
      61             :   explicit
      62             :   Histogram (const Parallel::Communicator & comm,
      63             :              const std::vector<KeyType> & d);
      64             : 
      65             :   /**
      66             :    * The actual function which sorts the data into
      67             :    * nbins.  Currently based on the global min and
      68             :    * max which you must provide e.g. by using MPI.
      69             :    */
      70             :   void make_histogram (const IdxType nbins,
      71             :                        KeyType max,
      72             :                        KeyType min);
      73             : 
      74             :   /**
      75             :    * Build the histogram across all processors and store the
      76             :    * result in the input vector \p hist.
      77             :    */
      78             :   void build_histogram ();
      79             : 
      80             :   /**
      81             :    * \returns The raw histogram data to the user.
      82             :    */
      83             :   const std::vector<IdxType> & get_histogram() const;
      84             : 
      85             :   /**
      86             :    * The number of bins in the histogram.
      87             :    */
      88             :   IdxType n_bins () const;
      89             : 
      90             :   /**
      91             :    * \returns The size of local bin \p bin.
      92             :    */
      93             :   IdxType local_bin_size (const IdxType bin) const;
      94             : 
      95             :   /**
      96             :    * \returns The size of global bin \p bin.
      97             :    *
      98             :    * Requires that the user first call \p build_histogram().
      99             :    */
     100             :   IdxType global_bin_size (const IdxType bin) const;
     101             : 
     102             :   /**
     103             :    * \returns The lower boundary of bin \p bin.
     104             :    */
     105             :   double lower_bound (const IdxType bin) const;
     106             : 
     107             :   /**
     108             :    * \returns The upper boundary of bin \p bin.
     109             :    */
     110             :   double upper_bound (const IdxType bin) const;
     111             : 
     112             : 
     113             : private:
     114             : 
     115             :   const std::vector<KeyType> & data;
     116             :   std::vector<IdxType> hist;        // The actual histogram
     117             :   std::vector<double>  bin_bounds;  // The boundary values of each bin
     118             :   std::vector<IterType> bin_iters;  // Iterators to the bin boundaries in data
     119             : };
     120             : 
     121             : 
     122             : 
     123             : template <typename KeyType, typename IdxType>
     124             : inline
     125       15230 : const std::vector<IdxType> & Histogram<KeyType,IdxType>::get_histogram () const
     126             : {
     127       15230 :   return hist;
     128             : }
     129             : 
     130             : 
     131             : 
     132             : template <typename KeyType, typename IdxType>
     133             : inline
     134     1538230 : IdxType Histogram<KeyType,IdxType>::n_bins () const
     135             : {
     136   362836622 :   if (bin_iters.empty())
     137           0 :     return 0;
     138             : 
     139   362836622 :   return cast_int<IdxType>(bin_iters.size()-1);
     140             : }
     141             : 
     142             : 
     143             : 
     144             : template <typename KeyType, typename IdxType>
     145             : inline
     146     1523000 : IdxType Histogram<KeyType,IdxType>::local_bin_size (const IdxType bin) const
     147             : {
     148     1523000 :   libmesh_assert_less ((bin+1), bin_iters.size());
     149             : 
     150             :   // The number of entries in the bin (locally)
     151             :   return cast_int<IdxType>
     152   359348550 :     (std::distance (bin_iters[bin], bin_iters[bin+1]));
     153             : }
     154             : 
     155             : 
     156             : 
     157             : template <typename KeyType, typename IdxType>
     158             : inline
     159           0 : IdxType Histogram<KeyType,IdxType>::global_bin_size (const IdxType bin) const
     160             : {
     161           0 :   libmesh_assert_less (bin, hist.size());
     162             : 
     163             :   // The number of entries in the bin (globally)
     164           0 :   return hist[bin];
     165             : }
     166             : 
     167             : 
     168             : 
     169             : template <typename KeyType, typename IdxType>
     170             : inline
     171           0 : double Histogram<KeyType,IdxType>::lower_bound (const IdxType bin) const
     172             : {
     173           0 :   libmesh_assert_less ((bin+1), bin_bounds.size());
     174             : 
     175           0 :   return bin_bounds[bin];
     176             : }
     177             : 
     178             : 
     179             : 
     180             : template <typename KeyType, typename IdxType>
     181             : inline
     182       30460 : double Histogram<KeyType,IdxType>::upper_bound (const IdxType bin) const
     183             : {
     184       30460 :   libmesh_assert_less ((bin+1), bin_bounds.size());
     185             : 
     186     7217431 :   return bin_bounds[bin+1];
     187             : }
     188             : 
     189             : }
     190             : 
     191             : } // namespace libMesh
     192             : 
     193             : #endif // LIBMESH_PARALLEL_HISTOGRAM_H