path: root/src/crf.c

#include <stdio.h>
#include <string.h>
#include "util.h"
#include "list.h"
#include "crf.h"

struct crf_s {
  luple6 *lup;
};

crf *
new_crf(Grammar *g, NUM input_len)
{
  NUM left_len = grammar_left_len(g);

  NUM max_alt_len = 0, max_rule_len = 0;

  for (NUM i = 0; i < left_len; i++) {
    NUM alt_len = rg_len(grammar_rule(g, i));
    if (alt_len > max_rule_len) max_rule_len = alt_len;
    for (NUM j = 0; j < alt_len; j++) {
      NUM jth_len = list_length(rg_nth(grammar_rule(g, i), j));
      if (jth_len > max_alt_len) max_alt_len = jth_len;
    }
  }

  NUM *len = NULL;

  crf *crfp = NULL;

  SAFE_MALLOC(crf, crfp, 1, goto cleanup;);

  SAFE_MALLOC(NUM, len, 6, goto cleanup;);

  *len = left_len;
  *(len+1) = input_len;
  *(len+2) = left_len;
  *(len+3) = max_rule_len;
  *(len+4) = max_alt_len+1;
  *(len+5) = input_len;

  crfp->lup = new_luple6(len);

  if (crfp->lup == NULL) goto cleanup;

  return crfp;

 cleanup:

  if (crfp) free(crfp);
  if (len) free(len);

  return NULL;
}

BOOL
crf_add_node(crf *crfp, pair2 node)
{
  return add_to_luple6_pt_2(crfp->lup, node);
}

HP_ATTR
BOOL
crf_find_node(crf *crfp, pair2 node)
{
  return luple6_pf_2(crfp->lup, node);
}

HP_ATTR
BOOL
crf_find_edge(crf *crfp, pair2 source, pair4 label)
{
  NUM *result = luple6_find(crfp->lup, (pair6) {
      source.x, source.y, label.x, label.y, label.z, label.u
    });

  return (result && *result) ? 1 : 0;
}

BOOL
crf_add_edge(crf *crfp, pair2 source, pair4 label)
{
  if (!(luple6_pf_2(crfp->lup, source))) {
    fleprintf0("add the node before adding its edges\n");
    return 1;
  }

  pair6 p6 = (pair6)
    {
      source.x,
      source.y,
      label.x,
      label.y,
      label.z,
      label.u
    };

#ifdef DEBUG
  fleprintf("adding (%ld, %ld, %ld, %ld, %ld, %ld)\n",
            p6.x, p6.y, p6.z, p6.u, p6.v, p6.w);
#endif

  NUM *find_result = luple6_find(crfp->lup, p6);

  if (find_result && *find_result) {
    /* fleprintf0("Already added!\n"); */
    return 0;
  }

  if (add_to_luple6(crfp->lup, p6, 1)) {
    fleprintf0("Fail to insert\n");
    fleprintf("adding (%ld, %ld, %ld, %ld, %ld, %ld)\n",
              p6.x, p6.y, p6.z, p6.u, p6.v, p6.w);
    return 1;
  }

  return 0;
}

void
destroy_crf(crf *crfp)
{
  /* fleprintf0("hi\n"); */
  destroy_luple6(crfp->lup);
  /* fleprintf0("hi\n"); */
  free(crfp);
}

UNUSED
static void
crf_print_internal(pair6 label)
{
  printf("(%ld, %ld, %ld, %ld)\n",
         label.z, label.u, label.v, label.w);
}

void
crf_print(crf *crfp)
{
  printf("Printing a call return forest...\n");

  NUM *len = luple6_len(crfp->lup);

  for (NUM i = 0; i < *len; i++)
    for (NUM j = 0; j < *(len+1); j++)
      if (luple6_pf_2(crfp->lup, (pair2) { i, j })) {
        printf("Printing edges for (%ld, %ld)...\n", i, j);
        luple6_map_2(crfp->lup, (pair2) { i, j }, -1,
                     crf_print_internal);
        printf("\n");
      }
}

H_ATTR
void
crf_map(crf *crfp, pair2 label, map_pair6_t fn)
{
  luple6_map_2(crfp->lup, label, label.y, fn);
}

struct spa_s {
  luple3 *lup;
};

spa *
new_spa(Grammar *g, NUM input_len)
{
  spa *spap = NULL;
  NUM *len = NULL;

  SAFE_MALLOC(spa, spap, 1, goto cleanup;);

  SAFE_MALLOC(NUM, len, 3, goto cleanup;);

  *len = grammar_left_len(g);
  *(len+1) = input_len;
  *(len+2) = input_len;

  spap->lup = new_luple3(len);

  if (spap->lup == NULL) {
    fleprintf0("Fail to create luple3\n");
    goto cleanup;
  }

  return spap;

 cleanup:
  if (spap) free(spap);
  if (len) free(len);
  return NULL;
}

void
destroy_spa(spa *spap)
{
  destroy_luple3(spap->lup);
  free(spap);
}

BOOL
spa_insert(spa *spap, pair3 label)
{
  if (add_to_luple3(spap->lup, label, 1)) {
    fleprintf0("Fail to insert\n");
    return 1;
  }

  return 0;
}

P_ATTR
BOOL
spa_belong(spa *spap, pair3 label)
{
  NUM *result = luple3_find(spap->lup, label);

  return (result && *result) ? 1 : 0;
}

H_ATTR
void
spa_map(spa *spap, pair2 label, map_pair3_t fn)
{
  luple3_map_2(spap->lup, label, fn);
}

typedef struct procr_array_element_s procr_array_element;

/* The list at index k is the set of "prodecor"s representing R_k. */
struct procr_array_element_s {
  BOOL initialized;
  List *ls;
};

struct procr_s {
  /* an array of length 5, holding the lengths */
  NUM *len;
  /* an array of lists */
  procr_array_element *array;
  /* minimal grade that is non-empty */
  NUM mg;
};

struct procu_s {
  luple5 *lup;
};

procr *
new_procr(Grammar *g, NUM input_len, BOOL *errorp)
{
  *errorp = 0;

  NUM left_len = grammar_left_len(g);

  NUM max_alt_len = 0, max_rule_len = 0;

  for (NUM i = 0; i < left_len; i++) {
    NUM alt_len = rg_len(grammar_rule(g, i));
    if (alt_len > max_rule_len) max_rule_len = alt_len;
    for (NUM j = 0; j < alt_len; j++) {
      NUM jth_len = list_length(rg_nth(grammar_rule(g, i), j));
      if (jth_len > max_alt_len) max_alt_len = jth_len;
    }
  }

  procr *pr = NULL;

  NUM *len = NULL;

  SAFE_CALLOC(procr, pr, 1, goto cleanup;);

  SAFE_MALLOC(NUM, len, 5, goto cleanup;);

  *len = input_len;
  *(len+1) = left_len;
  *(len+2) = max_rule_len;
  *(len+3) = max_alt_len+1;
  *(len+4) = input_len;

  pr->len = len;

  SAFE_CALLOC(procr_array_element, pr->array, *len, goto cleanup;);

  goto success;

 cleanup:

  *errorp = 1;

  if (pr) free(pr);
  if (len) free(len);

  pr = NULL;

 success:

  return pr;
}

procu *
new_procu(Grammar *g, NUM input_len, BOOL *errorp)
{
  *errorp = 0;

  NUM left_len = grammar_left_len(g);

  NUM max_alt_len = 0, max_rule_len = 0;

  for (NUM i = 0; i < left_len; i++) {
    NUM alt_len = rg_len(grammar_rule(g, i));
    if (alt_len > max_rule_len) max_rule_len = alt_len;
    for (NUM j = 0; j < alt_len; j++) {
      NUM jth_len = list_length(rg_nth(grammar_rule(g, i), j));
      if (jth_len > max_alt_len) max_alt_len = jth_len;
    }
  }

  procu *pu = NULL;
  NUM *len = NULL;

  SAFE_MALLOC(procu, pu, 1, goto cleanup;);
  SAFE_MALLOC(NUM, len, 5, goto cleanup;);

  *len = input_len;
  *(len+1) = left_len;
  *(len+2) = max_rule_len;
  *(len+3) = max_alt_len+1;
  *(len+4) = input_len;

  pu->lup = new_luple5(len);

  if (pu->lup == NULL) {
    fleprintf0("Fail to create luple5\n");
    goto cleanup;
  }

  goto success;

 cleanup:

  *errorp = 1;

  if (len) free(len);
  if (pu) free(pu);

  pu = NULL;

 success:

  return pu;
}

UNUSED
static void
print_label4(pair4 label)
{
  printf("(%ld, %ld, %ld, %ld)\n",
         label.x, label.y, label.z, label.u);
}

void
print_procr(procr *pr)
{
  printf("\nPrinting procr...\n");
  printf("MG = %ld\n", pr->mg);

  NUM *len = pr->len;

  for (NUM i = 0; i < *len; i++) {
    if (!((pr->array+i)->initialized)) continue;

    printf("Grade = %ld\n", i);

    for (NUM j = 0; j < list_length((pr->array+i)->ls); j++)
      printf("(%ld, %ld, %ld, %ld)\n",
             ((prodecor *) list_nth((pr->array+i)->ls, j))->x,
             ((prodecor *) list_nth((pr->array+i)->ls, j))->y,
             ((prodecor *) list_nth((pr->array+i)->ls, j))->z,
             ((prodecor *) list_nth((pr->array+i)->ls, j))->u);
  }
  printf("\n");
}

void
destroy_procr(procr *pr)
{
  if (pr == NULL) return;

  if (pr->array == NULL) {
    if (pr->len) free(pr->len);
    free(pr);
    return;
  }

  for (NUM i = 0; i < *(pr->len); i++) {
    if (!((pr->array+i)->initialized)) continue;
    destroy_list((pr->array+i)->ls, 1);
  }

  if (pr->len) free(pr->len);

  free(pr->array);
  free(pr);
}

void
destroy_procu(procu *pu)
{
  destroy_luple5(pu->lup);
  free(pu);
}

BOOL
desc_add(procr *pr, procu *pu, NUM grade, prodecor dec)
{
  pair5 label = (pair5) { grade, dec.x, dec.y, dec.z, dec.u };

  NUM *result = luple5_find(pu->lup, label);

  if (result && *result) return 0;

  if (add_to_luple5(pu->lup, label, 1)) {
    fleprintf0("Fail to add to procu\n");
    return 1;
  }

  if (!((pr->array+grade)->initialized)) {
    (pr->array+grade)->ls = new_list();
    if ((pr->array+grade)->ls == NULL) {
      fleprintf0("Fail to create new list for procr\n");
      return 1;
    }

    (pr->array+grade)->initialized = 1;
  }

  prodecor *element = NULL;

  SAFE_MALLOC(prodecor, element, 1, return 1;);

  *element = dec;

  if (add_to_list((pr->array+grade)->ls, element)) {
    fleprintf0("Fail to add to procr\n");
    free(element);
    return 1;
  }

  return 0;
}

prodecor *
pop_procr(procr *pr, procu *pu, NUM *gradep)
{
  prodecor *result = NULL;

  NUM *len = pr->len;

  if (pr->mg >= *len) goto success;

#define ELEMENT (pr->array+pr->mg)

  if (ELEMENT->initialized && list_length(ELEMENT->ls))
    goto no_reset_mg;

  if (ELEMENT->initialized && list_length(ELEMENT->ls) == 0) {
    luple5_free_1(pu->lup, pr->mg);

    destroy_list(ELEMENT->ls, 1);
    ELEMENT->initialized = 0;
    ELEMENT->ls = NULL;
  }

  while (++(pr->mg) < *(pr->len)) {
    if (ELEMENT->initialized) break;
  }

  if (pr->mg >= *(pr->len)) goto success;

 no_reset_mg:

  result = pop_from_list(ELEMENT->ls);

  *gradep = pr->mg;

#undef ELEMENT

 success:
  return result;
}