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