//---------------------------------------------------------------------------
#include <vcl\vcl.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
	: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void  TForm1::main()
{
 char    *stime[30],*etime[30];
 __int64  tick1,tick2;

      tick1 = GetTickCount();

      Form1->Cursor = crHourGlass;

      fid    = fopen("log.txt","wt");

      time(&t1);
      *stime = ctime(&t1);
      fprintf(fid,"*** pazul started : %s \n",*stime);

      Edit1->Text = *stime;
      Edit3->Text = IntToStr(time(&t2)-t1);

      Form1->Refresh();

      exec();

      tick2 = GetTickCount();
      result = (int) (tick2 -tick1);

      time(&t2);
      *etime = ctime(&t2);
      fprintf(fid,"\n*** pazul  ended  time = %d ms  : %s \n",result,*etime);

      Edit2->Text = *etime;
      Edit3->Text = IntToStr(t2-t1);
      Edit4->Text = IntToStr(result);

      fclose(fid);

  // reset cursor mark
      Form1->Cursor = crDefault;

 }
//---------------------------------------------------------------------------
void    TForm1::exec()
{
 int   n,m,k;
 unsigned __int64 pat;

        for (k=0; k<64; k++) bit64[k] = 0x8000000000000000 >> k;

        RI[1] = 0;
        RI[2] = 1;
        Result[0].pattern = 0;    //initial = 00
        NN = 1;

        for (N=2; N<=15; N++) {
            for (k=0; k<=MAXHkey+1; k++)  Hash[k] = 0;  //clear Hash index
            for (n=RI[N-1]; n<RI[N]; n++) {
                toNodeForm(Result[n].pattern);
                for (m=1; m<=N; m++) {
                    if (modifyNode(m) < 0)  continue;
                    toNormalForm(&pat);
                    if (addPattern(pat) < 0) {
                        fprintf(fid,"*** Result Overflow !!!\n");
                        return;
                     }
                    resetNode(m);
                 }
             }
            RI[N+1] = NN;
            fprintf(fid,"\n====== N=%2d,count=%6d      NN=%7d\n",N+1,RI[N+1]-RI[N],NN);
         }
 }
//---------------------------------------------------------------------------
void    TForm1::toNodeForm(unsigned __int64 pattern)
{
 int    pre,pos,six,i,j,c;
 unsigned __int64 pat;
 int    stack[32];

        pat = pattern;
        pre = 1;
        six = 0;
        Node[1][0] = 0;

        for (pos=2; pos<=N; pos++) {
           c  = ((pat & bit64[pos*2])   == 0)?  0 : 2;
           c += ((pat & bit64[pos*2+1]) == 0)?  0 : 1;
           Node[pos][0] = 0;

       //    fprintf(fid,"*** pos=%d,c=%d,pre=%d,six=%d\n",pos,c,pre,six);
       //    fflush(fid);

         //linkNode
           i = ++Node[pre][0];
           j = ++Node[pos][0];
           Node[pre][i] = pos;
           Node[pos][j] = pre;

           if (c == 3)  stack[++six] = pos;
           if (c >= 2)  stack[++six] = pos;
           if (c >  0)  pre = pos;
           else         pre = stack[six--];
        }
   //    printNode(N);
 }
//---------------------------------------------------------------------------
void   TForm1::printNode(int N)
{
 int   i,j;

       fprintf(fid,"\n***** Node List *****\n");
       for (i=1; i<=N; i++) {
          fprintf(fid,"*** (%d)  %d    ",i,Node[i][0]);
          for (j=1; j<=Node[i][0]; j++)   fprintf(fid,"  %d",Node[i][j]);
          fprintf(fid,"\n");
        }
       fflush(fid);
 }
//---------------------------------------------------------------------------
int     TForm1::modifyNode(int m)
{
 int    n;

        n = Node[m][0];
        if (n == 4)  return -1;
        n++;
        Node[m][0]   = n;
        Node[m][n]   = N+1;
        Node[N+1][0] = 1;
        Node[N+1][1] = m;

  //      printNode(N+1);
        return 0;
 }
//---------------------------------------------------------------------------
void    TForm1::resetNode(int m)
{
        Node[m][0]--;
 }
//---------------------------------------------------------------------------
void    TForm1::toNormalForm(unsigned __int64 *pattern)
{
 int    k,n,n1,l,Bsize;
 unsigned __int64 pat,pat1;

        Bsize = toNF(0,N+1,0,&n,&pat);

        for (k=1; k<=N; k++) {
            if (Node[k][0] != 1)        continue;
            l = toNF(0,k,Bsize,&n1,&pat1) ;
            if (l < 0)                  continue;
            if (pat > pat1) {
                pat   = pat1;
                Bsize = l;
             }
         }
        *pattern = pat;
        return;
 }
//---------------------------------------------------------------------------
int    TForm1::toNF(int from,int to,int Bsize,int *len,unsigned __int64 *ans)
{
 int    p,q,t,c,n,m,i,j,k,newBsize;
 int    size2,size[4];
 unsigned __int64 pat,pat2,pattern[4];

        p   = from;
        q   = to;
        pat = 0;

        for (c=1; c<=(N+1); c++) {
            n = Node[q][0];

  //          fprintf(fid,"*** p=%d,q=%d,n=%d, pattrn=%08x %08x\n",
  //                      p,q,n,(int)(pat>>32),(int)(pat & 0xffffffff));
  //          fflush(fid);

            if (n == 1) {
                if (p == 0) {  //start point?
                    //pat |= 00
                    p = q;
                    q = Node[q][1];
                    continue;
                 }
                *len = c;
                *ans = pat;
                return c;
             }
            if (n == 2) {
                pat |= bit64[1] >> (c*2);   // bit "01"
                t = p;
                p = q;
                q = (Node[q][1] != t)?  Node[q][1] : Node[q][2];
                continue;
             }
            if (n == 3) {
                pat |= bit64[0] >> (c*2);   // bit "10"
                break;
             }
            // n == 4
            pat |= (bit64[0]+bit64[1]) >> (c*2);   // bit "11"
            break;
         }
        if (c < Bsize)  return -1;
        newBsize = c - 1;

     //break leaf
        m = 0;
        for (k=1; k<=n; k++) {
            if (p == Node[q][k])   continue;
            m++;
            toNF(q,Node[q][k],0,&size[m],&pattern[m]);
  //          fprintf(fid,"*** m=%d, size=%d,pattern=%08x %08x\n",
  //                      m,size[m],(int)(pattern[m]>>32),(int)(pattern[m] & 0xffffffff));
  //          fflush(fid);
         }
        for (i=1; i<=m; i++)
        for (j=i+1; j<=m; j++)
            if (pattern[i] > pattern[j]) {
                pat2       = pattern[i];
                pattern[i] = pattern[j];
                pattern[j] = pat2;
                size2      = size[i];
                size[i]    = size[j];
                size[j]    = size2;
             }

    //link pattern
        for (k=1; k<=m; k++) {
            pat |= pattern[k] >> (c*2);
            c   += size[k];
  //          fprintf(fid,"*** link(%d), size=%d,pattern=%08x %08x\n",
  //                      k,c,(int)(pat>>32),(int)(pat & 0xffffffff));
  //          fflush(fid);
         }
        *len = c;
        *ans = pat;
        return newBsize;

 }
//---------------------------------------------------------------------------
int     TForm1::addPattern(unsigned __int64 pattern)
{
 int    hkey,h;

        if (NN > Maxsize)         return -1;

        hkey = (int)(pattern % MAXHkey) + 1;
        h = Hash[hkey];
        while (h > 0) {
           if (Result[h].pattern == pattern)  return 0;
           h = Result[h].link;
         }
        if (N <= 7) {
            fprintf(fid,"*** added(%d), pattern=%08x %08x\n",
                         NN,(int)(pattern>>32),(int)(pattern & 0xffffffff));
            fflush(fid);
         }
        Result[NN].pattern = pattern;
        Result[NN].link    = Hash[hkey];
        Hash[hkey]         = NN++;

        return 0;
 }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormClick(TObject *Sender)
{
     main();
}
//---------------------------------------------------------------------------