williamr@2
|
1 |
//
|
williamr@2
|
2 |
//=======================================================================
|
williamr@2
|
3 |
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
|
williamr@2
|
4 |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
|
williamr@2
|
5 |
//
|
williamr@2
|
6 |
// Distributed under the Boost Software License, Version 1.0. (See
|
williamr@2
|
7 |
// accompanying file LICENSE_1_0.txt or copy at
|
williamr@2
|
8 |
// http://www.boost.org/LICENSE_1_0.txt)
|
williamr@2
|
9 |
//=======================================================================
|
williamr@2
|
10 |
//
|
williamr@2
|
11 |
#if __KCC
|
williamr@2
|
12 |
namespace std {
|
williamr@2
|
13 |
|
williamr@2
|
14 |
template <class RandomAccessIterator, class Distance>
|
williamr@2
|
15 |
bool __is_heap(RandomAccessIterator first, RandomAccessIterator last,
|
williamr@2
|
16 |
Distance*)
|
williamr@2
|
17 |
{
|
williamr@2
|
18 |
const Distance n = last - first;
|
williamr@2
|
19 |
|
williamr@2
|
20 |
Distance parent = 0;
|
williamr@2
|
21 |
for (Distance child = 1; child < n; ++child) {
|
williamr@2
|
22 |
if (first[parent] < first[child])
|
williamr@2
|
23 |
return false;
|
williamr@2
|
24 |
if ((child & 1) == 0)
|
williamr@2
|
25 |
++parent;
|
williamr@2
|
26 |
}
|
williamr@2
|
27 |
return true;
|
williamr@2
|
28 |
}
|
williamr@2
|
29 |
|
williamr@2
|
30 |
template <class RandomAccessIterator>
|
williamr@2
|
31 |
inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last)
|
williamr@2
|
32 |
{
|
williamr@2
|
33 |
return __is_heap(first, last, distance_type(first));
|
williamr@2
|
34 |
}
|
williamr@2
|
35 |
|
williamr@2
|
36 |
|
williamr@2
|
37 |
template <class RandomAccessIterator, class Distance, class StrictWeakOrdering>
|
williamr@2
|
38 |
bool __is_heap(RandomAccessIterator first, RandomAccessIterator last,
|
williamr@2
|
39 |
StrictWeakOrdering comp,
|
williamr@2
|
40 |
Distance*)
|
williamr@2
|
41 |
{
|
williamr@2
|
42 |
const Distance n = last - first;
|
williamr@2
|
43 |
|
williamr@2
|
44 |
Distance parent = 0;
|
williamr@2
|
45 |
for (Distance child = 1; child < n; ++child) {
|
williamr@2
|
46 |
if (comp(first[parent], first[child]))
|
williamr@2
|
47 |
return false;
|
williamr@2
|
48 |
if ((child & 1) == 0)
|
williamr@2
|
49 |
++parent;
|
williamr@2
|
50 |
}
|
williamr@2
|
51 |
return true;
|
williamr@2
|
52 |
}
|
williamr@2
|
53 |
|
williamr@2
|
54 |
template <class RandomAccessIterator, class StrictWeakOrdering>
|
williamr@2
|
55 |
inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last,
|
williamr@2
|
56 |
StrictWeakOrdering comp)
|
williamr@2
|
57 |
{
|
williamr@2
|
58 |
return __is_heap(first, last, comp, distance_type(first));
|
williamr@2
|
59 |
}
|
williamr@2
|
60 |
|
williamr@2
|
61 |
}
|
williamr@2
|
62 |
#endif
|