Advertisement
Guest User

Untitled

a guest
Aug 8th, 2014
229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
D 1.74 KB | None | 0 0
  1. import std.algorithm, std.conv, std.range, std.random;
  2.  
  3. void main(string[] args) {
  4.     void test(size_t n, size_t k)
  5.     {
  6.         assert(k < n);
  7.         //writefln("n: %s, k: %s", n, k);
  8.         auto a = iota(0, n).array;
  9.         rotate(a.ptr, a.ptr + k, a.ptr + a.length);
  10.         if (k) rotate(a.ptr, a.ptr + a.length - k, a.ptr + a.length);
  11.         assert(a.equal(iota(0, a.length)));
  12.  
  13.         auto b = rotate(a[0 .. k], a[k .. $]);
  14.         if (k == 0) assert(b == b.init);
  15.         else assert(b == tuple(k, n - k), text(b));
  16.         b = rotate(a[0 .. $ - k], a[$ - k .. $]);
  17.         if (k == 0) assert(b == b.init);
  18.         else assert(b == tuple(n - k, k), text(b));
  19.         assert(a.equal(iota(0, n)));
  20.      }
  21.  
  22.     test(1, 0);
  23.     test(100, 0);
  24.     test(100, 99);
  25.     test(100, uniform(0, 99));
  26. }
  27.  
  28. Tuple!(size_t, size_t) rotate(R1, R2)(R1 left, R2 right)
  29. {
  30.     auto l = left.save, r = right.save;
  31.     size_t rotated = 0;
  32.     for (;; l.popFront, r.popFront, ++rotated)
  33.     {
  34.         if (l.empty)
  35.         {
  36.             if (!rotated) return typeof(return).init;
  37.             auto x = rotate(right.takeExactly(rotated), r);
  38.             return tuple(rotated, rotated + x[1]);
  39.         }
  40.         if (r.empty)
  41.         {
  42.             if (right.empty) return tuple(rotated, cast(size_t) 0);
  43.             auto x = rotate(l, right);
  44.             return tuple(rotated + x[0], rotated);
  45.         }
  46.         swap(l.front, r.front);
  47.     }
  48. }
  49.  
  50. // Only works with pointers
  51. void rotate(T)(T* first, T* middle, T* last)
  52. {
  53.     assert(middle < last);
  54.     auto next = middle;
  55.     while (first != next)
  56.     {
  57.         swap(*first++, *next++);
  58.         if (next == last) next = middle;
  59.         else if (first == middle) middle = next;
  60.     }
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement