]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright 2009 The Trustees of Indiana University. |
2 | ||
3 | // Distributed under the Boost Software License, Version 1.0. | |
4 | // (See accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | // Authors: Jeremiah Willcock | |
8 | // Andrew Lumsdaine | |
9 | ||
10 | #ifndef BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP | |
11 | #define BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP | |
12 | ||
13 | #include <boost/assert.hpp> | |
14 | ||
15 | namespace boost { | |
16 | namespace graph { | |
17 | namespace detail { | |
18 | ||
19 | template<typename InputIterator> | |
20 | size_t | |
21 | reserve_count_for_single_pass_helper(InputIterator, InputIterator, | |
22 | std::input_iterator_tag) | |
23 | { | |
24 | // Do nothing: we have no idea how much storage to reserve. | |
25 | return 0; | |
26 | } | |
27 | ||
28 | template<typename InputIterator> | |
29 | size_t | |
30 | reserve_count_for_single_pass_helper(InputIterator first, InputIterator last, | |
31 | std::random_access_iterator_tag) | |
32 | { | |
33 | using std::distance; | |
34 | typename std::iterator_traits<InputIterator>::difference_type n = | |
35 | distance(first, last); | |
36 | return (size_t)n; | |
37 | } | |
38 | ||
39 | template<typename InputIterator> | |
40 | size_t | |
41 | reserve_count_for_single_pass(InputIterator first, InputIterator last) { | |
42 | typedef typename std::iterator_traits<InputIterator>::iterator_category | |
43 | category; | |
44 | return reserve_count_for_single_pass_helper(first, last, category()); | |
45 | } | |
46 | ||
47 | template <typename KeyIterator, typename RowstartIterator, | |
48 | typename VerticesSize, typename KeyFilter, typename KeyTransform> | |
49 | void | |
50 | count_starts | |
51 | (KeyIterator begin, KeyIterator end, | |
52 | RowstartIterator starts, // Must support numverts + 1 elements | |
53 | VerticesSize numkeys, | |
54 | KeyFilter key_filter, | |
55 | KeyTransform key_transform) { | |
56 | ||
57 | typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex; | |
58 | ||
59 | // Put the degree of each vertex v into m_rowstart[v + 1] | |
60 | for (KeyIterator i = begin; i != end; ++i) { | |
61 | if (key_filter(*i)) { | |
62 | BOOST_ASSERT (key_transform(*i) < numkeys); | |
63 | ++starts[key_transform(*i) + 1]; | |
64 | } | |
65 | } | |
66 | ||
67 | // Compute the partial sum of the degrees to get the actual values of | |
68 | // m_rowstart | |
69 | EdgeIndex start_of_this_row = 0; | |
70 | starts[0] = start_of_this_row; | |
71 | for (VerticesSize i = 1; i < numkeys + 1; ++i) { | |
72 | start_of_this_row += starts[i]; | |
73 | starts[i] = start_of_this_row; | |
74 | } | |
75 | } | |
76 | ||
77 | template <typename KeyIterator, typename RowstartIterator, | |
78 | typename NumKeys, | |
79 | typename Value1InputIter, | |
80 | typename Value1OutputIter, typename KeyFilter, typename KeyTransform> | |
81 | void | |
82 | histogram_sort(KeyIterator key_begin, KeyIterator key_end, | |
83 | RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed | |
84 | NumKeys numkeys, | |
85 | Value1InputIter values1_begin, | |
86 | Value1OutputIter values1_out, | |
87 | KeyFilter key_filter, | |
88 | KeyTransform key_transform) { | |
89 | ||
90 | typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex; | |
91 | ||
92 | // Histogram sort the edges by their source vertices, putting the targets | |
93 | // into m_column. The index current_insert_positions[v] contains the next | |
94 | // location to insert out edges for vertex v. | |
95 | std::vector<EdgeIndex> | |
96 | current_insert_positions(rowstart, rowstart + numkeys); | |
97 | Value1InputIter v1i = values1_begin; | |
98 | for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i) { | |
99 | if (key_filter(*i)) { | |
100 | NumKeys source = key_transform(*i); | |
101 | BOOST_ASSERT (source < numkeys); | |
102 | EdgeIndex insert_pos = current_insert_positions[source]; | |
103 | ++current_insert_positions[source]; | |
104 | values1_out[insert_pos] = *v1i; | |
105 | } | |
106 | } | |
107 | } | |
108 | ||
109 | template <typename KeyIterator, typename RowstartIterator, | |
110 | typename NumKeys, | |
111 | typename Value1InputIter, | |
112 | typename Value1OutputIter, | |
113 | typename Value2InputIter, | |
114 | typename Value2OutputIter, | |
115 | typename KeyFilter, typename KeyTransform> | |
116 | void | |
117 | histogram_sort(KeyIterator key_begin, KeyIterator key_end, | |
118 | RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed | |
119 | NumKeys numkeys, | |
120 | Value1InputIter values1_begin, | |
121 | Value1OutputIter values1_out, | |
122 | Value2InputIter values2_begin, | |
123 | Value2OutputIter values2_out, | |
124 | KeyFilter key_filter, | |
125 | KeyTransform key_transform) { | |
126 | ||
127 | typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex; | |
128 | ||
129 | // Histogram sort the edges by their source vertices, putting the targets | |
130 | // into m_column. The index current_insert_positions[v] contains the next | |
131 | // location to insert out edges for vertex v. | |
132 | std::vector<EdgeIndex> | |
133 | current_insert_positions(rowstart, rowstart + numkeys); | |
134 | Value1InputIter v1i = values1_begin; | |
135 | Value2InputIter v2i = values2_begin; | |
136 | for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i, ++v2i) { | |
137 | if (key_filter(*i)) { | |
138 | NumKeys source = key_transform(*i); | |
139 | BOOST_ASSERT (source < numkeys); | |
140 | EdgeIndex insert_pos = current_insert_positions[source]; | |
141 | ++current_insert_positions[source]; | |
142 | values1_out[insert_pos] = *v1i; | |
143 | values2_out[insert_pos] = *v2i; | |
144 | } | |
145 | } | |
146 | } | |
147 | ||
148 | template <typename KeyIterator, typename RowstartIterator, | |
149 | typename NumKeys, | |
150 | typename Value1Iter, | |
151 | typename KeyTransform> | |
152 | void | |
153 | histogram_sort_inplace(KeyIterator key_begin, | |
154 | RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed | |
155 | NumKeys numkeys, | |
156 | Value1Iter values1, | |
157 | KeyTransform key_transform) { | |
158 | ||
159 | typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex; | |
160 | ||
161 | // 1. Copy m_rowstart (except last element) to get insert positions | |
162 | std::vector<EdgeIndex> insert_positions(rowstart, rowstart + numkeys); | |
163 | // 2. Swap the sources and targets into place | |
164 | for (size_t i = 0; i < rowstart[numkeys]; ++i) { | |
165 | BOOST_ASSERT (key_transform(key_begin[i]) < numkeys); | |
166 | // While edge i is not in the right bucket: | |
167 | while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) { | |
168 | // Add a slot in the right bucket | |
169 | size_t target_pos = insert_positions[key_transform(key_begin[i])]++; | |
170 | BOOST_ASSERT (target_pos < rowstart[key_transform(key_begin[i]) + 1]); | |
171 | if (target_pos == i) continue; | |
172 | // Swap this edge into place | |
173 | using std::swap; | |
174 | swap(key_begin[i], key_begin[target_pos]); | |
175 | swap(values1[i], values1[target_pos]); | |
176 | } | |
177 | } | |
178 | } | |
179 | ||
180 | template <typename KeyIterator, typename RowstartIterator, | |
181 | typename NumKeys, | |
182 | typename Value1Iter, | |
183 | typename Value2Iter, | |
184 | typename KeyTransform> | |
185 | void | |
186 | histogram_sort_inplace(KeyIterator key_begin, | |
187 | RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed | |
188 | NumKeys numkeys, | |
189 | Value1Iter values1, | |
190 | Value2Iter values2, | |
191 | KeyTransform key_transform) { | |
192 | ||
193 | typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex; | |
194 | ||
195 | // 1. Copy m_rowstart (except last element) to get insert positions | |
196 | std::vector<EdgeIndex> insert_positions(rowstart, rowstart + numkeys); | |
197 | // 2. Swap the sources and targets into place | |
198 | for (size_t i = 0; i < rowstart[numkeys]; ++i) { | |
199 | BOOST_ASSERT (key_transform(key_begin[i]) < numkeys); | |
200 | // While edge i is not in the right bucket: | |
201 | while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) { | |
202 | // Add a slot in the right bucket | |
203 | size_t target_pos = insert_positions[key_transform(key_begin[i])]++; | |
204 | BOOST_ASSERT (target_pos < rowstart[key_transform(key_begin[i]) + 1]); | |
205 | if (target_pos == i) continue; | |
206 | // Swap this edge into place | |
207 | using std::swap; | |
208 | swap(key_begin[i], key_begin[target_pos]); | |
209 | swap(values1[i], values1[target_pos]); | |
210 | swap(values2[i], values2[target_pos]); | |
211 | } | |
212 | } | |
213 | } | |
214 | ||
215 | template <typename InputIterator, typename VerticesSize> | |
216 | void split_into_separate_coords(InputIterator begin, InputIterator end, | |
217 | std::vector<VerticesSize>& firsts, | |
218 | std::vector<VerticesSize>& seconds) { | |
219 | firsts.clear(); | |
220 | seconds.clear(); | |
221 | size_t reserve_size | |
222 | = detail::reserve_count_for_single_pass(begin, end); | |
223 | firsts.reserve(reserve_size); | |
224 | seconds.reserve(reserve_size); | |
225 | for (; begin != end; ++begin) { | |
226 | std::pair<VerticesSize, VerticesSize> edge = *begin; | |
227 | firsts.push_back(edge.first); | |
228 | seconds.push_back(edge.second); | |
229 | } | |
230 | } | |
231 | ||
232 | template <typename InputIterator, typename VerticesSize, typename SourceFilter> | |
233 | void split_into_separate_coords_filtered | |
234 | (InputIterator begin, InputIterator end, | |
235 | std::vector<VerticesSize>& firsts, | |
236 | std::vector<VerticesSize>& seconds, | |
237 | const SourceFilter& filter) { | |
238 | firsts.clear(); | |
239 | seconds.clear(); | |
240 | for (; begin != end; ++begin) { | |
241 | std::pair<VerticesSize, VerticesSize> edge = *begin; | |
242 | if (filter(edge.first)) { | |
243 | firsts.push_back(edge.first); | |
244 | seconds.push_back(edge.second); | |
245 | } | |
246 | } | |
247 | } | |
248 | ||
249 | template <typename InputIterator, typename PropInputIterator, | |
250 | typename VerticesSize, typename PropType, typename SourceFilter> | |
251 | void split_into_separate_coords_filtered | |
252 | (InputIterator begin, InputIterator end, | |
253 | PropInputIterator props, | |
254 | std::vector<VerticesSize>& firsts, | |
255 | std::vector<VerticesSize>& seconds, | |
256 | std::vector<PropType>& props_out, | |
257 | const SourceFilter& filter) { | |
258 | firsts.clear(); | |
259 | seconds.clear(); | |
260 | props_out.clear(); | |
261 | for (; begin != end; ++begin) { | |
262 | std::pair<VerticesSize, VerticesSize> edge = *begin; | |
263 | if (filter(edge.first)) { | |
264 | firsts.push_back(edge.first); | |
265 | seconds.push_back(edge.second); | |
266 | props_out.push_back(*props); | |
267 | } | |
268 | ++props; | |
269 | } | |
270 | } | |
271 | ||
272 | // The versions of operator()() here can't return by reference because the | |
273 | // actual type passed in may not match Pair, in which case the reference | |
274 | // parameter is bound to a temporary that could end up dangling after the | |
275 | // operator returns. | |
276 | ||
277 | template <typename Pair> | |
278 | struct project1st { | |
279 | typedef typename Pair::first_type result_type; | |
280 | result_type operator()(const Pair& p) const {return p.first;} | |
281 | }; | |
282 | ||
283 | template <typename Pair> | |
284 | struct project2nd { | |
285 | typedef typename Pair::second_type result_type; | |
286 | result_type operator()(const Pair& p) const {return p.second;} | |
287 | }; | |
288 | ||
289 | } | |
290 | } | |
291 | } | |
292 | ||
293 | #endif // BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP |