home *** CD-ROM | disk | FTP | other *** search
/ H4CK3R 14 / hacker14.iso / programacao / cwin / c.exe / $INSTDIR / include / c++ / bits / stl_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  2003-12-15  |  10.9 KB  |  309 lines
  1. // Heap implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2001 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 _CPP_BITS_STL_HEAP_H
  61. #define _CPP_BITS_STL_HEAP_H 1
  62.  
  63. namespace std
  64. {
  65.  
  66.   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
  67.  
  68.   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
  69.     void 
  70.     __push_heap(_RandomAccessIterator __first,
  71.         _Distance __holeIndex, _Distance __topIndex, _Tp __value)
  72.     {
  73.       _Distance __parent = (__holeIndex - 1) / 2;
  74.       while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
  75.     *(__first + __holeIndex) = *(__first + __parent);
  76.     __holeIndex = __parent;
  77.     __parent = (__holeIndex - 1) / 2;
  78.       }    
  79.       *(__first + __holeIndex) = __value;
  80.     }
  81.  
  82.   template<typename _RandomAccessIterator>
  83.     inline void 
  84.     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  85.     {
  86.       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  87.       _ValueType;
  88.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  89.       _DistanceType;
  90.  
  91.       // concept requirements
  92.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  93.         _RandomAccessIterator>)
  94.       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
  95.  
  96.       __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 
  97.           _ValueType(*(__last - 1)));
  98.     }
  99.  
  100.   template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 
  101.         typename _Compare>
  102.     void
  103.     __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  104.         _Distance __topIndex, _Tp __value, _Compare __comp)
  105.     {
  106.       _Distance __parent = (__holeIndex - 1) / 2;
  107.       while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
  108.     *(__first + __holeIndex) = *(__first + __parent);
  109.     __holeIndex = __parent;
  110.     __parent = (__holeIndex - 1) / 2;
  111.       }
  112.       *(__first + __holeIndex) = __value;
  113.     }
  114.  
  115.   template<typename _RandomAccessIterator, typename _Compare>
  116.     inline void 
  117.     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  118.           _Compare __comp)
  119.     {
  120.       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  121.       _ValueType;
  122.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  123.       _DistanceType;
  124.  
  125.       // concept requirements
  126.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  127.         _RandomAccessIterator>)
  128.  
  129.       __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 
  130.           _ValueType(*(__last - 1)), __comp);
  131.     }
  132.  
  133.   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
  134.     void 
  135.     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  136.           _Distance __len, _Tp __value)
  137.     {
  138.       _Distance __topIndex = __holeIndex;
  139.       _Distance __secondChild = 2 * __holeIndex + 2;
  140.       while (__secondChild < __len) {
  141.     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
  142.       __secondChild--;
  143.     *(__first + __holeIndex) = *(__first + __secondChild);
  144.     __holeIndex = __secondChild;
  145.     __secondChild = 2 * (__secondChild + 1);
  146.       }
  147.       if (__secondChild == __len) {
  148.     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  149.     __holeIndex = __secondChild - 1;
  150.       }
  151.       __push_heap(__first, __holeIndex, __topIndex, __value);
  152.     }
  153.  
  154.   template<typename _RandomAccessIterator, typename _Tp>
  155.     inline void 
  156.     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  157.            _RandomAccessIterator __result, _Tp __value)
  158.     {
  159.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
  160.       *__result = *__first;
  161.       __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
  162.     }
  163.  
  164.   template<typename _RandomAccessIterator>
  165.     inline void
  166.     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  167.     {
  168.       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
  169.  
  170.       // concept requirements
  171.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  172.         _RandomAccessIterator>)
  173.       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
  174.  
  175.       __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)));
  176.     }
  177.  
  178.   template<typename _RandomAccessIterator, typename _Distance,
  179.        typename _Tp, typename _Compare>
  180.     void
  181.     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  182.           _Distance __len, _Tp __value, _Compare __comp)
  183.     {
  184.       _Distance __topIndex = __holeIndex;
  185.       _Distance __secondChild = 2 * __holeIndex + 2;
  186.       while (__secondChild < __len) {
  187.     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
  188.       __secondChild--;
  189.     *(__first + __holeIndex) = *(__first + __secondChild);
  190.     __holeIndex = __secondChild;
  191.     __secondChild = 2 * (__secondChild + 1);
  192.       }
  193.       if (__secondChild == __len) {
  194.     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  195.     __holeIndex = __secondChild - 1;
  196.       }
  197.       __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
  198.     }
  199.  
  200.   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
  201.     inline void 
  202.     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  203.            _RandomAccessIterator __result, _Tp __value, _Compare __comp)
  204.     {
  205.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
  206.       *__result = *__first;
  207.       __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 
  208.             __value, __comp);
  209.     }
  210.  
  211.   template<typename _RandomAccessIterator, typename _Compare>
  212.     inline void 
  213.     pop_heap(_RandomAccessIterator __first,
  214.          _RandomAccessIterator __last, _Compare __comp)
  215.     {
  216.       // concept requirements
  217.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  218.         _RandomAccessIterator>)
  219.  
  220.       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
  221.       __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)), __comp);
  222.     }
  223.  
  224.   template<typename _RandomAccessIterator>
  225.     void 
  226.     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  227.     {
  228.       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  229.       _ValueType;
  230.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  231.       _DistanceType;
  232.  
  233.       // concept requirements
  234.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  235.         _RandomAccessIterator>)
  236.       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
  237.  
  238.       if (__last - __first < 2) return;
  239.       _DistanceType __len = __last - __first;
  240.       _DistanceType __parent = (__len - 2)/2;
  241.     
  242.       while (true) {
  243.     __adjust_heap(__first, __parent, __len, _ValueType(*(__first + __parent)));
  244.     if (__parent == 0) return;
  245.     __parent--;
  246.       }
  247.     }
  248.  
  249.   template<typename _RandomAccessIterator, typename _Compare>
  250.     inline void 
  251.     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  252.           _Compare __comp)
  253.     {
  254.       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  255.       _ValueType;
  256.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  257.       _DistanceType;
  258.  
  259.       // concept requirements
  260.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  261.         _RandomAccessIterator>)
  262.  
  263.       if (__last - __first < 2) return;
  264.       _DistanceType __len = __last - __first;
  265.       _DistanceType __parent = (__len - 2)/2;
  266.     
  267.       while (true) {
  268.     __adjust_heap(__first, __parent, __len,
  269.                   _ValueType(*(__first + __parent)), __comp);
  270.     if (__parent == 0) return;
  271.     __parent--;
  272.       }
  273.     }
  274.  
  275.   template<typename _RandomAccessIterator>
  276.     void
  277.     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  278.     {
  279.       // concept requirements
  280.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  281.         _RandomAccessIterator>)
  282.       __glibcpp_function_requires(_LessThanComparableConcept<
  283.         typename iterator_traits<_RandomAccessIterator>::value_type>)
  284.  
  285.       while (__last - __first > 1)
  286.     pop_heap(__first, __last--);
  287.     }
  288.  
  289.   template<typename _RandomAccessIterator, typename _Compare>
  290.     void 
  291.     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  292.           _Compare __comp)
  293.     {
  294.       // concept requirements
  295.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  296.         _RandomAccessIterator>)
  297.  
  298.       while (__last - __first > 1)
  299.     pop_heap(__first, __last--, __comp);
  300.     }
  301.  
  302. } // namespace std
  303.  
  304. #endif /* _CPP_BITS_STL_HEAP_H */
  305.  
  306. // Local Variables:
  307. // mode:C++
  308. // End:
  309.