path: root/src/crf.c

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

struct crf_s {
  ht *table;
};

crf *
new_crf()
{
  crf *crfp = NULL;
  SAFE_MALLOC(crf, crfp, 1, goto cleanup;);

  crfp->table = new_ht2(HT_INIT_CAP);

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

  return crfp;

 cleanup:

  if (crfp) free(crfp);

  return NULL;
}

BOOL
crf_add_node(crf * const restrict crfp, pair2 node)
{
  if (ht_find(crfp->table, &node)) return 0;

  pair2 *p2 = NULL;

  NEW_P2(p2, node.x, node.y, return 1;);

  ht *value_table = new_ht4(HT_INIT_CAP);

  if (value_table == NULL) {
    free(p2);
    return 1;
  }

  if (ht_insert(crfp->table, p2, value_table)) {
    fleprintf0("Fail to insert\n");
    destroy_ht(value_table, DESTROY_NONE_SELF);
    free(p2);
    return 1;
  }

  return 0;
}

ht *
crf_find_node(crf * const restrict crfp, pair2 node)
{
  return ht_find(crfp->table, &node);
}

BOOL
crf_add_edge(crf * const restrict crfp, pair2 source, pair4 label)
{
  if (ht_find(crfp->table, &source) == NULL) {
    fleprintf0("add the node before adding its edges\n");
    return 1;
  }

  if (ht_find(ht_find(crfp->table, &source), &label)) return 0;

  pair4 *p = NULL;

  NEW_P4(p, label.x, label.y, label.z, label.w, return 1;);

  if (ht_insert(ht_find(crfp->table, &source), p, (void*)1)) {
    fleprintf0("Fail to insert\n");
    free(p);
    return 1;
  }

  return 0;
}

void
destroy_crf(crf * const restrict crfp)
{

#define SIZE (ht_size(crfp->table))
#define VALUES ((ht**) ht_values(crfp->table))

  for (NUM i = 0; i < SIZE;)
    destroy_ht(*(VALUES+i++), DESTROY_KEY_SELF);

  destroy_ht(crfp->table, DESTROY_KEY_SELF);

  free(crfp);

#undef SIZE
#undef VALUES

}

struct spa_s {
  ht *table;
};

spa *
new_spa()
{
  spa *spap = NULL;
  SAFE_MALLOC(spa, spap, 1, return NULL;);

  spap->table = new_ht2(HT_INIT_CAP);

  if (spap->table == NULL) {
    free(spap);
    return NULL;
  }

  return spap;
}

void
destroy_spa(spa * const restrict spap)
{
  for (NUM i = 0; i < ht_size(spap->table); i++)
    destroy_ht(*((ht **) ht_values(spap->table)+i), DESTROY_KEY_SELF);

  /* fleprintf0("ho\n"); */

  destroy_ht(spap->table, DESTROY_KEY_SELF);

  free(spap);
}

BOOL
spa_insert(spa * const restrict spap, pair3 label)
{
  pair2 first_two = (pair2) { 0 }, *p2 = NULL;

  first_two.x = label.x;
  first_two.y = label.y;

  NUM j = label.z, *np = NULL;

  ht *value_table = NULL;

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

    if (value_table == NULL) {
      fleprintf0("Fail to have new hash table\n");
      goto cleanup;
    }

    SAFE_MALLOC(NUM, np, 1, goto cleanup;);
    *np = label.z;

    if (ht_insert(value_table, np, (void*)1)) {
      fleprintf0("Fail to insert\n");
      goto cleanup;
    }

    np = NULL;

    NEW_P2(p2, label.x, label.y, goto cleanup;);

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

    p2 = NULL;

    goto success;
  }

  if (ht_find(ht_find(spap->table, &first_two), &j) == NULL) {
    SAFE_MALLOC(NUM, np, 1, goto cleanup;);
    *np = label.z;

    if (ht_insert(ht_find(spap->table, &first_two), np, (void*)1)) {
      fleprintf0("Fail to insert\n");
      goto cleanup;
    }

    np = NULL;
  }

  goto success;

 cleanup:
  if (value_table) destroy_ht(value_table, DESTROY_KEY_SELF);
  if (p2) free(p2);
  if (np) free(np);

  return 1;

 success:
  return 0;
}

P_ATTR
BOOL
spa_belong(CCR_MOD(spa *) spap, pair3 label)
{
  pair2 first_two = (pair2) { 0 };

  first_two.x = label.x;
  first_two.y = label.y;

  if (ht_find(spap->table, &first_two) == NULL) return 0;

  NUM j = label.z;

  if (ht_find(ht_find(spap->table, &first_two), &j) == NULL) return 0;

  return 1;
}

P_ATTR
ht *
spa_find(CCR_MOD(spa *) spap, pair2 label)
{
  return ht_find(spap->table, &label);
}

typedef struct procr_array_element_s procr_array_element;

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

struct procr_s {
  /* input length */
  NUM len;
  /* an array of lists */
  procr_array_element *array;
  /* minimal grade that is non-empty */
  NUM mg;
};

typedef struct procu_array_element_s procu_array_element;

/* The table at index k represents the set U_k.  Its keys are those
   (X, a, i, j) such that (X, a, i, j, k) belongs to U_k. */
struct procu_array_element_s {
  BOOL initialized;
  ht *table;
};

struct procu_s {
  /* input length */
  NUM len;
  /* an array of hash tables */
  procu_array_element *array;
};

procr *
new_procr(NUM size, BOOL * const restrict errorp)
{
  *errorp = 0;

  procr *pr = NULL;

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

  pr->len = size;
  pr->array = NULL;

  SAFE_MALLOC(procr_array_element, pr->array,
              sizeof(procr_array_element) * size,
              goto cleanup;);

  memset(pr->array, 0, sizeof(procr_array_element) * size);

  goto success;

 cleanup:

  *errorp = 1;

  if (pr && pr->array) free(pr->array);

  if (pr) free(pr);

 success:

  return pr;
}

procu *
new_procu(NUM size, BOOL * const restrict errorp)
{
  *errorp = 0;

  procu *pu = NULL;

  SAFE_MALLOC(procu, pu, 1, goto cleanup;);

  pu->len = size;
  pu->array = NULL;

  SAFE_MALLOC(procu_array_element, pu->array,
              sizeof(procu_array_element) * size,
              goto cleanup;);

  memset(pu->array, 0, sizeof(procu_array_element) * size);

  goto success;

 cleanup:

  *errorp = 1;

  if (pu && pu->array) free(pu->array);

  if (pu) free(pu);

 success:

  return pu;
}

void
destroy_procr(procr * const restrict pr)
{
  for (NUM i = 0; i < pr->len; i++)
    if ((pr->array+i)->initialized)
      destroy_list((pr->array+i)->ls, 1);

  free(pr->array);

  free(pr);
}

void
destroy_procu(procu * const restrict pu)
{
  for (NUM i = 0; i < pu->len; i++)
    if ((pu->array+i)->initialized)
      destroy_ht((pu->array+i)->table, DESTROY_KEY_SELF);

  free(pu->array);

  free(pu);
}

BOOL
desc_add(procr * const restrict pr, procu * const restrict pu,
         NUM grade, prodecor dec)
{
  if (grade < 0 || grade >= pu->len) {
    fleprintf("Invalid grade: %ld\n", grade);
    goto cleanup;
  }

  pair4 *p4 = NULL;

#define HELE (pu->array+grade)
#define LELE (pr->array+grade)

  if (HELE->initialized) {
    /* If HELE is initialized then LELE should also be initialized. */
    if (ht_find(HELE->table, &dec) != NULL) goto success;

    NEW_P4(p4, dec.x, dec.y, dec.z, dec.w, goto cleanup;);

    if (ht_insert(HELE->table, p4, (void*)1)) {
      fleprintf0("Fail to insert\n");
      goto cleanup;
    }

    NEW_P4(p4, dec.x, dec.y, dec.z, dec.w,
           ht_delete(HELE->table, &dec, DELETE_KEY); goto cleanup;);

    if (add_to_list(LELE->ls, p4)) {
      fleprintf0("Fail to add to list\n");
      ht_delete(HELE->table, &dec, DELETE_KEY);
      goto cleanup;
    }

    goto success;
  }

  HELE->table = new_ht4(HT_INIT_CAP);

  if (HELE->table == NULL) {
    fleprintf0("Fail to have new hash table\n");
    goto cleanup;
  }

  HELE->initialized = 1;

  NEW_P4(p4, dec.x, dec.y, dec.z, dec.w,
         destroy_ht(HELE->table, DESTROY_KEY_SELF);
         HELE->initialized = 0;
         goto cleanup;);

  if (ht_insert(HELE->table, p4, (void*)1)) {
    fleprintf0("Fail to insert\n");
    destroy_ht(HELE->table, DESTROY_KEY_SELF);
    HELE->initialized = 0;
    goto cleanup;
  }

  LELE->ls = new_list();

  if (LELE->ls == NULL) {
    fleprintf0("Fail to have new list\n");
    destroy_ht(HELE->table, DESTROY_KEY_SELF);
    HELE->initialized = 0;
    goto cleanup;
  }

  LELE->initialized = 1;

  NEW_P4(p4, dec.x, dec.y, dec.z, dec.w,
         destroy_ht(HELE->table, DESTROY_KEY_SELF);
         HELE->initialized = 0;
         destroy_list(LELE->ls, 1);
         LELE->initialized = 0;
         goto cleanup;);

  if (add_to_list(LELE->ls, p4)) {
    fleprintf0("Fail to add to list\n");
    destroy_ht(HELE->table, DESTROY_KEY_SELF);
    HELE->initialized = 0;
    destroy_list(LELE->ls, 1);
    LELE->initialized = 0;
    goto cleanup;
  }

#undef HELE
#undef LELE

  goto success;

 cleanup:

  return 1;

 success:

  return 0;
}

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

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

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

  if (!(ELEMENT->initialized)) goto reset_mg;

  *gradep = pr->mg;

  result = pop_from_list(ELEMENT->ls);

  if (list_length(ELEMENT->ls) == 0) {
    destroy_ht((pu->array+pr->mg)->table, DESTROY_KEY_SELF);
    (pu->array+pr->mg)->initialized = 0;
    (pu->array+pr->mg)->table = NULL;

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

    /* REVIEW: Maybe we can just increment the minimal grade, as we
       won't jump over two steps? */
  reset_mg:
    while (++(pr->mg) < pr->len) {
      if (ELEMENT->initialized) break;
    }
  }

#undef ELEMENT

 success:
  return result;
}