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