SEclone basic classes for tagging

The table of strong links TZL

 

We now start with a new key table, the table of strong links.

In my solve, that table is strictly used for tagging. In SE clone, it is also the central place to find pieces of path included in layers.

 

To achieve that task, additional data are prepared at the end of the tagging function.

 

One of these new data is a table ZLI storing for each candidates the nearby candidates one can reach thru strong links (bi values)

 

The elementary class for TZL is ZLN containing

  the 2 candidates of the link

  type that will be set to 1 for equivalence links  a<-> b

  used  to control the tagging process

 

In the TZL class itself

 

tdir is the table of direct links indexed on TZPLN  position of the candidate

zp  is the table of links (index ip)

 

done, path1,pathr,ich,ichbon,length are key data of the procedure looking for pieces of path.

 

The tagging process itself starts in Marquer();

The search for a piece of path starts usually in Direct(); IsDirect() is called to skip that task is a direct strong link fits.

HiddenKite() is looking for a kite starting from a contradiction within a layer.

Clean() send eliminations to TCHAIN when the path is entirely contained in the layer

 

Note: These are the main functions, it could be that part of other entries are obsolete;

 

#define zl_lim 1000

class TZL          // lien type 0 fort, 1 egal

{public:       // bit 2 origine LMEM

     class ZLI{public://index storing direct links

                      USHORT ti[4],iti; // maxi one cell and 3 row/col/box

                            inline void Init(){iti=0;}

                            void Charge(USHORT x){if(iti<4)ti[iti++]=x;}

                            int Dir(USHORT x) {for(int i=0;i<iti;i++) if(ti[i]==x) return 1;

                                                return 0;}

                            void Liste(USHORT ip)

                                  {if(iti) {zpln.Image(ip);E$.Esp();

                                               for(int i=0;i<iti;i++)zpln.Image(ti[i]);

                                                        E$.Enl();}}

                            };

     class ZLN

        {public: USHORT l1,l2,orig; UCHAR used,type;

          void  Charge(USHORT i1,USHORT i2,UCHAR typee=0,USHORT orige=0)

                   {l1=i1;l2=i2;type=typee;used=0;orig=orige;}

 

        int Marque(){if(used) return 0;  

                     zpln.zp[l1].m=col;  col+=2;return 1;}

          void Image(int i);

          

        };

 CB1024 done[20]; // zch chemin trouve

 int ich,ichbon,opy,length,iskip;

 USHORT ip,mmfin;

 PATH path1, pathr[2];

 ZLI tdir[400];

 ZLN zp[zl_lim];   

 

 

 void Init(){ip=1;  // 0 réservé ŕ retour nul

             for(int i=0;i<400;i++) tdir[i].Init();}

 int  Charge(USHORT i1,USHORT i2,UCHAR typee=0,USHORT orige=0);

 void Marquer();

 void Image(int d,int f);

 void Image(){Image(1,ip);}

 

  int IsDirect(USHORT p1,USHORT p2)     {return tdir[p1].Dir(p2);}

 

 

  void Direct(int p1,int p2){iskip=0;GoDirect(p1,p2);}

  void GoDirect(int p1,int p2);

  void Direct_Step();

  int Chemin(USHORT p1,USHORT p2){Direct(p1,p2);     return length;}

  int Chemin(CB1024 &ptsd,CB1024 &ptsf,USHORT p3);

 

  int HiddenKite(int i,int j,USHORT ch);

 

 

  inline void Copy_Path(USHORT i){if(i<2)pathr[i]=path1;}

  inline void Copy_Back(USHORT i){if(i<2)path1=pathr[i];}

 

  void Print_path(){}

 

  int Loop_thru(USHORT p1,USHORT p2,USHORT p3);

  int LoopD(USHORT p1,USHORT p2,USHORT p3,USHORT p2a,USHORT p2b);

  int Clean(int go);

 

 private:

 void UnUsed(){for(int i=1;i<ip;i++)zp[i].used=0;}

 int NextUnmarqued(UCHAR x=0);

 int  ColorCycle(UCHAR x=0);

 void ListeTd() {E$.Enl("liste tdir");

                    for(int i=0;i<400;i++) tdir[i].Liste(i);}

  }zl;

 

Basic functions,  liens0.cpp

 

Here are Charger() to enter a ne link and Marquer()  to do the tagging.

 

int  TZL::Charge(USHORT l1,USHORT l2,UCHAR typee,USHORT orige)

{USHORT wl1=l1,wl2=l2; if(l1>l2){wl1=l2;wl2=l1;}

for(int i=1;i<ip;i++)if((wl1==zp[i].l1) &&( wl2== zp[i].l2)) return 0;

if(typee<1) {tdir[wl1].Charge(wl2);tdir[wl2].Charge(wl1);}

if(ip<zl_lim)  {zp[ip++].Charge(wl1,wl2,typee,orige);

                return (ip-1);}

E$.Elimite("TZL");return 0; }

 

//-----

int   TZL::NextUnmarqued(UCHAR x)

{ int i;  for (i=1;i<ip;i++)

  {  if((zp[i].type&2)-x)  continue;      if(zp[i].Marque())  return  1; }

return 0;}

//<<<<<<<<<<<<<<<     priorite liens de base, seulement aprčs liens ==

int  TZL::ColorCycle(UCHAR x)

{int ir=0;  for(int i=1;i<ip;i++)

{if(zp[i].used) continueif((zp[i].type&2)-x)  continue;

 ZPTLN  *pp1= &zpln.zp[zp[i].l1],*pp2=&zpln.zp[zp[i].l2],

          p1=*pp1,p2=*pp2;

 if((!p1.m)&& (!p2.m) )continue;     zp[i].used=1;

 if(p1.m && p2.m ){ /*if(x) ztlm.Inactif(zp[i].orig);*/  continue; } // en attente<<<<<<

USHORT m2= (p1.m)? p1.m:p2.m;  if(!(zp[i].type&1))m2=m2^1;

 ir=1;if (p1.m)pp2->m=m2; else pp1->m=m2;   }

return  ir;}

//---

void TZL::Marquer()

{zpln.InitCol(); UnUsed();col=2;

 while( NextUnmarqued()||NextUnmarqued(2))     //épuiser d'abord base

        while (ColorCycle()||ColorCycle(2)) {}  // rien a faire

 zpln.MarquerSolde();

}

 

Recursive search of a piece of path,  liens1.cpp

 

 Direct_Step() is the recursive function.

Here, the search is relatively simple. We go from a start candidate to reach a final candidate. The first time we see the final candidate is the good one.

Each step expand all candidates reached in former times with the following restrictions

  . The target has not yet been reached

  . The target is not market as “not authorized in the path”

When the target is reached; the path is built backward.

 

 

 

GoDirect()  is the common entry assuming iskip has the correct value (0 for no control)

 

 

/* done[]  is a CB1024 containing all tags already in the path

   ich is the last index of the known path

   path1 is the current path

   mmfin is the target            

   expand in paralle

   stop as soon as you reach the target*/

 

void TZL::Direct_Step()

{if(op0){E$.E("direct step ich ="); E$.E(ich );

         zpln.ImagePoints( done[ich]," done =");                E$.Enl();}

   USHORT ii,aig=0;  done[ich+1]=done[ich];

       for(int i=1;i<ip;i++)   // look for next possible tags from links

  { ZLN wwl=zp[i]; CB1024 * wcb=& done[ich];

       USHORT l1=wwl.l1,l2=wwl.l2; 

       if(l1==iskip  || l2==iskip) continue; // unauthorized candidate

       if(wcb->On(l1) && (wcb->Off(l2) || (l2==mmfin)) )ii=l2;

       else if(wcb->On(l2) && (wcb->Off(l1)|| (l1==mmfin)) ) ii=l1;

       else continue;

       if(ii==mmfin){aig=1;break;} // ok if target

       aig=2; done[ich+1].Set(ii);

  }

  if(!aig) return; // nothing new, its over

  if(aig>1){ich++; Direct_Step(); return;}

  // now aig=1; ii is the target found; we go back to create the path in "done"

  path1.ipth=ich+2; path1.Set(ich+1,ii);

  while(1)

  {for(int i=1;i<ip;i++)   // find the way back from  links as well

   { ZLN wwl=zp[i]; CB1024 * wcb=& done[ich];

       USHORT l1=wwl.l1,l2=wwl.l2; 

       if((l1==ii) && done[ich].On(l2) )ii=l2;

       else if((l2==ii)&& done[ich].On(l1) )ii=l1;

       else continue;

       path1.Set(ich,ii);

       break;

   }  

       if(!ich) break; ich--;

 }

}

 

 

                           //=======================================

void TZL::GoDirect(int p1, int p2)

{if(op0){E$.E("direct path "); zpln.Image(p1);E$.E("->");zpln.Image(p2);

           E$.Enl();}

mmfin=p2;    ichbon=ich=0;path1.Init(); 

done[0].Init(); done[0].Set(p1);

 

Direct_Step();

length=path1.ipth;   

 }