ceph/src/boost/libs/graph/include/boost/graph/detail/histogram_sort.hpp

   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