Line data    Source code

       1             : //* This file is part of the MOOSE framework
       2             : //* https://mooseframework.inl.gov
       3             : //*
       4             : //* All rights reserved, see COPYRIGHT for full restrictions
       5             : //* https://github.com/idaholab/moose/blob/master/COPYRIGHT
       6             : //*
       7             : //* Licensed under LGPL 2.1, please see LICENSE for details
       8             : //* https://www.gnu.org/licenses/lgpl-2.1.html
       9             : 
      10             : #pragma once
      11             : 
      12             : #include <functional>
      13             : #include <vector>
      14             : #include <algorithm>
      15             : #include <iterator> // std::iterator_traits
      16             : 
      17             : namespace Moose
      18             : {
      19             : 
      20             : // The indirect (or index) comparison functor is templated on a random
      21             : // access iterator type, and a user comparison function.  This class
      22             : // is to be constructed with a random access iterator which points to
      23             : // the beginning of the container whose values are to be indirectly
      24             : // sorted.  This class is not to be used directly by the user.
      25             : template <class RandomAccessIterator, class UserComparisonFunctor>
      26             : struct indirect_comparator
      27             : {
      28             :   // ctor
      29        9645 :   indirect_comparator(RandomAccessIterator r, UserComparisonFunctor c)
      30        9645 :     : _random_access_iterator(r), _user_comp(c)
      31             :   {
      32        9645 :   }
      33             : 
      34             :   // comparison operator - calls the user's comparison function on
      35             :   // v[lhs] and v[rhs]
      36     1472940 :   bool operator()(size_t lhs, size_t rhs)
      37             :   {
      38             :     // Note: operator[] is defined for random access iterators!
      39     1472940 :     return _user_comp(_random_access_iterator[lhs], _random_access_iterator[rhs]);
      40             :   }
      41             : 
      42             : private:
      43             :   // data
      44             :   RandomAccessIterator _random_access_iterator;
      45             :   UserComparisonFunctor _user_comp;
      46             : };
      47             : 
      48             : // This is a common initialization function called by the indirect_sort's.
      49             : // Should not be called directly by users...
      50             : template <class RandomAccessIterator>
      51             : void
      52        9645 : initialize_indirect_sort(RandomAccessIterator beg,
      53             :                          RandomAccessIterator end,
      54             :                          std::vector<size_t> & b)
      55             : {
      56             :   // enough storage for all the indices
      57        9645 :   b.resize(std::distance(beg, end));
      58             : 
      59             :   // iota
      60      334413 :   for (size_t i = 0; i < b.size(); ++i)
      61      324768 :     b[i] = i;
      62        9645 : }
      63             : 
      64             : // A generic indirect sort function templated on the iterator type.  Uses
      65             : // std::less<T> for the comparisons.
      66             : template <class RandomAccessIterator>
      67             : void
      68        9621 : indirectSort(RandomAccessIterator beg, RandomAccessIterator end, std::vector<size_t> & b)
      69             : {
      70             :   // Space in b
      71        9621 :   initialize_indirect_sort(beg, end, b);
      72             : 
      73             :   // Typedef for less typing.  Note: use of std::iterator_traits means this should work with
      74             :   // naked pointers too...
      75             :   typedef std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>
      76             :       LessThanComparator;
      77             : 
      78             :   // Construct comparator object
      79        9621 :   indirect_comparator<RandomAccessIterator, LessThanComparator> ic(beg, LessThanComparator());
      80             : 
      81             :   // Sort the indices, based on the data
      82             :   //
      83             :   // Many use cases pass in a partial order, not a total order; use
      84             :   // stable_sort to make the results of that as reproduceable as
      85             :   // possible.
      86        9621 :   std::stable_sort(b.begin(), b.end(), ic);
      87        9621 : }
      88             : 
      89             : // A generic indirect sort function templated on the iterator type *and* the comparison functor
      90             : // to be used for the ordering.
      91             : template <class RandomAccessIterator, class UserComparisonFunctor>
      92             : void
      93          24 : indirectSort(RandomAccessIterator beg,
      94             :              RandomAccessIterator end,
      95             :              std::vector<size_t> & b,
      96             :              UserComparisonFunctor user_comp)
      97             : {
      98             :   // Space in b
      99          24 :   initialize_indirect_sort(beg, end, b);
     100             : 
     101             :   // Construct comparator object
     102          24 :   indirect_comparator<RandomAccessIterator, UserComparisonFunctor> ic(beg, user_comp);
     103             : 
     104             :   // Sort the indices, based on the data
     105             :   //
     106             :   // Many use cases pass in a partial order, not a total order; use
     107             :   // stable_sort to make the results of that as reproduceable as
     108             :   // possible.
     109          24 :   std::stable_sort(b.begin(), b.end(), ic);
     110          24 : }
     111             : 
     112             : /// Uses indices created by the indirectSort function to sort the given
     113             : /// container (which must support random access, resizing, and std::swap.
     114             : template <typename T>
     115             : void
     116        1688 : applyIndices(T & container, const std::vector<size_t> & indices)
     117             : {
     118        1688 :   T tmp;
     119        1688 :   tmp.resize(container.size());
     120       24588 :   for (size_t i = 0; i < indices.size(); i++)
     121       22900 :     tmp[i] = container[indices[i]];
     122        1688 :   std::swap(tmp, container);
     123        1688 : }
     124             : 
     125             : } // namespace Moose