boost/graph/planar_detail/bucket_sort.hpp
//=======================================================================
// 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__