home *** CD-ROM | disk | FTP | other *** search
/ Beginning C++ Through Gam…rogramming (2nd Edition) / BCGP2E.ISO / bloodshed / devcpp-4.9.9.2_setup.exe / stl_heap.h < prev    next >
C/C++ Source or Header  |  2005-01-29  |  16KB  |  468 lines
  1. // Heap implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2001, 2004 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the
  7. // terms of the GNU General Public License as published by the
  8. // Free Software Foundation; either version 2, or (at your option)
  9. // any later version.
  10.  
  11. // This library is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. // GNU General Public License for more details.
  15.  
  16. // You should have received a copy of the GNU General Public License along
  17. // with this library; see the file COPYING.  If not, write to the Free
  18. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19. // USA.
  20.  
  21. // As a special exception, you may use this file as part of a free software
  22. // library without restriction.  Specifically, if other files instantiate
  23. // templates or use macros or inline functions from this file, or you compile
  24. // this file and link it with other files to produce an executable, this
  25. // file does not by itself cause the resulting executable to be covered by
  26. // the GNU General Public License.  This exception does not however
  27. // invalidate any other reasons why the executable file might be covered by
  28. // the GNU General Public License.
  29.  
  30. /*
  31.  *
  32.  * Copyright (c) 1994
  33.  * Hewlett-Packard Company
  34.  *
  35.  * Permission to use, copy, modify, distribute and sell this software
  36.  * and its documentation for any purpose is hereby granted without fee,
  37.  * provided that the above copyright notice appear in all copies and
  38.  * that both that copyright notice and this permission notice appear
  39.  * in supporting documentation.  Hewlett-Packard Company makes no
  40.  * representations about the suitability of this software for any
  41.  * purpose.  It is provided "as is" without express or implied warranty.
  42.  *
  43.  * Copyright (c) 1997
  44.  * Silicon Graphics Computer Systems, Inc.
  45.  *
  46.  * Permission to use, copy, modify, distribute and sell this software
  47.  * and its documentation for any purpose is hereby granted without fee,
  48.  * provided that the above copyright notice appear in all copies and
  49.  * that both that copyright notice and this permission notice appear
  50.  * in supporting documentation.  Silicon Graphics makes no
  51.  * representations about the suitability of this software for any
  52.  * purpose.  It is provided "as is" without express or implied warranty.
  53.  */
  54.  
  55. /** @file stl_heap.h
  56.  *  This is an internal header file, included by other library headers.
  57.  *  You should not attempt to use it directly.
  58.  */
  59.  
  60. #ifndef _STL_HEAP_H
  61. #define _STL_HEAP_H 1
  62.  
  63. #include <debug/debug.h>
  64.  
  65. namespace std
  66. {
  67.   // is_heap, a predicate testing whether or not a range is
  68.   // a heap.  This function is an extension, not part of the C++
  69.   // standard.
  70.   template<typename _RandomAccessIterator, typename _Distance>
  71.     bool
  72.     __is_heap(_RandomAccessIterator __first, _Distance __n)
  73.     {
  74.       _Distance __parent = 0;
  75.       for (_Distance __child = 1; __child < __n; ++__child)
  76.     {
  77.       if (__first[__parent] < __first[__child])
  78.         return false;
  79.       if ((__child & 1) == 0)
  80.         ++__parent;
  81.     }
  82.       return true;
  83.     }
  84.  
  85.   template<typename _RandomAccessIterator, typename _Distance,
  86.            typename _StrictWeakOrdering>
  87.     bool
  88.     __is_heap(_RandomAccessIterator __first, _StrictWeakOrdering __comp,
  89.           _Distance __n)
  90.     {
  91.       _Distance __parent = 0;
  92.       for (_Distance __child = 1; __child < __n; ++__child)
  93.     {
  94.       if (__comp(__first[__parent], __first[__child]))
  95.         return false;
  96.       if ((__child & 1) == 0)
  97.         ++__parent;
  98.     }
  99.       return true;
  100.     }
  101.  
  102.   template<typename _RandomAccessIterator>
  103.     bool
  104.     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  105.     { return std::__is_heap(__first, std::distance(__first, __last)); }
  106.  
  107.   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
  108.     bool
  109.     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  110.         _StrictWeakOrdering __comp)
  111.     { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
  112.  
  113.   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
  114.  
  115.   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
  116.     void
  117.     __push_heap(_RandomAccessIterator __first,
  118.         _Distance __holeIndex, _Distance __topIndex, _Tp __value)
  119.     {
  120.       _Distance __parent = (__holeIndex - 1) / 2;
  121.       while (__holeIndex > __topIndex && *(__first + __parent) < __value)
  122.     {
  123.       *(__first + __holeIndex) = *(__first + __parent);
  124.       __holeIndex = __parent;
  125.       __parent = (__holeIndex - 1) / 2;
  126.     }
  127.       *(__first + __holeIndex) = __value;
  128.     }
  129.  
  130.   /**
  131.    *  @brief  Push an element onto a heap.
  132.    *  @param  first  Start of heap.
  133.    *  @param  last   End of heap + element.
  134.    *  @ingroup heap
  135.    *
  136.    *  This operation pushes the element at last-1 onto the valid heap over the
  137.    *  range [first,last-1).  After completion, [first,last) is a valid heap.
  138.   */
  139.   template<typename _RandomAccessIterator>
  140.     inline void
  141.     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  142.     {
  143.       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  144.       _ValueType;
  145.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  146.       _DistanceType;
  147.  
  148.       // concept requirements
  149.       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
  150.         _RandomAccessIterator>)
  151.       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
  152.       __glibcxx_requires_valid_range(__first, __last);
  153.       //      __glibcxx_requires_heap(__first, __last - 1);
  154.  
  155.       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
  156.                _DistanceType(0), _ValueType(*(__last - 1)));
  157.     }
  158.  
  159.   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
  160.         typename _Compare>
  161.     void
  162.     __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  163.         _Distance __topIndex, _Tp __value, _Compare __comp)
  164.     {
  165.       _Distance __parent = (__holeIndex - 1) / 2;
  166.       while (__holeIndex > __topIndex
  167.          && __comp(*(__first + __parent), __value))
  168.     {
  169.       *(__first + __holeIndex) = *(__first + __parent);
  170.       __holeIndex = __parent;
  171.       __parent = (__holeIndex - 1) / 2;
  172.     }
  173.       *(__first + __holeIndex) = __value;
  174.     }
  175.  
  176.   /**
  177.    *  @brief  Push an element onto a heap using comparison functor.
  178.    *  @param  first  Start of heap.
  179.    *  @param  last   End of heap + element.
  180.    *  @param  comp   Comparison functor.
  181.    *  @ingroup heap
  182.    *
  183.    *  This operation pushes the element at last-1 onto the valid heap over the
  184.    *  range [first,last-1).  After completion, [first,last) is a valid heap.
  185.    *  Compare operations are performed using comp.
  186.   */
  187.   template<typename _RandomAccessIterator, typename _Compare>
  188.     inline void
  189.     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  190.           _Compare __comp)
  191.     {
  192.       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  193.       _ValueType;
  194.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  195.       _DistanceType;
  196.  
  197.       // concept requirements
  198.       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
  199.         _RandomAccessIterator>)
  200.       __glibcxx_requires_valid_range(__first, __last);
  201.       __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
  202.  
  203.       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
  204.                _DistanceType(0), _ValueType(*(__last - 1)), __comp);
  205.     }
  206.  
  207.   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
  208.     void
  209.     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  210.           _Distance __len, _Tp __value)
  211.     {
  212.       const _Distance __topIndex = __holeIndex;
  213.       _Distance __secondChild = 2 * __holeIndex + 2;
  214.       while (__secondChild < __len)
  215.     {
  216.       if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
  217.         __secondChild--;
  218.       *(__first + __holeIndex) = *(__first + __secondChild);
  219.       __holeIndex = __secondChild;
  220.       __secondChild = 2 * (__secondChild + 1);
  221.     }
  222.       if (__secondChild == __len)
  223.     {
  224.       *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  225.       __holeIndex = __secondChild - 1;
  226.     }
  227.       std::__push_heap(__first, __holeIndex, __topIndex, __value);
  228.     }
  229.  
  230.   template<typename _RandomAccessIterator, typename _Tp>
  231.     inline void
  232.     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  233.            _RandomAccessIterator __result, _Tp __value)
  234.     {
  235.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  236.     _Distance;
  237.       *__result = *__first;
  238.       std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
  239.              __value);
  240.     }
  241.  
  242.   /**
  243.    *  @brief  Pop an element off a heap.
  244.    *  @param  first  Start of heap.
  245.    *  @param  last   End of heap.
  246.    *  @ingroup heap
  247.    *
  248.    *  This operation pops the top of the heap.  The elements first and last-1
  249.    *  are swapped and [first,last-1) is made into a heap.
  250.   */
  251.   template<typename _RandomAccessIterator>
  252.     inline void
  253.     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  254.     {
  255.       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  256.     _ValueType;
  257.  
  258.       // concept requirements
  259.       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
  260.         _RandomAccessIterator>)
  261.       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
  262.       __glibcxx_requires_valid_range(__first, __last);
  263.       __glibcxx_requires_heap(__first, __last);
  264.  
  265.       std::__pop_heap(__first, __last - 1, __last - 1,
  266.               _ValueType(*(__last - 1)));
  267.     }
  268.  
  269.   template<typename _RandomAccessIterator, typename _Distance,
  270.        typename _Tp, typename _Compare>
  271.     void
  272.     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  273.           _Distance __len, _Tp __value, _Compare __comp)
  274.     {
  275.       const _Distance __topIndex = __holeIndex;
  276.       _Distance __secondChild = 2 * __holeIndex + 2;
  277.       while (__secondChild < __len)
  278.     {
  279.       if (__comp(*(__first + __secondChild),
  280.              *(__first + (__secondChild - 1))))
  281.         __secondChild--;
  282.       *(__first + __holeIndex) = *(__first + __secondChild);
  283.       __holeIndex = __secondChild;
  284.       __secondChild = 2 * (__secondChild + 1);
  285.     }
  286.       if (__secondChild == __len)
  287.     {
  288.       *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  289.       __holeIndex = __secondChild - 1;
  290.     }
  291.       std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp);
  292.     }
  293.  
  294.   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
  295.     inline void
  296.     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  297.            _RandomAccessIterator __result, _Tp __value, _Compare __comp)
  298.     {
  299.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  300.     _Distance;
  301.       *__result = *__first;
  302.       std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
  303.              __value, __comp);
  304.     }
  305.  
  306.   /**
  307.    *  @brief  Pop an element off a heap using comparison functor.
  308.    *  @param  first  Start of heap.
  309.    *  @param  last   End of heap.
  310.    *  @param  comp   Comparison functor to use.
  311.    *  @ingroup heap
  312.    *
  313.    *  This operation pops the top of the heap.  The elements first and last-1
  314.    *  are swapped and [first,last-1) is made into a heap.  Comparisons are
  315.    *  made using comp.
  316.   */
  317.   template<typename _RandomAccessIterator, typename _Compare>
  318.     inline void
  319.     pop_heap(_RandomAccessIterator __first,
  320.          _RandomAccessIterator __last, _Compare __comp)
  321.     {
  322.       // concept requirements
  323.       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
  324.         _RandomAccessIterator>)
  325.       __glibcxx_requires_valid_range(__first, __last);
  326.       __glibcxx_requires_heap_pred(__first, __last, __comp);
  327.  
  328.       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  329.     _ValueType;
  330.       std::__pop_heap(__first, __last - 1, __last - 1,
  331.               _ValueType(*(__last - 1)), __comp);
  332.     }
  333.  
  334.   /**
  335.    *  @brief  Construct a heap over a range.
  336.    *  @param  first  Start of heap.
  337.    *  @param  last   End of heap.
  338.    *  @ingroup heap
  339.    *
  340.    *  This operation makes the elements in [first,last) into a heap.
  341.   */
  342.   template<typename _RandomAccessIterator>
  343.     void
  344.     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  345.     {
  346.       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  347.       _ValueType;
  348.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  349.       _DistanceType;
  350.  
  351.       // concept requirements
  352.       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
  353.         _RandomAccessIterator>)
  354.       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
  355.       __glibcxx_requires_valid_range(__first, __last);
  356.  
  357.       if (__last - __first < 2)
  358.     return;
  359.  
  360.       const _DistanceType __len = __last - __first;
  361.       _DistanceType __parent = (__len - 2) / 2;
  362.       while (true)
  363.     {
  364.       std::__adjust_heap(__first, __parent, __len,
  365.                  _ValueType(*(__first + __parent)));
  366.       if (__parent == 0)
  367.         return;
  368.       __parent--;
  369.     }
  370.     }
  371.  
  372.   /**
  373.    *  @brief  Construct a heap over a range using comparison functor.
  374.    *  @param  first  Start of heap.
  375.    *  @param  last   End of heap.
  376.    *  @param  comp   Comparison functor to use.
  377.    *  @ingroup heap
  378.    *
  379.    *  This operation makes the elements in [first,last) into a heap.
  380.    *  Comparisons are made using comp.
  381.   */
  382.   template<typename _RandomAccessIterator, typename _Compare>
  383.     inline void
  384.     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  385.           _Compare __comp)
  386.     {
  387.       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  388.       _ValueType;
  389.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  390.       _DistanceType;
  391.  
  392.       // concept requirements
  393.       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
  394.         _RandomAccessIterator>)
  395.       __glibcxx_requires_valid_range(__first, __last);
  396.  
  397.       if (__last - __first < 2)
  398.     return;
  399.  
  400.       const _DistanceType __len = __last - __first;
  401.       _DistanceType __parent = (__len - 2) / 2;
  402.       while (true)
  403.     {
  404.       std::__adjust_heap(__first, __parent, __len,
  405.                  _ValueType(*(__first + __parent)), __comp);
  406.       if (__parent == 0)
  407.         return;
  408.       __parent--;
  409.     }
  410.     }
  411.  
  412.   /**
  413.    *  @brief  Sort a heap.
  414.    *  @param  first  Start of heap.
  415.    *  @param  last   End of heap.
  416.    *  @ingroup heap
  417.    *
  418.    *  This operation sorts the valid heap in the range [first,last).
  419.   */
  420.   template<typename _RandomAccessIterator>
  421.     void
  422.     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  423.     {
  424.       // concept requirements
  425.       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
  426.         _RandomAccessIterator>)
  427.       __glibcxx_function_requires(_LessThanComparableConcept<
  428.         typename iterator_traits<_RandomAccessIterator>::value_type>)
  429.       __glibcxx_requires_valid_range(__first, __last);
  430.       //      __glibcxx_requires_heap(__first, __last);
  431.  
  432.       while (__last - __first > 1)
  433.     std::pop_heap(__first, __last--);
  434.     }
  435.  
  436.   /**
  437.    *  @brief  Sort a heap using comparison functor.
  438.    *  @param  first  Start of heap.
  439.    *  @param  last   End of heap.
  440.    *  @param  comp   Comparison functor to use.
  441.    *  @ingroup heap
  442.    *
  443.    *  This operation sorts the valid heap in the range [first,last).
  444.    *  Comparisons are made using comp.
  445.   */
  446.   template<typename _RandomAccessIterator, typename _Compare>
  447.     void
  448.     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  449.           _Compare __comp)
  450.     {
  451.       // concept requirements
  452.       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
  453.         _RandomAccessIterator>)
  454.       __glibcxx_requires_valid_range(__first, __last);
  455.       __glibcxx_requires_heap_pred(__first, __last, __comp);
  456.  
  457.       while (__last - __first > 1)
  458.     std::pop_heap(__first, __last--, __comp);
  459.     }
  460.  
  461. } // namespace std
  462.  
  463. #endif /* _STL_HEAP_H */
  464.  
  465. // Local Variables:
  466. // mode:C++
  467. // End:
  468.