path: root/src/bsr.c

#include "list.h"
#include "util.h"
#include "ht.h"
#include "bsr.h"
#include <stdio.h>
#include <string.h>
#include <stdarg.h>

typedef struct first_type_bsr_s first_type_bsr;
typedef struct second_type_bsr_s second_type_bsr;

typedef struct first_type_array_element_s first_type_array_element;

/* The keys of the table are (i, k) and values are hash tables whose
   keys are (a, j) such that (X, a, i, j, k) belongs to the set. */
struct first_type_array_element_s {
  ht *table;
  BOOL initialized;
};

struct first_type_bsr_s {
  NUM len;
  first_type_array_element *array;
};

/* Arrrrgh! */
typedef struct second_arrarrarr_element_s second_arrarrarr_element;

/* The keys are (i, k) and the values are hash tables whose keys are
   those j such that

   (X, a, c, i, j, k)

   belongs to the set. */
struct second_arrarrarr_element_s {
  ht *table;
  BOOL initialized;
};

typedef struct second_array_array_element_s \
second_array_array_element;

struct second_array_array_element_s {
  NUM len;
  second_arrarrarr_element *array;
  BOOL initialized;
};

typedef struct second_type_array_element_s second_type_array_element;

struct second_type_array_element_s {
  NUM len;
  second_array_array_element *array;
  BOOL initialized;
};

struct second_type_bsr_s {
  NUM len;
  second_type_array_element *array;
};

struct bsr_s {
   /* bsr_type type; */
  /* union { */
  first_type_bsr f;
  second_type_bsr s;
  /* } data; */
};

bsr *
new_bsr(BOOL * const restrict errorp, Grammar *g)
{
  NUM left_len = grammar_left_len(g);

  bsr *bsrp = NULL;
  SAFE_MALLOC(bsr, bsrp, 1, *errorp = 1; return NULL;);

  /* first type */
  bsrp->f.len = left_len;
  SAFE_MALLOC(first_type_array_element,
              bsrp->f.array, bsrp->f.len, goto cleanup;);

  /* ensure every bit is zero, including the initialized field */
  memset(bsrp->f.array, 0,
         sizeof(first_type_array_element) * bsrp->f.len);

  /* second type */
  bsrp->s.len = left_len;
  SAFE_MALLOC(second_type_array_element,
              bsrp->s.array, bsrp->s.len, goto cleanup;);
  memset(bsrp->s.array, 0,
         sizeof(second_type_array_element) * bsrp->s.len);

  for (NUM i = 0; i < left_len; i++)
    (bsrp->s.array+i)->len = rg_len(grammar_rule(g, i));

  return bsrp;

 cleanup:
  *errorp = 1;

  if (bsrp->f.array) free(bsrp->f.array);
  if (bsrp->s.array) free(bsrp->s.array);
  if (bsrp) free(bsrp);

  return NULL;
}

void
destroy_bsr(bsr * const restrict bsrp)
{
  /* destroy first type */
  for (NUM i = 0; i < bsrp->f.len; i++) {
#define ELEMENT (bsrp->f.array+i)
    if (ELEMENT->initialized) {
      /* destroy every hash table values as well */

#define HTS ((ht **) ht_values(ELEMENT->table))

      for (NUM j = 0; j < ht_size(ELEMENT->table); j++)
        destroy_ht(*(HTS+j), DESTROY_KEY_SELF);

      destroy_ht(ELEMENT->table, DESTROY_KEY_SELF);
    }
  }

#undef ELEMENT
#undef HTS

  free(bsrp->f.array);

  /* destroy second type */

  for (NUM i = 0; i < bsrp->s.len; i++) {

#define ELEMENT (bsrp->s.array+i)

    if (ELEMENT->initialized) {
      for (NUM j = 0; j < ELEMENT->len; j++) {

#define SELE (ELEMENT->array+j)

        if (SELE->initialized) {
          for (NUM k = 0; k < SELE->len; k++) {

#define HELE (SELE->array+k)

            if (HELE->initialized) {

#define HTS ((ht **) ht_values(HELE->table))

              for (NUM ell = 0; ell < ht_size(HELE->table); ell++)
                destroy_ht(*(HTS+ell), DESTROY_KEY_SELF);

              destroy_ht(HELE->table, DESTROY_KEY_SELF);
            }
          }

          free(SELE->array);
        }
      }

      free(ELEMENT->array);
    }
  }

#undef ELEMENT
#undef SELE
#undef HELE
#undef HTS

  free(bsrp->s.array);

  free(bsrp);
}

/* X = non-terminal index, a = index of alternate, c = length of
   prefix */

/* i = left-extent of X, and j = right-extent.  k = the left-extent of
   the right-most terminal or non-terminal in the alternate
   corresponding to a. */

BOOL
bsr_add(CCR_MOD(Grammar *) g, bsr * const restrict b,
        NUM X, NUM a, NUM c, NUM i, NUM k, NUM j)
{
  if (X < 0 || X >= b->f.len) {
    fleprintf("Invalid X: %ld\n", X);
    return 1;
  }

  if (c > list_length(rg_nth(grammar_rule(g, X), a)) || c < 0) {
    fleprintf("Invalid c: %ld\n", c);
    return 1;
  }

  BOOL errorp = 0;

  ht *value_table = NULL;

  pair2 *p2 = NULL, p21 = { 0 }, p22 = { 0 };

  NUM *p1 = NULL, p11 = 0;

  if (c == list_length(rg_nth(grammar_rule(g, X), a))) {
    /* first type BSR */
    /* fleprintf0("First type\n"); */

#define ARR (b->f.array+X)

    if (!(ARR->initialized)) {
      ARR->table = new_ht2(HT_INIT_CAP);

      if (ARR->table == NULL) {
        fleprintf0("Fail to get new ht\n");
        goto cleanup;
      }

      ARR->initialized = 1;

      value_table = new_ht2(HT_INIT_CAP);

      if (value_table == NULL) {
        fleprintf0("Fail to get new ht\n");
        goto cleanup;
      }

      NEW_P2(p2, a, k, goto cleanup;);
      if (ht_insert(value_table, p2, (void*)1)) goto cleanup;

      NEW_P2(p2, i, j, goto cleanup;);

      if (ht_insert(ARR->table, p2, value_table)) goto cleanup;
      /* don't destroy the pointers once they have been inserted */
      value_table = NULL;
      p2 = NULL;
    } else {
      p21.x = i;
      p21.y = j;

      if (ht_find(ARR->table, &p21) == NULL) {
        value_table = new_ht2(HT_INIT_CAP);

        if (value_table == NULL) {
          fleprintf0("Fail to get new ht\n");
          goto cleanup;
        }

        NEW_P2(p2, a, k, goto cleanup;);
        if (ht_insert(value_table, p2, (void*)1)) goto cleanup;

        NEW_P2(p2, i, j, goto cleanup;);
        if (ht_insert(ARR->table, p2, value_table)) goto cleanup;

        /* don't destroy the pointers once they have been inserted */
        value_table = NULL;
        p2 = NULL;
      } else {
        p22.x = a;
        p22.y = k;

        if (ht_find(ht_find(ARR->table, &p21), &p22) == NULL) {
          NEW_P2(p2, a, k, goto cleanup;);
          if (ht_insert(ht_find(ARR->table, &p21), p2, (void*)1))
            goto cleanup;

          /* don't destroy the pointer once it has been inserted */
          p2 = NULL;
        } else {
          /* this element is already present */
        }
      }
    }

#undef ARR

  } else {
    /* second type BSR */
    /* fleprintf0("Second type\n"); */

#define AR (b->s.array+X)

    if (!(AR->initialized)) {
      SAFE_MALLOC(second_array_array_element,
                  AR->array, AR->len,
                  goto cleanup;);
      memset(AR->array, 0,
             sizeof(second_array_array_element)*(AR->len));
      AR->initialized = 1;
    }

#define ARR (AR->array+a)

    if (a < 0 || a >= rg_len(grammar_rule(g, X))) {
      fleprintf("Invalid a: %ld\n", a);
      goto cleanup;
    }

    ARR->len = list_length(rg_nth(grammar_rule(g, X), a));

    if (!(ARR->initialized)) {
      SAFE_MALLOC(second_arrarrarr_element,
                  ARR->array, ARR->len,
                  goto cleanup;);
      memset(ARR->array, 0,
             sizeof(second_arrarrarr_element)*(ARR->len));
      ARR->initialized = 1;
    }

#define ARRR (ARR->array+c)

    if (!(ARRR->initialized)) {
      ARRR->table = new_ht2(HT_INIT_CAP);

      if (ARRR->table == NULL) {
        fleprintf0("Fail to get new ht\n");
        goto cleanup;
      }

      ARRR->initialized = 1;
    }

    p21.x = i;
    p21.y = j;

    if (ht_find(ARRR->table, &p21) == NULL) {
      value_table = new_ht(HT_INIT_CAP, 0);

      if (value_table == NULL) {
        fleprintf0("Fail to get new ht\n");
        goto cleanup;
      }

      NEW_P2(p2, i, j, goto cleanup;);

      if (ht_insert(ARRR->table, p2, value_table)) {
        fleprintf0("Fail to insert into table\n");
        goto cleanup;
      }
      value_table = NULL;
      p2 = NULL;
    }

    p11 = k;

    if (ht_find(ht_find(ARRR->table, &p21),
                &p11) == NULL) {
      SAFE_MALLOC(NUM, p1, 1, goto cleanup;);
      *p1 = k;
      if (ht_insert(ht_find(ARRR->table, &p21),
                    p1, (void *)1)) {
        fleprintf0("Fail to insert into table\n");
        goto cleanup;
      }
      p1 = NULL;
    }

#undef AR
#undef ARR
#undef ARRR

  }

  goto success;

 cleanup:
  errorp = 1;

 success:

  if (value_table) destroy_ht(value_table, DESTROY_KEY_SELF);
  if (p2) free(p2);
  if (p1) free(p1);

  return errorp;
}

BOOL
bsr_find(CCR_MOD(bsr *) b, CCR_MOD(Grammar *) g,
         BOOL * const restrict errorp,
         NUM X, NUM a, NUM c, NUM i, NUM k, NUM j)
{
  *errorp = 0;
  BOOL result = 0;

  if (X < 0 || X >= b->f.len) {
    fleprintf("Invalid X: %ld\n", X);
    goto cleanup;
  }

  if (a < 0 || a >= rg_len(grammar_rule(g, X))) {
    fleprintf("Invalid a: %ld\n", a);
    goto cleanup;
  }

  if (c < 0 || c > list_length(rg_nth(grammar_rule(g, X), a))) {
    fleprintf("Invalid c: %ld\n", c);
    goto cleanup;
  }

  pair2 p21 = { 0 }, p22 = { 0 };
  NUM p11 = 0;

  if (c == list_length(rg_nth(grammar_rule(g, X), a))) {
    /* first type */
#define ARR (b->f.array+X)

    if (!(ARR->initialized)) {
      goto success;
    } else {
      p21.x = i;
      p21.y = j;

      if (ht_find(ARR->table, &p21) == NULL) {
        goto success;
      } else {
        p22.x = a;
        p22.y = k;

        if (ht_find(ht_find(ARR->table, &p21), &p22) == NULL) {
          goto success;
        } else {
          result = 1;
          goto success;
        }
      }
    }

#undef ARR

  } else {
    /* second type */

#define AR (b->s.array+X)

    if (!(AR->initialized)) {
      goto success;
    }

#define ARR (AR->array+a)

    ARR->len = list_length(rg_nth(grammar_rule(g, X), a));

    if (!(ARR->initialized)) goto success;

#define ARRR (ARR->array+c)

    if (!(ARRR->initialized)) goto success;

    p21.x = i;
    p21.y = j;

    if (ht_find(ARRR->table, &p21) == NULL) goto success;

    p11 = k;

    if (ht_find(ht_find(ARRR->table, &p21), &p11) == NULL)
      goto success;

    result = 1;

    goto success;

    #undef AR
    #undef ARR
    #undef ARRR
  }

 cleanup:
  *errorp = 1;

 success:
  return result;
}

static void
print_sep()
{
  printf(" ");
}

void
bsr_print(CCR_MOD(bsr *) b, CCR_MOD(Grammar *) g, NUM line_len)
{
  printf("Printing a BSR set...\n");

  NUM count = 0;

  /* print first type BSR */
  for (NUM i = 0; i < b->f.len; i++) {

#define ELEMENT (b->f.array+i)

    if (ELEMENT->initialized) {

#define KEYS ((pair2 **) ht_keys(ELEMENT->table))
#define VALUES ((ht **) ht_values(ELEMENT->table))
#define SIZE (ht_size(ELEMENT->table))

      for (NUM j = 0; j < SIZE; j++) {

#define VALUE_TABLE (*(VALUES+j))
#define VALUE_TABLE_KEYS ((pair2 **) ht_keys(VALUE_TABLE))

        for (NUM k = 0; k < ht_size(VALUE_TABLE); k++) {
          count++;
          printf("(");
          print_name(list_nth(grammar_names(g), i));
          printf(" := ");
          map_list_between
            (rg_nth
             (grammar_rule(g, i),
              (*(VALUE_TABLE_KEYS+k))->x),
             print_tnt, print_sep);
          printf(", %ld, %ld, %ld)",
                 (*(KEYS+j))->x,
                 (*(VALUE_TABLE_KEYS+k))->y,
                 (*(KEYS+j))->y);

          if (count == line_len) {
            count = 0;
            printf("\n");
          } else {
            printf(", ");
          }
        }
      }
    }
  }

#undef ELEMENT
#undef KEYS
#undef VALUES
#undef SIZE
#undef VALUE_TABLE
#undef VALUE_TABLE_KEYS

  for (NUM i = 0; i < b->s.len; i++) {

#define ELEMENT (b->s.array+i)

    if (!(ELEMENT->initialized)) continue;

    for (NUM j = 0; j < ELEMENT->len; j++) {

#define SELE (ELEMENT->array+j)

      if (!(SELE->initialized)) continue;

      for (NUM k = 0; k < SELE->len; k++) {

#define HELE (SELE->array+k)

        if (!(HELE->initialized)) continue;

#define KEYS ((pair2 **) ht_keys(HELE->table))
#define VALUES ((ht **) ht_values(HELE->table))

        for (NUM n = 0; n < ht_size(HELE->table); n++) {
          for (NUM ell = 0; ell < ht_size(*(VALUES+n)); ell++) {

#define VALUE_KEYS ((NUM **) ht_keys(*(VALUES+n)))

            count++;
            printf("(");
            print_name(list_nth(grammar_names(g), i));
            printf(" := ");

#define LS rg_nth(grammar_rule(g, i), j)

            for (NUM m = 0; m < k; m++) {
              print_tnt(*(list_array(LS)+m));
              if (m+1<k) printf(" ");
            }

            printf(" · ");

            for (NUM m = k; m < list_length(LS); m++) {
              print_tnt(*(list_array(LS)+m));
              if (m+1<list_length(LS)) printf(" ");
            }

            printf(", %ld, %ld, %ld)",
                   (*(KEYS+n))->x,
                   **(VALUE_KEYS+ell),
                   (*(KEYS+n))->y);

            if (count == line_len) {
              count = 0;
              printf("\n");
            } else {
              printf(", ");
            }
          }
        }
      }
    }
  }

  printf("\n");

#undef ELEMENT
#undef SELE
#undef HELE
#undef KEYS
#undef VALUES
#undef VALUE_KEYS
#undef LS

}