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_ROTATE_HPP
00008 #define INSTIGATE_STL_ROTATE_HPP
00009
00058
00059 #include "concept.hpp"
00060 #include "_basis.hpp"
00061 #include "_swap.hpp"
00062 #include "_swap_ranges.hpp"
00063 #include "_reverse.hpp"
00064
00065
00066
00067
00068
00069
00070 namespace instigate {
00071 namespace stl {
00072 template <typename I>
00073 inline I rotate(I, I, I);
00074 namespace implementation {
00075 template <typename I>
00076 I rotate_aux(I, I, I, stl::forward_iterator::tag);
00077 template <typename I>
00078 I rotate_aux(I, I, I, stl::bidirectional_iterator::tag);
00079 template <typename R>
00080 R rotate_aux(R, R, R, stl::random_access_iterator::tag);
00081 template <typename T>
00082 T gcd(T, T);
00083 }
00084 }
00085 }
00086
00115 template <typename I>
00116 inline I instigate::stl::rotate(I b, I m, I e)
00117 {
00118 CHECK(stl::forward_iterator::requirements<I>);
00119 CHECK(stl::lvalue_iterator::requirements<I>);
00120 typedef typename stl::forward_iterator::interface<I>::iterator_category
00121 category;
00122 return implementation::rotate_aux(b, m, e, category());
00123
00124 }
00125
00130 template <typename I>
00131 I instigate::stl::implementation::rotate_aux(I b, I m, I e,
00132 instigate::stl::forward_iterator::tag)
00133 {
00134 if (equal(b, m)) {
00135 return e;
00136 } else if (equal(e, m)) {
00137 return b;
00138 }
00139 char k1[sizeof(I)];
00140 I* b2 = 0;
00141 assign(b2, copy_constructor(k1, m));
00142 assert(0 != b2);
00143 do {
00144 swap(dereference(b), dereference(*b2));
00145 increment(b);
00146 increment(*b2);
00147 if(equal(b, m))
00148 assign(m, *b2);
00149 } while (!equal(*b2, e));
00150 char k2[sizeof(I)];
00151 I* new_m = 0;
00152 assign(new_m, copy_constructor(k2, b));
00153 assert(0 != new_m);
00154 assign(*b2, m);
00155 while (!equal(*b2, e)) {
00156 swap(dereference(b), dereference(*b2));
00157 increment(b);
00158 increment(*b2);
00159 if (equal(b, m)) {
00160 assign(m, *b2);
00161 } else if (equal(*b2, e)) {
00162 assign(*b2, m);
00163 }
00164 }
00165 return *new_m;
00166 }
00167
00172 template <typename I>
00173 I instigate::stl::implementation::rotate_aux(I b, I m, I e,
00174 instigate::stl::bidirectional_iterator::tag)
00175 {
00176 CHECK(stl::bidirectional_iterator::requirements<I>);
00177 if (equal(b, m)) {
00178 return e;
00179 } else if (equal(e, m)) {
00180 return b;
00181 }
00182 implementation::reverse_aux(b, m, bidirectional_iterator::tag());
00183 implementation::reverse_aux(m, e, bidirectional_iterator::tag());
00184 while (!equal(b, m) && !equal(m, e)) {
00185 decrement(e);
00186 std::swap(dereference(b), dereference(e));
00187 increment(b);
00188 }
00189 if (equal(b, m)) {
00190 implementation::reverse_aux(m, e,bidirectional_iterator::tag());
00191 return e;
00192 } else {
00193 implementation::reverse_aux(b, m,bidirectional_iterator::tag());
00194 return b;
00195 }
00196 }
00197
00202 template <class T>
00203 T instigate::stl::implementation::gcd(T m, T n)
00204 {
00205 while (n != 0) {
00206 T t = m % n;
00207 m = n;
00208 n = t;
00209 }
00210 return m;
00211 }
00212
00217 template <typename R>
00218 R instigate::stl::implementation::rotate_aux(R b, R m, R e,
00219 instigate::stl::random_access_iterator::tag)
00220 {
00221 namespace RA = instigate::stl::random_access_iterator;
00222 namespace WR = instigate::stl::writable_iterator;
00223 typedef typename RA::interface<R>::difference_type difference_type;
00224 typedef typename WR::interface<R>::value_type value_type;
00225 difference_type n = e - b;
00226 difference_type k = m - b;
00227 difference_type l = n - k;
00228 R* r = 0;
00229 char k1[sizeof(R)];
00230 assign(r, copy_constructor(k1, b));
00231 assert(0 != r);
00232 instigate::stl::advance(*r, instigate::stl::distance(m, e));
00233 if (k == 0) {
00234 return e;
00235 } else if (k == l) {
00236 instigate::stl::swap_ranges(b, m, m);
00237 return *r;
00238 }
00239 difference_type d = implementation::gcd(n, k);
00240 for (difference_type i = 0; i < d; ++i) {
00241 value_type t = dereference(b);
00242 char k2[sizeof(R)];
00243 R* p = 0;
00244 assign(p, copy_constructor(k2, b));
00245 assert(0 != p);
00246 if (k < l) {
00247 for (difference_type j = 0; j < l/d; j++) {
00248 char k3[sizeof(R)];
00249 R* h = 0;
00250 assign(h, copy_constructor(k3, b));
00251 assert(0 != h);
00252 instigate::stl::advance(*h, l);
00253 if (less_than(*h, *p)) {
00254 char k4[sizeof(R)];
00255 R* o = 0;
00256 assign(o, copy_constructor(k4, *p));
00257 assert(0 != o);
00258 instigate::stl::advance(*o, -l);
00259 dereference_assign(*p, dereference(*o));
00260 assign(*o, *p);
00261 instigate::stl::advance(*o, -l);
00262 assign(*p, *o);
00263 }
00264 char k5[sizeof(R)];
00265 R* s = 0;
00266 assign(s, copy_constructor(k5, *p));
00267 assert(0 != s);
00268 instigate::stl::advance(*s, k);
00269 dereference_assign(*p, dereference(*s));
00270 assign(*s, *p);
00271 instigate::stl::advance(*s, k);
00272 assign(*p, *s);
00273 }
00274 } else {
00275 for (difference_type j = 0; j < k/d - 1; j ++) {
00276 char k6[sizeof(R)];
00277 R* f = 0;
00278 assign(f, copy_constructor(k6, e));
00279 assert(0 != f);
00280 instigate::stl::advance(*f, -k);
00281 if (less_than(*p, *f)) {
00282 char k7[sizeof(R)];
00283 R* u = 0;
00284 assign(u, copy_constructor(k7, *p));
00285 assert(0 != u);
00286 instigate::stl::advance(*u, k);
00287 dereference_assign(*p, dereference(*u));
00288 assign(*u, *p);
00289 instigate::stl::advance(*u, k);
00290 assign(*p, *u);
00291 }
00292 char k8[sizeof(R)];
00293 R* v = 0;
00294 assign(v, copy_constructor(k8, *p));
00295 instigate::stl::advance(*p, -l);
00296 assert(0 != v);
00297 dereference_assign(*p, dereference(*v));
00298 assign(*v, *p);
00299 instigate::stl::advance(*v, -l);
00300 assign(*p, *v);
00301 }
00302 }
00303 dereference_assign(*p, t);
00304 increment(b);
00305 }
00306 return *r;
00307 }
00308
00309
00310
00311
00312 #endif // INSTIGATE_STL_ROTATE_HPP