#include <stdio.h>
#include <stdlib.h>

#define OBSERVED 0
#define DEBUG 0
#define TRACKING 0
#define STATS 0
#define ALLOC_BIG_CHUNKS 1
#define LARGEST_ONLY 0

#define CHECK_INCL 0

#include "readpairs.c"
#include "getbingraph.c"
#include "maxcliques.c"

////////////////////////////////////////////////////////////////////////////
// test harness

struct graphInfo *curGraph;

void printRevNodeList (ObjList p) {
  ObjList q = p->tail;
  if (q) printRevNodeList (q);
#if DEBUG
  printf (" %d", (int) p->head);
#else
  //  printf (" %d", i);
  printf (" %s", curGraph->names[(int) p->head]);
#endif
}

void printCliqTreeAux (CliqTree t, ObjList p, int cnt) {
  while (t) {
    struct objList q;
    q.head = (object) t->node;
    q.tail = p;
    ++cnt;
    if (t->with == NULL) {
      printf ("%02d", cnt);
      printRevNodeList (&q);
      printf ("\n");
    }
    else printCliqTreeAux (t->with, &q, cnt);
    t = t->without;
    --cnt;
  }
}

int printCliqTree (CliqTree t) {
  printCliqTreeAux (t, NULL, 0);
}

void checkAgainst (const char *fname, CliqTree p) {
  char *start, *c, *be, buf[20], ch;
  struct stat st;
  FILE *f;
  int i, j, l, m, n;
  unsigned int k;
  CliqTree q;
  int cliq[100];
  BitMatrix graph = curGraph->graph;
  int nNodes = curGraph->nNodes;
  char **names = curGraph->names;
  ASCIITrie nodeDict = curGraph->nodeDict;

  c = start = mmapFile (f = openFile (fname), &st);
  be = start + st.st_size;
  l = 0;
  while (c < be) {
    ++l;
    if (*c == '#') {
      while (*c++ != '\n');
      continue;
    }
    for (j = 0; (k = *c++ - '0') <= 9; j = j*10+k);
    --j;
    while (*c == ' ') ++c;
    for (m = 0, ch = ' '; m <= j; ++m) {
      if (m == j) ch = '\n';
      i = getNameIndex (&c, ch);
      for (n = 0; n < m && cliq[n] < i; ++n);
      if (n < m) {
	if (cliq[n] == i) printf ("bogus line %d\n", l), exit (1);
	int k;
	for (k = m; k > n; --k) cliq[k] = cliq[k-1];
      }
      cliq[n] = i;
    }
    for (q = p, m = 0; m <= j; ++m) {
      n = cliq[m];
      while (q && q->node < n) q = q->without;
      if (q == NULL || q->node > n) {
	printf ("line %d not found:", l);
	for (n = 0; n <= j; ++n) printf (" %d", cliq[n]);
	printf ("\n");
	q = NULL;
	break;
      }
      if (m == j) q->node = -1;
      q = q->with;
    }
    if (q != NULL) printf ("line %d longer\n", l);
  }
  munmap (start, st.st_size);
  fclose (f);
  for (q = p;;) {
    if (q->with == NULL) {
      if (q->node >= 0) {
	printf ("extra");
	CliqTree r = q;
	for (; r; r = r->up)
	  printf (" %s(%d)", names[r->node], r->node);
	printf ("\n");
      }
      while (q && q->without == NULL) q = q->up;
      if (q == NULL) break;
      q = q->without;
    }
    else q = q->with;
  }
}

void printSet (IntSet s, int n) {
  int i;
  for (i = SetFindNext (s, n, 0); i < n; i = SetFindNext (s, n, i+1))
    printf (" %s", curGraph->names[i]);
  printf ("\n");
}

#if 0
void checkInclusion (CliqTree p, CliqTree p1) {
  ObjList *cliqs, *l;
  CliqTree q;
  IntSet cliq = NewEmptySet (nNodes);

  cliqs = (ObjList *) calloc (nNodes, sizeof (ObjList));
  ScanCliqTree (q, p1, { l = &cliqs[q->node]; }, { SetAdd (cliq, q->node); },
  {
    IntSet c = NewSet (nNodes);
    SetExactCopy (c, cliq, nNodes);
    ConsOn (*l, c);
  }, { SetDel (cliq, q->node); });
  ScanCliqTree (q, p, { l = &cliqs[q->node]; }, { SetAdd (cliq, q->node); },
  {
    ObjList r = *l;
    while (r && !Subset (cliq, (IntSet) r->head, nNodes)) r = r->tail;
    if (r == NULL) printSet (cliq, nNodes);
  }, { SetDel (cliq, q->node); });
}
#endif

main (int argc, char **argv) {
  if (argc < 2)
    fprintf (stderr, "usage: %s <bin-graph> [<bigger-bin-graph>]\n", argv[0]),
      exit (1);
  struct graphInfo g;
  curGraph = &g;
  getGraph (argv[1], &g);
  maxCliques_traceout = stdout;
  CliqTree p = maxCliques (&g);
  if (argc == 2) {
#if LARGEST_ONLY
    printf ("\n========\n");
    printLargest ();
#else
    printCliqTree (p);
#endif
  }
  else {
#if CHECK_INCL
    BitMatrix graph1 = readGraph (argv[2]);
    CliqTree q = maxCliques (graph1, nNodes);
    checkInclusion (p, q);
#else
    checkAgainst (argv[2], p);
#endif
  }
}