n type different from ISO C++. template void fill_n(_OIter, _Size, const _Tp&); */ template _OIter fill_n(_OIter, _Size, const _Tp&); // find template _FIter1 find_end(_FIter1, _FIter1, _FIter2, _FIter2); template _FIter1 find_end(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate); // find_first_of // find_if // for_each // generate // generate_n template bool includes(_IIter1, _IIter1, _IIter2, _IIter2); template bool includes(_IIter1, _IIter1, _IIter2, _IIter2, _Compare); template void inplace_merge(_BIter, _BIter, _BIter); template void inplace_merge(_BIter, _BIter, _BIter, _Compare); #ifdef __GXX_EXPERIMENTAL_CXX0X__ template bool is_heap(_RAIter, _RAIter); template bool is_heap(_RAIter, _RAIter, _Compare); template _RAIter is_heap_until(_RAIter, _RAIter); template _RAIter is_heap_until(_RAIter, _RAIter, _Compare); template bool is_sorted(_FIter, _FIter); template bool is_sorted(_FIter, _FIter, _Compare); template _FIter is_sorted_until(_FIter, _FIter); template _FIter is_sorted_until(_FIter, _FIter, _Compare); #endif template void iter_swap(_FIter1, _FIter2); template _FIter lower_bound(_FIter, _FIter, const _Tp&); template _FIter lower_bound(_FIter, _FIter, const _Tp&, _Compare); template void make_heap(_RAIter, _RAIter); template void make_heap(_RAIter, _RAIter, _Compare); template const _Tp& max(const _Tp&, const _Tp&); template const _Tp& max(const _Tp&, const _Tp&, _Compare); // max_element // merge template const _Tp& min(const _Tp&, const _Tp&); template const _Tp& min(const _Tp&, const _Tp&, _Compare); // min_element #ifdef __GXX_EXPERIMENTAL_CXX0X__ template pair minmax(const _Tp&, const _Tp&); template pair minmax(const _Tp&, const _Tp&, _Compare); template pair<_FIter, _FIter> minmax_element(_FIter, _FIter); template pair<_FIter, _FIter> minmax_element(_FIter, _FIter, _Compare); #endif // mismatch template bool next_permutation(_BIter, _BIter); template bool next_permutation(_BIter, _BIter, _Compare); // nth_element // partial_sort template _RAIter partial_sort_copy(_IIter, _IIter, _RAIter, _RAIter); template _RAIter partial_sort_copy(_IIter, _IIter, _RAIter, _RAIter, _Compare); template void pop_heap(_RAIter, _RAIter); template void pop_heap(_RAIter, _RAIter, _Compare); template bool prev_permutation(_BIter, _BIter); template bool prev_permutation(_BIter, _BIter, _Compare); template void push_heap(_RAIter, _RAIter); template void push_heap(_RAIter, _RAIter, _Compare); // random_shuffle template _FIter remove(_FIter, _FIter, const _Tp&); template _FIter remove_if(_FIter, _FIter, _Predicate); template _OIter remove_copy(_IIter, _IIter, _OIter, const _Tp&); template _OIter remove_copy_if(_IIter, _IIter, _OIter, _Predicate); // replace template _OIter replace_copy(_IIter, _IIter, _OIter, const _Tp&, const _Tp&); template _OIter replace_copy_if(_Iter, _Iter, _OIter, _Predicate, const _Tp&); // replace_if template void reverse(_BIter, _BIter); template _OIter reverse_copy(_BIter, _BIter, _OIter); template void rotate(_FIter, _FIter, _FIter); template _OIter rotate_copy(_FIter, _FIter, _FIter, _OIter); // search // search_n // set_difference // set_intersection // set_symmetric_difference // set_union template void sort_heap(_RAIter, _RAIter); template void sort_heap(_RAIter, _RAIter, _Compare); template _BIter stable_partition(_BIter, _BIter, _Predicate); template void swap(_Tp&, _Tp&); template _FIter2 swap_ranges(_FIter1, _FIter1, _FIter2); // transform template _FIter unique(_FIter, _FIter); template _FIter unique(_FIter, _FIter, _BinaryPredicate); // unique_copy template _FIter upper_bound(_FIter, _FIter, const _Tp&); template _FIter upper_bound(_FIter, _FIter, const _Tp&, _Compare); _GLIBCXX_END_NAMESPACE _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) template _FIter adjacent_find(_FIter, _FIter); template _FIter adjacent_find(_FIter, _FIter, _BinaryPredicate); template typename iterator_traits<_IIter>::difference_type count(_IIter, _IIter, const _Tp&); template typename iterator_traits<_IIter>::difference_type count_if(_IIter, _IIter, _Predicate); template bool equal(_IIter1, _IIter1, _IIter2); template bool equal(_IIter1, _IIter1, _IIter2, _BinaryPredicate); template _IIter find(_IIter, _IIter, const _Tp&); template _FIter1 find_first_of(_FIter1, _FIter1, _FIter2, _FIter2); template _FIter1 find_first_of(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate); template _IIter find_if(_IIter, _IIter, _Predicate); template _Funct for_each(_IIter, _IIter, _Funct); template void generate(_FIter, _FIter, _Generator); /* XXX NB: return type different from ISO C++. template void generate_n(_OIter, _Size, _Generator); */ template _OIter generate_n(_OIter, _Size, _Generator); template bool lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2); template bool lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, _Compare); template _FIter max_element(_FIter, _FIter); template _FIter max_element(_FIter, _FIter, _Compare); template _OIter merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); template _OIter merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare); template _FIter min_element(_FIter, _FIter); template _FIter min_element(_FIter, _FIter, _Compare); template pair<_IIter1, _IIter2> mismatch(_IIter1, _IIter1, _IIter2); template pair<_IIter1, _IIter2> mismatch(_IIter1, _IIter1, _IIter2, _BinaryPredicate); template void nth_element(_RAIter, _RAIter, _RAIter); template void nth_element(_RAIter, _RAIter, _RAIter, _Compare); template void partial_sort(_RAIter, _RAIter, _RAIter); template void partial_sort(_RAIter, _RAIter, _RAIter, _Compare); template _BIter partition(_BIter, _BIter, _Predicate); template void random_shuffle(_RAIter, _RAIter); template void random_shuffle(_RAIter, _RAIter, _Generator&); template void replace(_FIter, _FIter, const _Tp&, const _Tp&); template void replace_if(_FIter, _FIter, _Predicate, const _Tp&); template _FIter1 search(_FIter1, _FIter1, _FIter2, _FIter2); template _FIter1 search(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate); template _FIter search_n(_FIter, _FIter, _Size, const _Tp&); template _FIter search_n(_FIter, _FIter, _Size, const _Tp&, _BinaryPredicate); template _OIter set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); template _OIter set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare); template _OIter set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); template _OIter set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare); template _OIter set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); template _OIter set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare); template _OIter set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); template _OIter set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare); template void sort(_RAIter, _RAIter); template void sort(_RAIter, _RAIter, _Compare); template void stable_sort(_RAIter, _RAIter); template void stable_sort(_RAIter, _RAIter, _Compare); template _OIter transform(_IIter, _IIter, _OIter, _UnaryOperation); template _OIter transform(_IIter1, _IIter1, _IIter2, _OIter, _BinaryOperation); template _OIter unique_copy(_IIter, _IIter, _OIter); template _OIter unique_copy(_IIter, _IIter, _OIter, _BinaryPredicate); _GLIBCXX_END_NESTED_NAMESPACE #ifdef _GLIBCXX_NAMESPACE_ASSOCIATION_PARALLEL # include #endif #endif // Heap implementation -*- C++ -*- // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License along // with this library; see the file COPYING. If not, write to the Free // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // USA. // As a special exception, you may use this file as part of a free software // library without restriction. Specifically, if other files instantiate // templates or use macros or inline functions from this file, or you compile // this file and link it with other files to produce an executable, this // file does not by itself cause the resulting executable to be covered by // the GNU General Public License. This exception does not however // invalidate any other reasons why the executable file might be covered by // the GNU General Public License. /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * Copyright (c) 1997 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. */ /** @file stl_heap.h * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ #ifndef _STL_HEAP_H #define _STL_HEAP_H 1 #include #include _GLIBCXX_BEGIN_NAMESPACE(std) template _Distance __is_heap_until(_RandomAccessIterator __first, _Distance __n) { _Distance __parent = 0; for (_Distance __child = 1; __child < __n; ++__child) { if (__first[__parent] < __first[__child]) return __child; if ((__child & 1) == 0) ++__parent; } return __n; } template _Distance __is_heap_until(_RandomAccessIterator __first, _Distance __n, _Compare __comp) { _Distance __parent = 0; for (_Distance __child = 1; __child < __n; ++__child) { if (__comp(__first[__parent], __first[__child])) return __child; if ((__child & 1) == 0) ++__parent; } return __n; } // __is_heap, a predicate testing whether or not a range is a heap. // This function is an extension, not part of the C++ standard. template inline bool __is_heap(_RandomAccessIterator __first, _Distance __n) { return std::__is_heap_until(__first, __n) == __n; } template inline bool __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n) { return std::__is_heap_until(__first, __n, __comp) == __n; } template inline bool __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { return std::__is_heap(__first, std::distance(__first, __last)); } template inline bool __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { return std::__is_heap(__first, __comp, std::distance(__first, __last)); } // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap, // + is_heap and is_heap_until in C++0x. template void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __value) { _Distance __parent = (__holeIndex - 1) / 2; while (__holeIndex > __topIndex && *(__first + __parent) < __value) { *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); __holeIndex = __parent; __parent = (__holeIndex - 1) / 2; } *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); } /** * @brief Push an element onto a heap. * @param first Start of heap. * @param last End of heap + element. * @ingroup heap * * This operation pushes the element at last-1 onto the valid heap over the * range [first,last-1). After completion, [first,last) is a valid heap. */ template inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType; // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_heap(__first, __last - 1); _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); std::__push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), _GLIBCXX_MOVE(__value)); } template void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __value, _Compare __comp) { _Distance __parent = (__holeIndex - 1) / 2; while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) { *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); __holeIndex = __parent; __parent = (__holeIndex - 1) / 2; } *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); } /** * @brief Push an element onto a heap using comparison functor. * @param first Start of heap. * @param last End of heap + element. * @param comp Comparison functor. * @ingroup heap * * This operation pushes the element at last-1 onto the valid heap over the * range [first,last-1). After completion, [first,last) is a valid heap. * Compare operations are performed using comp. */ template inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType; // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_heap_pred(__first, __last - 1, __comp); _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); std::__push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), _GLIBCXX_MOVE(__value), __comp); } template void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __value) { const _Distance __topIndex = __holeIndex; _Distance __secondChild = __holeIndex; while (__secondChild < (__len - 1) / 2) { __secondChild = 2 * (__secondChild + 1); if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) __secondChild--; *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); __holeIndex = __secondChild; } if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) { __secondChild = 2 * (__secondChild + 1); *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + (__secondChild - 1))); __holeIndex = __secondChild - 1; } std::__push_heap(__first, __holeIndex, __topIndex, _GLIBCXX_MOVE(__value)); } template inline void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType; _ValueType __value = _GLIBCXX_MOVE(*__result); *__result = _GLIBCXX_MOVE(*__first); std::__adjust_heap(__first, _DistanceType(0), _DistanceType(__last - __first), _GLIBCXX_MOVE(__value)); } /** * @brief Pop an element off a heap. * @param first Start of heap. * @param last End of heap. * @ingroup heap * * This operation pops the top of the heap. The elements first and last-1 * are swapped and [first,last-1) is made into a heap. */ template inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_heap(__first, __last); std::__pop_heap(__first, __last - 1, __last - 1); } template void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __value, _Compare __comp) { const _Distance __topIndex = __holeIndex; _Distance __secondChild = __holeIndex; while (__secondChild < (__len - 1) / 2) { __secondChild = 2 * (__secondChild + 1); if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) __secondChild--; *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); __holeIndex = __secondChild; } if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) { __secondChild = 2 * (__secondChild + 1); *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + (__secondChild - 1))); __holeIndex = __secondChild - 1; } std::__push_heap(__first, __holeIndex, __topIndex, _GLIBCXX_MOVE(__value), __comp); } template inline void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Compare __comp) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType; _ValueType __value = _GLIBCXX_MOVE(*__result); *__result = _GLIBCXX_MOVE(*__first); std::__adjust_heap(__first, _DistanceType(0), _DistanceType(__last - __first), _GLIBCXX_MOVE(__valu›'ś'ť'ž'ź' 'ˇ'˘'e), __comp); } /** * @brief Pop an element off a heap using comparison functor. * @param first Start of heap. * @param last End of heap. * @param comp Comparison functor to use. * @ingroup heap * * This operation pops the top of the heap. The elements first and last-1 * are swapped and [first,last-1) is made into a heap. Comparisons are * made using comp. */ template inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_heap_pred(__first, __last, __comp); std::__pop_heap(__first, __last - 1, __last - 1, __comp); } /** * @brief Construct a heap over a range. * @param first Start of heap. * @param last End of heap. * @ingroup heap * * This operation makes the elements in [first,last) into a heap. */ template void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType; // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) __glibcxx_requires_valid_range(__first, __last); if (__last - __first < 2) return; const _DistanceType __len = __last - __first; _DistanceType __parent = (__len - 2) / 2; while (true) { _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value)); if (__parent == 0) return; __parent--; } } /** * @brief Construct a heap over a range using comparison functor. * @param first Start of heap. * @param last End of heap. * @param comp Comparison functor to use. * @ingroup heap * * This operation makes the elements in [first,last) into a heap. * Comparisons are made using comp. */ template void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType; // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); if (__last - __first < 2) return; const _DistanceType __len = __last - __first; _DistanceType __parent = (__len - 2) / 2; while (true) { _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), __comp); if (__parent == 0) return; __parent--; } } /** * @brief Sort a heap. * @param first Start of heap. * @param last End of heap. * @ingroup heap * * This operation sorts the valid heap in the range [first,last). */ template void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_heap(__first, __last); while (__last - __first > 1) std::pop_heap(__first, _RandomAccessIterator(__last--)); } /** * @brief Sort a heap using comparison functor. * @param first Start of heap. * @param last End of heap. * @param comp Comparison functor to use. * @ingroup heap * * This operation sorts the valid heap in the range [first,last). * Comparisons are made using comp. */ template void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_heap_pred(__first, __last, __comp); while (__last - __first > 1) std::pop_heap(__first, _RandomAccessIterator(__last--), __comp); } #ifdef __GXX_EXPERIMENTAL_CXX0X__ /** * @brief Search the end of a heap. * @param first Start of range. * @param last End of range. * @return An iterator pointing to the first element not in the heap. * @ingroup heap * * This operation returns the last iterator i in [first, last) for which * the range [first, i) is a heap. */ template inline _RandomAccessIterator is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) { // concept requirements __glibcxx_function_requires(_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); return __first + std::__is_heap_until(__first, std::distance(__first, __last)); } /** * @brief Search the end of a heap using comparison functor. * @param first Start of range. * @param last End of range. * @param comp Comparison functor to use. * @return An iterator pointing to the first element not in the heap. * @ingroup heap * * This operation returns the last iterator i in [first, last) for which * the range [first, i) is a heap. Comparisons are made using comp. */ template inline _RandomAccessIterator is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // concept requirements __glibcxx_function_requires(_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); return __first + std::__is_heap_until(__first, std::distance(__first, __last), __comp); } /** * @brief Determines whether a range is a heap. * @param first Start of range. * @param last End of range. * @return True if range is a heap, false otherwise. * @ingroup heap */ template inline bool is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { return std::is_heap_until(__first, __last) == __last; } /** * @brief Determines whether a range is a heap using comparison functor. * @param first Start of range. * @param last End of range. * @param comp Comparison functor to use. * @return True if range is a heap, false otherwise. * @ingroup heap */ template inline bool is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { return std::is_heap_until(__first, __last, __comp) == __last; } #endif _GLIBCXX_END_NAMESPACE #endif /* _STL_HEAP_H */ // The template and inlines for the -*- C++ -*- internal _Meta class. // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License along // with this library; see the file COPYING. If not, write to the Free // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // USA. // As a special exception, you may use this file as part of a free software // library without restriction. Specifically, if other files instantiate // templates or use macros or inline functions from this file, or you compile // this file and link it with other files to produce an executable, this // file does not by itself cause the resulting executable to be covered by // the GNU General Public License. This exception does not however // invalidate any other reasons why the executable file might be covered by // the GNU General Public License. /** @file valarray_after.h * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ // Written by Gabriel Dos Reis #ifndef _VALARRAY_AFTER_H #define _VALARRAY_AFTER_H 1 #pragma GCC system_header _GLIBCXX_BEGIN_NAMESPACE(std) // // gslice_array closure. // template class _GBase { public: typedef typename _Dom::value_type value_type; _GBase (const _Dom& __e, const valarray& __i) : _M_expr (__e), _M_index(__i) {} value_type operator[] (size_t __i) const { return _M_expr[_M_index[__i]]; } size_t size () const { return _M_index.size(); } private: const _Dom& _M_expr; const valarray& _M_index; }; template class _GBase<_Array<_Tp> > { public: typedef _Tp value_type; _GBase (_Array<_Tp> __a, const valarray& __i) : _M_array (__a), _M_index(__i) {} value_type operator[] (size_t __i) const { return _M_array._M_data[_M_index[__i]]; } size_t size () const { return _M_index.size(); } private: const _Array<_Tp> _M_array; const valarray& _M_index; }; template struct _GClos<_Expr, _Dom> : _GBase<_Dom> { typedef _GBase<_Dom> _Base; typedef typename _Base::value_type value_type; _GClos (const _Dom& __e, const valarray& __i) : _Base (__e, __i) {} }; template struct _GClos<_ValArray, _Tp> : _GBase<_Array<_Tp> > { typedef _GBase<_Array<_Tp> > _Base; typedef typename _Base::value_type value_type; _GClos (_Array<_Tp> __a, const valarray& __i) : _Base (__a, __i) {} }; // // indirect_array closure // template class _IBase { public: typedef typename _Dom::value_type value_type; _IBase (const _Dom& __e, const valarray& __i) : _M_expr (__e), _M_index (__i) {} value_type operator[] (size_t __i) const { return _M_expr[_M_index[__i]]; } size_t size() const { return _M_index.size(); } private: const _Dom& _M_expr; const valarray& _M_index; }; template struct _IClos<_Expr, _Dom> : _IBase<_Dom> { typedef _IBase<_Dom> _Base; typedef typename _Base::value_type value_type; _IClos (const _Dom& __e, const valarray& __i) : _Base (__e, __i) {} }; template struct _IClos<_ValArray, _Tp> : _IBase > { typedef _IBase > _Base; typedef _Tp value_type; _IClos (const valarray<_Tp>& __a, const valarray& __i) : _Base (__a, __i) {} }; // // class _Expr // template class _Expr { public: typedef _Tp value_type; _Expr(const _Clos&); const _Clos& operator()() const; value_type operator[](size_t) const; valarray operator[](slice) const; valarray operator[](const gslice&) const; valarray operator[](const valarray&) const; valarray operator[](const valarray&) const; _Expr<_UnClos<__unary_plus, std::_Expr, _Clos>, value_type> operator+() const; _Expr<_UnClos<__negate, std::_Expr, _Clos>, value_type> operator-() const; _Expr<_UnClos<__bitwise_not, std::_Expr, _Clos>, value_type> operator~() const; _Expr<_UnClos<__logical_not, std::_Expr, _Clos>, bool> operator!() const; size_t size() const; value_type sum() const; valarray shift(int) const; valarray cshift(int) const; value_type min() const; value_type max() const; valarray apply(value_type (*)(const value_type&)) const; valarray apply(value_type (*)(value_type)) const; private: const _Clos _M_closure; }; template inline _Expr<_Clos, _Tp>::_Expr(const _Clos& __c) : _M_closure(__c) {} template inline const _Clos& _Expr<_Clos, _Tp>::operator()() const { return _M_closure; } template inline _Tp _Expr<_Clos, _Tp>::operator[](size_t __i) const { return _M_closure[__i]; } template inline valarray<_Tp> _Expr<_Clos, _Tp>::operator[](slice __s) const { valarray<_Tp> __v = valarray<_Tp>(*this)[__s]; return __v; } template inline valarray<_Tp> _Expr<_Clos, _Tp>::operator[](const gslice& __gs) const { valarray<_Tp> __v = valarray<_Tp>(*this)[__gs]; return __v; } template inline valarray<_Tp> _Expr<_Clos, _Tp>::operator[](const valarray& __m) const { valarray<_Tp> __v = valarray<_Tp>(*this)[__m]; return __v; } template inline valarray<_Tp> _Expr<_Clos, _Tp>::operator[](const valarray& __i) const { valarray<_Tp> __v = valarray<_Tp>(*this)[__i]; return __v; } template inline size_t _Expr<_Clos, _Tp>::size() const { return _M_closure.size(); } template inline valarray<_Tp> _Expr<_Clos, _Tp>::shift(int __n) const { valarray<_Tp> __v = valarray<_Tp>(*this).shift(__n); return __v; } template inline valarray<_Tp> _Expr<_Clos, _Tp>::cshift(int __n) const { valarray<_Tp> __v = valarray<_Tp>(*this).cshift(__n); return __v; } template inline valarray<_Tp> _Expr<_Clos, _Tp>::apply(_Tp __f(const _Tp&)) const { valarray<_Tp> __v = valarray<_Tp>(*this).apply(__f); return __v; } template inline valarray<_Tp> _Expr<_Clos, _Tp>::apply(_Tp __f(_Tp)) const { valarray<_Tp> __v = valarray<_Tp>(*this).apply(__f); return __v; } // XXX: replace this with a more robust summation algorithm. template inline _Tp _Expr<_Clos, _Tp>::sum() const { size_t __n = _M_closure.size(); if (__n == 0) return _Tp(); else { _Tp __s = _M_closure[--__n]; while (__n != 0) __s += _M_closure[--__n]; return __s; } } template inline _Tp _Expr<_Clos, _Tp>::min() const { return __valarray_min(_M_closure); } template inline _Tp _Expr<_Clos, _Tp>::max() const { return __valarray_max(_M_closure); } template inline _Expr<_UnClos<__logical_not, _Expr, _Dom>, bool> _Expr<_Dom, _Tp>::operator!() const { typedef _UnClos<__logical_not, std::_Expr, _Dom> _Closure; return _Expr<_Closure, _Tp>(_Closure(this->_M_closure)); } #define _DEFINE_EXPR_UNARY_OPERATOR(_Op, _Name) \ template \ inline _Expr<_UnClos<_Name, std::_Expr, _Dom>, _Tp> \ _Expr<_Dom, _Tp>::operator _Op() const \ { \ typedef _UnClos<_Name, std::_Expr, _Dom> _Closure; \ return _Expr<_Closure, _Tp>(_Closure(this->_M_closure)); \ } _DEFINE_EXPR_UNARY_OPERATOR(+, __unary_plus) _DEFINE_EXPR_UNARY_OPERATOR(-, __negate) _DEFINE_EXPR_UNARY_OPERATOR(~, __bitwise_not) #undef _DEFINE_EXPR_UNARY_OPERATOR #define _DEFINE_EXPR_BINARY_OPERATOR(_Op, _Name) \ template \ inline _Expr<_BinClos<_Name, _Expr, _Expr, _Dom1, _Dom2>, \ typename __fun<_Name, typename _Dom1::value_type>::result_type> \ operator _Op(const _Expr<_Dom1, typename _Dom1::value_type>& __v, \ const _Expr<_Dom2, typename _Dom2::value_type>& __w) \ { \ typedef typename _Dom1::value_type _Arg; \ typedef typename __fun<_Name, _Arg>::result_type _Value; \ typedef _BinClos<_Name, _Expr, _Expr, _Dom1, _Dom2> _Closure; \ return _Expr<_Closure, _Value>(_Closure(__v(), __w())); \ } \ \ template \ inline _Expr<_BinClos<_Name, _Expr, _Constant, _Dom, \ typename _Dom::value_type>, \ typename __fun<_Name, typename _Dom::value_type>::result_type> \ operator _Op(const _Expr<_Dom, typename _Dom::value_type>& __v, \ const typename _Dom::value_type& __t) \ { \ typedef typename _Dom::value_type _Arg; \ typedef typename __fun<_Name, _Arg>::result_type _Value; \ typedef _BinClos<_Name, _Expr, _Constant, _Dom, _Arg> _Closure; \ return _Expr<_Closure, _Value>(_Closure(__v(), __t)); \ } \ \ template \ inline _Expr<_BinClos<_Name, _Constant, _Expr, \ typename _Dom::value_type, _Dom>, \ typename __fun<_Name, typename _Dom::value_type>::result_type> \ operator _Op(const typename _Dom::value_type& __t, \ const _Expr<_Dom, typename _Dom::value_type>& __v) \ { \ typedef typename _Dom::value_type _Arg; \ typedef typename __fun<_Name, _Arg>::result_type _Value; \ typedef _BinClos<_Name, _Constant, _Expr, _Arg, _Dom> _Closure; \ return _Expr<_Closure, _Value>(_Closure(__t, __v())); \ } °'±'˛'ł'´'µ'¶'·'¸'ą'ş' \ \ template \ inline _Expr<_BinClos<_Name, _Expr, _ValArray, \ _Dom, typename _Dom::value_type>, \ typename __fun<_Name, typename _Dom::value_type>::result_type> \ operator _Op(const _Expr<_Dom,typename _Dom::value_type>& __e, \ const valarray& __v) \ { \ typedef typename _Dom::value_type _Arg; \ typedef typename __fun<_Name, _Arg>::result_type _Value; \ typedef _BinClos<_Name, _Expr, _ValArray, _Dom, _Arg> _Closure; \ return _Expr<_Closure, _Value>(_Closure(__e(), __v)); \ } \ \ template \ inline _Expr<_BinClos<_Name, _ValArray, _Expr, \ typename _Dom::value_type, _Dom>, \ typename __fun<_Name, typename _Dom::value_type>::result_type> \ operator _Op(const valarray& __v, \ const _Expr<_Dom, typename _Dom::value_type>& __e) \ { \ typedef typename _Dom::value_type _Tp; \ typedef typename __fun<_Name, _Tp>::result_type _Value; \ typedef _BinClos<_Name, _ValArray, _Expr, _Tp, _Dom> _Closure; \ return _Expr<_Closure, _Value>(_Closure(__v, __e ())); \ } _DEFINE_EXPR_BINARY_OPERATOR(+, __plus) _DEFINE_EXPR_BINARY_OPERATOR(-, __minus) _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies) _DEFINE_EXPR_BINARY_OPERATOR(/, __divides) _DEFINE_EXPR_BINARY_OPERATOR(%, __modulus) _DEFINE_EXPR_BINARY_OPERATOR(^, __bitwise_xor) _DEFINE_EXPR_BINARY_OPERATOR(&, __bitwise_and) _DEFINE_EXPR_BINARY_OPERATOR(|, __bitwise_or) _DEFINE_EXPR_BINARY_OPERATOR(<<, __shift_left) _DEFINE_EXPR_BINARY_OPERATOR(>>, __shift_right) _DEFINE_EXPR_BINARY_OPERATOR(&&, __logical_and) _DEFINE_EXPR_BINARY_OPERATOR(||, __logical_or) _DEFINE_EXPR_BINARY_OPERATOR(==, __equal_to) _DEFINE_EXPR_BINARY_OPERATOR(!=, __not_equal_to) _DEFINE_EXPR_BINARY_OPERATOR(<, __less) _DEFINE_EXPR_BINARY_OPERATOR(>, __greater) _DEFINE_EXPR_BINARY_OPERATOR(<=, __less_equal) _DEFINE_EXPR_BINARY_OPERATOR(>=, __greater_equal) #undef _DEFINE_EXPR_BINARY_OPERATOR #define _DEFINE_EXPR_UNARY_FUNCTION(_Name) \ template \ inline _Expr<_UnClos<__##_Name, _Expr, _Dom>, \ typename _Dom::value_type> \ _Name(const _Expr<_Dom, typename _Dom::value_type>& __e) \ { \ typedef typename _Dom::value_type _Tp; \ typedef _UnClos<__##_Name, _Expr, _Dom> _Closure; \ return _Expr<_Closure, _Tp>(_Closure(__e())); \ } \ \ template \ inline _Expr<_UnClos<__##_Name, _ValArray, _Tp>, _Tp> \ _Name(const valarray<_Tp>& __v) \ { \ typedef _UnClos<__##_Name, _ValArray, _Tp> _Closure; \ return _Expr<_Closure, _Tp>(_Closure(__v)); \ } _DEFINE_EXPR_UNARY_FUNCTION(abs) _DEFINE_EXPR_UNARY_FUNCTION(cos) _DEFINE_EXPR_UNARY_FUNCTION(acos) _DEFINE_EXPR_UNARY_FUNCTION(cosh) _DEFINE_EXPR_UNARY_FUNCTION(sin) _DEFINE_EXPR_UNARY_FUNCTION(asin) _DEFINE_EXPR_UNARY_FUNCTION(sinh) _DEFINE_EXPR_UNARY_FUNCTION(tan) _DEFINE_EXPR_UNARY_FUNCTION(tanh) _DEFINE_EXPR_UNARY_FUNCTION(atan) _DEFINE_EXPR_UNARY_FUNCTION(exp) _DEFINE_EXPR_UNARY_FUNCTION(log) _DEFINE_EXPR_UNARY_FUNCTION(log10) _DEFINE_EXPR_UNARY_FUNCTION(sqrt) #undef _DEFINE_EXPR_UNARY_FUNCTION #define _DEFINE_EXPR_BINARY_FUNCTION(_Fun) \ template \ inline _Expr<_BinClos<__##_Fun, _Expr, _Expr, _Dom1, _Dom2>, \ typename _Dom1::value_type> \ _Fun(const _Expr<_Dom1, typename _Dom1::value_type>& __e1, \ const _Expr<_Dom2, typename _Dom2::value_type>& __e2) \ { \ typedef typename _Dom1::value_type _Tp; \ typedef _BinClos<__##_Fun, _Expr, _Expr, _Dom1, _Dom2> _Closure; \ return _Expr<_Closure, _Tp>(_Closure(__e1(), __e2())); \ } \ \ template \ inline _Expr<_BinClos<__##_Fun, _Expr, _ValArray, _Dom, \ typename _Dom::value_type>, \ typename _Dom::value_type> \ _Fun(const _Expr<_Dom, typename _Dom::value_type>& __e, \ const valarray& __v) \ { \ typedef typename _Dom::value_type _Tp; \ typedef _BinClos<__##_Fun, _Expr, _ValArray, _Dom, _Tp> _Closure; \ return _Expr<_Closure, _Tp>(_Closure(__e(), __v)); \ } \ \ template \ inline _Expr<_BinClos<__##_Fun, _ValArray, _Expr, \ typename _Dom::value_type, _Dom>, \ typename _Dom::value_type> \ _Fun(const valarray& __v, \ const _Expr<_Dom, typename _Dom::value_type>& __e) \ { \ typedef typename _Dom::value_type _Tp; \ typedef _BinClos<__##_Fun, _ValArray, _Expr, _Tp, _Dom> _Closure; \ return _Expr<_Closure, _Tp>(_Closure(__v, __e())); \ } \ \ template \ inline _Expr<_BinClos<__##_Fun, _Expr, _Constant, _Dom, \ typename _Dom::value_type>, \ typename _Dom::value_type> \ _Fun(const _Expr<_Dom, typename _Dom::value_type>& __e, \ const typename _Dom::value_type& __t) \ { \ typedef typename _Dom::value_type _Tp; \ typedef _BinClos<__##_Fun, _Expr, _Constant, _Dom, _Tp> _Closure;\ return _Expr<_Closure, _Tp>(_Closure(__e(), __t)); \ } \ \ template \ inline _Expr<_BinClos<__##_Fun, _Constant, _Expr, \ typename _Dom::value_type, _Dom>, \ typename _Dom::value_type> \ _Fun(const typename _Dom::value_type& __t, \ const _Expr<_Dom, typename _Dom::value_type>& __e) \ { \ typedef typename _Dom::value_type _Tp; \ typedef _BinClos<__##_Fun, _Constant, _Expr, _Tp, _Dom> _Closure; \ return _Expr<_Closure, _Tp>(_Closure(__t, __e())); \ } \ \ template \ inline _Expr<_BinClos<__##_Fun, _ValArray, _ValArray, _Tp, _Tp>, _Tp> \ _Fun(const valarray<_Tp>& __v, const valarray<_Tp>& __w) \ { \ typedef _BinClos<__##_Fun, _ValArray, _ValArray, _Tp, _Tp> _Closure; \ return _Expr<_Closure, _Tp>(_Closure(__v, __w)); \ } \ \ template \ inline _Expr<_BinClos<__##_Fun, _ValArray, _Constant, _Tp, _Tp>, _Tp> \ _Fun(const valarray<_Tp>& __v, const _Tp& __t) \ { \ typedef _BinClos<__##_Fun, _ValArray, _Constant, _Tp, _Tp> _Closure; \ return _Expr<_Closure, _Tp>(_Closure(__v, __t)); \ } \ \ template \ inline _Expr<_BinClos<__##_Fun, _Constant, _ValArray, _Tp, _Tp>, _Tp> \ _Fun(const _Tp& __t, const valarray<_Tp>& __v) \ { \ typedef _BinClos<__##_Fun, _Constant, _ValArray, _Tp, _Tp> _Closure; \ return _Expr<_Closure, _Tp>(_Closure(__t, __v)); \ } _DEFINE_EXPR_BINARY_FUNCTION(atan2) _DEFINE_EXPR_BINARY_FUNCTION(pow) #undef _DEFINE_EXPR_BINARY_FUNCTION _GLIBCXX_END_NAMESPACE #endif /* _CPP_VALARRAY_AFTER_H */ // Functor implementations -*- C++ -*- // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License along // with this library; see the file COPYING. If not, write to the Free // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // USA. // As a special exception, you may use this file as part of a free software // library without restriction. Specifically, if other files instantiate // templates or use macros or inline functions from this file, or you compile // this file and link it with other files to produce an executable, this // file does not by itself cause the resulting executable to be covered by // the GNU General Public License. This exception does not however // invalidate any other reasons why the executable file might be covered by // the GNU General Public License. /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * * Copyright (c) 1996-1998 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. */ /** @file stl_function.h * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ #ifndef _STL_FUNCTION_H #define _STL_FUNCTION_H 1 _GLIBCXX_BEGIN_NAMESPACE(std) // 20.3.1 base classes /** @defgroup s20_3_1_base Functor Base Classes * Function objects, or @e functors, are objects with an @c operator() * defined and accessible. They can be passed as arguments to algorithm * templates and used in place of a function pointer. Not only is the * resulting expressiveness of the library increased, but the generated * code can be more efficient than what you might write by hand. When we * refer to "functors," then, generally we include function pointers in * the description as well. * * Often, functors are only created as temporaries passed to algorithm * calls, rather than being created as named variables. * * Two examples taken from the standard itself follow. To perform a * by-element addition of two vectors @c a and @c b containing @c double, * and put the result in @c a, use * \code * transform (a.begin(), a.end(), b.begin(), a.begin(), plus()); * \endcode * To negate every element in @c a, use * \code * transform(a.begin(), a.end(), a.begin(), negate()); * \endcode * The addition and negation functions will be inlined directly. * * The standard functors are derived from structs named @c unary_function * and @c binary_function. These two classes contain nothing but typedefs, * to aid in generic (template) programming. If you write your own * functors, you might consider doing the same. * * @{ */ /** * This is one of the @link s20_3_1_base functor base classes@endlink. */ template struct unary_function { typedef _Arg argument_type; ///< @c argument_type is the type of the /// argument (no surprises here) typedef _Result result_type; ///< @c result_type is the return type }; /** * This is one of the @link s20_3_1_base functor base classes@endlink. */ template struct binary_function { typedef _Arg1 first_argument_type; ///< the type of the first argument /// (no surprises here) typedef _Arg2 second_argument_type; ///< the type of the second argument typedef _Result