OSDN Git Service

Daily bump.
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / stl_heap.h
index 8f4d068..eff7fd3 100644 (file)
@@ -1,6 +1,6 @@
 // Heap implementation -*- C++ -*-
 
-// Copyright (C) 2001 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2004 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
  * 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.
+/** @file stl_heap.h
+ *  This is an internal header file, included by other library headers.
+ *  You should not attempt to use it directly.
  */
 
-#ifndef _CPP_BITS_STL_HEAP_H
-#define _CPP_BITS_STL_HEAP_H 1
+#ifndef _STL_HEAP_H
+#define _STL_HEAP_H 1
+
+#include <debug/debug.h>
 
 namespace std
 {
+  // 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>
+    bool
+    __is_heap(_RandomAccessIterator __first, _Distance __n)
+    {
+      _Distance __parent = 0;
+      for (_Distance __child = 1; __child < __n; ++__child)
+       {
+         if (__first[__parent] < __first[__child])
+           return false;
+         if ((__child & 1) == 0)
+           ++__parent;
+       }
+      return true;
+    }
+
+  template<typename _RandomAccessIterator, typename _Distance,
+           typename _StrictWeakOrdering>
+    bool
+    __is_heap(_RandomAccessIterator __first, _StrictWeakOrdering __comp,
+             _Distance __n)
+    {
+      _Distance __parent = 0;
+      for (_Distance __child = 1; __child < __n; ++__child)
+       {
+         if (__comp(__first[__parent], __first[__child]))
+           return false;
+         if ((__child & 1) == 0)
+           ++__parent;
+       }
+      return true;
+    }
+
+  template<typename _RandomAccessIterator>
+    bool
+    __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+    { return std::__is_heap(__first, std::distance(__first, __last)); }
+
+  template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
+    bool
+    __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
+           _StrictWeakOrdering __comp)
+    { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
 
   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
 
   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
-    void 
+    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;
-      }    
+      while (__holeIndex > __topIndex && *(__first + __parent) < __value)
+       {
+         *(__first + __holeIndex) = *(__first + __parent);
+         __holeIndex = __parent;
+         __parent = (__holeIndex - 1) / 2;
+       }
       *(__first + __holeIndex) = __value;
     }
 
+  /**
+   *  @brief  Push an element onto a heap.
+   *  @param  first  Start of heap.
+   *  @param  last   End of heap + element.
+   *  @ingroup heap
+   *
+   *  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 
+    inline void
     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     {
       typedef typename iterator_traits<_RandomAccessIterator>::value_type
@@ -88,31 +146,46 @@ namespace std
          _DistanceType;
 
       // concept requirements
-      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
-      __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
+      //      __glibcxx_requires_heap(__first, __last - 1);
 
-      __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 
-                 _ValueType(*(__last - 1)));
+      std::__push_heap(__first, _DistanceType((__last - __first) - 1),
+                      _DistanceType(0), _ValueType(*(__last - 1)));
     }
 
-  template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 
+  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) = *(__first + __parent);
-       __holeIndex = __parent;
-       __parent = (__holeIndex - 1) / 2;
-      }
+      while (__holeIndex > __topIndex
+            && __comp(*(__first + __parent), __value))
+       {
+         *(__first + __holeIndex) = *(__first + __parent);
+         __holeIndex = __parent;
+         __parent = (__holeIndex - 1) / 2;
+       }
       *(__first + __holeIndex) = __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
+   *
+   *  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 
+    inline void
     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
              _Compare __comp)
     {
@@ -122,56 +195,75 @@ namespace std
          _DistanceType;
 
       // concept requirements
-      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
 
-      __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 
-                 _ValueType(*(__last - 1)), __comp);
+      std::__push_heap(__first, _DistanceType((__last - __first) - 1),
+                      _DistanceType(0), _ValueType(*(__last - 1)), __comp);
     }
 
   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
-    void 
+    void
     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
                  _Distance __len, _Tp __value)
     {
-      _Distance __topIndex = __holeIndex;
+      const _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);
+      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;
+       }
+      std::__push_heap(__first, __holeIndex, __topIndex, __value);
     }
 
   template<typename _RandomAccessIterator, typename _Tp>
-    inline void 
+    inline void
     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
               _RandomAccessIterator __result, _Tp __value)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
+      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+       _Distance;
       *__result = *__first;
-      __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
+      std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
+                        __value);
     }
 
+  /**
+   *  @brief  Pop an element off a heap.
+   *  @param  first  Start of heap.
+   *  @param  last   End of heap.
+   *  @ingroup heap
+   *
+   *  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;
+      typedef typename iterator_traits<_RandomAccessIterator>::value_type
+       _ValueType;
 
       // concept requirements
-      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
-      __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+      __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_heap(__first, __last);
 
-      __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)));
+      std::__pop_heap(__first, __last - 1, __last - 1,
+                     _ValueType(*(__last - 1)));
     }
 
   template<typename _RandomAccessIterator, typename _Distance,
@@ -180,48 +272,75 @@ namespace std
     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
                  _Distance __len, _Tp __value, _Compare __comp)
     {
-      _Distance __topIndex = __holeIndex;
+      const _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);
+      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;
+       }
+      std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp);
     }
 
   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
-    inline void 
+    inline void
     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
               _RandomAccessIterator __result, _Tp __value, _Compare __comp)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
+      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+       _Distance;
       *__result = *__first;
-      __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 
-                   __value, __comp);
+      std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
+                        __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
+   *
+   *  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 
+    inline void
     pop_heap(_RandomAccessIterator __first,
             _RandomAccessIterator __last, _Compare __comp)
     {
       // concept requirements
-      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_heap_pred(__first, __last, __comp);
 
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
-      __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)), __comp);
+      typedef typename iterator_traits<_RandomAccessIterator>::value_type
+       _ValueType;
+      std::__pop_heap(__first, __last - 1, __last - 1,
+                     _ValueType(*(__last - 1)), __comp);
     }
 
+  /**
+   *  @brief  Construct a heap over a range.
+   *  @param  first  Start of heap.
+   *  @param  last   End of heap.
+   *  @ingroup heap
+   *
+   *  This operation makes the elements in [first,last) into a heap.
+  */
   template<typename _RandomAccessIterator>
-    void 
+    void
     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     {
       typedef typename iterator_traits<_RandomAccessIterator>::value_type
@@ -230,23 +349,38 @@ namespace std
          _DistanceType;
 
       // concept requirements
-      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
-      __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
-
-      if (__last - __first < 2) return;
-      _DistanceType __len = __last - __first;
-      _DistanceType __parent = (__len - 2)/2;
-       
-      while (true) {
-       __adjust_heap(__first, __parent, __len, _ValueType(*(__first + __parent)));
-       if (__parent == 0) return;
-       __parent--;
-      }
+      __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)
+       {
+         std::__adjust_heap(__first, __parent, __len,
+                            _ValueType(*(__first + __parent)));
+         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
+   *
+   *  This operation makes the elements in [first,last) into a heap.
+   *  Comparisons are made using comp.
+  */
   template<typename _RandomAccessIterator, typename _Compare>
-    inline void 
+    inline void
     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
              _Compare __comp)
     {
@@ -256,51 +390,77 @@ namespace std
          _DistanceType;
 
       // concept requirements
-      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
-
-      if (__last - __first < 2) return;
-      _DistanceType __len = __last - __first;
-      _DistanceType __parent = (__len - 2)/2;
-       
-      while (true) {
-       __adjust_heap(__first, __parent, __len,
-                     _ValueType(*(__first + __parent)), __comp);
-       if (__parent == 0) return;
-       __parent--;
-      }
+      __glibcxx_requires_valid_range(__first, __last);
+
+      if (__last - __first < 2)
+       return;
+
+      const _DistanceType __len = __last - __first;
+      _DistanceType __parent = (__len - 2) / 2;
+      while (true)
+       {
+         std::__adjust_heap(__first, __parent, __len,
+                            _ValueType(*(__first + __parent)), __comp);
+         if (__parent == 0)
+           return;
+         __parent--;
+       }
     }
 
+  /**
+   *  @brief  Sort a heap.
+   *  @param  first  Start of heap.
+   *  @param  last   End of heap.
+   *  @ingroup heap
+   *
+   *  This operation sorts the valid heap in the range [first,last).
+  */
   template<typename _RandomAccessIterator>
     void
     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     {
       // concept requirements
-      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
-      __glibcpp_function_requires(_LessThanComparableConcept<
+      __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)
-       pop_heap(__first, __last--);
+       std::pop_heap(__first, __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
+   *
+   *  This operation sorts the valid heap in the range [first,last).
+   *  Comparisons are made using comp.
+  */
   template<typename _RandomAccessIterator, typename _Compare>
-    void 
+    void
     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
              _Compare __comp)
     {
       // concept requirements
-      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_heap_pred(__first, __last, __comp);
 
       while (__last - __first > 1)
-       pop_heap(__first, __last--, __comp);
+       std::pop_heap(__first, __last--, __comp);
     }
 
 } // namespace std
 
-#endif /* _CPP_BITS_STL_HEAP_H */
+#endif /* _STL_HEAP_H */
 
 // Local Variables:
 // mode:C++