boost/pending/is_heap.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #if __KCC
0012 namespace std
0013 {
0014
0015 template < class RandomAccessIterator, class Distance >
0016 bool __is_heap(RandomAccessIterator first, RandomAccessIterator last, Distance*)
0017 {
0018     const Distance n = last - first;
0019
0020     Distance parent = 0;
0021     for (Distance child = 1; child < n; ++child)
0022     {
0023         if (first[parent] < first[child])
0024             return false;
0025         if ((child & 1) == 0)
0026             ++parent;
0027     }
0028     return true;
0029 }
0030
0031 template < class RandomAccessIterator >
0032 inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last)
0033 {
0034     return __is_heap(first, last, distance_type(first));
0035 }
0036
0037 template < class RandomAccessIterator, class Distance,
0038     class StrictWeakOrdering >
0039 bool __is_heap(RandomAccessIterator first, RandomAccessIterator last,
0040     StrictWeakOrdering comp, Distance*)
0041 {
0042     const Distance n = last - first;
0043
0044     Distance parent = 0;
0045     for (Distance child = 1; child < n; ++child)
0046     {
0047         if (comp(first[parent], first[child]))
0048             return false;
0049         if ((child & 1) == 0)
0050             ++parent;
0051     }
0052     return true;
0053 }
0054
0055 template < class RandomAccessIterator, class StrictWeakOrdering >
0056 inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last,
0057     StrictWeakOrdering comp)
0058 {
0059     return __is_heap(first, last, comp, distance_type(first));
0060 }
0061
0062 }
0063 #endif