alg_prog.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>
#include <ctype.h>
#define cons(X,Y) new_list((void *) X, Y)

/* Definition of data structures */
typedef struct list{
  void *data;
  struct list *next;
} list;

list *new_list(void *data, list *next){
  list *lst = (list *) malloc(sizeof(list));
  lst->data = data; lst->next = next;
  return lst;
}

void dest_list(list *lst){
  while(lst != NULL){
    list *next = lst->next;
    free(lst);
    lst = next;
  }
}

typedef struct stack{
  list *top;
} stack;

typedef struct queue{
  int size;
  list *first;
  list *last;
} queue;

stack *new_stack(){
  stack *s = (stack*) malloc(sizeof(stack));
  s->top = NULL;
  return s;
}

queue *new_queue(){
  queue *q = (queue*) malloc(sizeof(stack));
  q->size = 0;
  q->first = NULL;
  q->last = NULL;
  return q;
}

void *pop(stack *s){
  list *old = s->top;
  if(old == NULL)
    return NULL;
  else{
    void *data = old->data;
    s->top = old->next;
    free(old);
    return data;
  }
}

void push(void* data, stack *s){
  s->top = cons(data, s->top);
}

void enqueue(void *data,queue *q){
  list *lst = cons(data,NULL);
  if(q->size <= 0){
    q->first = lst;
    q->last = lst;
  } else{
    q->last->next = lst;
    q->last = lst;
  }
  q->size = q->size + 1;
}

void *dequeue(queue *q){
  void *data;
  if(q->size <= 0)
    data = NULL;
  else{
    list *old = q->first;
    data = old->data;
    q->first = old->next;
    q->size = q->size - 1;
    free(old);
  }
  return data;
}


void **dequeue_to_array(queue *q){
  int len = q->size;
  list *lst = q->first;
  void **a = (void **)malloc(len * sizeof(void*));
  for(int i = 0; i < len; i++)
    a[i] = dequeue(q);
  return a;
}

typedef struct node{
  int size;
  char *name;
  struct node *parent;
  struct node **children;
} node;

typedef struct graph{
  int root_size;
  node **root_set;
} graph;

node *new_node(char *name,node *parent){
  node *nd = (node *) malloc(sizeof(node));
  nd->name = name;
  nd->parent = parent;
  return nd;
}

graph *new_graph(){
  graph *g =  (graph *) malloc(sizeof(graph));
  return g;
}

void dest_graph(graph *g){
  
}


typedef struct lexer{
  int pos;
  char *input;
  char *cur;
  char sep;
} lexer;

lexer *new_lexer(char *in){
  lexer *l = malloc(sizeof(lexer));
  l->pos = 0;
  l->cur = strdup("");
  l->input = strdup(in);
  l->sep = '\n';
  return l;
}


void dest_lexer(lexer *lex){
  free(lex);
}


/* lexer + parser */
int special_char(char c) {return (c == '\n' || c == '\0'|| c == ':' || c == ',');}

char* trim(char* str){
  char* dup = strdup(str);
  int i = 0, j = 0, sp=1;
  while(str[i] != '\0'){
    if(str[i] == ' ' || str[i] == '_'){
      if(sp){
	i++;
      }else{
	sp = !sp;
	dup[j] = ' ';
	i++; j++;
      }
    }else{
      sp = 0;
      dup[j] = tolower(str[i]);
      i++; j++;
    }
  }
  if(sp){
    dup[j-1] = '\0';
    return (char*) realloc(dup,(j)*sizeof(char));
  } else {
    dup[j] = '\0';
    return (char*) realloc(dup,(j+1)*sizeof(char));
  }
}

void advance_lexer(lexer *l){
  if(l->sep != '\0'){
    int start = l->pos, pos;
    while(l->input[start] == ' ') start++;
    pos = start;
    while(!special_char(l->input[pos])) pos++;
    l->sep = l->input[pos];
    if(start == pos){
      l->cur = strdup("");
      l->pos = pos+1;
    } else {
      int len = pos - start;
      char *cur = (char*)malloc((len+1)*sizeof(char));
      for(int i = 0; i < len; i++)
		cur[i] = l->input[start+i];
      cur[len] = '\0';
      l->cur = trim(cur);
      free(cur);
    }
    l->pos = pos+1;
  }
}


node *find_node(char *str){
  ENTRY e;
  e.key = str;
  return (node*)(hsearch(e,FIND)->data);
}

node *find_or_make_node(char *str, node *par){
  ENTRY e, *ep;
  e.key = str;
  ep = hsearch(e,FIND);
  if(ep == NULL){
    node *nd = new_node(str,par);
    e.data = (void*) nd;
    hsearch(e,ENTER);
    return nd;
  } else {
    node *nd = (node*)ep->data;
    if(par != NULL)
      nd->parent = par;
    return nd;
  }
}

void dequeue_into_node(node *nd, queue *q){
  nd->size = q->size;
  nd->children = (node**) dequeue_to_array(q);
}

graph *parse(char *input){
  lexer *lex = new_lexer(input);
  graph *g = new_graph();
  node *par = NULL;
  queue *root_queue = new_queue(),
        *row_queue = new_queue();
  int in_line = 0;
  while(lex->sep != '\0'){
    node *nd;
    advance_lexer(lex);
    nd = find_or_make_node(lex->cur,par);
    switch(lex->sep){
    case ':':
      if(nd->parent == NULL)
	enqueue((void*)nd,root_queue);
      par = nd;
      in_line = 1;
      break;
    case ',':
      enqueue((void*)nd,row_queue);
      break;
    case '\n':
      if(in_line){
	enqueue((void*)nd,row_queue);
	dequeue_into_node(par, row_queue);
	par = NULL;
	in_line = 0;
      }
      break;
    case '\0':
      if(in_line){
	enqueue((void*)nd,row_queue);
	dequeue_into_node(par,row_queue);
      }
      break;
    }
  }
  while(root_queue->size != 0){
    node* nd = (node*)dequeue(root_queue);
    if(nd->parent == NULL)
      enqueue((void*)nd,row_queue);
  }
  g->root_size = row_queue->size;
  g->root_set = (node**)dequeue_to_array(row_queue);
  
  free(row_queue);
  free(root_queue);
  free(lex);
  return g;
}


int num_elem(char *input){
  int c = 0;
  for(int i = 0; input[i] != '\0';i++)
    if(special_char(input[i]))
      c++;
  return c;
}

char *get_stdin(){
  char *buff;
  int count=0,max=1024;
  buff = (char *) malloc(1024 * sizeof(char));
  for(char c = getchar(); c != EOF; c = getchar()){
    if(count == max ){
      max = 2 * max;
      buff = (char*) realloc(buff,max * sizeof(char));
    }
    buff[count] = c;
    count++;
  }
  buff = realloc(buff,(count + 1) * sizeof(char));
  buff[count] = '\0';
  return buff;
}

queue *children_in_order(node* anc, int n, int o){
  node *nd = anc;
  int order = 1, count = 1, next_count = 0;
  queue *q = new_queue();
  queue *ret_q = new_queue();
  enqueue((void*) nd,q);
  while(order < o){
    for(int i = 0; i < count; i++){
      nd = dequeue(q);
      next_count += nd->size;
      for(int i = 0; i < nd->size; i++)
	enqueue((void*)nd->children[i] ,q);
    }
    count = next_count; next_count = 0;
    order++;
  }
  for(int i = 0; (i < count &&  0 != n); i++){
    nd = dequeue(q);
    next_count += nd->size;
    for(int i = 0; (i < nd->size && 0 != n); i++){
      enqueue((void*)nd->children[i] ,ret_q);
      n--;
    }
  }
  return ret_q;
}

void print_children_of_order(char* name, int n, int o){
  queue *q = children_in_order(find_node(name), n, o);
  int comma = 0;
  if(n >= 0)
    printf("%d order %d descendents of %s:\n", q->size,o,name);
  else
    printf("All order %d descendents of %s:\n",o,name);
  for(;q->size != 0;comma = 1){
    printf("%c %s", comma?',':' ', ((node*)dequeue(q))->name);
  }
  printf("\n");
}

void print_all_children_of_order(char* name, int o){
  print_children_of_order(name,-1,o);
}

int main(char *argv[]) {
  char *input = get_stdin();
  hcreate(2 * num_elem(input));
  graph *g = parse(input);
  print_all_children_of_order("dog",1);
  print_children_of_order("entity",7,5);
  return 0;
}