Last active
December 17, 2015 19:58
-
-
Save rezoo/5663872 to your computer and use it in GitHub Desktop.
Implementation of sort_by_key algorithms.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #pragma once | |
| #include <algorithm> | |
| #include <functional> | |
| #include <boost/iterator/iterator_facade.hpp> | |
| #include <boost/tuple/tuple.hpp> | |
| namespace aoba { | |
| namespace detail { | |
| template<typename KeyIterator, typename ValueIterator> | |
| struct sort_keyvalue_iter_helper_type { | |
| typedef boost::tuple< | |
| typename std::iterator_traits<KeyIterator>::value_type, | |
| typename std::iterator_traits<ValueIterator>::value_type> value_type; | |
| typedef boost::tuple< | |
| typename std::iterator_traits<KeyIterator>::reference, | |
| typename std::iterator_traits<ValueIterator>::reference> reference; | |
| }; | |
| template<typename KeyIterator, typename ValueIterator> | |
| class sort_keyvalue_iterator | |
| : public boost::iterator_facade< | |
| sort_keyvalue_iterator<KeyIterator, ValueIterator>, | |
| typename sort_keyvalue_iter_helper_type< | |
| KeyIterator, ValueIterator>::value_type, | |
| std::random_access_iterator_tag, | |
| typename sort_keyvalue_iter_helper_type< | |
| KeyIterator, ValueIterator>::reference, | |
| typename std::iterator_traits<KeyIterator>::difference_type> | |
| { | |
| public: | |
| sort_keyvalue_iterator() {} | |
| sort_keyvalue_iterator(KeyIterator key_iter, ValueIterator value_iter) | |
| : m_key_iter(key_iter), m_value_iter(value_iter) {} | |
| private: | |
| KeyIterator m_key_iter; | |
| ValueIterator m_value_iter; | |
| friend class boost::iterator_core_access; | |
| void increment() | |
| { | |
| ++m_key_iter; | |
| ++m_value_iter; | |
| } | |
| void decrement() | |
| { | |
| --m_key_iter; | |
| --m_value_iter; | |
| } | |
| bool equal(const sort_keyvalue_iterator& other) const | |
| { | |
| return (m_key_iter == other.m_key_iter); | |
| } | |
| typename sort_keyvalue_iter_helper_type< | |
| KeyIterator, ValueIterator>::reference dereference() const | |
| { | |
| return (typename sort_keyvalue_iter_helper_type< | |
| KeyIterator, ValueIterator>::reference( | |
| *m_key_iter, *m_value_iter)); | |
| } | |
| void advance( | |
| typename std::iterator_traits<KeyIterator>::difference_type n) | |
| { | |
| m_key_iter += n; | |
| m_value_iter += n; | |
| } | |
| typename std::iterator_traits<KeyIterator>::difference_type | |
| distance_to(const sort_keyvalue_iterator& other) const | |
| { | |
| return std::distance(m_key_iter, other.m_key_iter); | |
| } | |
| }; | |
| template<typename KeyIterator, typename ValueIterator, typename Compare> | |
| struct sort_keyvalue_iter_compare | |
| : public std::binary_function< | |
| typename sort_keyvalue_iter_helper_type< | |
| KeyIterator, ValueIterator>::value_type, | |
| typename sort_keyvalue_iter_helper_type< | |
| KeyIterator, ValueIterator>::value_type, bool> | |
| { | |
| public: | |
| typedef typename sort_keyvalue_iter_helper_type< | |
| KeyIterator, ValueIterator>::value_type T; | |
| sort_keyvalue_iter_compare(Compare comp) : m_comp(comp) {} | |
| bool operator()(const T& left, const T& right) | |
| { | |
| return m_comp(boost::get<0>(left), boost::get<0>(right)); | |
| } | |
| private: | |
| Compare m_comp; | |
| }; | |
| template<typename KeyIterator, typename ValueIterator> | |
| sort_keyvalue_iterator<KeyIterator, ValueIterator> | |
| make_sort_keyvalue_iterator( | |
| KeyIterator sort_iter, ValueIterator permute_iter) | |
| { | |
| return sort_keyvalue_iterator<KeyIterator, ValueIterator>( | |
| sort_iter, permute_iter); | |
| } | |
| } // namespace detail | |
| template<typename KeyIterator, typename ValueIterator, typename Compare> | |
| void sort_by_key( | |
| KeyIterator keys_first, KeyIterator keys_last, | |
| ValueIterator values_begin, Compare comp) | |
| { | |
| std::sort( | |
| detail::make_sort_keyvalue_iterator( | |
| keys_first, values_begin), | |
| detail::make_sort_keyvalue_iterator( | |
| keys_last, values_begin + std::distance(keys_first, keys_last)), | |
| detail::sort_keyvalue_iter_compare< | |
| KeyIterator, ValueIterator, Compare>(comp)); | |
| } | |
| template<typename KeyIterator, typename ValueIterator> | |
| void sort_by_key( | |
| KeyIterator keys_first, KeyIterator keys_last, | |
| ValueIterator values_begin) | |
| { | |
| sort_by_key( | |
| keys_first, keys_last, values_begin, | |
| std::less<typename std::iterator_traits<KeyIterator>::value_type>()); | |
| } | |
| template<typename KeyIterator, typename ValueIterator, typename Compare> | |
| void stable_sort_by_key( | |
| KeyIterator keys_first, KeyIterator keys_last, | |
| ValueIterator values_begin, Compare comp) | |
| { | |
| std::stable_sort( | |
| detail::make_sort_keyvalue_iterator( | |
| keys_first, values_begin), | |
| detail::make_sort_keyvalue_iterator( | |
| keys_last, values_begin + std::distance(keys_first, keys_last)), | |
| detail::sort_keyvalue_iter_compare< | |
| KeyIterator, ValueIterator, Compare>(comp)); | |
| } | |
| template<typename KeyIterator, typename ValueIterator> | |
| void stable_sort_by_key( | |
| KeyIterator keys_first, KeyIterator keys_last, | |
| ValueIterator values_begin) | |
| { | |
| stable_sort_by_key( | |
| keys_first, keys_last, values_begin, | |
| std::less<typename std::iterator_traits<KeyIterator>::value_type>()); | |
| } | |
| template<typename KeyIterator, typename ValueIterator, typename Compare> | |
| void partial_sort_by_key( | |
| KeyIterator keys_first, KeyIterator keys_middle, KeyIterator keys_last, | |
| ValueIterator values_first, Compare comp) | |
| { | |
| std::partial_sort( | |
| detail::make_sort_keyvalue_iterator( | |
| keys_first, | |
| values_first), | |
| detail::make_sort_keyvalue_iterator( | |
| keys_middle, | |
| values_first + std::distance(keys_first, keys_middle)), | |
| detail::make_sort_keyvalue_iterator( | |
| keys_last, | |
| values_first + std::distance(keys_first, keys_last)), | |
| detail::sort_keyvalue_iter_compare< | |
| KeyIterator, ValueIterator, Compare>(comp)); | |
| } | |
| template<typename KeyIterator, typename ValueIterator> | |
| void partial_sort_by_key( | |
| KeyIterator keys_first, KeyIterator keys_middle, KeyIterator keys_last, | |
| ValueIterator values_first) | |
| { | |
| partial_sort_by_key( | |
| keys_first, keys_middle, keys_last, values_first, | |
| std::less<typename std::iterator_traits<KeyIterator>::value_type>()); | |
| } | |
| template<typename KeyIterator, typename ValueIterator, | |
| typename OutputKeyIterator, typename OutputValueIterator, | |
| typename Compare> | |
| void partial_sort_copy_by_key( | |
| KeyIterator keys_first, KeyIterator keys_last, | |
| ValueIterator values_first, | |
| OutputKeyIterator result_keys_first, OutputKeyIterator result_keys_last, | |
| OutputValueIterator result_values_first, Compare comp) | |
| { | |
| std::partial_sort_copy( | |
| detail::make_sort_keyvalue_iterator( | |
| keys_first, values_first), | |
| detail::make_sort_keyvalue_iterator( | |
| keys_last, | |
| values_first + std::distance(keys_first, keys_last)), | |
| detail::make_sort_keyvalue_iterator( | |
| result_keys_first, | |
| result_values_first), | |
| detail::make_sort_keyvalue_iterator( | |
| result_keys_last, | |
| result_values_first + | |
| std::distance(result_keys_first, result_keys_last)), | |
| detail::sort_keyvalue_iter_compare< | |
| KeyIterator, ValueIterator, Compare>(comp)); | |
| } | |
| template<typename KeyIterator, typename ValueIterator, | |
| typename OutputKeyIterator, typename OutputValueIterator> | |
| void partial_sort_copy_by_key( | |
| KeyIterator keys_first, KeyIterator keys_last, | |
| ValueIterator values_first, | |
| OutputKeyIterator result_keys_first, OutputKeyIterator result_keys_last, | |
| OutputValueIterator result_values_first) | |
| { | |
| partial_sort_copy_by_key( | |
| keys_first, keys_last, values_first, | |
| result_keys_first, result_keys_last, result_values_first, | |
| std::less<typename std::iterator_traits<KeyIterator>::value_type>()); | |
| } | |
| template<typename KeyIterator, typename ValueIterator, typename Compare> | |
| void nth_element_by_key( | |
| KeyIterator keys_first, KeyIterator nth_keys, KeyIterator keys_last, | |
| ValueIterator values_first, Compare comp) | |
| { | |
| std::nth_element( | |
| detail::make_sort_keyvalue_iterator( | |
| keys_first, values_first), | |
| detail::make_sort_keyvalue_iterator( | |
| nth_keys, | |
| values_first + std::distance(keys_first, nth_keys)), | |
| detail::make_sort_keyvalue_iterator( | |
| keys_last, | |
| values_first + std::distance(keys_first, keys_last)), | |
| detail::sort_keyvalue_iter_compare< | |
| KeyIterator, ValueIterator, Compare>(comp)); | |
| } | |
| template<typename KeyIterator, typename ValueIterator> | |
| void nth_element_by_key( | |
| KeyIterator keys_first, KeyIterator nth_keys, KeyIterator keys_last, | |
| ValueIterator values_first) | |
| { | |
| nth_element_by_key( | |
| keys_first, nth_keys, keys_last, values_first, | |
| std::less<typename std::iterator_traits<KeyIterator>::value_type>()); | |
| } | |
| } // namespace aoba |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment