00001
00002 #ifndef _INSTIGATE_STL_INTERNAL_HEADER_IN_ALGORITHM
00003 #error This is an internal header file used to implement Instigate STL.\
00004 It should never be included directly by a program.
00005 #endif
00006
00007 #ifndef INSTIGATE_STL_IS_HEAP_HPP
00008 #define INSTIGATE_STL_IS_HEAP_HPP
00009
00059
00060 #include "concept.hpp"
00061 #include "_basis.hpp"
00062 #include "_distance.hpp"
00063
00064
00065 #include <generic/base.hpp>
00066
00067
00068
00069
00070 namespace instigate {
00071 namespace stl {
00072 template <typename I>
00073 bool is_heap(I, I);
00074
00075 template <typename I, typename C>
00076 bool is_heap(I, I, C);
00077 }
00078 }
00079
00114 template <typename I>
00115 bool instigate::stl::is_heap(I b, I e)
00116 {
00117 typedef typename stl::readable_iterator::interface<I>::value_type V;
00118 typedef typename stl::random_access_iterator::interface<I>::
00119 difference_type D;
00120 CHECK(stl::random_access_iterator::requirements<I>);
00121 CHECK(instigate::generic::less_than_comparable::requirements<V>);
00122 D p = 0;
00123 D c = 1;
00124 char buf[sizeof(I)];
00125 I* buf_p = 0;
00126 char buf1[sizeof(I)];
00127 I* buf_p1 = 0;
00128 assign(buf_p, copy_constructor(buf, b));
00129 assert(0 != buf_p);
00130 assign(buf_p1, copy_constructor(buf1, b));
00131 assert(0 != buf_p1);
00132 for (; less_than(c, stl::distance(b, e)); ++c)
00133 {
00134 assign(*buf_p, b);
00135 stl::advance(*buf_p, p);
00136 assign(*buf_p1, b);
00137 stl::advance(*buf_p1, c);
00138 if (less_than(const_dereference(*buf_p),
00139 const_dereference(*buf_p1))) {
00140 return false;
00141 }
00142 if (0 == (c & 1)) {
00143 ++p;
00144 }
00145 }
00146 return true;
00147 }
00148
00174 template <typename I, typename C>
00175 bool instigate::stl::is_heap(I b, I e, C c)
00176 {
00177 CHECK(stl::random_access_iterator::requirements<I>);
00178 CHECK(stl::binary_predicate::requirements<C>);
00179 typedef typename stl::readable_iterator::interface<I>::value_type V;
00180 typedef typename stl::random_access_iterator::interface<I>::
00181 difference_type D;
00182 D p = 0;
00183 D l = 1;
00184 for (; less_than(l, stl::distance(b, e)); ++l)
00185 {
00186 if (invoke(c, b[p], b[l]))
00187 return false;
00188 if (0 == (l & 1)) {
00189 ++p;
00190 }
00191 }
00192 return true;
00193 }
00194
00195
00196
00197 #endif // INSTIGATE_STL_IS_HEAP_HPP