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        8758 :   indirect_comparator(RandomAccessIterator r, UserComparisonFunctor c)
      30        8758 :     : _random_access_iterator(r), _user_comp(c)
      31             :   {
      32        8758 :   }
      33             : 
      34             :   // comparison operator - calls the user's comparison function on
      35             :   // v[lhs] and v[rhs]
      36     2502289 :   bool operator()(size_t lhs, size_t rhs)
      37             :   {
      38             :     // Note: operator[] is defined for random access iterators!
      39     2502289 :     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        8758 : initialize_indirect_sort(RandomAccessIterator beg,
      53             :                          RandomAccessIterator end,
      54             :                          std::vector<size_t> & b)
      55             : {
      56             :   // enough storage for all the indices
      57        8758 :   b.resize(std::distance(beg, end));
      58             : 
      59             :   // iota
      60      304786 :   for (size_t i = 0; i < b.size(); ++i)
      61      296028 :     b[i] = i;
      62        8758 : }
      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        8736 : indirectSort(RandomAccessIterator beg, RandomAccessIterator end, std::vector<size_t> & b)
      69             : {
      70             :   // Space in b
      71        8736 :   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        8736 :   indirect_comparator<RandomAccessIterator, LessThanComparator> ic(beg, LessThanComparator());
      80             : 
      81             :   // Sort the indices, based on the data
      82        8736 :   std::sort(b.begin(), b.end(), ic);
      83        8736 : }
      84             : 
      85             : // A generic indirect sort function templated on the iterator type *and* the comparison functor
      86             : // to be used for the ordering.
      87             : template <class RandomAccessIterator, class UserComparisonFunctor>
      88             : void
      89          22 : indirectSort(RandomAccessIterator beg,
      90             :              RandomAccessIterator end,
      91             :              std::vector<size_t> & b,
      92             :              UserComparisonFunctor user_comp)
      93             : {
      94             :   // Space in b
      95          22 :   initialize_indirect_sort(beg, end, b);
      96             : 
      97             :   // Construct comparator object
      98          22 :   indirect_comparator<RandomAccessIterator, UserComparisonFunctor> ic(beg, user_comp);
      99             : 
     100             :   // Sort the indices, based on the data
     101          22 :   std::sort(b.begin(), b.end(), ic);
     102          22 : }
     103             : 
     104             : /// Uses indices created by the indirectSort function to sort the given
     105             : /// container (which must support random access, resizing, and std::swap.
     106             : template <typename T>
     107             : void
     108        1512 : applyIndices(T & container, const std::vector<size_t> & indices)
     109             : {
     110        1512 :   T tmp;
     111        1512 :   tmp.resize(container.size());
     112       21692 :   for (size_t i = 0; i < indices.size(); i++)
     113       20180 :     tmp[i] = container[indices[i]];
     114        1512 :   std::swap(tmp, container);
     115        1512 : }
     116             : 
     117             : } // namespace Moose