source: trunk/yat/utility/sort_index.h @ 3285

#ifndef _theplu_yat_utility_sort_index_
#define _theplu_yat_utility_sort_index_

// $Id: sort_index.h 3285 2014-07-11 10:59:46Z peter $

/*
  Copyright (C) 2008, 2010, 2014 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 {

  /**
     Create a vector \a sort_index containing the indeces of elements
     in a range [first, last). The elements of \a sort_index give the
     index of the range element which would have been stored in that
     position if the range had been sorted in place. The first element
     of \a sort_index gives the index of the least element in the
     range, and the last element of \a sort_index gives the index of
     the greatest element in the range. The function will not affect
     the range, i.e., ForwardIterator can be read-only.

     Type Requirements:
     - \c InputIterator is a model of \input_iterator
     - \c InputIterator::value_type is
     <a href=http://www.sgi.com/tech/stl/LessThanComparable.html>
     LessThan Comparable</a>
     - Either \c InputIterator::value_type is <a
     href=http://www.sgi.com/tech/stl/DefaultConstructible.html>
     Default Constructible</a> or \c InputIterator is
     \random_access_traversal_iterator.
     - Either \c InputIterator::value_type is
     <a href=http://www.sgi.com/tech/stl/Assignable.html>
     Assignable</a> or \c InputIterator is
     \random_access_traversal_iterator.

     \since New in yat 0.5. In versions prior 0.13 function was restricted to
     \forward_iterator with \c value_type convertible to \c double.
  */
  template<typename InputIterator>
  void sort_index(InputIterator first, InputIterator last,
                  std::vector<size_t>& sort_index);

  /**
     Same as sort_index(InputIterator, InputIterator,std::vector<size_t>&),
     but objects are compared with \c comp rather than with \c operator<.

     Type Requirements:
     - \c InputIterator is a model of \input_iterator
     - Either \c InputIterator::value_type is <a
     href=http://www.sgi.com/tech/stl/DefaultConstructible.html>
     Default Constructible</a> or \c InputIterator is
     \random_access_traversal_iterator.
     - Either \c InputIterator::value_type is
     <a href=http://www.sgi.com/tech/stl/Assignable.html>
     Assignable</a> or \c InputIterator is
     \random_access_traversal_iterator.
     - \c Compare is a model of
     <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
     Strict Weak Ordering</a>
     - \c Compare is
     <a href="http://www.sgi.com/tech/stl/CopyConstructible.html">
     Copy Constructible</a>
     - \c InputIterator::value_type is convertible to \c Compare's
       argument type

     \since New in yat 0.13
   */
  template<typename InputIterator, class Compare>
  void sort_index(InputIterator first, InputIterator last,
                  std::vector<size_t>& sort_index, Compare comp);


  /// \cond IGNORE_DOXYGEN

  // 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

  /// \endcond


  //////////////  template implementation ///////////////////////////

  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