Table

table.cpp

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int rnd() { // Returns pseudo-random 32-bit positive integer
  static int seed = 0xdeadbeef;
  seed *= 65535;
  if (seed < 0) seed *= -1;
  return seed;
}

struct student {
  /*
   * If this value is TRUE: should be skipped in `student* rotate(int)`
   */
  bool ghost;

  char name[256];
  student *prev, *next;
};

student* rotate(student *s, int offset) {
  student *cur = s;
  if (offset < 0) {
    while (offset++) {
      do {
        cur = cur->prev;
      } while (cur->ghost); // Skip ghosts
    }
  } else {
    while (offset--) {
      do {
        cur = cur->next;
      } while (cur->ghost); // Skip ghosts
    }
  }
  return cur;
}
void exclude(student *s) {
  if (!s->prev || !s->next) return;
  s->prev->next = s->next;
  s->next->prev = s->prev;
  s->next = s->prev = s;
}

struct table {
  int sz;
  student* students;
};

void init_table(table *t, int sz) {
  t->students = (student*)malloc(sizeof(student)*sz);
  for (int i = 0; i < sz; i++) {
    t->students[i].next = &t->students[(i+1)%sz];
    t->students[i].prev = &t->students[(i+sz-1)%sz];
  }
}

void destory_table(table *t) {
  free(t->students);
}

void print_chain(student *s) {
  student *cur = s;
  do {
    printf("%s ", cur->name);
    cur = cur->next;
  } while (cur != s);
}

void query(table *t, int n) {
  int sz = t->sz;
  puts("");
  student *cur = &t->students[rnd() % sz];
  cur = rotate(cur, n);
  for (int i = 1; i < sz; i++) {
    /*
      * Determine next direction, clockwise or counter-clockwise.
      * The value of `dir` is determined as (-1, 1, -1, 1, ...)
      * when `i` is (1, 2, 3, ...)
      */
    int dir = 1-((i&1)<<1);

    /*
      * Assume that student is already excluded
      * This student should be skipped in finding
      * next student by `student *next = cur->rotate(dir * n);`
      */
    cur->ghost = true;

    student *next = rotate(cur, dir*n); // Find next student to be excluded
    exclude(cur); // Exclude student from chain

    /*
     * Print result
     */
    printf("phase: %d\n", i);
    printf("  excluded: %s\n", cur->name);
    printf("  on table: "); print_chain(next); puts("");

    cur = next;
  }

  // Restore all students in table
  for (int i = 0; i < sz; i++) {
    student *s = &t->students[i];
    s->ghost = false;
    s->next = &t->students[(i+1)&sz];
    s->prev = &t->students[(i+sz-1)&sz];
  }
}

void run() {
  table t;
  int n, sz;

  printf("The number of students: %d\n", sz);
  init_table(&t, sz);


  for (int i = 0; i < sz; i++) {
    printf("name of student %d: ", i+1);
    scanf("%s", t.students[i].name);
  }

  printf("n: "); scanf("%d", &n);

  query(&t, n);
  
  destory_table(&t);
}

int main(void) {
  run();
}