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_NEXT_PERMUTATION_HPP
00008 #define INSTIGATE_STL_NEXT_PERMUTATION_HPP
00009
00059
00060 #include "_basis.hpp"
00061 #include "concept.hpp"
00062 #include "_iter_swap.hpp"
00063 #include "_reverse.hpp"
00064
00065
00066
00067
00068
00069
00070 namespace instigate {
00071 namespace stl {
00072 template <typename I>
00073 bool next_permutation(I b, I e);
00074 template <typename I, typename C>
00075 bool next_permutation(I b, I e, C c);
00076 }
00077 }
00078
00115 template <typename I>
00116 bool instigate::stl::next_permutation(I b, I e)
00117 {
00118 typedef typename instigate::stl::readable_iterator::interface<I>::
00119 value_type value_type;
00120 CHECK(instigate::stl::bidirectional_iterator::requirements<I>);
00121 CHECK(instigate::stl::readable_iterator::requirements<I>);
00122 if (instigate::stl::equal(b, e)) {
00123 return false;
00124 }
00125 char k[sizeof(I)];
00126 I* i = 0;
00127 assign(i, copy_constructor(k, b));
00128 assert(0 != i);
00129 increment(*i);
00130 if (equal(*i, e)) {
00131 return false;
00132 }
00133 assign(*i, e);
00134 decrement(*i);
00135 for (;;) {
00136 char k1[sizeof(I)];
00137 I* ii = 0;
00138 assign(ii, copy_constructor(k1, *i));
00139 assert(0 != ii);
00140 decrement(*i);
00141 if (less_than(const_dereference(*i), const_dereference(*ii))) {
00142 char k2[sizeof(I)];
00143 I* j = 0;
00144 assign(j, copy_constructor(k2, e));
00145 assert(0 != j);
00146 decrement(*j);
00147 while (!less_than(const_dereference(*i),
00148 const_dereference(*j)))
00149 {
00150 decrement(*j);
00151 }
00152 instigate::stl::iter_swap(*i, *j);
00153 instigate::stl::reverse(*ii, e);
00154 return true;
00155 }
00156 if (equal(*i, b)) {
00157 instigate::stl::reverse(b, e);
00158 return false;
00159 }
00160 }
00161 }
00162
00202 template <typename I, typename C>
00203 bool instigate::stl::next_permutation(I b, I e, C c)
00204 {
00205 typedef typename instigate::stl::readable_iterator::interface<I>::
00206 value_type value_type;
00207 CHECK(instigate::stl::bidirectional_iterator::requirements<I>);
00208 CHECK(instigate::stl::readable_iterator::requirements<I>);
00209 CHECK(instigate::stl::binary_predicate::requirements<C>);
00210 if (equal(b, e)) {
00211 return false;
00212 }
00213 char k[sizeof(I)];
00214 I* i = 0;
00215 assign(i, copy_constructor(k, b));
00216 assert(0 != i);
00217 increment(*i);
00218 if (equal(*i, e)) {
00219 return false;
00220 }
00221 assign(*i, e);
00222 decrement(*i);
00223 for (;;) {
00224 char k1[sizeof(I)];
00225 I* ii = 0;
00226 assign(ii, copy_constructor(k1, *i));
00227 assert(0 != ii);
00228 decrement(*i);
00229 if (invoke_predicate(c, const_dereference(*i),
00230 const_dereference(*ii)))
00231 {
00232 char k2[sizeof(I)];
00233 I* j = 0;
00234 assign(j, copy_constructor(k2, e));
00235 assert(0 != j);
00236 decrement(*j);
00237 while (!invoke_predicate(c, const_dereference(*i),
00238 const_dereference(*j)))
00239 {
00240 decrement(*j);
00241 }
00242 instigate::stl::iter_swap(*i, *j);
00243 instigate::stl::reverse(*ii, e);
00244 return true;
00245 }
00246 if (equal(*i, b)) {
00247 instigate::stl::reverse(b, e);
00248 return false;
00249 }
00250 }
00251 }
00252
00253
00254
00255 #endif // INSTIGATE_STL_NEXT_PERMUTATION_HPP
00256