/* ************************************************************************************ If we limit the maximal possible length of an input string from UNSIGNED LONG MAX to LONG MAX (for a 32-bit long it is 2 147 483 647) we can virtualize CMember over Gap, GNext, GPrev memory required: 13*N*integers **************************************************************************************/ #include #include #include // compilation control -- comment out the undesirable, while uncomment the desirable #define _show_string //#define _output_runs // takes precedence over _show_runs #define _show_runs #define _count_runs /* ************************************************************************************* */ #ifdef _output_runs #undef _show_runs #endif #ifdef _output_runs #ifdef _count_runs #define _output_count_runs #undef _output_runs #undef _count_runs #endif #endif char* S; typedef unsigned long ulong; ulong null; ulong N, N_1; #define setCMember(e,c) setCMember1(e,c,Gap,GNext,GPrev) void setCMember1(ulong e,ulong c,long* Gap,long* GNext,long* GPrev) { if (Gap[e] == null || Gap[e] < 0) if (c == null) Gap[e] = null; else Gap[e] = 0-1-c; else if (c == null) GNext[GPrev[Gap[e]]] = null; else GNext[GPrev[Gap[e]]] = 0-1-c; } #define getCMember(e) getCMember1(e,Gap,GNext,GPrev) ulong getCMember1(ulong e,long* Gap,long* GNext,long* GPrev) { if (Gap[e]==null) return null; else if (Gap[e] < 0) return 0-1-Gap[e]; else if (GNext[GPrev[Gap[e]]] == null) return null; else return 0-1-GNext[GPrev[Gap[e]]]; } #define CEnd(s) CPrev[CStart[s]] #define CSize(s) CNext[CPrev[CStart[s]]] #define GMember(p) ((getCMember(p)==null)?(null):((CStart[getCMember(p)]==p)?(null):(p-CPrev[p]))) #define F1(f) FStart[f] #define F2(f) ((F1(f)==null)?(null):((FPrev[F1(f)]==F1(f))?(null):((FNext[F1(f)])))) #define F3(f) ((F2(f)==null)?(null):((FPrev[F1(f)]==F2(f))?(null):((FNext[F2(f)])))) #define FBig(f) ((F2(f)==null)?(F1(f)):((CSize(F1(f))>CSize(F2(f)))?(F1(f)):(F2(f)))) #define CEmptyPop() CEmptyPop1(CEmpty,CEmptyTop,ScFirst,ScLast) inline ulong CEmptyPop1(ulong* CEmpty,ulong& CEmptyTop,ulong ScFirst,ulong ScLast) { if (CEmptyTop==null) return null; else return CEmpty[CEmptyTop++]; } #define CEmptyPush(a) CEmptyPush1(a,CEmpty,CEmptyTop,ScFirst) inline void CEmptyPush1(ulong a,ulong* CEmpty,ulong& CEmptyTop,ulong ScFirst) { CEmptyTop--; if (CEmptyTop <= ScFirst && ScFirst != null) { printf("CEmptyPush error\n"); getchar(); } CEmpty[CEmptyTop]=a; } #define FStartPop() FStartPop1(FStart,FStartTop) ulong FStartPop1(ulong* FStart,ulong& FStartTop) { ulong x; if (FStartTop==null) return null; else{ x = FStart[FStartTop]; if (FStartTop==0) FStartTop=null; else FStartTop--; return x; } } #define FStartPush(a) FStartPush1(a,FStart,FStartTop) inline void FStartPush1(ulong a,ulong* FStart,ulong& FStartTop) { if (FStartTop==null) FStart[FStartTop=0]=a; else FStart[++FStartTop]=a; } #define RStackPop() RStackPop1(RStack,RStackTop) inline ulong RStackPop1(ulong* RStack,ulong& RStackTop) { ulong x; if (RStackTop==null) return null; else{ x = RStack[RStackTop]; if (RStackTop==0) RStackTop=null; else RStackTop--; return x; } } #define RStackPush(a) RStackPush1(a,RStack,RStackTop) inline void RStackPush1(ulong a,ulong* RStack,ulong& RStackTop) { if (RStackTop==null) RStack[RStackTop=0]=a; else RStack[++RStackTop]=a; } #define SelIn(a) SelIn1(a,Sel,SelFirst,SelLast) inline void SelIn1(ulong a,ulong* Sel,ulong& SelFirst,ulong& SelLast) { if (SelLast==null) Sel[SelFirst=SelLast=0]=a; else Sel[++SelLast]=a; } #define SelOut() SelOut1(Sel,SelFirst,SelLast) inline ulong SelOut1(ulong* Sel,ulong& SelFirst,ulong& SelLast) { ulong x; if (SelFirst==null) return null; else{ x = Sel[SelFirst]; if (SelFirst==SelLast) SelFirst=SelLast=null; else SelFirst++; return x; } } #define ScIn(a) ScIn1(a,Sc,ScFirst,ScLast,CEmptyTop) void ScIn1(ulong a,ulong* Sc, ulong& ScFirst,ulong& ScLast,ulong CEmptyTop) { // note that we "loud" Sc in the wrong order, it is assumed that // after Sc is completely loaded, the conents are reversed if (ScFirst==null) Sc[ScFirst=ScLast=0] = a; else{ ScFirst++; Sc[ScFirst]=a; } if (ScFirst >= CEmptyTop) { printf("ScIn error\n"); getchar(); } } #define Reverse() Reverse1(Sc,ScFirst,ScLast) void Reverse1(ulong* Sc,ulong ScFirst,ulong ScLast) { ulong l, r, x; if (ScFirst == ScLast) return; l = ScLast; r = ScFirst; while(l < r) { x = Sc[l]; Sc[l] = Sc[r]; Sc[r] = x; l++; r--; } } #define ScOut() ScOut1(Sc,ScFirst,ScLast) ulong ScOut1(ulong* Sc,ulong& ScFirst, ulong& ScLast) { ulong x; if (ScFirst==null) return null; else if (ScFirst==ScLast) { x = Sc[ScFirst]; ScFirst=ScLast=null; return x; }else{ x = Sc[ScFirst]; ScFirst--; return x; } } #define FEnd(f) FPrev[FStart[f]] #define FMember(c) FMember1(c,FStart,FStartTop,FNext,FPrev) ulong& FMember1(ulong c,ulong* FStart,ulong FStartTop,ulong* FNext,ulong* FPrev) { if (FStartTop==null) return FStart[c]; else if (c <= FStartTop) return FNext[FPrev[FStart[c]]]; else return FStart[c]; } class CROCH { private: ulong *block; ulong block_size; long number_of_classes; ulong* CStart; // 1 ulong* CNext; // 2 ulong* CPrev; // 3 ulong* CEmpty; // 4 ulong CEmptyTop; ulong* FStart; // 5 ulong FStartTop; ulong* FNext; // 6 ulong* FPrev; // 7 ulong* Refine; // 8 ulong* RStack; // 9 ulong RStackTop; ulong* Sel; // 10 ulong SelFirst, SelLast; ulong* Sc; ulong ScFirst, ScLast; long* Gap; // 11 long* GNext; // 12 long* GPrev; // 13 public: CROCH() { block=0; block_size=0; number_of_classes = 0; } /* ********************************************************************************** * auxiliary methods * ************************************************************************************ */ #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) void showGap(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"); } void showCMember(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); } } } 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(long 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,"\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 // method Process --------------------------------------------------------------------- // process the input string ulong Process(char* string,FILE* fp=stdout) { ulong L; bool done; ulong count=0; ulong n = strlen(string); init(n); #ifdef _show_string showString(string,N); #endif L = 1; done = Level_1(string); #ifdef _show_count_runs count += traceRuns(string,1,fp,1); #endif #ifdef _output_count_runs count += traceRuns(0,L,fp,1); #endif #ifdef _show_runs traceRuns(string,L,fp,1); #endif #ifdef _output_runs traceRuns(0,L,fp,1); #endif #ifdef _count_runs count += traceRuns(0,L,fp,0); #endif while(!done) { L++; done = Level(L); #ifdef _show_count_runs count += traceRuns(string,1,fp,1); #endif #ifdef _output_count_runs count += traceRuns(0,L,fp,1); #endif #ifdef _show_runs traceRuns(string,L,fp,1); #endif #ifdef _output_runs traceRuns(0,L,fp,1); #endif #ifdef _count_runs count += traceRuns(0,L,fp,0); #endif } fprintf(fp,"\n\nnumber of runs: %u\n",count); return count; }//end Process // method init ------------------------------------------------------------------------ // allocate space and initilaize it void init(ulong n) { N=null=n; N_1=N-1; ulong size = 13*sizeof(ulong)*N; if (block_size < size) { if (block_size > 0) delete[] block; block_size=size; block = new ulong[block_size]; } for(ulong i=0; i < block_size; block[i++]=null); CStart = block; CNext = CStart+N; CPrev = CNext+N; CEmpty = CPrev+N; CEmptyTop = null; FStart = CEmpty+N; FStartTop = null; FNext = FStart+N; FPrev = FNext+N; Refine = FPrev+N; RStack = Refine+N; RStackTop = null; Sel = RStack+N; SelFirst = SelLast = null; Sc = CEmpty; ScFirst = ScLast = null; Gap = (long*) Sel+N; GNext = Gap+N; GPrev = GNext+N; // all classes are empty for(ulong i=N_1; ; i--) { CEmptyPush(i); if (i == 0) break; } number_of_classes = 0; }//end init /* ********************************************************************************** * family handling methods * ************************************************************************************ */ // method showFamily ------------------------------------------------------------------- void showFamily(ulong f,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 showFamily // method showFamilies ----------------------------------------------------------------- void showFamilies(FILE *fp=stdout) { ulong f; bool empty; fprintf(fp,"families: "); for(empty = true, f = 0; f <= FStartTop; f++) { if (FStart[f] != null) { showFamily(f,fp); fprintf(fp," "); empty = false; } } if (empty) fprintf(fp,"\n"); else fprintf(fp,"\n"); }//end showFamilies // method showSeeds -------------------------------------------------------------------- void showSeeds(FILE *fp=stdout) { ulong f; bool empty; fprintf(fp,"seeds\n"); for(empty = true, f = 0; f <= FStartTop; f++) { if (FStart[f] != null) { showFamily(f,fp); fprintf(fp," "); empty = false; } } if (empty) fprintf(fp,"\n"); else fprintf(fp,"\n"); }//end showSeeds // method IT_Families ------------------------------------------------------------------- // test integrity of families bool IT_Families(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)) { bad = true; fprintf(fp,"families %u and %u not disjoint\n",f,f1); showFamily(f,fp); fprintf(fp,"\n"); showFamily(f1,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_Families // method startFamily ------------------------------------------------------------------- ulong startFamily(ulong c) { ulong f; if (FStartTop == null) // save FMember value f = FStart[FStartTop = 0]; else f = FStart[++FStartTop]; FStart[FStartTop] = c; FNext[c] = f; // restore FMember FPrev[c] = c; // set FEnd return FStartTop; }//end startFamily // method addToFamily ------------------------------------------------------------------- // add class c to family f, always as a second element void addToFamily(ulong c,ulong f) { ulong f1, f2, f3; // if size of c > size of F2(f), we make c F2(f) // otherwise we make c F3(f) FMember(c) = f; if (FPrev[FStart[f]] == FStart[f]) { // singleton family, so c will become F2(f) f1 = FMember(f); // save FMember FNext[FStart[f]] = c; FPrev[c] = FStart[f]; FEnd(f) = c; // set FEnd FMember(f) = f1; // restore FMember }else{ if (CSize(c) > CSize(F2(f))) { // c will become F2(f) and F2(f) will become F3(f) f1 = F2(f); // save F2 f2 = FPrev[FStart[f]]; // save end f3 = FMember(f); // save FMember FNext[F1(f)] = c; FNext[c] = f1; if (f1 != null) FPrev[f1] = c; FPrev[c] = F1(f); FEnd(f) = f2; // reset end FMember(f) = f3; // restore FMember }else{ // c will become F3(f) f1 = F3(f); // save F3 if (FEnd(f)==F2(f)) // determine and save end f2 = c; else f2 = FEnd(f); f3 = FMember(f); // save FMember FNext[F2(f)] = c; FNext[c] = f1; if (f1 != null) FPrev[f1] = c; FPrev[c] = F2(f); FEnd(f) = f2; // reset end FMember(f) = f3; // restore FMember } } }//end addToFamily // method isinF ------------------------------------------------------------------------- // returns true if class e belongs to family f bool isinF(ulong e,ulong f) { 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 /* *********************************************************************************** * class handling methods * ************************************************************************************* */ // method showClass --------------------------------------------------------------------- void showClass(ulong i,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 showClass // method showClasses ------------------------------------------------------------------ void showClasses(FILE *fp=stdout) { ulong i; bool empty; fprintf(fp,"classes: "); for(empty = true, i = 0; i < N; i++) { if (CStart[i] == null) continue; showClass(i,fp); empty = false; fprintf(fp," "); } if (empty) fprintf(fp,"\n"); else fprintf(fp,"\n"); }//end showClasses // method isinC ------------------------------------------------------------------------- // returns true if element e belongs to class c bool isinC(ulong e,ulong c) { 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 e; for(e = CStart[c1]; ; e = CNext[e]) { if (isinC(e,c2)) return false; if (e == CEnd(c1)) break; } return true; }//end disjointC // method disjointF -------------------------------------------------------------------- // returns true if f1 and f2 are disjoint families bool disjointF(ulong f1,ulong f2) { ulong e; for(e = FStart[f1]; ; e = FNext[e]) { if (isinF(e,f2)) return false; if (e == FEnd(f1)) break; } return true; }//end disjointF // method IT_Classes -------------------------------------------------------------------- bool IT_Classes(char* string,ulong L,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)) { bad = true; fprintf(fp,"classes %u and %u are not disjoint\n",i,j); showClass(i,fp); fprintf(fp,"\n"); showClass(j,fp); fprintf(fp,"\n"); } } } //if (! bad) // fprintf(fp,"classes passed integrity test\n"); return ! bad; }//end IT_Classes // method showEmptyClasses -------------------------------------------------------------- void showEmptyClasses(FILE *fp=stdout) { ulong i, top; fprintf(fp,"empty classes: "); top = CEmptyTop; // so we can restore it if (CEmptyTop==null) { fprintf(fp,"\n"); return; } while((i = CEmptyPop()) != null) fprintf(fp,"%u ",i); fprintf(fp,"\n"); CEmptyTop = top; // restore CEmptyTop }//end showEmptyClasses // method showCEmpty ------------------------------------------------------------------- void showCEmpty(FILE* fp=stdout) { ulong i; if ((i = CEmptyTop) == null) { fprintf(fp,"CEmpty: \n"); return; } fprintf(fp,"CEmpty: top-down \n"); }//end showCEmpty // method showSc --------------------------------------------------------------------- void showSc(FILE* fp=stdout) { ulong s; if ((s = ScFirst) == null) { fprintf(fp,"Sc: \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"); } // method showShowSmallClasses ---------------------------------------------------------- void showSmallClasses(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 showClass(FStart[f],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; showClass(c,fp); fprintf(fp," "); if (c == FEnd(f)) break; } } if (empty) fprintf(fp,"\n"); else fprintf(fp,"\n"); }//end showSmallClasses // method startNewClass ----------------------------------------------------------------- // element e is put to a new class as a part of family f ulong startNewClass(ulong e,ulong f) { ulong c = CEmptyPop(); // take first available empty class CStart[c] = e; CPrev[e] = e; // set CEnd() CNext[e] = 1; // set CSize() setCMember(e,c); if (f != null) addToFamily(c,f); return c; }//end startNewClass // method addToNewClass ----------------------------------------------------------------- // element e is added to a new class c void addToNewClass(ulong e, ulong c, ulong f) { ulong l, r, f1, f2; ulong xend, xsize; // since the original parent mught have vanished, it is possible // that c == F1(f), in which case we leave it in place xend = CEnd(c); xsize = CSize(c)+1; if (F1(f) != c) { if (F2(f) != c) { if (xsize > CSize(F2(f))) { // must move c to be F2(f) f1 = FEnd(f); // save new FEnd if (f1 == c) f1 = FPrev[c]; f2 = FMember(f); // save FMember if (c == FStart[f]) l = null; else l = FPrev[c]; // save left neighbour if (c == FEnd(f)) r = null; else r = FNext[c]; // save right neighbour FNext[c]=FPrev[c]=null; // unlink c if (l != null) FNext[l] = r; // mend the hole if (r != null) FPrev[r] = l; // mend the hole l = F2(f); FNext[F1(f)] = c; FNext[c] = l; if (l != null) FPrev[l] = c; FPrev[c] = F1(f); FEnd(f) = f1; // restore FEnd FMember(f) = f2; // restore FMember } } } CNext[xend] = e; CPrev[e] = xend; CEnd(c) = e; // set CEnd() CSize(c) = xsize; // set CSize() setCMember(e,c); // now we have to add it to Gap insertGap(e,e-CPrev[e]); }//end addToNewClass // method removeFromClass ---------------------------------------------------------------- // element e is removed from an existing class void removeFromClass(ulong e) { ulong e1, e2, c, f, f1, f2, f3, right, rgap, egap; ulong cend, csize; ulong gend; long cmember; c = getCMember(e); cend = CEnd(c); csize = CSize(c); if (e == cend) right = null; else{ right = CNext[e]; rgap = right-CPrev[right]; } if (e == CStart[c]) egap = null; else egap = e-CPrev[e]; setCMember(e,null); // removing e from class c csize--; // class c shrinks if (csize == 0) { // class vanishes, must be removed from family, since // it shrinks, it must be the first in the family f = FMember(c); if (f != null) { if (c != F1(f)) { printf("removeFromClass error\n"); exit(1); } f1 = F2(f); // save second guy in family f2 = FEnd(f); // save FEnd f3 = FMember(f); // save FMember FStart[f] = f1; FNext[c]=FPrev[c]=null; FEnd(f) = f2; // restore FEnd FMember(f) = f3; // restore FMember FMember(c) = null; } CNext[CStart[c]] = CPrev[CStart[c]] = null; setCMember(CStart[c],null); // this sets CEnd() and CSize() CStart[c] = null; CEmptyPush(c); number_of_classes--; }else{ if (CStart[c] == e) { // removing first element in the class CStart[c] = CNext[e]; setCMember(e,null); CEnd(c) = cend; CSize(c) = csize; CPrev[e] = CNext[e] = null; }else if (CEnd(c) == e) { // removing last element setCMember(e,null); CEnd(c) = CPrev[cend]; CSize(c) = csize; CPrev[e] = CNext[e] = null; }else{ // removing middle element setCMember(e,null); e1 = CPrev[e]; e2 = CNext[e]; CNext[e1] = e2; CPrev[e2] = e1; // CEnd(c) = cend; CSize(c) = csize; CNext[e] = CPrev[e] = null; } } // now we have to remove e it from Gap, if it is there if (egap != null) { if (Gap[egap] == e) { // e is the first in Gap if (GPrev[e] == e) { // the list is {e} cmember = GNext[e]; // save CMember value GNext[e] = GPrev[e] = null; Gap[egap] = cmember; }else{ gend = GPrev[Gap[egap]]; cmember = GNext[gend]; Gap[egap] = GNext[e]; GNext[e] = GPrev[e] = null; GPrev[Gap[egap]] = gend; GNext[gend] = cmember; } }else if (GPrev[Gap[egap]] == e) { // e is the last in Gap gend = GPrev[e]; // e has previous, otherwise e would be the first as well cmember = GNext[e]; GPrev[Gap[egap]] = gend; GNext[gend] = cmember; GNext[e] = GPrev[e] = null; }else{ // e is in the middle of Gap GNext[GPrev[e]] = GNext[e]; GPrev[GNext[e]] = GPrev[e]; GNext[e] = GPrev[e] = null; } } // now we have to update gap for the right neighbour if (right != null) { if (rgap != null) removeGap(right,rgap); if ((rgap = GMember(right)) != null) { insertGap(right,rgap); } } }//end RemoveFromClas /* *********************************************************************************** * snapshot handling methods * ************************************************************************************* */ // method showSnapshot ------------------------------------------------------------------ void showSnapshot(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 showSnapshot // method createSnapshot ----------------------------------------------------------------- bool createSnapshot(ulong L) { // Create snapshot from current level for level L // parent-seed new families ulong f, c, c1, big, e, s; ulong maxd, x; // at this point RStack is not needed, we use it to seed new families RStackTop = null; for(f = 0; f <= FStartTop; f++) { // traverse all families // nullify the links, also delete all FMemebrs[c] for c <= FStartTops FNext[FPrev[FStart[f]]] = null; FPrev[FStart[f]] = null; c = FStart[f]; if (FNext[c] == null) { // *** singleton family, so no need to do snapshot if (CSize(c) == 1) { // ** singleton family of a singleton class // this does not go to the snapshot, so can push it onto CEmpty CPrev[CStart[c]] = CNext[CStart[c]] = null; setCMember(CStart[c],null); // this sets CEnd() and CSize() CStart[c] = null; CEmptyPush(c); if (c > FStartTop) FMember(c) = null; }else{ // ** singleton family of a thick class RStackPush(c); // make seed if (c > FStartTop) FMember(c) = null; } }else{ // *** thick family, so must choose small ones // determine big class big = FBig(f); while(c != null) { // traverse the family if (CSize(c) == 1) { // singleton class if (c == big) { // this does not go into snapshot, so we can push it onto CEmpty CPrev[CStart[c]] = CNext[CStart[c]] = null; setCMember(CStart[c],null); CStart[c] = null; // remove the class CEmptyPush(c); // do not put in snapshot as it is big }else{ SelIn(CStart[c]); // put in snapshot ScIn(CStart[c]); } }else{ // thick class RStackPush(c); // make seed if (c != big) { // put in snapshot for(e = CStart[c]; ; e = CNext[e]) { SelIn(e); if (e == CEnd(c)) break; } ScIn(e); } } c1 = FNext[c]; FNext[c] = FPrev[c] = null; // remove from family if (c > FStartTop) FMember(c) = null; c = c1; }//endwhile }// end of singleton / thick family FStart[f] = null; // remove family }//endfor // now we have to reverse Sc Reverse(); // at this point, FStart[], FNext[] and FPrev[] ought to be empty FStartTop = null; // now all seeds are in RStack if (RStackTop == null) return true; // to indicate done // seed the families and decide if we need to continue; maxd = 0; while((c = RStackPop()) != null) { if ((x = CEnd(c) - CStart[c]) > maxd) maxd = x; if (FStartTop==null) FStartTop=0; else FStartTop++; s = FStart[FStartTop]; // save FMember[FStartTop] if any FStart[FStartTop] = c; FEnd(FStartTop) = c; // set FEnd FMember(FStartTop) = s; // restore FMember[FSTartTop] FMember(c) = FStartTop; // set FMemebr(c) } if (maxd < L) return true; // to indicate done return false; // to indicate not done }//end createSnapshott /* ************************************************************************************ * Gap handling methods * ************************************************************************************** */ // method showGaps ---------------------------------------------------------------------- void showGaps(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 showGaps // method insertGap --------------------------------------------------------------------- void insertGap(ulong p,ulong g) { // insert position p into Gap g long c, gend, cmember; if (Gap[g]==null) { // nothing stored in Gap[g] Gap[g]=p; GPrev[p]=p; // set GEnd GNext[p]=null; // set CMember }else if (Gap[g] < 0) { // Gap[g] contains CMember cmember = Gap[g]; // save CMember Gap[g] = p; // store p in Gap[g] GPrev[p] = p; // set GEnd GNext[p] = cmember; }else{ // Gap[g] contains gap gend = GPrev[Gap[g]]; c = Gap[g]; Gap[g] = p; GPrev[p] = gend; GNext[p] = c; GPrev[c] = p; } }//end insertGap // method removeGap -------------------------------------------------------------------- void removeGap(ulong p,ulong g) { // remove position p from Gap g long gend, cmember; if (Gap[g] == p) { // p is first if (GPrev[p] == p) { // gap is {p} cmember = GNext[p]; Gap[g]=cmember; GNext[p] = GPrev[p] = null; }else{ // gap is {p, ...} gend = GPrev[p]; cmember = GNext[gend]; Gap[g] = GNext[p]; GPrev[Gap[g]] = gend; GNext[gend] = cmember; GPrev[p] = GNext[p] = null; } }else if (GPrev[Gap[g]] == p) { // p is last gend = p; cmember = GNext[gend]; gend = GPrev[gend]; GPrev[Gap[g]] = gend; GNext[gend] = cmember; GPrev[p] = GNext[p] = null; }else{ // p in the middle GNext[GPrev[p]]=GNext[p]; GPrev[GNext[p]]=GPrev[p]; GNext[p]=GPrev[p]=null; } }//end removeGap // method IT_Gaps ------------------------------------------------------------------- // integrity test of Gaps bool IT_Gaps(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_Gaps /* ********************************************************************************** * Refine handling methods * ************************************************************************************ */ // method cleanRefine --------------------------------------------------------------- void cleanRefine() { ulong c; while((c = RStackPop()) != null) Refine[c] = null; }//end cleanRefine /* ********************************************************************************** * level handling methods * ************************************************************************************ */ // method Level_1 ---------------------------------------------------------------------- bool Level_1(char* string) { ulong i, j, c, c1, last, s, xend, xsize; ulong count; // count singletons on level 0 // on level 0 we do not list the implicit singleton class {N} // and for the snapshot we consider all classes small and {N} big for(i = 0; i < N; i++) { c = find(string[i]); // position i goes to class c if (CStart[c] == null) { // class c does not exist yet CStart[c] = i; CPrev[i] = i; // set CEnd() CNext[i] = 1; // set CStart() setCMember(i,c); c1 = CEmptyPop(); number_of_classes++; }else{ // class c already exists xend = CEnd(c); xsize = CSize(c); CNext[xend] = i; CPrev[i] = xend; xend = i; CNext[xend] = xsize+1; // set CSize() CPrev[CStart[c]] = xend; // set CEnd() setCMember(i,c); insertGap(i,i-CPrev[i]); } } //clean up Sel[0]=null; // was used by find() for(i = 0; i < N; i++) // were used by find FStart[i]=FNext[i]=FPrev[i]=null; // create a snapshot of small classes, all classes are small // and seed families and count singletons count = 0; for(i = 0; i < N; i++) { if (CStart[i] == null) continue; last = j = CStart[i]; for(j = CStart[i]; j != CEnd(i); j = CNext[j]) SelIn(j); SelIn(j); ScIn(j); if (CSize(i) == 1) { // singleton class cannot be removed, no room in Sc count++; }else{ // make parent seed if (FStartTop==null) // save FMember and move FStartTop s = FStart[FStartTop=0]; else s = FStart[++FStartTop]; FStart[FStartTop] = i; FPrev[i] = i; // set FEnd FNext[i] = s; // restore FMember FMember(i) = FStartTop; } }//endfor // now we have to reverse Sc Reverse(); if (count == N) // all small classes were singletons, hence all done return true; return false; }//end Level_1 // method Level -------------------------------------------------------------------- // used to create levels 1 and up bool Level(ulong L) { ulong s, e, e1, c, d, f, ssize; bool done; ssize = 0; while((s = ScOut()) != null) { if (s == 0) { // then the small class is {0} e = SelOut(); c = getCMember(e); // now we have room in CEmpty, so we can remove this class CPrev[e] = CNext[e] = null; setCMember(e,null); CStart[c] = null; CEmptyPush(c); number_of_classes--; continue; } while(true) { e = SelOut(); // element of the snapshot of a small class ssize++; if (e == 0) if (e == s) { if (ssize == 1) { // remove singleton small class // this makes room for CEmptyPush c = getCMember(s); if (c != null) { CNext[s] = CPrev[s] = null; setCMember(s,null); CStart[c] = null; CEmptyPush(c); number_of_classes--; } } cleanRefine(); ssize = 0; break; }else continue; e1 = e-1; c = getCMember(e1); // e1 is a member of class c if (c == null) { if (e == s) { if (ssize == 1) { // remove singleton small class c = getCMember(s); if (c != null) { CPrev[s] = CNext[s] = null; setCMember(s,null); CStart[c] = null; CEmptyPush(c); number_of_classes--; } } cleanRefine(); ssize = 0; break; }else continue; } f = FMember(c); // family seeded by c removeFromClass(e1); if (Refine[c] == null) { // no destination yet for class c RStackPush(c); Refine[c] = startNewClass(e1,f); number_of_classes++; }else{ // there is destination for class c d = Refine[c]; // d is the destination for c addToNewClass(e1,d,f); } if (e == s) { cleanRefine(); ssize = 0; break; } }//endwhile }//endwhile if (number_of_classes == 0) done = true; else done = createSnapshot(L+1); return done; }//end Level /* *********************************************************************************** * maximal repetitions handling methods * ************************************************************************************* */ // method traceMaxRep ------------------------------------------------------------------- void traceMaxRep(ulong g,ulong p,ulong& first,ulong& last) { ulong q, c; first = last = p; RStackPush(p); Refine[p]=1; c = getCMember(first); // p being in Gap must have a prev and must be // a member of a class for(q = CPrev[first]; q != CStart[c]; q = CPrev[q]) { if ((first-q) == g) { first = q; if (GMember(first) != null) { RStackPush(first); Refine[first]=1; } }else break; }//endfor if ((first-q) == g) { first = q; if (GMember(first) != null) { RStackPush(first); Refine[first]=1; } } // so we have first if (last != CEnd(c)) { for(q = CNext[last]; q != CEnd(c); q = CNext[q]) { if ((q-last) == g) { last = q; if (GMember(last) != null) { RStackPush(last); Refine[last]=1; } }else break; }//endfor if ((q-last) == g) { last = q; if (GMember(last) != null) { RStackPush(last); Refine[last]=1; } } } // so we have position of the last occurrence of the generator last = last+g-1; // last position }//end traceMaxRep // method showMaxReps ----------------------------------------------------------------------- void showMaxReps(ulong g,FILE* fp=stdout) { ulong p, first, last; // we use RStack+Refine to indicate if we already visited it for(p = Gap[g]; p != null; p = GNext[p]) { if (Refine[p]!=null) continue; traceMaxRep(g,p,first,last); showMaxRep(first,g,(last-first)/g,fp); }//endfor cleanRefine(); }//end showMaxReps // method showMaxReps ------------------------------------------------------------------- void showMaxReps(char* string,ulong g,FILE* fp=stdout) { ulong p, first, last; // we use RStack+Refine to indicate if we already visited it for(p = Gap[g]; p != null; p = GNext[p]) { if (Refine[p]!=null) continue; traceMaxRep(g,p,first,last); showMaxRep(string,first,g,(last-first+1)/g,fp); }//endfor cleanRefine(); }//end showMaxReps // method showMaxRep ---------------------------------------------------------------- void showMaxRep(ulong s,ulong p,ulong e,FILE* fp) { fprintf(fp,"(%u,%u,%u)\n",s,p,e); } // method showMaxRep ---------------------------------------------------------------- void showMaxRep(char* string,ulong s,ulong p,ulong e,FILE* fp) { ulong i, j, k; bool toggle = false; for(i = 0; i < s; i++) fputc('.',fp); for(j = 0; j < e; j++) { if (toggle) toggle=false; else toggle=true; for(k = 0; k < p; k++) { if (toggle) fputc(string[i++],fp); else fputc(string[i++]-'a'+'A',fp); }//endfor }//endfor for( ; i < N; i++) fputc('.',fp); fputc('\n',fp); }//end showMaxRep // method countMaxR---------------------------------------------------------------------- ulong countMaxReps(ulong g) { ulong p, first, last; ulong count = 0; // we use RStack+Refine to indicate if we already visited it for(p = Gap[g]; p != null; p = GNext[p]) { if (Refine[p]!=null) continue; traceMaxRep(g,p,first,last); count++; }//endfor cleanRefine(); return count; }//end countMaxReps /* ********************************************************************************** * runs handling methods * ************************************************************************************ */ // method traceRuns ------------------------------------------------------------------ ulong traceRuns(char* string,ulong g,FILE* fp,bool _show) { ulong p, first, last, fi, la, x; ulong count = 0; if (g > N/2) return 0; if (Gap[g] == null || Gap[g] < 0) return 0; // we use RStack+Refine to indicate if we already visited it for(p = Gap[g]; ; p = GNext[p]) { if (Refine[p]!= null) if (p == GPrev[Gap[g]]) break; else continue; // already done traceMaxRep(g,p,first,last); // so we have the first and the last occurrence of the max repeat // we have to check if we can shift left or right // first check left shift while(first > 0) { fi = first-1+g; if (GMember(fi) == g) { // so we can shift left traceMaxRep(g,fi,first,x); continue; }else break; }//endwhile // then check right shift while(last < N_1) { la = last+2-g; if (GMember(la) == g) { // so we can shift right traceMaxRep(g,la,x,last); continue; }else break; }//endwhile count++; if (_show) if (string == 0) outputRun(first,g,(last-first+1)/g,(last-first+1)%g); else showRun(string,first,g,(last-first+1)/g,(last-first+1)%g); if (p == GPrev[Gap[g]]) break; }//end for cleanRefine(); return count; }//end traceRuns // method outputRun ------------------------------------------------------------------ void outputRun(ulong s,ulong p,ulong e,ulong t,FILE* fp=stdout) { fprintf(fp,"(%u,%u,%u,%u)\n",s,p,e,t); } // method showRun ------------------------------------------------------------------ void showRun(char* string,ulong s,ulong p,ulong e,ulong t,FILE* fp=stdout) { ulong i, j, k; bool toggle = false; for(i = 0; i < s; i++) fputc('.',fp); for(j = 0; j < e; j++) { if (toggle) toggle=false; else toggle=true; for(k = 0; k < p; k++) { if (toggle) fputc(string[i++],fp); else fputc(string[i++]-'a'+'A',fp); }//endfor }//endfor if (toggle) toggle=false; else toggle=true; for(j = 0; j < t; j++) if (toggle) fputc(string[i++],fp); else fputc(string[i++]-'a'+'A',fp); for( ; i < N; i++) fputc('.',fp); fputc('\n',fp); }//end showRun /* *********************************************************************************** * private methods * ************************************************************************************* */ private: // method find ------------------------------------------------------------------------ // it is only used for creation of level 0. // FStart, FNext, FPrev are used to emulate a binary earch tree // to sort out the letters in the input string; SelQu[0] is used // as a static variable to remember the last node used ulong find(char c1) { ulong c = c1; if (Sel[0] == null) { Sel[0] = 0; // root FStart[0] = c; // root FNext[0]=FPrev[0] = null; // children return 0; } ulong n = 0; while(true) { if (c == FStart[n]) return n; // character c belongs to class n if (c < FStart[n]) { // go left if (FPrev[n] == null) { Sel[0]++; FPrev[n] = Sel[0]; FStart[Sel[0]]=c; FNext[Sel[0]]=FPrev[Sel[0]]=null; return Sel[0]; }else{ n = FNext[n]; continue; } }else{ // go right if (FNext[n] == null) { Sel[0]++; FNext[n] = Sel[0]; FStart[Sel[0]] = c; FNext[Sel[0]] = FPrev[Sel[0]] = null; return Sel[0]; }else{ n = FNext[n]; continue; } } } return null; }//end find };//end class CROCH #define _a1 int main() { #ifdef _a1 char string[] = "aaabcaaaaabcaaaabcaaaaabca"; S = string; #endif CROCH c; #ifdef _a1 c.Process(string); #else FILE *fpi; char string[300]; ulong max, i; fpi = fopen("xxx.asc","r"); while(fgets(string,300,fpi) != 0) { for(i = 0; string[i] != ','; i++); string[strlen(string)-1]='\0'; string[i]='\0'; max = atoi(string); S = &string[i+1]; if (c.Process(&string[i+1]) != max) { printf("max should be %d\n",max); break; } printf("\n-----------------------------------------\n"); } #endif return 0; }