//  Boost general library sorting_view.hpp header file ---------------------------//
//  what:   indirect view of sorted array
//  who:    contributed by Boris Kats
//  when:   February 2016
//  Copyright © 2007 Boris Kats
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_SORTING_VIEW_INCLUDED
#define BOOST_SORTING_VIEW_INCLUDED

#if defined(_MSC_VER) && (_MSC_VER >= 1020)
# pragma once
#endif

#include <vector>
#include <functional>
#include <algorithm>
#include <cassert>
namespace boost {
template<typename Iterator>
struct iterator_less: public std::binary_function<Iterator,Iterator,bool>
{
  bool operator()(const Iterator & x, const Iterator & y) const
  { 
     typedef typename std::iterator_traits<Iterator>::value_type value_type;
     return std::less<value_type>()(*x,*y);
  }
};

template<typename Iterator>
struct iterator_greater: public std::binary_function<Iterator,Iterator,bool>
{
  bool operator()(const Iterator & x, const Iterator & y) const
  {  
     typedef typename std::iterator_traits<Iterator>::value_type value_type;
     return std::greater<value_type>()(*x,*y);
  }
};

template< class Iterator, class Compare >
inline std::vector<int> sorting_view(const Iterator  begin, const Iterator  end, Compare compare)
{
  int size = (int)std::distance(begin,end);
  std::vector<int> view(size);
  std::vector<Iterator> temp(size);
  for(int i = 0; i < size; ++i)
    temp[i] = begin+i;
  std::sort(temp.begin(),temp.end(),compare);
  for(int i = 0; i < size; ++i)
      view[i] = (int)std::distance(begin,temp[i]);
  return view;
}


template< class Iterator>
inline std::vector<int> sorting_view(const Iterator  begin, const Iterator  end)
{
  return sorting_view(begin,end,iterator_less<Iterator>());
}

template<typename Iterator>
inline void apply_view(const Iterator & begin, const Iterator & end, const std::vector<int> & view)
{
  typedef typename std::iterator_traits<Iterator>::value_type value_type;
  int size = (int)std::distance(begin,end);
  assert(size == (int)view.size());
  std::vector<value_type> res(size);
  for(int i = 0; i < size; ++i)
      res[i] = *(begin+view[i]);
  for(int i = 0; i < size; ++i)
    *(begin +i) = res[i];
}
} // namespace
#endif