Subversion Repositories Kolibri OS

/*

 *

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

 */

/* NOTE: This is an internal header file, included by other STL headers.

 *   You should not attempt to use it directly.

 */

#ifndef _CPP_BITS_STL_HEAP_H

#define _CPP_BITS_STL_HEAP_H 1

namespace std

{

// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.

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) = *(__first + __parent);

    __holeIndex = __parent;

    __parent = (__holeIndex - 1) / 2;

  }

  *(__first + __holeIndex) = __value;

}

template 

inline void

__push_heap_aux(_RandomAccessIterator __first,

                _RandomAccessIterator __last, _Distance*, _Tp*)

{

  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),

              _Tp(*(__last - 1)));

}

template 

inline void

push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

{

  // concept requirements

  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<

        _RandomAccessIterator>);

  __glibcpp_function_requires(_LessThanComparableConcept<

        typename iterator_traits<_RandomAccessIterator>::value_type>);

  __push_heap_aux(__first, __last,

                  __distance_type(__first), __value_type(__first));

}

template 

          class _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) = *(__first + __parent);

    __holeIndex = __parent;

    __parent = (__holeIndex - 1) / 2;

  }

  *(__first + __holeIndex) = __value;

}

template 

          class _Distance, class _Tp>

inline void

__push_heap_aux(_RandomAccessIterator __first,

                _RandomAccessIterator __last, _Compare __comp,

                _Distance*, _Tp*)

{

  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),

              _Tp(*(__last - 1)), __comp);

}

template 

inline void

push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,

          _Compare __comp)

{

  // concept requirements

  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<

        _RandomAccessIterator>);

  __push_heap_aux(__first, __last, __comp,

                  __distance_type(__first), __value_type(__first));

}

template 

void

__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,

              _Distance __len, _Tp __value)

{

  _Distance __topIndex = __holeIndex;

  _Distance __secondChild = 2 * __holeIndex + 2;

  while (__secondChild < __len) {

    if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))

      __secondChild--;

    *(__first + __holeIndex) = *(__first + __secondChild);

    __holeIndex = __secondChild;

    __secondChild = 2 * (__secondChild + 1);

  }

  if (__secondChild == __len) {

    *(__first + __holeIndex) = *(__first + (__secondChild - 1));

    __holeIndex = __secondChild - 1;

  }

  __push_heap(__first, __holeIndex, __topIndex, __value);

}

template 

inline void

__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,

           _RandomAccessIterator __result, _Tp __value, _Distance*)

{

  *__result = *__first;

  __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);

}

template 

inline void

__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,

               _Tp*)

{

  __pop_heap(__first, __last - 1, __last - 1,

             _Tp(*(__last - 1)), __distance_type(__first));

}

template 

inline void pop_heap(_RandomAccessIterator __first,

                     _RandomAccessIterator __last)

{

  // concept requirements

  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<

        _RandomAccessIterator>);

  __glibcpp_function_requires(_LessThanComparableConcept<

        typename iterator_traits<_RandomAccessIterator>::value_type>);

  __pop_heap_aux(__first, __last, __value_type(__first));

}

template 

          class _Tp, class _Compare>

void

__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,

              _Distance __len, _Tp __value, _Compare __comp)

{

  _Distance __topIndex = __holeIndex;

  _Distance __secondChild = 2 * __holeIndex + 2;

  while (__secondChild < __len) {

    if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))

      __secondChild--;

    *(__first + __holeIndex) = *(__first + __secondChild);

    __holeIndex = __secondChild;

    __secondChild = 2 * (__secondChild + 1);

  }

  if (__secondChild == __len) {

    *(__first + __holeIndex) = *(__first + (__secondChild - 1));

    __holeIndex = __secondChild - 1;

  }

  __push_heap(__first, __holeIndex, __topIndex, __value, __comp);

}

template 

          class _Distance>

inline void

__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,

           _RandomAccessIterator __result, _Tp __value, _Compare __comp,

           _Distance*)

{

  *__result = *__first;

  __adjust_heap(__first, _Distance(0), _Distance(__last - __first),

                __value, __comp);

}

template 

inline void

__pop_heap_aux(_RandomAccessIterator __first,

               _RandomAccessIterator __last, _Tp*, _Compare __comp)

{

  __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,

             __distance_type(__first));

}

template 

inline void

pop_heap(_RandomAccessIterator __first,

         _RandomAccessIterator __last, _Compare __comp)

{

  // concept requirements

  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<

        _RandomAccessIterator>);

  __pop_heap_aux(__first, __last, __value_type(__first), __comp);

}

template 

void

__make_heap(_RandomAccessIterator __first,

            _RandomAccessIterator __last, _Tp*, _Distance*)

{

  if (__last - __first < 2) return;

  _Distance __len = __last - __first;

  _Distance __parent = (__len - 2)/2;

  while (true) {

    __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));

    if (__parent == 0) return;

    __parent--;

  }

}

template 

inline void

make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

{

  // concept requirements

  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<

        _RandomAccessIterator>);

  __glibcpp_function_requires(_LessThanComparableConcept<

        typename iterator_traits<_RandomAccessIterator>::value_type>);

  __make_heap(__first, __last,

              __value_type(__first), __distance_type(__first));

}

template 

          class _Tp, class _Distance>

void

__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,

            _Compare __comp, _Tp*, _Distance*)

{

  if (__last - __first < 2) return;

  _Distance __len = __last - __first;

  _Distance __parent = (__len - 2)/2;

  while (true) {

    __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),

                  __comp);

    if (__parent == 0) return;

    __parent--;

  }

}

template 

inline void

make_heap(_RandomAccessIterator __first,

          _RandomAccessIterator __last, _Compare __comp)

{

  // concept requirements

  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<

        _RandomAccessIterator>);

  __make_heap(__first, __last, __comp,

              __value_type(__first), __distance_type(__first));

}

template 

void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

{

  // concept requirements

  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<

        _RandomAccessIterator>);

  __glibcpp_function_requires(_LessThanComparableConcept<

        typename iterator_traits<_RandomAccessIterator>::value_type>);

  while (__last - __first > 1)

    pop_heap(__first, __last--);

}

template 

void

sort_heap(_RandomAccessIterator __first,

          _RandomAccessIterator __last, _Compare __comp)

{

  // concept requirements

  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<

        _RandomAccessIterator>);

  while (__last - __first > 1)

    pop_heap(__first, __last--, __comp);

}

} // namespace std

#endif /* _CPP_BITS_STL_HEAP_H */

// Local Variables:

// mode:C++

// End: