sortperm.h

Go to the documentation of this file.

// ========================================================================= //
// This file is part of MyraMath, copyright (c) 2014-2019 by Ryan A Chilton  //
// and distributed by MyraCore, LLC. See LICENSE.txt for license terms.      //
// ========================================================================= //

#ifndef MYRAMATH_UTILITY_SORTPERM_H
#define MYRAMATH_UTILITY_SORTPERM_H

#include <vector>
#include <iterator>
#include <algorithm>

#include <myramath/utility/detail/ssize.h>

namespace myra {
namespace detail {

// Implementation detail of sortperm(), holds an Iterator along with index data.
template<class Iterator> class sortperm_Pair
  {
  public:
    sortperm_Pair(Iterator in_i, int in_index) 
      : i(in_i), index(in_index) { }
    Iterator i;
    int index;
  };

// Comparator for sortperm_Pair's. Compares through the iterator, but carries the index data along.
template<class Iterator, class Comparator> class sortperm_Comparator
  {
  public:
    typedef sortperm_Pair<Iterator> Pair;
    sortperm_Comparator(const Comparator& in_cmp) 
      : cmp(in_cmp) { }
    bool operator() (const Pair& a, const Pair& b)
      { return cmp(*(a.i),*(b.i)); }
  private:
    const Comparator& cmp;
  };
  
} // namespace detail

template<class Iterator, class Comparator> 
std::vector<int> sortperm(Iterator begin, Iterator end, const Comparator& cmp)
  {
  // Form pairs of iterators+indices ("schwartzian transform")
  typedef detail::sortperm_Pair<Iterator> Pair;
  typedef std::vector<Pair> Pairs;
  Pairs pairs; pairs.reserve(std::distance(begin,end));
  for (Iterator i = begin; i != end; ++i)
    pairs.push_back( Pair(i,ssize(pairs)) );
  // Delegate to std::sort with a special comparator. 
  std::sort(pairs.begin(), pairs.end(), detail::sortperm_Comparator<Iterator,Comparator>(cmp));
  // Extract permutation vector.
  std::vector<int> perm; perm.reserve(pairs.size());
  for (typename Pairs::const_iterator i = pairs.begin(); i != pairs.end(); ++i)
    perm.push_back(i->index);
  return perm;
  }

template<class Iterator>
std::vector<int> sortperm(Iterator begin, Iterator end)
  {
  typedef typename std::iterator_traits<Iterator>::value_type T;
  typedef std::less<T> Comparator;
  return sortperm(begin,end,Comparator());
  }

} // namespace myra

#endif