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