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

#ifndef _theplu_yat_utility_sort_index_
#define _theplu_yat_utility_sort_index_

// $Id: sort_index.h 3238 2014-05-24 10:27:39Z 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 <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>
     - \c InputIterator::value_type is
     <a href=http://www.sgi.com/tech/stl/DefaultConstructible.html>
     Default Constructible</a> and
     <a href=http://www.sgi.com/tech/stl/Assignable.html>
     Assignable</a>

     \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
     - \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/Assignable.html">
     Assignable</a>
     - \c InputIterator::value_type is
     <a href=http://www.sgi.com/tech/stl/DefaultConstructible.html>
     Default Constructible</a> and
     <a href=http://www.sgi.com/tech/stl/Assignable.html>
     Assignable</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,
                    std::input_iterator_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,
                    std::random_access_iterator_tag);


    template<typename RandomAccessIterator, class Compare>
    class sort_index_Compare
    {
    public:
      sort_index_Compare(RandomAccessIterator it, Compare comp)
        : data_(it), compare_(comp) {}

      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)
  {
    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
    typedef typename std::iterator_traits<InputIterator>::value_type T;
    BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<T>));
    BOOST_CONCEPT_ASSERT((boost::SGIAssignable<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>));
    typedef typename std::iterator_traits<InputIterator> traits;
    typedef typename std::iterator_traits<InputIterator>::value_type T;
    BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<T>));
    BOOST_CONCEPT_ASSERT((boost::SGIAssignable<T>));
    BOOST_CONCEPT_ASSERT((boost::Assignable<Compare>));

    typedef typename traits::iterator_category category;
    detail::sort_index(first, last, idx, comp, category());
  }


  // 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,
                    std::input_iterator_tag tag)
    {
      typedef typename std::iterator_traits<InputIterator>::value_type T;
      std::vector<T> vec(first, last);
      sort_index(vec.begin(), vec.end(), idx, comp,
                 std::random_access_iterator_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,
                    std::random_access_iterator_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