rename cnp to crf

THat file implements support functions for the CNP algorithm, not the
algorithm itself.

1 files changed, 487 insertions, 0 deletions

diff --git a/src/crf.c b/src/crf.c
new file mode 100644
index 0000000..dbcb050
--- /dev/null
+++ b/src/crf.c
@@ -0,0 +1,487 @@
+#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;
+}