#ifndef _auxil_h
#define _auxil_h

  #define showGNext() showArray1(GNext)
  #define showGPrev() showArray1(GPrev)
  #define showCStart() showArray(CStart)
  #define showCNext() showArray(CNext)
  #define showCPrev() showArray(CPrev)
  #define showFStart() showArray(FStart)
  #define showFNext() showArray(FNext)
  #define showFPrev() showArray(FPrev)
  #define showRefine() showArray(Refine)
  #define emptyFStart() emptyArray(FStart)
  #define emptyFNext() emptyArray(FNext)
  #define emptyFPrev() emptyArray(FPrev)
  #define showRStack() showStack(RStack,RStackTop)
  #define showSel() showFifo(Sel,SelFirst,SelLast)

  #define showGap() showGap1(Gap)

  void showGap1(ulong* Gap,FILE* fp = stdout) {
    ulong g;

    for(g = 0; g < N; g++)
      if (Gap[g] == null)
        fprintf(fp,"null ");
      else if (Gap[g] < 0)
        fprintf(fp,"%d ",Gap[g]);
      else
        fprintf(fp,"%u ",Gap[g]);
    fprintf(fp,"\n");
  }// showGap1

  #define showCMemebr() showCMember1(Gap,GMext,GPrev)

  void showCMember1(ulong* Gap,ulong* GNext,ulong* GPrev,FILE* fp = stdout) {
    ulong g;
    long x;

    for(g = 0; g < N; g++) {
      if (Gap[g] == null) 
        fprintf(fp,"CMember[%u]=null\n",g);
      else if (Gap[g] < 0) {
        x = 0-1-Gap[g];
        if (x == null)
          fprintf(fp,"CMember[%u]=null\n",g);
        else
          fprintf(fp,"CMember[%u]=%d\n",g,x);
      }else{
        x = 0-1-GNext[GPrev[Gap[g]]];
        if (x == null)
          fprintf(fp,"CMember[%u]=null\n",g);
        else
          fprintf(fp,"CMember[%u]=%d\n",g,x);
      }
    }
  }// showCMember1

  void showArray(ulong *x, FILE *fp = stdout) {
    for(ulong i = 0; i < N; i++) {
      if (x[i]==null)
        fprintf(fp,"null ");
      else
        fprintf(fp,"%u ",x[i]);
    }
    fprintf(fp,"\n");
  }

  void showArray1(long *x, FILE *fp = stdout) {
    for(ulong i = 0; i < N; i++) {
      if (x[i]==null)
        fprintf(fp,"null ");
      else
        fprintf(fp,"%d ",x[i]);
    }
    fprintf(fp,"\n");
  }

  void showStack(ulong *x, ulong top, FILE *fp = stdout) {
    if (top==null) {
      fprintf(fp,"<empty>\n");
      return;
    }
    for(ulong i = 0; i <= top; i++) {
      if (x[i]==null)
        fprintf(fp,"null ");
      else
        fprintf(fp,"%u ",x[i]);
    }
    fprintf(fp,"\n");
  }

  ulong emptyArray(ulong *x,FILE *fp=stdout) {
    for(ulong i = 0; i < N; i++) {
      if (x[i]!=null) {
        printf("item %u not null\n",i);
        return false;
      }
    }
    return true;
  }

  void showFifo(ulong* x,ulong f,ulong l,FILE *fp=stdout) {
    for(ulong i = f; i < N; i++) {
      fprintf(fp,"%u ",x[i]);
      if (i == l) break;
    }
    fprintf(fp,"\n");
  }

  void showString(char* string,ulong n,FILE* fp=stdout) {
    ulong i;

    if (n >= 10) {
      for(i = 0; i < n; i++) {
        if (i < 10)
          fprintf(fp," ");
        else
          fprintf(fp,"%d",i/10);
      }
      fputc('\n',fp);
    }
    for(i = 0; i < n; i++) 
      fprintf(fp,"%d",i%10);
    fputc('\n',fp);
    for(i = 0; i < n; i++)
      fprintf(fp,"%c",string[i]);
    fputc('\n',fp);
    for(i = 0; i < n; i++)
      fputc('-',fp);
    fputc('\n',fp);
  }//end showString

  #define showFamily(f) showFamily1(f,FStart,FNext,FPrev,CNext,CPrev,CStart)

  // method showFamily1 ------------------------------------------------------
  void showFamily1(ulong f,ulong* FStart,ulong* FNext,ulong* FPrev,ulong* CNext,
    ulong* CPrev,ulong* CStart,FILE *fp=stdout) {
    ulong big, c;
    
    big = FBig(f);
    c = FStart[f];

    if (c == big)
      fprintf(fp,"f%u={C%u",f,c);
    else
      fprintf(fp,"f%u={c%u",f,c);

    while (c != FEnd(f)) {
      c = FNext[c];
      if (c == big)
        fprintf(fp,",C%u",c);
      else
        fprintf(fp,",c%u",c);
      if (c == FEnd(f)) break;
    }
    fprintf(fp,"}");
  }//end showFamily1

  #define showFamilies() \
       showFamilies1(FStart,FNext,FPrev,FStartTop,CNext,CPrev,CStart)

  // method showFamilies1 ------------------------------------------------------
  void showFamilies1(ulong* FStart,ulong* FNext,ulong* FPrev,ulong FStartTop,
                     ulong* CNext,ulong* CPrev,ulong* CStart,FILE *fp=stdout) {
    ulong f;
    bool empty;

    fprintf(fp,"families: ");
    for(empty = true, f = 0; f <= FStartTop; f++) {
      if (FStart[f] != null) {
        showFamily1(f,FStart,FNext,FPrev,CNext,CPrev,CStart,fp);
        fprintf(fp," ");
        empty = false;
      }
    }
    if (empty)
      fprintf(fp,"<empty>\n");
    else
      fprintf(fp,"\n");
  }//end showFamilies1


  // method isinF -------------------------------------------------------------
  // returns true if class e belongs to family f
  bool isinF(ulong e,ulong f,ulong* FStart,ulong* FNext,ulong* FPrev,
             ulong FStartTop) {
    ulong e1;
    bool in;

    for(in = false, e1 = FStart[f];     ; e1 = FNext[e1]) {
      if (e1 == e) {
        break;
        in = true;
      }
      if (e1 == FEnd(f)) break;
    }
    return in;
  }//end isinF



  // method disjointF ----------------------------------------------------------
  // returns true if f1 and f2 are disjoint families
  bool disjointF(ulong f1,ulong f2,ulong* FStart,ulong* FNext,ulong* FPrev,
                 ulong FStartTop) {
    ulong e;

    for(e = FStart[f1];   ; e = FNext[e]) {
      if (isinF(e,f2,FStart,FNext,FPrev,FStartTop)) 
        return false;
      if (e == FEnd(f1)) break;
    }
    return true;
  }//end disjointF


  #define IT_Families() \
          IT_Families1(FStart,FNext,FPrev,FStartTop,CStart,CNext,CPrev)

  // method IT_Families1 -------------------------------------------------------
  // test integrity of families
  bool IT_Families1(ulong* FStart,ulong* FNext,ulong* FPrev,ulong FStartTop,
                    ulong* CStart,ulong* CNext,ulong* CPrev,FILE *fp=stdout) {
    ulong f, f1, c, big, m;
    bool bad, found;

    if (FStartTop == null) return true;

    for(bad = false, f = 0; f < N; f++) {
      if (f > FStartTop && FStart[f] != null) { // it must be FMember()
        if (FStart[f] > FStartTop) {
          fprintf(fp,"dangling FMember[%u]=%u\n",f,FStart[f]);
          bad = true;
          getchar();
        }
        continue;
      }
      if (f > FStartTop) continue;
      if (FStart[f]==null) {
        fprintf(fp,"family %u failed top test\n",f);
        bad = true;
        getchar();
        continue;
      }
      big = FBig(f);
      for(c = FStart[f];    ; c = FNext[c]) {
        if (c != FStart[f] && FNext[FPrev[c]] != c ) {
          fprintf(fp,"family %u failed link test\n",f);
          bad = true;
          getchar();
          break;
        }
        m = FMember(c);
        if (m != f) {
          fprintf(fp,"family %u failed integrity test\n",f);
          bad = true;
          getchar();
          break;
        }
        if (c != FStart[f] && c != big && CSize(c) > CSize(big)) {
          fprintf(fp,"family %u failed big test\n",f);
          bad = true;
          getchar();
          break;
        }
        if (c == FEnd(f)) break;
      }
      for(f1 = f+1; f1 <= FStartTop; f1++) {
        if (! disjointF(f,f1,FStart,FNext,FPrev,FStartTop)) {
          bad = true;
          fprintf(fp,"families %u and %u not disjoint\n",f,f1);
          showFamily1(f,FStart,FNext,FPrev,CNext,CPrev,CStart,fp);
          fprintf(fp,"\n");
          showFamily1(f1,FStart,FNext,FPrev,CNext,CPrev,CStart,fp);
          fprintf(fp,"\n");
          getchar();
          break;
        }
      }
    }
    // check for spurious FMember()
    for(m = 0; m < N; m++) {
      f = FMember(m);
      if (f == null) continue;
      // so class m is supposed to be in family f
      for(found=false, f1 = FStart[f];  ; f1 = FNext[f1]) {
        if (f1 == m) {
          found = true;
          break;
        }
        if (f1 == FEnd(f)) break;
      }
      if (! found) {
        bad = true;
        fprintf(fp,"spurious FMember(%u)=%u\n",m,f);
        getchar();
      }
    }

    //if (! bad)
    //  fprintf(fp,"families passed integrity test\n");
    return ! bad;
  }//end IT_Families1

  #define showClass(i)  showClass1(i,CStart,CNext,CPrev)

  // method showClass1 --------------------------------------------------------
  void showClass1(ulong i,ulong* CStart,ulong* CNext,ulong* CPrev,
                  FILE *fp=stdout) {
    ulong j;

    j = CStart[i];
    fprintf(fp,"c%d={%u",i,j);
    if (j == CEnd(i)) {
      fprintf(fp,"}");
      return;
    }
    while(true) {
      j = CNext[j];
      fprintf(fp,",%u",j);
      if (j == CEnd(i)) {
        fprintf(fp,"}");
        break;
      }
    }
  }//end showClass1

  #define showClasses()  showClasses1(CStart,CNext,CPrev)

  // method showClasses1 -----------------------------------------------------
  void showClasses1(ulong* CStart,ulong* CNext,ulong* CPrev,FILE *fp=stdout) {
    ulong i;
    bool empty;

    fprintf(fp,"classes: ");
    for(empty = true, i = 0; i < N; i++) {
      if (CStart[i] == null) continue;
      showClass1(i,CStart,CNext,CPrev,fp);
      empty = false;
      fprintf(fp," ");
    }
    if (empty)
      fprintf(fp,"<empty>\n");
    else
      fprintf(fp,"\n");
  }//end showClasses1

  // method isinC ------------------------------------------------------------
  // returns true if element e belongs to class c
  bool isinC(ulong e,ulong c,ulong* CStart,ulong* CNext,ulong* CPrev) {
    ulong e1;
    bool in;

    for(in = false, e1 = CStart[c];  ; e1 = CNext[e1]) {
      if (e1 == e) {
        break;
        in = true;
      }
      if (e1 == CEnd(c)) break;
    }
    return in;
  }//end isinC

  // method disjointC --------------------------------------------------------
  // returns true if c1 and c2 are disjoint classes
  bool disjointC(ulong c1,ulong c2,ulong* CStart,ulong* CNext,ulong* CPrev) {
    ulong e;

    for(e = CStart[c1];    ; e = CNext[e]) {
      if (isinC(e,c2,CStart,CNext,CPrev)) return false;
      if (e == CEnd(c1)) break;
    }
    return true;
  }//end disjointC

  #define IT_Classes(s,L)  IT_Classes1(s,L,CStart,CNext,CPrev,Gap,GNext,GPrev,S)

  // method IT_Classes1 -------------------------------------------------------
  bool IT_Classes1(char* string,ulong L,ulong* CStart,ulong* CNext,ulong* CPrev,
                   long* Gap,long* GNext,long* GPrev,char* S,FILE *fp=stdout) {
    ulong i, j, e, prev, count;
    bool bad;
  
    for(bad = false, i = 0; i < N; i++) {
      if (CStart[i] == null) continue;
      prev = null;
      count = 0;
      // traverse class i
      for(e = CStart[i];    ; count++, prev = e, e = CNext[e]) {
        if (strncmp(&string[CStart[i]],&string[e],L)!=0) {
          fprintf(fp,"class %u, position %u, failed substring "
                     "integrity test\n",i,e);
          fprintf(fp,"string=\"%s\"\n",S);
          for(j = 0; j < L; j++)
            fputc(string[CStart[i]+j],fp);
          fputc('\n',fp);
          for(j = 0; j < L; j++)
            fputc(string[e+j],fp);
          fputc('\n',fp);
          getchar();
          bad = true;
        }
        if (getCMember(e) != i)  {
          bad = true;
          fprintf(fp,"class %u (element %u) failed membership test\n",i,e);
        }
        if (CPrev[e] != prev && e != CStart[i]) {
          bad = true;
          fprintf(fp,"class %u (element %u) failed previous test\n",i,e);
        }
        if (e == CEnd(i)) {
          count++;
          break;
        }
      }
      if (count != CSize(i)) {
        bad = true;
        fprintf(fp,"class %u failed size test\n",i);
      }
      for(j = i+1; j < N; j++) {
        if (CStart[j] == null) continue;
        if (! disjointC(i,j,CStart,CNext,CPrev)) {
          bad = true;
          fprintf(fp,"classes %u and %u are not disjoint\n",i,j);
          showClass1(i,CStart,CNext,CPrev,fp);
          fprintf(fp,"\n");
          showClass1(j,CStart,CNext,CPrev,fp);
          fprintf(fp,"\n");
        }
      }
    }
    //if (! bad)
    //  fprintf(fp,"classes passed integrity test\n");
    return ! bad;
  }//end IT_Classes1

  #define showCEmpty()  showCEmpty1(CEmpty,CEmptyTop)

  // method showCEmpty1 ------------------------------------------------------
  void showCEmpty1(ulong* CEmpty,ulong CEmptyTop,FILE* fp=stdout) {
    ulong i;

    if ((i = CEmptyTop) == null) {
      fprintf(fp,"CEmpty: <empty>\n");
      return;
    }
    fprintf(fp,"CEmpty: top-down <c%u",CEmpty[i++]);
    while(i < N)
      fprintf(fp," c%u",CEmpty[i++]);
    fprintf(fp,">\n");
  }//end showCEmpty1

  #define showSc()  showSc1(Sc,ScFirst,ScLast)

  // method showSc1 ----------------------------------------------------------
  void showSc1(ulong* Sc,ulong ScFirst,ulong ScLast,FILE* fp=stdout) {
    ulong s;

    if ((s = ScFirst) == null) { 
      fprintf(fp,"Sc: <empty>\n");
      return;
    }
    fprintf(fp,"Sc: first to last <%u",Sc[s]);
    if (s == ScLast) 
      s = null;
    else
      s--;
    while(s != null) {
      fprintf(fp," %u",Sc[s]);
      if (s == ScLast)
        s = null;
      else
        s--;
    }
    fprintf(fp,">\n");
  }// showSc1

  #define showSmallClasses()  \
          showSmallClasses1(FStart,FNext,FPrev,FStartTop,CStart,CNext,CPrev)

  // method showSmallClasses1 -------------------------------------------------
  void showSmallClasses1(ulong* FStart,ulong* FNext,ulong* FPrev,
                         ulong FStartTop,ulong* CStart,
    ulong* CNext,ulong* CPrev,FILE *fp=stdout) {
    ulong f, c, big;
    bool empty;

    fprintf(fp,"small classes\n");
    for(empty = true, f=0; f <= FStartTop; f++) {
      if (FNext[FStart[f]] == null)  {       // singleton family
        showClass1(FStart[f],CStart,CNext,CPrev,fp);
        fprintf(fp," ");
        continue;
      }
      empty = false;
      // determine the big class for family
      // it is either first or the second one
      big = FBig(f);
      for(c = FStart[f];  ; c = FNext[c]) {
        if (c == big) continue;
        showClass1(c,CStart,CNext,CPrev,fp);
        fprintf(fp," ");
        if (c == FEnd(f)) break;
      }
    }
    if (empty)
      fprintf(fp,"<empty>\n");
    else
      fprintf(fp,"\n");
  }//end showSmallClasses1

  #define showSnapshot() showSnapshot1(Sc,ScFirst,ScLast,Sel,SelFirst,SelLast)

  // method showSnapshot1 -----------------------------------------------------
  void showSnapshot1(ulong* Sc,ulong ScFirst,ulong ScLast,ulong* Sel,
                     ulong SelFirst,ulong SelLast,FILE *fp=stdout) {
    ulong send, e, sc_First, sc_Last, sel_First, sel_Last;
    char ind;

    fprintf(fp,"snapshot: ");
    // we must preserve First and Last
    sc_First = ScFirst;
    sc_Last = ScLast;
    sel_First = SelFirst;
    sel_Last = SelLast;

    while((send = ScOut()) != null) {
      ind = '{';
      while((e = SelOut()) != send) {
        if (e == null) {
          printf("snapshot problem\n");
          exit(1);
        }
        fprintf(fp,"%c%u",ind,e);
        ind = ',';
      }//endwile
      fprintf(fp,"%c%u}",ind,e);
    }//endwhile
    fprintf(fp,"\n");

    // we must restore First and Last
    ScFirst = sc_First;
    ScLast = sc_Last;
    SelFirst = sel_First;
    SelLast = sel_Last;
  }//end showSnapshot1

  #define showGaps() showGaps1(Gap,GNext,GPrev)

  // method showGaps1 --------------------------------------------------------
  void showGaps1(long* Gap,long* GNext,long* GPrev,FILE* fp=stdout) {
    long g, p, gend;

    fprintf(fp,"Gaps:\n");
    for(g = 0; g < (long) N; g++) {
      if (Gap[g] < 0 || Gap[g] == null) continue;
      gend = GPrev[Gap[g]];
      fprintf(fp,"gap %d:",g);
      for(p = Gap[g];   ; p = GNext[p]) {
        fprintf(fp,"%d ",p);
        if (p == gend) break;
      }
      fprintf(fp,"\n");
    }
  }//end showGaps1

  #define IT_Gaps() IT_Gaps1(Gap,GNext,GPrev,CStart,CNext,CPrev)

  // method IT_Gaps1 ---------------------------------------------------------
  // integrity test of Gaps
  bool IT_Gaps1(long* Gap,long* GNext,long* GPrev,ulong* CStart,ulong* CNext,
                ulong* CPrev,FILE* fp=stdout) {
    long p, g, prev;
    bool bad=false;

    // check links
    for(g = 0; g < (long) N; g++) {
      if (Gap [g] <= 0 || Gap[g] == null) continue;
      // traverse the list in both directions
      for(prev = null, p = Gap[g];    ; prev = p, p=GNext[p]) {
        if (GMember(p) != g) {
          printf("position %u with gap %u in Gap[%u]\n",p,GMember(p),g);
            bad=true;
        }
        if (prev != null) {
          if (GPrev[p] != prev) {
            printf("wrong previous link in Gap list for %d\n",p);
            bad = true;
          }
        }
        if (p == GPrev[Gap[g]]) break;
      }
    }
    if (! bad) fprintf(fp,"Gaps integrity OK\n");
    if (bad) {
      getchar();
      exit(1);
    }
    return bad;
  }//end IT_Gaps1

  // check by brute force if the run is a real run
  static void BFrun(char* str,ulong s,ulong p,ulong e,ulong t) {
    ulong i, j;
  
    for(i = 0; i < p; i++) {
      if (i < t) {
        for(j = 1; j <= e; j++)
          if (str[s+i] != str[s+j*p+i]) 
            goto bad;
      }else{
        for(j = 1; j < e; j++)
          if (str[s+i] != str[s+j*p+i]) 
            goto bad;
      }  
    }
    if (s > 0 && str[s-1] == str[s+p-1]) 
      goto bad;
    if (s+e*p+t < strlen(str)-1 && str[s+e*p+t] == str[s+(e-1)*p+t]) 
      goto bad;
    return;
bad:
    printf("not a run\n");
    getchar();
  }//end BFrun

#endif // _auxil_h