third_party/boost/include/boost/graph/detail/histogram_sort.hpp - webm/webmlive - Git at Google

 // Copyright 2009 The Trustees of Indiana University.

 // 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)

 //  Authors: Jeremiah Willcock
 //           Andrew Lumsdaine

 #ifndef BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
 #define BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP

 #include <boost/assert.hpp>

 namespace boost {
   namespace graph {
     namespace detail {

 template<typename InputIterator>
 size_t
 reserve_count_for_single_pass_helper(InputIterator, InputIterator,
                                      std::input_iterator_tag)
 {
   // Do nothing: we have no idea how much storage to reserve.
   return 0;
 }

 template<typename InputIterator>
 size_t
 reserve_count_for_single_pass_helper(InputIterator first, InputIterator last,
                                      std::random_access_iterator_tag)
 {
   using std::distance;
   typename std::iterator_traits<InputIterator>::difference_type n =
     distance(first, last);
   return (size_t)n;
 }

 template<typename InputIterator>
 size_t
 reserve_count_for_single_pass(InputIterator first, InputIterator last) {
   typedef typename std::iterator_traits<InputIterator>::iterator_category
     category;
   return reserve_count_for_single_pass_helper(first, last, category());
 }

 template <typename KeyIterator, typename RowstartIterator,
           typename VerticesSize, typename KeyFilter, typename KeyTransform>
 void
 count_starts
   (KeyIterator begin, KeyIterator end,
    RowstartIterator starts, // Must support numverts + 1 elements
    VerticesSize numkeys,
    KeyFilter key_filter,
    KeyTransform key_transform) {

   typedef VerticesSize vertices_size_type;
   typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;

   // Put the degree of each vertex v into m_rowstart[v + 1]
   for (KeyIterator i = begin; i != end; ++i) {
     if (key_filter(*i)) {
       ++starts[key_transform(*i) + 1];
     }
   }

   // Compute the partial sum of the degrees to get the actual values of
   // m_rowstart
   EdgeIndex start_of_this_row = 0;
   starts[0] = start_of_this_row;
   for (vertices_size_type i = 1; i <= numkeys; ++i) {
     start_of_this_row += starts[i];
     starts[i] = start_of_this_row;
   }
 }

 template <typename KeyIterator, typename RowstartIterator,
           typename NumKeys,
           typename Value1InputIter,
           typename Value1OutputIter, typename KeyFilter, typename KeyTransform>
 void
 histogram_sort(KeyIterator key_begin, KeyIterator key_end,
                RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
                NumKeys numkeys,
                Value1InputIter values1_begin,
                Value1OutputIter values1_out,
                KeyFilter key_filter,
                KeyTransform key_transform) {

   typedef NumKeys vertices_size_type;
   typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;

   // Histogram sort the edges by their source vertices, putting the targets
   // into m_column.  The index current_insert_positions[v] contains the next
   // location to insert out edges for vertex v.
   std::vector<EdgeIndex>
     current_insert_positions(rowstart, rowstart + numkeys);
   Value1InputIter v1i = values1_begin;
   for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i) {
     if (key_filter(*i)) {
       vertices_size_type source = key_transform(*i);
       EdgeIndex insert_pos = current_insert_positions[source];
       ++current_insert_positions[source];
       values1_out[insert_pos] = *v1i;
     }
   }
 }

 template <typename KeyIterator, typename RowstartIterator,
           typename NumKeys,
           typename Value1InputIter,
           typename Value1OutputIter,
           typename Value2InputIter,
           typename Value2OutputIter,
           typename KeyFilter, typename KeyTransform>
 void
 histogram_sort(KeyIterator key_begin, KeyIterator key_end,
                RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
                NumKeys numkeys,
                Value1InputIter values1_begin,
                Value1OutputIter values1_out,
                Value2InputIter values2_begin,
                Value2OutputIter values2_out,
                KeyFilter key_filter,
                KeyTransform key_transform) {

   typedef NumKeys vertices_size_type;
   typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;

   // Histogram sort the edges by their source vertices, putting the targets
   // into m_column.  The index current_insert_positions[v] contains the next
   // location to insert out edges for vertex v.
   std::vector<EdgeIndex>
     current_insert_positions(rowstart, rowstart + numkeys);
   Value1InputIter v1i = values1_begin;
   Value2InputIter v2i = values2_begin;
   for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i, ++v2i) {
     if (key_filter(*i)) {
       vertices_size_type source = key_transform(*i);
       EdgeIndex insert_pos = current_insert_positions[source];
       ++current_insert_positions[source];
       values1_out[insert_pos] = *v1i;
       values2_out[insert_pos] = *v2i;
     }
   }
 }

 template <typename KeyIterator, typename RowstartIterator,
           typename NumKeys,
           typename Value1Iter,
           typename KeyTransform>
 void
 histogram_sort_inplace(KeyIterator key_begin,
                        RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
                        NumKeys numkeys,
                        Value1Iter values1,
                        KeyTransform key_transform) {

   typedef NumKeys vertices_size_type;
   typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;

   // 1. Copy m_rowstart (except last element) to get insert positions
   std::vector<EdgeIndex> insert_positions(rowstart, rowstart + numkeys);
   // 2. Swap the sources and targets into place
   for (size_t i = 0; i < rowstart[numkeys]; ++i) {
     // While edge i is not in the right bucket:
     while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) {
       // Add a slot in the right bucket
       size_t target_pos = insert_positions[key_transform(key_begin[i])]++;
       BOOST_ASSERT (target_pos < rowstart[key_transform(key_begin[i]) + 1]);
       if (target_pos == i) continue;
       // Swap this edge into place
       using std::swap;
       swap(key_begin[i], key_begin[target_pos]);
       swap(values1[i], values1[target_pos]);
     }
   }
 }

 template <typename KeyIterator, typename RowstartIterator,
           typename NumKeys,
           typename Value1Iter,
           typename Value2Iter,
           typename KeyTransform>
 void
 histogram_sort_inplace(KeyIterator key_begin,
                        RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
                        NumKeys numkeys,
                        Value1Iter values1,
                        Value2Iter values2,
                        KeyTransform key_transform) {

   typedef NumKeys vertices_size_type;
   typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;

   // 1. Copy m_rowstart (except last element) to get insert positions
   std::vector<EdgeIndex> insert_positions(rowstart, rowstart + numkeys);
   // 2. Swap the sources and targets into place
   for (size_t i = 0; i < rowstart[numkeys]; ++i) {
     // While edge i is not in the right bucket:
     while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) {
       // Add a slot in the right bucket
       size_t target_pos = insert_positions[key_transform(key_begin[i])]++;
       BOOST_ASSERT (target_pos < rowstart[key_transform(key_begin[i]) + 1]);
       if (target_pos == i) continue;
       // Swap this edge into place
       using std::swap;
       swap(key_begin[i], key_begin[target_pos]);
       swap(values1[i], values1[target_pos]);
       swap(values2[i], values2[target_pos]);
     }
   }
 }

 template <typename InputIterator, typename VerticesSize>
 void split_into_separate_coords(InputIterator begin, InputIterator end,
                                 std::vector<VerticesSize>& firsts,
                                 std::vector<VerticesSize>& seconds) {
   firsts.clear();
   seconds.clear();
   size_t reserve_size
     = detail::reserve_count_for_single_pass(begin, end);
   firsts.reserve(reserve_size);
   seconds.reserve(reserve_size);
   for (; begin != end; ++begin) {
     std::pair<VerticesSize, VerticesSize> edge = *begin;
     firsts.push_back(edge.first);
     seconds.push_back(edge.second);
   }
 }

 template <typename InputIterator, typename VerticesSize, typename SourceFilter>
 void split_into_separate_coords_filtered
   (InputIterator begin, InputIterator end,
    std::vector<VerticesSize>& firsts,
    std::vector<VerticesSize>& seconds,
    const SourceFilter& filter) {
   firsts.clear();
   seconds.clear();
   for (; begin != end; ++begin) {
     std::pair<VerticesSize, VerticesSize> edge = *begin;
     if (filter(edge.first)) {
       firsts.push_back(edge.first);
       seconds.push_back(edge.second);
     }
   }
 }

 template <typename InputIterator, typename PropInputIterator,
           typename VerticesSize, typename PropType, typename SourceFilter>
 void 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) {
   firsts.clear();
   seconds.clear();
   props_out.clear();
   for (; begin != end; ++begin) {
     std::pair<VerticesSize, VerticesSize> edge = *begin;
     if (filter(edge.first)) {
       firsts.push_back(edge.first);
       seconds.push_back(edge.second);
       props_out.push_back(*props);
     }
     ++props;
   }
 }

 template <typename Pair>
 struct project1st {
   typedef typename Pair::first_type result_type;
   const result_type& operator()(const Pair& p) const {return p.first;}
 };

 template <typename Pair>
 struct project2nd {
   typedef typename Pair::second_type result_type;
   const result_type& operator()(const Pair& p) const {return p.second;}
 };

     }
   }
 }

 #endif // BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
	// Copyright 2009 The Trustees of Indiana University.

	// 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)

	// Authors: Jeremiah Willcock
	// Andrew Lumsdaine

	#ifndef BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
	#define BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP

	#include <boost/assert.hpp>

	namespace boost {
	namespace graph {
	namespace detail {

	template<typename InputIterator>
	size_t
	reserve_count_for_single_pass_helper(InputIterator, InputIterator,
	std::input_iterator_tag)
	{
	// Do nothing: we have no idea how much storage to reserve.
	return 0;
	}

	template<typename InputIterator>
	size_t
	reserve_count_for_single_pass_helper(InputIterator first, InputIterator last,
	std::random_access_iterator_tag)
	{
	using std::distance;
	typename std::iterator_traits<InputIterator>::difference_type n =
	distance(first, last);
	return (size_t)n;
	}

	template<typename InputIterator>
	size_t
	reserve_count_for_single_pass(InputIterator first, InputIterator last) {
	typedef typename std::iterator_traits<InputIterator>::iterator_category
	category;
	return reserve_count_for_single_pass_helper(first, last, category());
	}

	template <typename KeyIterator, typename RowstartIterator,
	typename VerticesSize, typename KeyFilter, typename KeyTransform>
	void
	count_starts
	(KeyIterator begin, KeyIterator end,
	RowstartIterator starts, // Must support numverts + 1 elements
	VerticesSize numkeys,
	KeyFilter key_filter,
	KeyTransform key_transform) {

	typedef VerticesSize vertices_size_type;
	typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;

	// Put the degree of each vertex v into m_rowstart[v + 1]
	for (KeyIterator i = begin; i != end; ++i) {
	if (key_filter(*i)) {
	++starts[key_transform(*i) + 1];
	}
	}

	// Compute the partial sum of the degrees to get the actual values of
	// m_rowstart
	EdgeIndex start_of_this_row = 0;
	starts[0] = start_of_this_row;
	for (vertices_size_type i = 1; i <= numkeys; ++i) {
	start_of_this_row += starts[i];
	starts[i] = start_of_this_row;
	}
	}

	template <typename KeyIterator, typename RowstartIterator,
	typename NumKeys,
	typename Value1InputIter,
	typename Value1OutputIter, typename KeyFilter, typename KeyTransform>
	void
	histogram_sort(KeyIterator key_begin, KeyIterator key_end,
	RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
	NumKeys numkeys,
	Value1InputIter values1_begin,
	Value1OutputIter values1_out,
	KeyFilter key_filter,
	KeyTransform key_transform) {

	typedef NumKeys vertices_size_type;
	typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;

	// Histogram sort the edges by their source vertices, putting the targets
	// into m_column. The index current_insert_positions[v] contains the next
	// location to insert out edges for vertex v.
	std::vector<EdgeIndex>
	current_insert_positions(rowstart, rowstart + numkeys);
	Value1InputIter v1i = values1_begin;
	for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i) {
	if (key_filter(*i)) {
	vertices_size_type source = key_transform(*i);
	EdgeIndex insert_pos = current_insert_positions[source];
	++current_insert_positions[source];
	values1_out[insert_pos] = *v1i;
	}
	}
	}

	template <typename KeyIterator, typename RowstartIterator,
	typename NumKeys,
	typename Value1InputIter,
	typename Value1OutputIter,
	typename Value2InputIter,
	typename Value2OutputIter,
	typename KeyFilter, typename KeyTransform>
	void
	histogram_sort(KeyIterator key_begin, KeyIterator key_end,
	RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
	NumKeys numkeys,
	Value1InputIter values1_begin,
	Value1OutputIter values1_out,
	Value2InputIter values2_begin,
	Value2OutputIter values2_out,
	KeyFilter key_filter,
	KeyTransform key_transform) {

	typedef NumKeys vertices_size_type;
	typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;

	// Histogram sort the edges by their source vertices, putting the targets
	// into m_column. The index current_insert_positions[v] contains the next
	// location to insert out edges for vertex v.
	std::vector<EdgeIndex>
	current_insert_positions(rowstart, rowstart + numkeys);
	Value1InputIter v1i = values1_begin;
	Value2InputIter v2i = values2_begin;
	for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i, ++v2i) {
	if (key_filter(*i)) {
	vertices_size_type source = key_transform(*i);
	EdgeIndex insert_pos = current_insert_positions[source];
	++current_insert_positions[source];
	values1_out[insert_pos] = *v1i;
	values2_out[insert_pos] = *v2i;
	}
	}
	}

	template <typename KeyIterator, typename RowstartIterator,
	typename NumKeys,
	typename Value1Iter,
	typename KeyTransform>
	void
	histogram_sort_inplace(KeyIterator key_begin,
	RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
	NumKeys numkeys,
	Value1Iter values1,
	KeyTransform key_transform) {

	typedef NumKeys vertices_size_type;
	typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;

	// 1. Copy m_rowstart (except last element) to get insert positions
	std::vector<EdgeIndex> insert_positions(rowstart, rowstart + numkeys);
	// 2. Swap the sources and targets into place
	for (size_t i = 0; i < rowstart[numkeys]; ++i) {
	// While edge i is not in the right bucket:
	while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) {
	// Add a slot in the right bucket
	size_t target_pos = insert_positions[key_transform(key_begin[i])]++;
	BOOST_ASSERT (target_pos < rowstart[key_transform(key_begin[i]) + 1]);
	if (target_pos == i) continue;
	// Swap this edge into place
	using std::swap;
	swap(key_begin[i], key_begin[target_pos]);
	swap(values1[i], values1[target_pos]);
	}
	}
	}

	template <typename KeyIterator, typename RowstartIterator,
	typename NumKeys,
	typename Value1Iter,
	typename Value2Iter,
	typename KeyTransform>
	void
	histogram_sort_inplace(KeyIterator key_begin,
	RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
	NumKeys numkeys,
	Value1Iter values1,
	Value2Iter values2,
	KeyTransform key_transform) {

	typedef NumKeys vertices_size_type;
	typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;

	// 1. Copy m_rowstart (except last element) to get insert positions
	std::vector<EdgeIndex> insert_positions(rowstart, rowstart + numkeys);
	// 2. Swap the sources and targets into place
	for (size_t i = 0; i < rowstart[numkeys]; ++i) {
	// While edge i is not in the right bucket:
	while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) {
	// Add a slot in the right bucket
	size_t target_pos = insert_positions[key_transform(key_begin[i])]++;
	BOOST_ASSERT (target_pos < rowstart[key_transform(key_begin[i]) + 1]);
	if (target_pos == i) continue;
	// Swap this edge into place
	using std::swap;
	swap(key_begin[i], key_begin[target_pos]);
	swap(values1[i], values1[target_pos]);
	swap(values2[i], values2[target_pos]);
	}
	}
	}

	template <typename InputIterator, typename VerticesSize>
	void split_into_separate_coords(InputIterator begin, InputIterator end,
	std::vector<VerticesSize>& firsts,
	std::vector<VerticesSize>& seconds) {
	firsts.clear();
	seconds.clear();
	size_t reserve_size
	= detail::reserve_count_for_single_pass(begin, end);
	firsts.reserve(reserve_size);
	seconds.reserve(reserve_size);
	for (; begin != end; ++begin) {
	std::pair<VerticesSize, VerticesSize> edge = *begin;
	firsts.push_back(edge.first);
	seconds.push_back(edge.second);
	}
	}

	template <typename InputIterator, typename VerticesSize, typename SourceFilter>
	void split_into_separate_coords_filtered
	(InputIterator begin, InputIterator end,
	std::vector<VerticesSize>& firsts,
	std::vector<VerticesSize>& seconds,
	const SourceFilter& filter) {
	firsts.clear();
	seconds.clear();
	for (; begin != end; ++begin) {
	std::pair<VerticesSize, VerticesSize> edge = *begin;
	if (filter(edge.first)) {
	firsts.push_back(edge.first);
	seconds.push_back(edge.second);
	}
	}
	}

	template <typename InputIterator, typename PropInputIterator,
	typename VerticesSize, typename PropType, typename SourceFilter>
	void 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) {
	firsts.clear();
	seconds.clear();
	props_out.clear();
	for (; begin != end; ++begin) {
	std::pair<VerticesSize, VerticesSize> edge = *begin;
	if (filter(edge.first)) {
	firsts.push_back(edge.first);
	seconds.push_back(edge.second);
	props_out.push_back(*props);
	}
	++props;
	}
	}

	template <typename Pair>
	struct project1st {
	typedef typename Pair::first_type result_type;
	const result_type& operator()(const Pair& p) const {return p.first;}
	};

	template <typename Pair>
	struct project2nd {
	typedef typename Pair::second_type result_type;
	const result_type& operator()(const Pair& p) const {return p.second;}
	};

	}
	}
	}

	#endif // BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP