#04

// iqueue.h --- int type queue interface
#include <stdbool.h>
struct iqueue;
typedef struct iqueue *iqueuep;
iqueuep iqueue_new(int size);
bool iqueue_isempty(iqueuep p);
bool iqueue_isfull(iqueuep p);
void iqueue_enq(iqueuep p, int v);
int iqueue_deq(iqueuep p);
// iqueue.c --- int type queue impl. with array
#include <stdlib.h>
#include "iqueue.h"
struct iqueue { int ip, op, size; int *arr; };
iqueuep iqueue_new(int size) {
  iqueuep p = (iqueuep)malloc(sizeof(struct iqueue));
  p->ip = p->op = 0; p->size = size;
  p->arr = (int*)malloc(size * sizeof(int)); return p;
}
bool iqueue_isempty(iqueuep p) { return p->ip == p->op; }
bool iqueue_isfull(iqueuep p) { return (p->ip+1)%p->size == p->op; }
void iqueue_enq(iqueuep p, int v) {
  if(iqueue_isfull(p)) { return; }
  p->arr[p->ip++] = v; if(p->ip >= p->size) { p->ip = 0; }
}
int iqueue_deq(iqueuep p) {
  if(iqueue_isempty(p)) { return 0; }
  int v = p->arr[p->op++]; if(p->op >= p->size) { p->op = 0; }
  return v;
}
// queuetest -- demonstration of iqueue
#include <stdio.h>
#include <stdlib.h>
#include "iqueue.h"

void readenq(iqueuep q) {
  int c;
  printf("s> ");
  for(c = getchar(); c != '\n' && c != EOF; c = getchar()) {
    iqueue_enq(q, c);
  }
}
int main(void) {
  int c;
  iqueuep q = iqueue_new(200);
  readenq(q); readenq(q); readenq(q);
  while(!iqueue_isempty(q)) { putchar(iqueue_deq(q)); }
  putchar('\n');
  return 0;
}
// test_iqueue.c --- unit test for iqueue
#include <stdbool.h>
#include <stdio.h>
#include "iqueue.h"
char *bool2str(bool b) { return b ? "true" : "false"; }
void expect_bool(bool b1, bool b2, char *msg) {
  printf("%s %s:%s %s\n", (b1==b2)?"OK":"NG",
         bool2str(b1), bool2str(b2), msg);
}
void expect_int(int i1, int i2, char *msg) {
  printf("%s %d:%d %s\n", (i1==i2)?"OK":"NG", i1, i2, msg);
}
int main(void) {
  iqueuep q = iqueue_new(4);
  iqueue_enq(q, 1); iqueue_enq(q, 2); iqueue_enq(q, 3);
  expect_bool(iqueue_isfull(q), true, "size=4 queue full");
  iqueue_enq(q, 4);
  expect_int(iqueue_deq(q), 1, "1st => 1");
  iqueue_enq(q, 5);
  expect_int(iqueue_deq(q), 2, "2nd => 2");
  expect_int(iqueue_deq(q), 3, "3rd => 3");
  expect_bool(iqueue_isempty(q), false, "queue not empty");
  expect_int(iqueue_deq(q), 5, "4th => 5");
  expect_bool(iqueue_isempty(q), true, "queue emptied");
  expect_int(iqueue_deq(q), 0, "0 returned for empty");
  return 0;
}
// istack.h --- int type stack interface
#include <stdbool.h>
struct istack;
typedef struct istack *istackp;
istackp istack_new(int size); // allocate new stack
bool istack_isempty(istackp p); // test if the stack is empty
void istack_push(istackp p, int v); // push a value
int istack_pop(istackp p);      // pop a value and return it
int istack_top(istackp p);      // peek the topmost value
// istack.c --- int type stack impl. with array
#include <stdlib.h>
#include "istack.h"
struct istack { int ptr; int *arr; };
istackp istack_new(int size) {
  istackp p = (istackp)malloc(sizeof(struct istack));
  p->ptr = 0; p->arr = (int*)malloc(size * sizeof(int));
  return p;
}
bool istack_isempty(istackp p) { return p->ptr <= 0; }
void istack_push(istackp p, int v) { p->arr[p->ptr++] = v; }
int istack_pop(istackp p) { return p->arr[--(p->ptr)]; }
int istack_top(istackp p) { return p->arr[p->ptr - 1]; }
// railmap.h -- a railroad map
struct node { char *name; int num, edge[5], dist; };
struct node map[13] = {
  { "yokohama", 3, { 1, 3, 4 }, -1 },    // 0
  { "kawasaki", 3, { 0, 2, 5 }, -1 },    // 1
  { "shinagawa", 3, { 1, 3, 9 }, -1 },   // 2
  { "osaki", 3, { 0, 2, 6 }, -1 },       // 3
  { "hachiouji", 2, { 0, 5 }, -1 },      // 4
  { "tachikawa", 3, { 1, 4, 6 }, -1 },   // 5
  { "shinjuku", 4, { 3, 5, 8, 7 }, -1 }, // 6
  { "ikebukuro", 3, { 6, 11, 12 }, -1 }, // 7
  { "ochanomizu", 3, { 6, 9, 10 }, -1 }, // 8
  { "tokyo", 3, { 2, 8, 10 } , -1 },     // 9
  { "akihabara", 3, { 8, 9, 11 }, -1 },  // 10
  { "tabata", 3, { 7, 10, 12 }, -1 },    // 11
  { "akabane", 2, { 7, 11 }, -1 },       // 12
};
// railmap.c -- search railroad paths
#include <stdio.h>
#include <stdlib.h>
#include "istack.h"
#include "railmap.h"

int main(int argc, char *argv[]) {
  int start = atoi(argv[1]), goal = atoi(argv[2]);
  istackp s = istack_new(100);
  map[start].dist = 0; istack_push(s, start);
  while(!istack_isempty(s)) {
    int i, n = istack_pop(s);
    struct node *p = map + n;
    printf("%d: %s, %d\n", n, p->name, p->dist);
    if(n == goal) { printf("GOAL.\n"); break; }
    for(i = 0; i < p->num; ++i) {
      int k = p->edge[i];
      if(map[k].dist < 0) {
        map[k].dist = p->dist+1; istack_push(s, k);
      }
    }
  }
  return 0;
}
// railmap2.c -- search railroad paths (queue version)
#include <stdio.h>
#include <stdlib.h>
#include "iqueue.h"
#include "railmap.h"

int main(int argc, char *argv[]) {
  int start = atoi(argv[1]), goal = atoi(argv[2]);
  iqueuep s = iqueue_new(100);
  map[start].dist = 0; iqueue_enq(s, start);
  while(!iqueue_isempty(s)) {
    int i, n = iqueue_deq(s);
    struct node *p = map + n;
    printf("%d: %s, %d\n", n, p->name, p->dist);
    if(n == goal) { printf("GOAL.\n"); break; }
    for(i = 0; i < p->num; ++i) {
      int k = p->edge[i];
      if(map[k].dist < 0) {
        map[k].dist = p->dist+1; iqueue_enq(s, k);
      }
    }
  }
  return 0;
}