robot/include/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
                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))
                {
                    BOOST_ASSERT(key_transform(*i) < numkeys);
                    ++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 (VerticesSize i = 1; i < numkeys + 1; ++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
                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))
                {
                    NumKeys source = key_transform(*i);
                    BOOST_ASSERT(source < numkeys);
                    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
                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))
                {
                    NumKeys source = key_transform(*i);
                    BOOST_ASSERT(source < numkeys);
                    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
                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)
            {
                BOOST_ASSERT(key_transform(key_begin[i]) < numkeys);
                // 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
                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)
            {
                BOOST_ASSERT(key_transform(key_begin[i]) < numkeys);
                // 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;
            }
        }

        // The versions of operator()() here can't return by reference because
        // the actual type passed in may not match Pair, in which case the
        // reference parameter is bound to a temporary that could end up
        // dangling after the operator returns.

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

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

    }
}
}

#endif // BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP