bucket_sort.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

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