//=======================================================================

// Copyright 2007 Aaron Windsor

//

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

#define __BUCKET_SORT_HPP__



#include <vector>

#include <algorithm>

#include <boost/property_map.hpp>







namespace boost

{





  template <typename ItemToRankMap>

  struct rank_comparison

  {

    rank_comparison(ItemToRankMap arg_itrm) : itrm(arg_itrm) {}



    template <typename Item>

    bool operator() (Item x, Item y) const

    {

      return get(itrm, x) < get(itrm, y);

    }

    

  private:

    ItemToRankMap itrm;



  };





  template <typename TupleType, 

            int N, 

            typename PropertyMapWrapper = identity_property_map>

  struct property_map_tuple_adaptor :

    public put_get_helper< typename PropertyMapWrapper::value_type,

                           property_map_tuple_adaptor

                             <TupleType, N, PropertyMapWrapper>

                           >

  {

    typedef typename PropertyMapWrapper::reference reference;

    typedef typename PropertyMapWrapper::value_type value_type;

    typedef TupleType key_type;

    typedef readable_property_map_tag category;



    property_map_tuple_adaptor() {}

    

    property_map_tuple_adaptor(PropertyMapWrapper wrapper_map) :

      m_wrapper_map(wrapper_map)

    {}



    inline value_type operator[](const key_type& x) const

    {

      return get(m_wrapper_map, get<n>(x));

    }



    static const int n = N;

    PropertyMapWrapper m_wrapper_map;



  };









  // This function sorts a sequence of n items by their ranks in linear time,

  // given that all ranks are in the range [0, range). This sort is stable.

  template <typename ForwardIterator, 

            typename ItemToRankMap, 

            typename SizeType>

  void bucket_sort(ForwardIterator begin, 

                   ForwardIterator end, 

                   ItemToRankMap rank,

                   SizeType range = 0)  

  {

#ifdef BOOST_GRAPH_PREFER_STD_LIB

    std::stable_sort(begin, end, rank_comparison<ItemToRankMap>(rank));

#else

    typedef std::vector

      < typename boost::property_traits<ItemToRankMap>::key_type >

      vector_of_values_t;

    typedef std::vector< vector_of_values_t > vector_of_vectors_t;



    if (!range)

      {

        rank_comparison<ItemToRankMap> cmp(rank);

        ForwardIterator max_by_rank = std::max_element(begin, end, cmp);

        if (max_by_rank == end)

          return;

        range = get(rank, *max_by_rank) + 1;

      }



    vector_of_vectors_t temp_values(range);



    for(ForwardIterator itr = begin; itr != end; ++itr)

      {

        temp_values[get(rank, *itr)].push_back(*itr);

      }



    ForwardIterator orig_seq_itr = begin;

    typename vector_of_vectors_t::iterator itr_end = temp_values.end();

    for(typename vector_of_vectors_t::iterator itr = temp_values.begin(); 

        itr != itr_end; ++itr

        )

      {

        typename vector_of_values_t::iterator jtr_end = itr->end();

        for(typename vector_of_values_t::iterator jtr = itr->begin(); 

            jtr != jtr_end; ++jtr

            )

        {

          *orig_seq_itr = *jtr;

          ++orig_seq_itr;

        }

      }

#endif

  }



  

  template <typename ForwardIterator, typename ItemToRankMap>

  void bucket_sort(ForwardIterator begin, 

                   ForwardIterator end, 

                   ItemToRankMap rank)  

  {

    bucket_sort(begin, end, rank, 0);

  }



  template <typename ForwardIterator>

  void bucket_sort(ForwardIterator begin, 

                   ForwardIterator end 

                   )  

  {

    bucket_sort(begin, end, identity_property_map());

  }

  



} //namespace boost





#endif //__BUCKET_SORT_HPP__

