Subversion Repositories altor32

// Heap implementation -*- C++ -*-

// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,

// 2011 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>

namespace std _GLIBCXX_VISIBILITY(default)

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /**

   * @defgroup heap_algorithms Heap

   * @ingroup sorting_algorithms

   */

  template<typename _RandomAccessIterator, typename _Distance>

    _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<typename _RandomAccessIterator, typename _Distance,

           typename _Compare>

    _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>

    inline bool

    __is_heap(_RandomAccessIterator __first, _Distance __n)

    { return std::__is_heap_until(__first, __n) == __n; }

  template<typename _RandomAccessIterator, typename _Compare,

           typename _Distance>

    inline bool

    __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)

    { return std::__is_heap_until(__first, __n, __comp) == __n; }

  template<typename _RandomAccessIterator>

    inline bool

    __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

    { return std::__is_heap(__first, std::distance(__first, __last)); }

  template<typename _RandomAccessIterator, typename _Compare>

    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<typename _RandomAccessIterator, typename _Distance, typename _Tp>

    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_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>

    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<typename _RandomAccessIterator, typename _Distance, typename _Tp,

           typename _Compare>

    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_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>

    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<typename _RandomAccessIterator, typename _Distance, typename _Tp>

    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<typename _RandomAccessIterator>

    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.

   *  @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>

    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_non_empty_range(__first, __last);

      __glibcxx_requires_valid_range(__first, __last);

      __glibcxx_requires_heap(__first, __last);

      --__last;

      std::__pop_heap(__first, __last, __last);

    }

  template<typename _RandomAccessIterator, typename _Distance,

           typename _Tp, typename _Compare>

    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<typename _RandomAccessIterator, typename _Compare>

    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 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>

    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_non_empty_range(__first, __last);

      __glibcxx_requires_heap_pred(__first, __last, __comp);

      --__last;

      std::__pop_heap(__first, __last, __last, __comp);

    }

  /**

   *  @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>

    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_algorithms

   *

   *  This operation makes the elements in [__first,__last) into a heap.

   *  Comparisons are made using __comp.

  */

  template<typename _RandomAccessIterator, typename _Compare>

    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_algorithms

   *

   *  This operation sorts the valid heap in the range [__first,__last).

  */

  template<typename _RandomAccessIterator>

    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)

        {

          --__last;

          std::__pop_heap(__first, __last, __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_algorithms

   *

   *  This operation sorts the valid heap in the range [__first,__last).

   *  Comparisons are made using __comp.

  */

  template<typename _RandomAccessIterator, typename _Compare>

    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)

        {

          --__last;

          std::__pop_heap(__first, __last, __last, __comp);

        }

    }

#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>

    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_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>

    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_algorithms

  */

  template<typename _RandomAccessIterator>

    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>

    inline bool

    is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,

            _Compare __comp)

    { return std::is_heap_until(__first, __last, __comp) == __last; }

#endif

_GLIBCXX_END_NAMESPACE_VERSION

} // namespace

#endif /* _STL_HEAP_H */