rotater.c rotate string using reverse

// avp 2016 rotate string using reverse (based on http://codelab.ru/task/cycle_shift/)

#ifdef TESTCNT
int Revcnt, Swpcnt;
#endif

/*
Алгоритм #3: переворотами

Задача кажется сложной, пока вас не осенит озарение («ага!»):
итак, нужно преобразовать массив ab в bа.

Предположим, что у нас есть функция reverse, переставляющая элементы некоторой
части массива в противоположном порядке.
В исходном состоянии массив имеет вид ab. Вызвав эту функцию для первой части,
получим аr b (прим. редактора:аr - это модифицированная часть a,
к которой применили фукнцию перестановки reverse).
Затем вызовем ее для второй части: получим аr br. Затем вызовем функцию для
всего массива, что даст (аr br)r, а это в точности соответствует bа.

Посмотрим, как будет такая функция действовать на массив "abcdefgh",
который нужно сдвинуть влево на три элемента:

 псевдокод: Сдвиг через функцию перестановки reverse


    reverse(0, i-1)   // cba|defgh
    reverse(i, n-1)   // cba|hgfed
    reverse(0, n-1)   // defgh|abc


Код, использующий функцию переворота, оказывается эффективным и
малотребовательным к памяти, и настолько короток и прост,
что при его реализации сложно ошибиться.

Б. Керниган и П. Дж. Плоджер пользовались именно этим методом для перемещения
строк в текстовом редакторе в своей книге (В. Kernighan, P. J. Plauger,
Software Tools in Pascal, 1981). Керниган пишет, что эта функция заработала
правильно с первого же запуска, тогда как их предыдущая версия, использовавшая
связный список, содержала несколько ошибок. Этот же код используется в
некоторых текстовых редакторах, включая тот, в котором я впервые набрал
настоящую главу. Кен Томпсон (Ken Thompson) написал этот редактор с функцией
reverse в 1971 году, и он утверждает, что она уже тогда была легендарной.

*/

static void
reverse (char *s, int n)
{
  char *t = s + n - 1, c;

  while (s < t) {
    //    swap(s++, t--);
    c = *s;
    *s++ = *t;
    *t-- = c;
#ifdef TESTCNT
    Revcnt++;
#endif
  }
}

char *
rotate (char *s, int len, int dist)
{
  if (len > 1 && (dist %= len)) {
    if (dist < 0)
      dist += len; // ROR == len - dist
    reverse(s, dist);
    reverse(s + dist, len - dist);
    reverse(s, len);
  }
  return s;
}

char *
rotate_l (char *s, int len, int dist) {
  return rotate(s, len, dist);
}

// -(dist % len) for dist == INT_MIN
char *
rotate_r (char *s, int len, int dist) {
  return len > 1 ? rotate(s, len, -(dist % len)) : s;
}


/* -----------------------
Алгоритм #2:

Можно предложить алгоритм, который возникает из рассмотрения задачи с другой
точки зрения.

Циклический сдвиг массива х сводится фактически к замене ab на bа,
где а — первые i элементов х, a b — оставшиеся элементы.

Предположим, что а короче b. Разобьем b на bleft и bright, где bright
содержит i элементов (столько же, сколько и а). Поменяем местами а и bright,
получим bright bleft а. При этом а окажется в конце массива — там,
где и полагается.

Поэтому можно сосредоточиться на перестановке bright и bleft.
Эта задача сводится к начальной, поэтому алгоритм можно вызывать рекурсивно.
Программа, реализующая этот алгоритм, будет достаточно красивой,
но она требует аккуратного написания кода, а оценить ее эффективность непросто:

*/

static inline void
swap (char a[], int f, int t, int l)
{
  int tt;

  for (l += f; f < l; f++, t++) {
    tt = a[f];
    a[f] = a[t];
    a[t] = tt;
#ifdef TESTCNT
    Swpcnt++;
#endif
  }
}

// not more swaps, but not faster (than reverse based) rotate left
void
rotatex (char a[], int n, int dist)
{
  if (n < 2 || (dist %= n) == 0)
    return;
  if (dist < 0)
    dist += n; // ROR == len - dist

  int i, j, p;
  i = p = dist;
  j = n - p;
  while (i != j) {
    if (i > j) {
      swap(a, p - i, p, j);
      i -= j;
    } else {
      swap(a, p - i, p + j - i, i);
      j -= i;
    }
  }
  swap(a, p - i, p, i);
}


// macroses for any array
#define REVERSE(a, size) ({int _i = 0, _j = (size) - 1;                 \
      while (_i < _j) {                                                 \
        __typeof__(*a) c = (a)[_i];                                     \
        (a)[_i] = (a)[_j];                                              \
        (a)[_j] = c;                                                    \
        _i++; _j--;                                                     \
      }})

#define ROTA_L(arr, size, dist) ({int _s = (size), _d = (dist);         \
      __typeof__(&((arr)[0])) _a = (arr);                               \
                                                                        \
      if (_s > 1 && (_d %= _s)) {                                       \
        if (_d < 0) _d += _s;                                           \
        REVERSE(_a, _d); REVERSE(_a + _d, _s - _d);                     \
        REVERSE(_a, _s);                                                \
      }})

#define ROTA_R(arr, size, dist) ({int __s = (size), __d = (dist);       \
      if (__s > 1) ROTA_L(arr, __s, -(__d % __s)); })

#include <stdio.h>
#include <string.h>
#ifdef TESTCNT
#include <stdlib.h>
#include <time.h>
#endif

int
main (int ac, char *av[])
{
  char s[1000], dir[100];
  int dist;

#ifdef TESTCNT
  puts("Enter ^D to time test");
#endif
  while (scanf("%s %s %d", dir, s, &dist) != EOF) {
    char t[1000], p[1000], *pt = t;
    strcpy(t, s); strcpy(p, s);

    if (*dir == 'l') {
      ROTA_L(pt, strlen(t), dist);
#ifdef TESTCNT
      Revcnt = Swpcnt = 0;
#endif
      rotate_l(s, strlen(s), dist);
      rotatex(p, strlen(s), dist);
    } else {
      ROTA_R(pt, strlen(t), dist);
#ifdef TESTCNT
      Revcnt = Swpcnt = 0;
#endif
      rotate_r(s, strlen(s), dist);
      rotatex(p, strlen(s), -dist);
    }
    printf("%s: [%s]    %s: [%s] "
#ifdef TESTCNT
       " (%d) "
#endif
       "  rotatex: [%s]"
#ifdef TESTCNT
       " (%d)"
#endif
       "\n",
       *dir == 'l' ? "ROTL" : "ROTR", t,
       *dir == 'l' ? "rotl" : "rotr", s,
#ifdef TESTCNT
       Revcnt,
#endif
       p
#ifdef TESTCNT
       , Swpcnt
#endif
       );
  }

#ifdef TESTCNT

  Swpcnt = Revcnt = 0;
  int i, j, n;
  long long sum = 0;

  srand(0);
  for (j = 2; j < 1000; j++)
    for (i = 0; i < 1000; i++)
      if (rand() % j)
    sum += j;

  puts("start measure");
  clock_t t1 = clock(), t1x, t2x;

  srand(0);
  for (j = 2; j < 1000; j++)
    for (i = 0; i < 1000; i++)
      rotate(s, j, rand() % j);
  t1x = clock();

  srand(0);
  for (j = 2; j < 1000; j++)
    for (i = 0; i < 1000; i++)
      rotatex(s, j, rand() % j);
  t2x = clock();

  printf("total %lld bytes rotate time:\n"
     "reverse %f sec (%d byte swaps)\n"
     "blockswap %f sec (%d byte swaps)\n",
     sum,
     (double)(t1x - t1)/CLOCKS_PER_SEC, Revcnt,
     (double)(t2x - t1x)/CLOCKS_PER_SEC, Swpcnt);
#endif


  return puts("End") == EOF;
}