#11

int *ivec_new(int size) {
  int *a = (int*)malloc((size+1) * sizeof(int));
  a[0] = size; return a;
}
int *ivec_merge(int *b, int *c) {
  int ib = 1, ic = 1, ia = 1, *a = ivec_new(b[0]+c[0]);
  while(ia <= a[0]) {
    if(ib > b[0])          { a[ia++] = c[ic++]; }
    else if(ic > c[0])     { a[ia++] = b[ib++]; }
    else if(c[ic] < b[ib]) { a[ia++] = c[ic++]; }
    else                   { a[ia++] = b[ib++]; }
  }
  return a;
}
// mergesort1 --- merge sort unsing queue
#include <stdlib.h>
#include "pqueue.h"
(ivec_new, ivec_mergeをここに)  
void mergesort1(int *a, int n) {
  pqueuep q = pqueue_new(n+1);
  int *v, *w;
  for(int i = 0; i < n; ++i) {
    v = ivec_new(1); v[1] = a[i]; pqueue_enq(q, v);
  }
  while(true) {
    v = (int*)pqueue_deq(q); if(pqueue_isempty(q)) { break; }
    w = (int*)pqueue_deq(q); pqueue_enq(q, ivec_merge(v, w));
    free(v); free(w);
  }
  for(int i = 0; i < n; ++i) { a[i] = v[i+1]; }
}
// pqueue.h --- int type queue interface
#include <stdbool.h>
struct pqueue;
typedef struct pqueue *pqueuep;
pqueuep pqueue_new(int size);
bool pqueue_isempty(pqueuep p);
bool pqueue_isfull(pqueuep p);
void pqueue_enq(pqueuep p, void *v);
void *pqueue_deq(pqueuep p);
// pqueue.c --- pointer type queue impl. with array
#include <stdlib.h>
#include "pqueue.h"
struct pqueue { int ip, op, size; void **arr; };
pqueuep pqueue_new(int size) {
  pqueuep p = (pqueuep)malloc(sizeof(struct pqueue));
  p->ip = p->op = 0; p->size = size;
  p->arr = (void**)malloc(size * sizeof(void*)); return p;
}
bool pqueue_isempty(pqueuep p) { return p->ip == p->op; }
bool pqueue_isfull(pqueuep p) { return (p->ip+1)%p->size == p->op; }
void pqueue_enq(pqueuep p, void *v) {
  if(pqueue_isfull(p)) { return; }
  p->arr[p->ip++] = v; if(p->ip >= p->size) { p->ip = 0; }
}
void *pqueue_deq(pqueuep p) {
  if(pqueue_isempty(p)) { return 0; }
  void *v = p->arr[p->op++]; if(p->op >= p->size) { p->op = 0; }
  return v;
}
// mergesort1demo.c --- demonstration of mergesort1.
// sortdemo.c --- demonstration for basic sort.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "pqueue.h"
#define MAXDATA 1000000
static int a[MAXDATA];

int *ivec_new(int size) {
  int *a = (int*)malloc((size+1) * sizeof(int));
  a[0] = size; return a;
}
int *ivec_merge(int *b, int *c) {
  int ib = 1, ic = 1, ia = 1, *a = ivec_new(b[0]+c[0]);
  while(ia <= a[0]) {
    if(ib > b[0])          { a[ia++] = c[ic++]; }
    else if(ic > c[0])     { a[ia++] = b[ib++]; }
    else if(c[ic] < b[ib]) { a[ia++] = c[ic++]; }
    else                   { a[ia++] = b[ib++]; }
  }
  return a;
}
void mergesort1(int *a, int n) {
  pqueuep q = pqueue_new(n+1);
  int *v, *w;
  for(int i = 0; i < n; ++i) {
    v = ivec_new(1); v[1] = a[i]; pqueue_enq(q, v);
  }
  while(true) {
    v = (int*)pqueue_deq(q); if(pqueue_isempty(q)) { break; }
    w = (int*)pqueue_deq(q); pqueue_enq(q, ivec_merge(v, w));
    free(v); free(w);
  }
  for(int i = 0; i < n; ++i) { a[i] = v[i+1]; }
}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  srand(time(NULL));
  for(int i = 0; i < n; ++i) { a[i] = rand()%10000; }
  mergesort1(a, n);
  for(int i = 0; i < n; ++i) { printf(" %d", a[i]); }
  printf("\n");
  return 0;
}
// mergesort2 --- merge sort with recuresive division
#include <stdlib.h>
(mergeはここでは省略)
static void ms(int *a, int i, int j, int *b) {
  if(i >= j) { return; }
  int k = (i + j) / 2;
  ms(a, i, k, b); ms(a, k+1, j, b);
  merge(b, a+i, k-i+1, a+k+1, j-k);
  for(k = 0; k < j-i+1; ++k) { a[i+k] = b[k]; }
}
void mergesort2(int *a, int n) {
  int *b = (int*)malloc(n * sizeof(int)); ms(a, 0, n-1, b); free(b);
}
// quicksort --- quick sort with recuresive division
static void iswap(int *a, int i, int j) {
  int x = a[i]; a[i] = a[j]; a[j] = x;
}
void qs(int *a, int i, int j) {
  if(j <= i) { return; }
  int s = i, pivot = a[j];
  for(int k = i; k < j; ++k) {
    if(a[k] < pivot) { iswap(a, s++, k); }
  }
  iswap(a, j, s); qs(a, i, s-1); qs(a, s+1, j);
}
void quicksort(int *a, int n) { qs(a, 0, n-1); }
// heapsort1 --- heap sort using balanced bin-tree
#define P(i) ((i-1)/2)
#define L(i) (2*i+1)
#define R(i) (2*i+2)

static void iswap(int *a, int i, int j) {
  int x = a[i]; a[i] = a[j]; a[j] = x;
}
void pd(int *a, int i, int j) {
  for(int k = L(i); k <= j; ) {
    if(k < j && a[k] < a[k+1]) { ++k; }
    if(a[P(k)] >= a[k]) { break; }
    iswap(a, P(k), k); k = L(k);
  }
}
void heapsort1(int *a, int n) {
  for(int i = n-1; i >= 0; --i) { pd(a, i, n-1); }
  for(int i = n-1; i > 0; --i) { iswap(a, 0, i); pd(a, 0, i-1); }
}
// heapgame.c --- construct heap and remove max screen game.
#include <stdio.h>
#include <stdbool.h>
#include <ncurses.h>
#include <stdlib.h>
#include <time.h>
#define P(i) ((i-1)/2)
#define L(i) (2*i+1)
#define R(i) (2*i+2)

#define MAXARR 128
static int a[MAXARR];
static int max, cur = 0;

static void pos(int n, int *x, int *y) {
  int y1 = 0, x1 = 0;
  for(int i = 1; i <= n; ++i) {
    if(i==1||i==3||i==7||i==15||i==31||i==63) { ++y1; x1 = 0; }
    else { ++x1; }
  }
  *x = x1; *y = y1;
}
static void upd() {
  char buf[10];
  int x, y;
  for(int i = 0; i < max; ++i) {
    pos(i, &x, &y); move(y*2+1, x*3+1);
    sprintf(buf, "%3d", a[i]); addstr(buf); 
  }
  pos(cur, &x, &y); move(y*2+1, x*3+3);
}
void iswap(int *a, int i, int j) { int x = a[i]; a[i] = a[j]; a[j] = x; }
void shuffle(int *a, int size) {
  for(int i = 0; i < size; ++i) { iswap(a, i, rand()%(size-i)); }
}
bool checkheap(int *a, int size) {
  for(int i = 1; i < size; ++i) { if(a[P(i)] < a[i]) { return false; } }
  return true;
}
int main(int argc, char *argv[]) {
  max = atoi(argv[1]); if(max > MAXARR) { max = MAXARR; }
  for(int i = 0; i < max; ++i) { a[i] = i; }
  srand(time(NULL));
  initscr(); noecho(); cbreak(); system("stty raw"); clear();
  while(true) {
    upd(); refresh(); int ch = getch();
    switch(ch) {
case 'q': endwin(); return 0;                           // quit
case 'p': if(cur > 0) { cur = P(cur); } break;          // parent
case 'l': if(L(cur) < max) { cur = L(cur); } break;     // left-child
case 'r': if(R(cur) < max) { cur = R(cur); } break;     // right-chlid
case 'x': if(cur > 0) { iswap(a, cur, P(cur)); } break; // excange
case 's': shuffle(a, max); break;                       // shuffle
case 'm': char *msg = "NG";                             // move top elt
          if(max <= 1) {
            msg = "GOAL!";
          } else if(checkheap(a, max)) {
            iswap(a, 0, max-1); --max; msg = "MOVED"; cur = 0;
          }
          clear(); move(15, 5); addstr(msg); clrtoeol(); break;
default: break;
    }
  }
}