wpkg test coverage results

Coverage test results of the Windows Packager by Made to Order Software Corporation.

LCOV - code coverage report
Current view: top level - usr/include/c++/4.6/bits - stl_heap.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 0 44 0.0 %
Date: 2013-06-17 Functions: 0 10 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // Heap implementation -*- C++ -*-
       2             : 
       3             : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
       4             : // Free Software Foundation, Inc.
       5             : //
       6             : // This file is part of the GNU ISO C++ Library.  This library is free
       7             : // software; you can redistribute it and/or modify it under the
       8             : // terms of the GNU General Public License as published by the
       9             : // Free Software Foundation; either version 3, or (at your option)
      10             : // any later version.
      11             : 
      12             : // This library is distributed in the hope that it will be useful,
      13             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      14             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15             : // GNU General Public License for more details.
      16             : 
      17             : // Under Section 7 of GPL version 3, you are granted additional
      18             : // permissions described in the GCC Runtime Library Exception, version
      19             : // 3.1, as published by the Free Software Foundation.
      20             : 
      21             : // You should have received a copy of the GNU General Public License and
      22             : // a copy of the GCC Runtime Library Exception along with this program;
      23             : // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
      24             : // <http://www.gnu.org/licenses/>.
      25             : 
      26             : /*
      27             :  *
      28             :  * Copyright (c) 1994
      29             :  * Hewlett-Packard Company
      30             :  *
      31             :  * Permission to use, copy, modify, distribute and sell this software
      32             :  * and its documentation for any purpose is hereby granted without fee,
      33             :  * provided that the above copyright notice appear in all copies and
      34             :  * that both that copyright notice and this permission notice appear
      35             :  * in supporting documentation.  Hewlett-Packard Company makes no
      36             :  * representations about the suitability of this software for any
      37             :  * purpose.  It is provided "as is" without express or implied warranty.
      38             :  *
      39             :  * Copyright (c) 1997
      40             :  * Silicon Graphics Computer Systems, Inc.
      41             :  *
      42             :  * Permission to use, copy, modify, distribute and sell this software
      43             :  * and its documentation for any purpose is hereby granted without fee,
      44             :  * provided that the above copyright notice appear in all copies and
      45             :  * that both that copyright notice and this permission notice appear
      46             :  * in supporting documentation.  Silicon Graphics makes no
      47             :  * representations about the suitability of this software for any
      48             :  * purpose.  It is provided "as is" without express or implied warranty.
      49             :  */
      50             : 
      51             : /** @file bits/stl_heap.h
      52             :  *  This is an internal header file, included by other library headers.
      53             :  *  Do not attempt to use it directly. @headername{queue}
      54             :  */
      55             : 
      56             : #ifndef _STL_HEAP_H
      57             : #define _STL_HEAP_H 1
      58             : 
      59             : #include <debug/debug.h>
      60             : #include <bits/move.h>
      61             : 
      62             : namespace std _GLIBCXX_VISIBILITY(default)
      63             : {
      64             : _GLIBCXX_BEGIN_NAMESPACE_VERSION
      65             : 
      66             :   /**
      67             :    * @defgroup heap_algorithms Heap
      68             :    * @ingroup sorting_algorithms
      69             :    */
      70             : 
      71             :   template<typename _RandomAccessIterator, typename _Distance>
      72             :     _Distance
      73             :     __is_heap_until(_RandomAccessIterator __first, _Distance __n)
      74             :     {
      75             :       _Distance __parent = 0;
      76             :       for (_Distance __child = 1; __child < __n; ++__child)
      77             :         {
      78             :           if (__first[__parent] < __first[__child])
      79             :             return __child;
      80             :           if ((__child & 1) == 0)
      81             :             ++__parent;
      82             :         }
      83             :       return __n;
      84             :     }
      85             : 
      86             :   template<typename _RandomAccessIterator, typename _Distance,
      87             :            typename _Compare>
      88             :     _Distance
      89             :     __is_heap_until(_RandomAccessIterator __first, _Distance __n,
      90             :                     _Compare __comp)
      91             :     {
      92             :       _Distance __parent = 0;
      93             :       for (_Distance __child = 1; __child < __n; ++__child)
      94             :         {
      95             :           if (__comp(__first[__parent], __first[__child]))
      96             :             return __child;
      97             :           if ((__child & 1) == 0)
      98             :             ++__parent;
      99             :         }
     100             :       return __n;
     101             :     }
     102             : 
     103             :   // __is_heap, a predicate testing whether or not a range is a heap.
     104             :   // This function is an extension, not part of the C++ standard.
     105             :   template<typename _RandomAccessIterator, typename _Distance>
     106             :     inline bool
     107             :     __is_heap(_RandomAccessIterator __first, _Distance __n)
     108             :     { return std::__is_heap_until(__first, __n) == __n; }
     109             : 
     110             :   template<typename _RandomAccessIterator, typename _Compare,
     111             :            typename _Distance>
     112             :     inline bool
     113             :     __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
     114             :     { return std::__is_heap_until(__first, __n, __comp) == __n; }
     115             : 
     116             :   template<typename _RandomAccessIterator>
     117             :     inline bool
     118             :     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     119             :     { return std::__is_heap(__first, std::distance(__first, __last)); }
     120             : 
     121             :   template<typename _RandomAccessIterator, typename _Compare>
     122             :     inline bool
     123             :     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
     124             :               _Compare __comp)
     125             :     { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
     126             : 
     127             :   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
     128             :   // + is_heap and is_heap_until in C++0x.
     129             : 
     130             :   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
     131             :     void
     132           0 :     __push_heap(_RandomAccessIterator __first,
     133             :                 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
     134             :     {
     135           0 :       _Distance __parent = (__holeIndex - 1) / 2;
     136           0 :       while (__holeIndex > __topIndex && *(__first + __parent) < __value)
     137             :         {
     138           0 :           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
     139           0 :           __holeIndex = __parent;
     140           0 :           __parent = (__holeIndex - 1) / 2;
     141             :         }
     142           0 :       *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
     143           0 :     }
     144             : 
     145             :   /**
     146             :    *  @brief  Push an element onto a heap.
     147             :    *  @param  first  Start of heap.
     148             :    *  @param  last   End of heap + element.
     149             :    *  @ingroup heap_algorithms
     150             :    *
     151             :    *  This operation pushes the element at last-1 onto the valid heap over the
     152             :    *  range [first,last-1).  After completion, [first,last) is a valid heap.
     153             :   */
     154             :   template<typename _RandomAccessIterator>
     155             :     inline void
     156             :     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     157             :     {
     158             :       typedef typename iterator_traits<_RandomAccessIterator>::value_type
     159             :           _ValueType;
     160             :       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
     161             :           _DistanceType;
     162             : 
     163             :       // concept requirements
     164             :       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
     165             :             _RandomAccessIterator>)
     166             :       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
     167             :       __glibcxx_requires_valid_range(__first, __last);
     168             :       __glibcxx_requires_heap(__first, __last - 1);
     169             : 
     170             :       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
     171             :       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
     172             :                        _DistanceType(0), _GLIBCXX_MOVE(__value));
     173             :     }
     174             : 
     175             :   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
     176             :            typename _Compare>
     177             :     void
     178             :     __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
     179             :                 _Distance __topIndex, _Tp __value, _Compare __comp)
     180             :     {
     181             :       _Distance __parent = (__holeIndex - 1) / 2;
     182             :       while (__holeIndex > __topIndex
     183             :              && __comp(*(__first + __parent), __value))
     184             :         {
     185             :           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
     186             :           __holeIndex = __parent;
     187             :           __parent = (__holeIndex - 1) / 2;
     188             :         }
     189             :       *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
     190             :     }
     191             : 
     192             :   /**
     193             :    *  @brief  Push an element onto a heap using comparison functor.
     194             :    *  @param  first  Start of heap.
     195             :    *  @param  last   End of heap + element.
     196             :    *  @param  comp   Comparison functor.
     197             :    *  @ingroup heap_algorithms
     198             :    *
     199             :    *  This operation pushes the element at last-1 onto the valid heap over the
     200             :    *  range [first,last-1).  After completion, [first,last) is a valid heap.
     201             :    *  Compare operations are performed using comp.
     202             :   */
     203             :   template<typename _RandomAccessIterator, typename _Compare>
     204             :     inline void
     205             :     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
     206             :               _Compare __comp)
     207             :     {
     208             :       typedef typename iterator_traits<_RandomAccessIterator>::value_type
     209             :           _ValueType;
     210             :       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
     211             :           _DistanceType;
     212             : 
     213             :       // concept requirements
     214             :       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
     215             :             _RandomAccessIterator>)
     216             :       __glibcxx_requires_valid_range(__first, __last);
     217             :       __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
     218             : 
     219             :       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
     220             :       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
     221             :                        _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
     222             :     }
     223             : 
     224             :   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
     225             :     void
     226           0 :     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
     227             :                   _Distance __len, _Tp __value)
     228             :     {
     229           0 :       const _Distance __topIndex = __holeIndex;
     230           0 :       _Distance __secondChild = __holeIndex;
     231           0 :       while (__secondChild < (__len - 1) / 2)
     232             :         {
     233           0 :           __secondChild = 2 * (__secondChild + 1);
     234           0 :           if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
     235           0 :             __secondChild--;
     236           0 :           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
     237           0 :           __holeIndex = __secondChild;
     238             :         }
     239           0 :       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
     240             :         {
     241           0 :           __secondChild = 2 * (__secondChild + 1);
     242           0 :           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
     243             :                                                      + (__secondChild - 1)));
     244           0 :           __holeIndex = __secondChild - 1;
     245             :         }
     246           0 :       std::__push_heap(__first, __holeIndex, __topIndex,
     247             :                        _GLIBCXX_MOVE(__value));
     248           0 :     }
     249             : 
     250             :   template<typename _RandomAccessIterator>
     251             :     inline void
     252           0 :     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
     253             :                _RandomAccessIterator __result)
     254             :     {
     255             :       typedef typename iterator_traits<_RandomAccessIterator>::value_type
     256             :         _ValueType;
     257             :       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
     258             :         _DistanceType;
     259             : 
     260           0 :       _ValueType __value = _GLIBCXX_MOVE(*__result);
     261           0 :       *__result = _GLIBCXX_MOVE(*__first);
     262           0 :       std::__adjust_heap(__first, _DistanceType(0),
     263             :                          _DistanceType(__last - __first),
     264             :                          _GLIBCXX_MOVE(__value));
     265           0 :     }
     266             : 
     267             :   /**
     268             :    *  @brief  Pop an element off a heap.
     269             :    *  @param  first  Start of heap.
     270             :    *  @param  last   End of heap.
     271             :    *  @ingroup heap_algorithms
     272             :    *
     273             :    *  This operation pops the top of the heap.  The elements first and last-1
     274             :    *  are swapped and [first,last-1) is made into a heap.
     275             :   */
     276             :   template<typename _RandomAccessIterator>
     277             :     inline void
     278             :     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     279             :     {
     280             :       typedef typename iterator_traits<_RandomAccessIterator>::value_type
     281             :         _ValueType;
     282             : 
     283             :       // concept requirements
     284             :       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
     285             :             _RandomAccessIterator>)
     286             :       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
     287             :       __glibcxx_requires_valid_range(__first, __last);
     288             :       __glibcxx_requires_heap(__first, __last);
     289             : 
     290             :       --__last;
     291             :       std::__pop_heap(__first, __last, __last);
     292             :     }
     293             : 
     294             :   template<typename _RandomAccessIterator, typename _Distance,
     295             :            typename _Tp, typename _Compare>
     296             :     void
     297             :     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
     298             :                   _Distance __len, _Tp __value, _Compare __comp)
     299             :     {
     300             :       const _Distance __topIndex = __holeIndex;
     301             :       _Distance __secondChild = __holeIndex;
     302             :       while (__secondChild < (__len - 1) / 2)
     303             :         {
     304             :           __secondChild = 2 * (__secondChild + 1);
     305             :           if (__comp(*(__first + __secondChild),
     306             :                      *(__first + (__secondChild - 1))))
     307             :             __secondChild--;
     308             :           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
     309             :           __holeIndex = __secondChild;
     310             :         }
     311             :       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
     312             :         {
     313             :           __secondChild = 2 * (__secondChild + 1);
     314             :           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
     315             :                                                      + (__secondChild - 1)));
     316             :           __holeIndex = __secondChild - 1;
     317             :         }
     318             :       std::__push_heap(__first, __holeIndex, __topIndex, 
     319             :                        _GLIBCXX_MOVE(__value), __comp);      
     320             :     }
     321             : 
     322             :   template<typename _RandomAccessIterator, typename _Compare>
     323             :     inline void
     324             :     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
     325             :                _RandomAccessIterator __result, _Compare __comp)
     326             :     {
     327             :       typedef typename iterator_traits<_RandomAccessIterator>::value_type
     328             :         _ValueType;
     329             :       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
     330             :         _DistanceType;
     331             : 
     332             :       _ValueType __value = _GLIBCXX_MOVE(*__result);
     333             :       *__result = _GLIBCXX_MOVE(*__first);
     334             :       std::__adjust_heap(__first, _DistanceType(0),
     335             :                          _DistanceType(__last - __first),
     336             :                          _GLIBCXX_MOVE(__value), __comp);
     337             :     }
     338             : 
     339             :   /**
     340             :    *  @brief  Pop an element off a heap using comparison functor.
     341             :    *  @param  first  Start of heap.
     342             :    *  @param  last   End of heap.
     343             :    *  @param  comp   Comparison functor to use.
     344             :    *  @ingroup heap_algorithms
     345             :    *
     346             :    *  This operation pops the top of the heap.  The elements first and last-1
     347             :    *  are swapped and [first,last-1) is made into a heap.  Comparisons are
     348             :    *  made using comp.
     349             :   */
     350             :   template<typename _RandomAccessIterator, typename _Compare>
     351             :     inline void
     352             :     pop_heap(_RandomAccessIterator __first,
     353             :              _RandomAccessIterator __last, _Compare __comp)
     354             :     {
     355             :       // concept requirements
     356             :       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
     357             :             _RandomAccessIterator>)
     358             :       __glibcxx_requires_valid_range(__first, __last);
     359             :       __glibcxx_requires_heap_pred(__first, __last, __comp);
     360             : 
     361             :       --__last;
     362             :       std::__pop_heap(__first, __last, __last, __comp);
     363             :     }
     364             : 
     365             :   /**
     366             :    *  @brief  Construct a heap over a range.
     367             :    *  @param  first  Start of heap.
     368             :    *  @param  last   End of heap.
     369             :    *  @ingroup heap_algorithms
     370             :    *
     371             :    *  This operation makes the elements in [first,last) into a heap.
     372             :   */
     373             :   template<typename _RandomAccessIterator>
     374             :     void
     375           0 :     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     376             :     {
     377             :       typedef typename iterator_traits<_RandomAccessIterator>::value_type
     378             :           _ValueType;
     379             :       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
     380             :           _DistanceType;
     381             : 
     382             :       // concept requirements
     383             :       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
     384             :             _RandomAccessIterator>)
     385             :       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
     386             :       __glibcxx_requires_valid_range(__first, __last);
     387             : 
     388           0 :       if (__last - __first < 2)
     389           0 :         return;
     390             : 
     391           0 :       const _DistanceType __len = __last - __first;
     392           0 :       _DistanceType __parent = (__len - 2) / 2;
     393           0 :       while (true)
     394             :         {
     395           0 :           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
     396           0 :           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
     397           0 :           if (__parent == 0)
     398           0 :             return;
     399           0 :           __parent--;
     400             :         }
     401             :     }
     402             : 
     403             :   /**
     404             :    *  @brief  Construct a heap over a range using comparison functor.
     405             :    *  @param  first  Start of heap.
     406             :    *  @param  last   End of heap.
     407             :    *  @param  comp   Comparison functor to use.
     408             :    *  @ingroup heap_algorithms
     409             :    *
     410             :    *  This operation makes the elements in [first,last) into a heap.
     411             :    *  Comparisons are made using comp.
     412             :   */
     413             :   template<typename _RandomAccessIterator, typename _Compare>
     414             :     void
     415             :     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
     416             :               _Compare __comp)
     417             :     {
     418             :       typedef typename iterator_traits<_RandomAccessIterator>::value_type
     419             :           _ValueType;
     420             :       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
     421             :           _DistanceType;
     422             : 
     423             :       // concept requirements
     424             :       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
     425             :             _RandomAccessIterator>)
     426             :       __glibcxx_requires_valid_range(__first, __last);
     427             : 
     428             :       if (__last - __first < 2)
     429             :         return;
     430             : 
     431             :       const _DistanceType __len = __last - __first;
     432             :       _DistanceType __parent = (__len - 2) / 2;
     433             :       while (true)
     434             :         {
     435             :           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
     436             :           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
     437             :                              __comp);
     438             :           if (__parent == 0)
     439             :             return;
     440             :           __parent--;
     441             :         }
     442             :     }
     443             : 
     444             :   /**
     445             :    *  @brief  Sort a heap.
     446             :    *  @param  first  Start of heap.
     447             :    *  @param  last   End of heap.
     448             :    *  @ingroup heap_algorithms
     449             :    *
     450             :    *  This operation sorts the valid heap in the range [first,last).
     451             :   */
     452             :   template<typename _RandomAccessIterator>
     453             :     void
     454           0 :     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     455             :     {
     456             :       // concept requirements
     457             :       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
     458             :             _RandomAccessIterator>)
     459             :       __glibcxx_function_requires(_LessThanComparableConcept<
     460             :             typename iterator_traits<_RandomAccessIterator>::value_type>)
     461             :       __glibcxx_requires_valid_range(__first, __last);
     462             :       __glibcxx_requires_heap(__first, __last);
     463             : 
     464           0 :       while (__last - __first > 1)
     465             :         {
     466           0 :           --__last;
     467           0 :           std::__pop_heap(__first, __last, __last);
     468             :         }
     469           0 :     }
     470             : 
     471             :   /**
     472             :    *  @brief  Sort a heap using comparison functor.
     473             :    *  @param  first  Start of heap.
     474             :    *  @param  last   End of heap.
     475             :    *  @param  comp   Comparison functor to use.
     476             :    *  @ingroup heap_algorithms
     477             :    *
     478             :    *  This operation sorts the valid heap in the range [first,last).
     479             :    *  Comparisons are made using comp.
     480             :   */
     481             :   template<typename _RandomAccessIterator, typename _Compare>
     482             :     void
     483             :     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
     484             :               _Compare __comp)
     485             :     {
     486             :       // concept requirements
     487             :       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
     488             :             _RandomAccessIterator>)
     489             :       __glibcxx_requires_valid_range(__first, __last);
     490             :       __glibcxx_requires_heap_pred(__first, __last, __comp);
     491             : 
     492             :       while (__last - __first > 1)
     493             :         {
     494             :           --__last;
     495             :           std::__pop_heap(__first, __last, __last, __comp);
     496             :         }
     497             :     }
     498             : 
     499             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     500             :   /**
     501             :    *  @brief  Search the end of a heap.
     502             :    *  @param  first  Start of range.
     503             :    *  @param  last   End of range.
     504             :    *  @return  An iterator pointing to the first element not in the heap.
     505             :    *  @ingroup heap_algorithms
     506             :    *
     507             :    *  This operation returns the last iterator i in [first, last) for which
     508             :    *  the range [first, i) is a heap.
     509             :   */
     510             :   template<typename _RandomAccessIterator>
     511             :     inline _RandomAccessIterator
     512             :     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
     513             :     {
     514             :       // concept requirements
     515             :       __glibcxx_function_requires(_RandomAccessIteratorConcept<
     516             :             _RandomAccessIterator>)
     517             :       __glibcxx_function_requires(_LessThanComparableConcept<
     518             :             typename iterator_traits<_RandomAccessIterator>::value_type>)
     519             :       __glibcxx_requires_valid_range(__first, __last);
     520             : 
     521             :       return __first + std::__is_heap_until(__first, std::distance(__first,
     522             :                                                                    __last));
     523             :     }
     524             : 
     525             :   /**
     526             :    *  @brief  Search the end of a heap using comparison functor.
     527             :    *  @param  first  Start of range.
     528             :    *  @param  last   End of range.
     529             :    *  @param  comp   Comparison functor to use.
     530             :    *  @return  An iterator pointing to the first element not in the heap.
     531             :    *  @ingroup heap_algorithms
     532             :    *
     533             :    *  This operation returns the last iterator i in [first, last) for which
     534             :    *  the range [first, i) is a heap.  Comparisons are made using comp.
     535             :   */
     536             :   template<typename _RandomAccessIterator, typename _Compare>
     537             :     inline _RandomAccessIterator
     538             :     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
     539             :                   _Compare __comp)
     540             :     {
     541             :       // concept requirements
     542             :       __glibcxx_function_requires(_RandomAccessIteratorConcept<
     543             :             _RandomAccessIterator>)
     544             :       __glibcxx_requires_valid_range(__first, __last);
     545             : 
     546             :       return __first + std::__is_heap_until(__first, std::distance(__first,
     547             :                                                                    __last),
     548             :                                             __comp);
     549             :     }
     550             : 
     551             :   /**
     552             :    *  @brief  Determines whether a range is a heap.
     553             :    *  @param  first  Start of range.
     554             :    *  @param  last   End of range.
     555             :    *  @return  True if range is a heap, false otherwise.
     556             :    *  @ingroup heap_algorithms
     557             :   */
     558             :   template<typename _RandomAccessIterator>
     559             :     inline bool
     560             :     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     561             :     { return std::is_heap_until(__first, __last) == __last; }
     562             : 
     563             :   /**
     564             :    *  @brief  Determines whether a range is a heap using comparison functor.
     565             :    *  @param  first  Start of range.
     566             :    *  @param  last   End of range.
     567             :    *  @param  comp   Comparison functor to use.
     568             :    *  @return  True if range is a heap, false otherwise.
     569             :    *  @ingroup heap_algorithms
     570             :   */
     571             :   template<typename _RandomAccessIterator, typename _Compare>
     572             :     inline bool
     573             :     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
     574             :             _Compare __comp)
     575             :     { return std::is_heap_until(__first, __last, __comp) == __last; }
     576             : #endif
     577             : 
     578             : _GLIBCXX_END_NAMESPACE_VERSION
     579             : } // namespace
     580             : 
     581             : #endif /* _STL_HEAP_H */

Generated by: LCOV version 1.9

The wpkg tool is an open source tool created by Made to Order Software Corporation.