graph/planar_detail/bucket_sort.hpp

0001 //=======================================================================
0002 // Copyright 2007 Aaron Windsor
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See
0005 // accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007 //=======================================================================
0008 #ifndef __BUCKET_SORT_HPP__
0009 #define __BUCKET_SORT_HPP__
0010
0011 #include <vector>
0012 #include <algorithm>
0013 #include <boost/property_map/property_map.hpp>
0014
0015 namespace boost
0016 {
0017
0018 template < typename ItemToRankMap > struct rank_comparison
0019 {
0020     rank_comparison(ItemToRankMap arg_itrm) : itrm(arg_itrm) {}
0021
0022     template < typename Item > bool operator()(Item x, Item y) const
0023     {
0024         return get(itrm, x) < get(itrm, y);
0025     }
0026
0027 private:
0028     ItemToRankMap itrm;
0029 };
0030
0031 template < typename TupleType, int N,
0032     typename PropertyMapWrapper = identity_property_map >
0033 struct property_map_tuple_adaptor
0034 : public put_get_helper< typename PropertyMapWrapper::value_type,
0035       property_map_tuple_adaptor< TupleType, N, PropertyMapWrapper > >
0036 {
0037     typedef typename PropertyMapWrapper::reference reference;
0038     typedef typename PropertyMapWrapper::value_type value_type;
0039     typedef TupleType key_type;
0040     typedef readable_property_map_tag category;
0041
0042     property_map_tuple_adaptor() {}
0043
0044     property_map_tuple_adaptor(PropertyMapWrapper wrapper_map)
0045     : m_wrapper_map(wrapper_map)
0046     {
0047     }
0048
0049     inline value_type operator[](const key_type& x) const
0050     {
0051         return get(m_wrapper_map, get< n >(x));
0052     }
0053
0054     static const int n = N;
0055     PropertyMapWrapper m_wrapper_map;
0056 };
0057
0058 // This function sorts a sequence of n items by their ranks in linear time,
0059 // given that all ranks are in the range [0, range). This sort is stable.
0060 template < typename ForwardIterator, typename ItemToRankMap, typename SizeType >
0061 void bucket_sort(ForwardIterator begin, ForwardIterator end, ItemToRankMap rank,
0062     SizeType range = 0)
0063 {
0064 #ifdef BOOST_GRAPH_PREFER_STD_LIB
0065     std::stable_sort(begin, end, rank_comparison< ItemToRankMap >(rank));
0066 #else
0067     typedef std::vector<
0068         typename boost::property_traits< ItemToRankMap >::key_type >
0069         vector_of_values_t;
0070     typedef std::vector< vector_of_values_t > vector_of_vectors_t;
0071
0072     if (!range)
0073     {
0074         rank_comparison< ItemToRankMap > cmp(rank);
0075         ForwardIterator max_by_rank = std::max_element(begin, end, cmp);
0076         if (max_by_rank == end)
0077             return;
0078         range = get(rank, *max_by_rank) + 1;
0079     }
0080
0081     vector_of_vectors_t temp_values(range);
0082
0083     for (ForwardIterator itr = begin; itr != end; ++itr)
0084     {
0085         temp_values[get(rank, *itr)].push_back(*itr);
0086     }
0087
0088     ForwardIterator orig_seq_itr = begin;
0089     typename vector_of_vectors_t::iterator itr_end = temp_values.end();
0090     for (typename vector_of_vectors_t::iterator itr = temp_values.begin();
0091          itr != itr_end; ++itr)
0092     {
0093         typename vector_of_values_t::iterator jtr_end = itr->end();
0094         for (typename vector_of_values_t::iterator jtr = itr->begin();
0095              jtr != jtr_end; ++jtr)
0096         {
0097             *orig_seq_itr = *jtr;
0098             ++orig_seq_itr;
0099         }
0100     }
0101 #endif
0102 }
0103
0104 template < typename ForwardIterator, typename ItemToRankMap >
0105 void bucket_sort(ForwardIterator begin, ForwardIterator end, ItemToRankMap rank)
0106 {
0107     bucket_sort(begin, end, rank, 0);
0108 }
0109
0110 template < typename ForwardIterator >
0111 void bucket_sort(ForwardIterator begin, ForwardIterator end)
0112 {
0113     bucket_sort(begin, end, identity_property_map());
0114 }
0115
0116 } // namespace boost
0117
0118 #endif //__BUCKET_SORT_HPP__