]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 2007 Aaron Windsor | |
3 | // | |
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__ | |
10 | ||
11 | #include <vector> | |
12 | #include <algorithm> | |
13 | #include <boost/property_map/property_map.hpp> | |
14 | ||
15 | ||
16 | ||
17 | namespace boost | |
18 | { | |
19 | ||
20 | ||
21 | template <typename ItemToRankMap> | |
22 | struct rank_comparison | |
23 | { | |
24 | rank_comparison(ItemToRankMap arg_itrm) : itrm(arg_itrm) {} | |
25 | ||
26 | template <typename Item> | |
27 | bool operator() (Item x, Item y) const | |
28 | { | |
29 | return get(itrm, x) < get(itrm, y); | |
30 | } | |
31 | ||
32 | private: | |
33 | ItemToRankMap itrm; | |
34 | ||
35 | }; | |
36 | ||
37 | ||
38 | template <typename TupleType, | |
39 | int N, | |
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> | |
45 | > | |
46 | { | |
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; | |
51 | ||
52 | property_map_tuple_adaptor() {} | |
53 | ||
54 | property_map_tuple_adaptor(PropertyMapWrapper wrapper_map) : | |
55 | m_wrapper_map(wrapper_map) | |
56 | {} | |
57 | ||
58 | inline value_type operator[](const key_type& x) const | |
59 | { | |
60 | return get(m_wrapper_map, get<n>(x)); | |
61 | } | |
62 | ||
63 | static const int n = N; | |
64 | PropertyMapWrapper m_wrapper_map; | |
65 | ||
66 | }; | |
67 | ||
68 | ||
69 | ||
70 | ||
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, | |
75 | typename SizeType> | |
76 | void bucket_sort(ForwardIterator begin, | |
77 | ForwardIterator end, | |
78 | ItemToRankMap rank, | |
79 | SizeType range = 0) | |
80 | { | |
81 | #ifdef BOOST_GRAPH_PREFER_STD_LIB | |
82 | std::stable_sort(begin, end, rank_comparison<ItemToRankMap>(rank)); | |
83 | #else | |
84 | typedef std::vector | |
85 | < typename boost::property_traits<ItemToRankMap>::key_type > | |
86 | vector_of_values_t; | |
87 | typedef std::vector< vector_of_values_t > vector_of_vectors_t; | |
88 | ||
89 | if (!range) | |
90 | { | |
91 | rank_comparison<ItemToRankMap> cmp(rank); | |
92 | ForwardIterator max_by_rank = std::max_element(begin, end, cmp); | |
93 | if (max_by_rank == end) | |
94 | return; | |
95 | range = get(rank, *max_by_rank) + 1; | |
96 | } | |
97 | ||
98 | vector_of_vectors_t temp_values(range); | |
99 | ||
100 | for(ForwardIterator itr = begin; itr != end; ++itr) | |
101 | { | |
102 | temp_values[get(rank, *itr)].push_back(*itr); | |
103 | } | |
104 | ||
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 | |
109 | ) | |
110 | { | |
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 | |
114 | ) | |
115 | { | |
116 | *orig_seq_itr = *jtr; | |
117 | ++orig_seq_itr; | |
118 | } | |
119 | } | |
120 | #endif | |
121 | } | |
122 | ||
123 | ||
124 | template <typename ForwardIterator, typename ItemToRankMap> | |
125 | void bucket_sort(ForwardIterator begin, | |
126 | ForwardIterator end, | |
127 | ItemToRankMap rank) | |
128 | { | |
129 | bucket_sort(begin, end, rank, 0); | |
130 | } | |
131 | ||
132 | template <typename ForwardIterator> | |
133 | void bucket_sort(ForwardIterator begin, | |
134 | ForwardIterator end | |
135 | ) | |
136 | { | |
137 | bucket_sort(begin, end, identity_property_map()); | |
138 | } | |
139 | ||
140 | ||
141 | } //namespace boost | |
142 | ||
143 | ||
144 | #endif //__BUCKET_SORT_HPP__ |