stl_heap.h

Go to the documentation of this file.

// Heap implementation -*- C++ -*-
 
// Copyright (C) 2001-2022 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 3, 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.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.
 
/*
 *
 * 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 bits/stl_heap.h
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly. @headername{queue}
 */
 
#ifndef _STL_HEAP_H
#define _STL_HEAP_H 1
 
#include <debug/debug.h>
#include <bits/move.h>
#include <bits/predefined_ops.h>
#include <bits/stl_iterator_base_funcs.h>
 
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
 
  /**
   * @defgroup heap_algorithms Heap
   * @ingroup sorting_algorithms
   */
 
  template<typename _RandomAccessIterator, typename _Distance,
           typename _Compare>
    _GLIBCXX20_CONSTEXPR
    _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<typename _RandomAccessIterator, typename _Distance>
    _GLIBCXX20_CONSTEXPR
    inline bool
    __is_heap(_RandomAccessIterator __first, _Distance __n)
    {
      __gnu_cxx::__ops::_Iter_less_iter __comp;
      return std::__is_heap_until(__first, __n, __comp) == __n;
    }
 
  template<typename _RandomAccessIterator, typename _Compare,
           typename _Distance>
    _GLIBCXX20_CONSTEXPR
    inline bool
    __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
    {
      typedef __decltype(__comp) _Cmp;
      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
      return std::__is_heap_until(__first, __n, __cmp) == __n;
    }
 
  template<typename _RandomAccessIterator>
    _GLIBCXX20_CONSTEXPR
    inline bool
    __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    { return std::__is_heap(__first, std::distance(__first, __last)); }
 
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline bool
    __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
              _Compare __comp)
    {
      return std::__is_heap(__first, _GLIBCXX_MOVE(__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<typename _RandomAccessIterator, typename _Distance, typename _Tp,
           typename _Compare>
    _GLIBCXX20_CONSTEXPR
    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.
   *  @param  __first  Start of heap.
   *  @param  __last   End of heap + element.
   *  @ingroup heap_algorithms
   *
   *  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<typename _RandomAccessIterator>
    _GLIBCXX20_CONSTEXPR
    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_irreflexive(__first, __last);
      __glibcxx_requires_heap(__first, __last - 1);
 
      __gnu_cxx::__ops::_Iter_less_val __comp;
      _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
      std::__push_heap(__first, _DistanceType((__last - __first) - 1),
                       _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
    }
 
  /**
   *  @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_algorithms
   *
   *  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<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    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_irreflexive_pred(__first, __last, __comp);
      __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
 
      __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
        __cmp(_GLIBCXX_MOVE(__comp));
      _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
      std::__push_heap(__first, _DistanceType((__last - __first) - 1),
                       _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
    }
 
  template<typename _RandomAccessIterator, typename _Distance,
           typename _Tp, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    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;
        }
      __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
        __cmp(_GLIBCXX_MOVE(__comp));
      std::__push_heap(__first, __holeIndex, __topIndex,
                       _GLIBCXX_MOVE(__value), __cmp);
    }
 
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    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(__value), __comp);
    }
 
  /**
   *  @brief  Pop an element off a heap.
   *  @param  __first  Start of heap.
   *  @param  __last   End of heap.
   *  @pre    [__first, __last) is a valid, non-empty range.
   *  @ingroup heap_algorithms
   *
   *  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<typename _RandomAccessIterator>
    _GLIBCXX20_CONSTEXPR
    inline void
    pop_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_non_empty_range(__first, __last);
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_irreflexive(__first, __last);
      __glibcxx_requires_heap(__first, __last);
 
      if (__last - __first > 1)
        {
          --__last;
          __gnu_cxx::__ops::_Iter_less_iter __comp;
          std::__pop_heap(__first, __last, __last, __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_algorithms
   *
   *  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<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    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_irreflexive_pred(__first, __last, __comp);
      __glibcxx_requires_non_empty_range(__first, __last);
      __glibcxx_requires_heap_pred(__first, __last, __comp);
 
      if (__last - __first > 1)
        {
          typedef __decltype(__comp) _Cmp;
          __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
          --__last;
          std::__pop_heap(__first, __last, __last, __cmp);
        }
    }
 
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    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;
 
      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  Construct a heap over a range.
   *  @param  __first  Start of heap.
   *  @param  __last   End of heap.
   *  @ingroup heap_algorithms
   *
   *  This operation makes the elements in [__first,__last) into a heap.
  */
  template<typename _RandomAccessIterator>
    _GLIBCXX20_CONSTEXPR
    inline void
    make_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_irreflexive(__first, __last);
 
      __gnu_cxx::__ops::_Iter_less_iter __comp;
      std::__make_heap(__first, __last, __comp);
    }
 
  /**
   *  @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_algorithms
   *
   *  This operation makes the elements in [__first,__last) into a heap.
   *  Comparisons are made using __comp.
  */
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
              _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
      typedef __decltype(__comp) _Cmp;
      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
      std::__make_heap(__first, __last, __cmp);
    }
 
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
                _Compare& __comp)
    {
      while (__last - __first > 1)
        {
          --__last;
          std::__pop_heap(__first, __last, __last, __comp);
        }
    }
 
  /**
   *  @brief  Sort a heap.
   *  @param  __first  Start of heap.
   *  @param  __last   End of heap.
   *  @ingroup heap_algorithms
   *
   *  This operation sorts the valid heap in the range [__first,__last).
  */
  template<typename _RandomAccessIterator>
    _GLIBCXX20_CONSTEXPR
    inline 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_irreflexive(__first, __last);
      __glibcxx_requires_heap(__first, __last);
 
      __gnu_cxx::__ops::_Iter_less_iter __comp;
      std::__sort_heap(__first, __last, __comp);
    }
 
  /**
   *  @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_algorithms
   *
   *  This operation sorts the valid heap in the range [__first,__last).
   *  Comparisons are made using __comp.
  */
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline 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_irreflexive_pred(__first, __last, __comp);
      __glibcxx_requires_heap_pred(__first, __last, __comp);
 
      typedef __decltype(__comp) _Cmp;
      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
      std::__sort_heap(__first, __last, __cmp);
    }
 
#if __cplusplus >= 201103L
  /**
   *  @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_algorithms
   *
   *  This operation returns the last iterator i in [__first, __last) for which
   *  the range [__first, i) is a heap.
  */
  template<typename _RandomAccessIterator>
    _GLIBCXX20_CONSTEXPR
    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);
      __glibcxx_requires_irreflexive(__first, __last);
 
      __gnu_cxx::__ops::_Iter_less_iter __comp;
      return __first + 
        std::__is_heap_until(__first, std::distance(__first, __last), __comp);
    }
 
  /**
   *  @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_algorithms
   *
   *  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<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline _RandomAccessIterator
    is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
                  _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
      typedef __decltype(__comp) _Cmp;
      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
      return __first
        + std::__is_heap_until(__first, std::distance(__first, __last), __cmp);
    }
 
  /**
   *  @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_algorithms
  */
  template<typename _RandomAccessIterator>
    _GLIBCXX20_CONSTEXPR
    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_algorithms
  */
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline bool
    is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
            _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
      const auto __dist = std::distance(__first, __last);
      typedef __decltype(__comp) _Cmp;
      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
      return std::__is_heap_until(__first, __dist, __cmp) == __dist;
    }
#endif
 
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace
 
#endif /* _STL_HEAP_H */