/* TestSearchComponent.c */

#include <stdio.h>
#define NN 1000       /* max number of links, etc */
#define MAXOBJ 100   /* max number of objects possible */

int Ary2TODouble(int*,int*,int*,int*,int*);
void TOGRAPH(int*, int*, int, int*);
int VISITALLOBJ(int*,int*);
void SSORT(int*, int);

void main(void)
{
 int K,N,N2,N3,               /* N pairs linked objects, N2 = 2N */
/*
  A[]={ 1, 1, 1, 2, 2, 4, 4, 4, 4, 5, 5, 5, 6, 7, 7, 8, 9,10,11,
       12,14,14,15,16,16,17,23,24, 0},
  B[]={ 2, 3, 5, 6, 7, 5, 8, 9,13, 9,10,20,11,12,17,13,14,15,22,
       18,19,20,16,21,22,22, 0, 0, 0},
*/
  A[]={ 1, 1, 2, 2, 4, 4, 4, 4, 5, 6, 7, 7, 8, 9,10,11,
       12,14,15,16,16,23,24, 0},
  B[]={ 3, 5, 6, 7, 5, 8, 9,13,20,11,12,17,13,14,15,22,
       18,19,16,21,22, 0, 0, 0},

 AA[NN],BB[NN],DIV[NN],FULLARY[NN],PATH[NN];

  N=0; while (A[N]) N++;
  printf("N=%d\n",N);
  for (K=0; K<=N; K++) printf("%2d ",A[K]); puts("");
  for (K=0; K<=N; K++) printf("%2d ",B[K]); puts("");

  N2=Ary2TODouble(A,B,AA,BB,DIV); printf("N2=%d AA[0]=%d\n",N2,AA[0]);

  printf("\nN2=%d\n",N2);
  for (K=0; K<=N2; K++) printf("%2d ",AA[K]); puts("");
  for (K=0; K<=N2; K++) printf("%2d ",BB[K]); puts("");

  TOGRAPH(AA,BB,N2,FULLARY);    N3=FULLARY[0];     printf("N3=%d\n",N3);
  for (K=0; K<=N3; K++)
   {if (FULLARY[K]<0) putchar(' '); printf("%d,",FULLARY[K]);}

 N=VISITALLOBJ(FULLARY,PATH);
 printf("\n%d = length of path\n",N);
 puts("path(s); zeros not objects but separate components");
 for (K=0; K<N; K++) printf("%d ",PATH[K]);    puts("\n");

 SSORT(PATH,N);


 getchar();
}

/*****************************/

int Ary2TODouble(int *P, int *Q, int *PP, int *QQ, int *RR)
{
 int CNT=0,I,J,K,M,TEMP,FIRSTOBJ,LASTOBJ, *R, C[NN],DIV[NN];

 R=C;
 while (*P)
   {
    *R = *P * 65536 + *Q;  CNT++;
     R++;
    if (*Q) {*R = *Q * 65536 + *P; CNT++; R++;}
     P++; Q++;
   }

 for (I=0; I<CNT; I++)
  {
   M=C[I]; K=I;
   for (J=I+1; J<CNT; J++) if (C[J]<M) {M=C[J]; K=J;}
   if (K!=I) {TEMP=C[I]; C[I]=C[K]; C[K]=TEMP;}
  }
 R=C;
 for (K=0; K<CNT; K++) {*PP = *R/65536; *QQ = *R%65536; PP++; QQ++; R++;}
 *PP=*QQ=0; K=CNT;

 PP--; K--;  LASTOBJ=*PP;

/* printf("*PP=%d\n",*PP); */
 QQ = PP; QQ--;
 while (K) {{if (*PP != *QQ) DIV[*PP] = K;  K--;} PP--; QQ--;}

 FIRSTOBJ=*PP;
 
 DIV[FIRSTOBJ]=K;

 /* printf("*PP=%d\n",*PP);
 for (K=1; K<=LASTOBJ; K++) printf("%d %d   ",K,DIV[K]); puts("\n"); */

 R=DIV;
 for (K=FIRSTOBJ; K<=LASTOBJ; K++) {RR++; R++; *RR=*R;}

 return CNT;
}

/******************** Graph in single array form *************************/

void TOGRAPH(int *P, int *Q, int N, int *R)
 {
  int I,K,X,*RSAV;

 RSAV=R;
 for (I=0; I<NN; I++) {*R=0; R++;}
 R=RSAV;

 P[N]=Q[N]=K=0;


 X=*P; R++;
 while (X)
  {
   *R=-X; R++; K++;
   while (X==*P) {if (*Q) {*R=*Q; K++; R++;} Q++; P++;}
   X=*P;
  }
                               
 R++; *R=0;  *RSAV=K;
 return;
}

/*********************  Paths to visit all objects  *************/

int VISITALLOBJ(int *FA,int *PATH)
{
 int H,I,J,K,Nint,Nobj,CNT=0,
               VISITED[MAXOBJ],
               NEGOBJ[MAXOBJ],
               NUMPOS[MAXOBJ],
               STARTPATH[MAXOBJ];

 Nint=FA[0];
 for (K=0; K<MAXOBJ; K++)
   VISITED[K]=NEGOBJ[K]=NUMPOS[MAXOBJ]=STARTPATH[MAXOBJ]=0;

 for (K=1; K<=Nint; K++) if (FA[K]<0) {NEGOBJ[-FA[K]]=K; CNT++;}
 Nobj = CNT;

 puts("\n\n");
 for (K=1; K<=Nobj; K++) printf("%d %d, ",NEGOBJ[K],K);   
 puts("\n");

 for (K=1; K<=Nobj; K++)
  {
   I=NEGOBJ[K]+1;     /* get number CNT of positive numbers (neighbors) */
   CNT=0; while (FA[I]>0) {CNT++; I++;}  NUMPOS[K]=CNT;

   I=NEGOBJ[K]+1;     /* reverse order of positive numbers */
   for (J=CNT; J>0; J--) {PATH[J]=FA[I]; I++;}    /* temp buff use of PATH */
   I=NEGOBJ[K]+1;
   for (J=1; J<=CNT; J++) {FA[I]=PATH[J]; I++;}
  }
  puts("NUMPOS");
 for (K=1; K<=Nobj; K++) printf("%d %d,  ",K,NUMPOS[K]);
 puts("\n");


 for (K=1; K<=Nint; K++) {if (FA[K]<0) printf("  "); printf("%d,",FA[K]);}
 puts("\n");


 for (I=0; I<NN; I++) PATH[I]=0;

 I=-1;

 /************ start path in new component *********/
NEWCOMP:
 I++; PATH[I]=0;  /* I = index of array PATH; Object 0 separates components */
 K=0;                                      /* K int-name of objects */
 for (J=Nobj; J>0; J--) if (!VISITED[J]) K=J;   /* Here J = int-names */
 if (!K) {I++; PATH[I]=0; return I;}

 I++; PATH[I]=K;

 VISITED[K]=K;
LP1:
 if (!NUMPOS[K]) goto BACKPATH;     /* K has no more unvisited neighbors */
LP2:
               /* seek a posnum object J (neighbor of K) not yet visited */
 J=FA[NEGOBJ[K]+NUMPOS[K]]; NUMPOS[K]--;
 if (VISITED[J]) goto LP1;               /* neighbor J has been visited */
 K=J; VISITED[J]=J; I++; PATH[I]=K;     /* put neighbor J on PATH as K */

BACKPATH:
 H=J=I;                               /* J = index on PATH */
 while (!NUMPOS[PATH[J]]) {H++; PATH[H]=-PATH[J];  if (!PATH[J]) goto NEWCOMP; J--;}
 K=PATH[J]; goto LP2;

}

/******************* Simple Sort of int-nums in Component *********************/

void SSORT(int *P,int N)
{
 int H,I,J,K,L,M,TEMP,COMPNUM=0,ZEROCNT=0,   *PSAV,         COMPONENT[NN];


 PSAV=P;
 for (H=1; H<N; H++) {if (!*P) ZEROCNT++;  P++;}

 /* printf("\nNumber of zeros = %d\n",ZEROCNT); */

 P=PSAV;

 for (H=1; H<=ZEROCNT; H++)
  {
   I=1;  P++;
   while (*P) {COMPONENT[I]=*P; I++;P++;}  L=I;

   for (I=1; I<L; I++)
    {
     M=COMPONENT[I]; K=I;
     for (J=I+1; J<L; J++) if (COMPONENT[J]<M) {K=J; M=COMPONENT[J];}
     if (K!=I) {TEMP=M; COMPONENT[K]=COMPONENT[I]; COMPONENT[I]=TEMP;}
    }
   COMPNUM++; printf("Component #%d   ",COMPNUM);
   for (I=1; I<L; I++) printf("%d ",COMPONENT[I]); puts("");
  }

 return;
}