Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import std.algorithm, std.conv, std.range, std.random;
- void main(string[] args) {
- void test(size_t n, size_t k)
- {
- assert(k < n);
- //writefln("n: %s, k: %s", n, k);
- auto a = iota(0, n).array;
- rotate(a.ptr, a.ptr + k, a.ptr + a.length);
- if (k) rotate(a.ptr, a.ptr + a.length - k, a.ptr + a.length);
- assert(a.equal(iota(0, a.length)));
- auto b = rotate(a[0 .. k], a[k .. $]);
- if (k == 0) assert(b == b.init);
- else assert(b == tuple(k, n - k), text(b));
- b = rotate(a[0 .. $ - k], a[$ - k .. $]);
- if (k == 0) assert(b == b.init);
- else assert(b == tuple(n - k, k), text(b));
- assert(a.equal(iota(0, n)));
- }
- test(1, 0);
- test(100, 0);
- test(100, 99);
- test(100, uniform(0, 99));
- }
- Tuple!(size_t, size_t) rotate(R1, R2)(R1 left, R2 right)
- {
- auto l = left.save, r = right.save;
- size_t rotated = 0;
- for (;; l.popFront, r.popFront, ++rotated)
- {
- if (l.empty)
- {
- if (!rotated) return typeof(return).init;
- auto x = rotate(right.takeExactly(rotated), r);
- return tuple(rotated, rotated + x[1]);
- }
- if (r.empty)
- {
- if (right.empty) return tuple(rotated, cast(size_t) 0);
- auto x = rotate(l, right);
- return tuple(rotated + x[0], rotated);
- }
- swap(l.front, r.front);
- }
- }
- // Only works with pointers
- void rotate(T)(T* first, T* middle, T* last)
- {
- assert(middle < last);
- auto next = middle;
- while (first != next)
- {
- swap(*first++, *next++);
- if (next == last) next = middle;
- else if (first == middle) middle = next;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement