sort_index.h

#ifndef _theplu_yat_utility_sort_index_
#define _theplu_yat_utility_sort_index_

// $Id: sort_index.h 3417 2015-05-25 01:35:59Z peter $

/*
  Copyright (C) 2008, 2010, 2014, 2015 Peter Johansson

  This file is part of the yat library, http://dev.thep.lu.se/yat

  The yat library is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 3 of the
  License, or (at your option) any later version.

  The yat library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with yat. If not, see <http://www.gnu.org/licenses/>.
*/

#include <boost/concept_check.hpp>
#include <boost/iterator/iterator_categories.hpp>
#include <boost/iterator/iterator_concepts.hpp>
#include <boost/iterator/iterator_traits.hpp>

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

namespace theplu {
namespace yat {
namespace utility {

  template<typename InputIterator>
  void sort_index(InputIterator first, InputIterator last,
                  std::vector<size_t>& sort_index);

  template<typename InputIterator, class Compare>
  void sort_index(InputIterator first, InputIterator last,
                  std::vector<size_t>& sort_index, Compare comp);



  // private stuff
  namespace detail {

    template<typename InputIterator, class Compare>
    void sort_index(InputIterator first, InputIterator last,
                    std::vector<size_t>& idx, Compare comp,
                    boost::single_pass_traversal_tag);

    // Specialization for random access iterator
    template<typename RandomAccessIterator, class Compare>
    void sort_index(RandomAccessIterator first, RandomAccessIterator last,
                    std::vector<size_t>& idx, Compare comp,
                    boost::random_access_traversal_tag);


    template<typename RandomAccessIterator, class Compare>
    class sort_index_Compare
    {
    public:
      sort_index_Compare(RandomAccessIterator it, Compare comp)
        : data_(it), compare_(comp)
      {
        using boost_concepts::ReadableIterator;
        BOOST_CONCEPT_ASSERT((ReadableIterator<RandomAccessIterator>));
        using boost_concepts::RandomAccessTraversal;
        BOOST_CONCEPT_ASSERT((RandomAccessTraversal<RandomAccessIterator>));
        typedef
          typename boost::iterator_reference<RandomAccessIterator>::type T;
        BOOST_CONCEPT_ASSERT((boost::BinaryPredicate<Compare, T, T>));
      }

      bool operator()(size_t i, size_t j) const
      { return compare_(data_[i], data_[j]); }

    private:
      RandomAccessIterator data_;
      Compare compare_;
    };

  } // end of namespace detail




  template<typename InputIterator>
  void sort_index(InputIterator first, InputIterator last,
                  std::vector<size_t>& idx)
  {
    typedef typename boost::iterator_value<InputIterator>::type T;
    // we use std::less<T>
    BOOST_CONCEPT_ASSERT((boost::LessThanComparable<T>));
    sort_index(first, last, idx, std::less<T>());
  }


  template<typename InputIterator, class Compare>
  void sort_index(InputIterator first, InputIterator last,
                  std::vector<size_t>& idx, Compare comp)
  {
    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
    typename boost::iterator_traversal<InputIterator>::type traversal;
    detail::sort_index(first, last, idx, comp, traversal);
  }


  // implementation of private functions
  namespace detail {

    // general implementation. copy range to a std::vector and call
    // random access version.
    template<typename InputIterator, class Compare>
    void sort_index(InputIterator first, InputIterator last,
                    std::vector<size_t>& idx, Compare comp,
                    boost::single_pass_traversal_tag tag)
    {
      typedef typename boost::iterator_value<InputIterator>::type T;
      // two concepts for vector<T>
      BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<T>));
      BOOST_CONCEPT_ASSERT((boost::SGIAssignable<T>));
      std::vector<T> vec(first, last);
      sort_index(vec.begin(), vec.end(), idx, comp,
                 boost::random_access_traversal_tag());
    }


    // Specialization for random access traversal
    template<typename RandomAccessIterator, class Compare>
    void sort_index(RandomAccessIterator first, RandomAccessIterator last,
                    std::vector<size_t>& idx, Compare comp,
                    boost::random_access_traversal_tag tag)
    {
      sort_index_Compare<RandomAccessIterator, Compare> compare(first, comp);
      // Peter would like to use boost::iota here, but that is only
      // available in boost v1.50 and newer, which is too recent at
      // time of writing.
      size_t n = last-first;
      idx.clear();
      idx.reserve(n);
      for (size_t i=0; i<n; ++i)
        idx.push_back(i);
      std::sort(idx.begin(), idx.end(), compare);
    }

  } // end of namespace detail

}}} // of namespace utility, yat, and theplu

#endif