1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
//=======================================================================
// 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__
|
