1 //=======================================================================
2 // Copyright 2007 Aaron Windsor
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
8 #ifndef __BUCKET_SORT_HPP__
9 #define __BUCKET_SORT_HPP__
13 #include <boost/property_map/property_map.hpp>
21 template <typename ItemToRankMap>
22 struct rank_comparison
24 rank_comparison(ItemToRankMap arg_itrm) : itrm(arg_itrm) {}
26 template <typename Item>
27 bool operator() (Item x, Item y) const
29 return get(itrm, x) < get(itrm, y);
38 template <typename TupleType,
40 typename PropertyMapWrapper = identity_property_map>
41 struct property_map_tuple_adaptor :
42 public put_get_helper< typename PropertyMapWrapper::value_type,
43 property_map_tuple_adaptor
44 <TupleType, N, PropertyMapWrapper>
47 typedef typename PropertyMapWrapper::reference reference;
48 typedef typename PropertyMapWrapper::value_type value_type;
49 typedef TupleType key_type;
50 typedef readable_property_map_tag category;
52 property_map_tuple_adaptor() {}
54 property_map_tuple_adaptor(PropertyMapWrapper wrapper_map) :
55 m_wrapper_map(wrapper_map)
58 inline value_type operator[](const key_type& x) const
60 return get(m_wrapper_map, get<n>(x));
63 static const int n = N;
64 PropertyMapWrapper m_wrapper_map;
71 // This function sorts a sequence of n items by their ranks in linear time,
72 // given that all ranks are in the range [0, range). This sort is stable.
73 template <typename ForwardIterator,
74 typename ItemToRankMap,
76 void bucket_sort(ForwardIterator begin,
81 #ifdef BOOST_GRAPH_PREFER_STD_LIB
82 std::stable_sort(begin, end, rank_comparison<ItemToRankMap>(rank));
85 < typename boost::property_traits<ItemToRankMap>::key_type >
87 typedef std::vector< vector_of_values_t > vector_of_vectors_t;
91 rank_comparison<ItemToRankMap> cmp(rank);
92 ForwardIterator max_by_rank = std::max_element(begin, end, cmp);
93 if (max_by_rank == end)
95 range = get(rank, *max_by_rank) + 1;
98 vector_of_vectors_t temp_values(range);
100 for(ForwardIterator itr = begin; itr != end; ++itr)
102 temp_values[get(rank, *itr)].push_back(*itr);
105 ForwardIterator orig_seq_itr = begin;
106 typename vector_of_vectors_t::iterator itr_end = temp_values.end();
107 for(typename vector_of_vectors_t::iterator itr = temp_values.begin();
108 itr != itr_end; ++itr
111 typename vector_of_values_t::iterator jtr_end = itr->end();
112 for(typename vector_of_values_t::iterator jtr = itr->begin();
113 jtr != jtr_end; ++jtr
116 *orig_seq_itr = *jtr;
124 template <typename ForwardIterator, typename ItemToRankMap>
125 void bucket_sort(ForwardIterator begin,
129 bucket_sort(begin, end, rank, 0);
132 template <typename ForwardIterator>
133 void bucket_sort(ForwardIterator begin,
137 bucket_sort(begin, end, identity_property_map());
144 #endif //__BUCKET_SORT_HPP__