/* ************************************************************************************
   CEmpty grows from right-to-left, Sc crosses First and Last, so CEmpty and Sc 
   can share the same memory segment. 

   The removal of singleton small classes was thus deferred to refinement from 
   createSnapshot() (we must remove it from Sc before we push it onto Sc
   The contents of Sc after loading must be reversed!

    memory required: 16*N*integers
 **************************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* S;

typedef unsigned long ulong;
ulong null;
ulong N, N_1;

#define GMember(p) ((CMember[p]==null)?(null):((CStart[CMember[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* CEnd;	// 2
	ulong* CNext;	// 3
	ulong* CPrev;	// 4
	ulong* CMember;	// 5
	ulong* CSize;	// 6
	ulong* CEmpty;	// 7
	ulong CEmptyTop;

	ulong* FStart;	// 8
	ulong FStartTop;
	ulong* FNext;	// 9
	ulong* FPrev;    // 10

	ulong* Refine;	// 11
	ulong* RStack;	// 12
	ulong RStackTop;

	ulong* Sel;   	// 13
	ulong SelFirst, SelLast;
	ulong* Sc;
	ulong ScFirst, ScLast;

	ulong* Gap;		// 14
	ulong* GNext;	// 15
	ulong* GPrev;	// 16

public:
	CROCH() { block=0; block_size=0; number_of_classes = 0; }

	// 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);
		showString(string,N);
		L = 1;
		done = Level_1(string);
		showRuns(string,L);
		count += countRuns(L);

		while(!done) {
			L++;
			done = Level(L);
			showRuns(string,L);
			count += countRuns(L);
		}
		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 = 16*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;
		CEnd = block+N;
		CNext = CEnd+N;
		CPrev = CNext+N;
		CMember = CPrev+N;
		CSize = CMember+N;
		CEmpty = CSize+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 = 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

	/* **********************************************************************************
	 *                                auxiliary methods                                 *
	 ************************************************************************************ */

	#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 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 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


	/* **********************************************************************************
	 *                             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,"<empty>\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,"<empty>\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,"<empty>\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 != null; e1 = CNext[e1]) {
			if (e1 == e) {
				break;
				in = true;
			}
		}
		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 != null; e = CNext[e])
			if (isinC(e,c2)) return false;
		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]; e != null; 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 (CMember[e] != i)  {
					bad = true;
					fprintf(fp,"class %u (element %u) failed membership test\n",i,e);
				}
				if (CPrev[e] != prev) {
					bad = true;
					fprintf(fp,"class %u (element %u) failed previous test\n",i,e);
				}
			}
			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,"<empty>\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: <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 showCEmpty


	// method showSc ---------------------------------------------------------------------
	void showSc(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");
	}

	// 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,"<empty>\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] = CEnd[c] = e;
		CNext[e] = CPrev[e] = null;
		CSize[c] = 1;
		CMember[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;
		
		CSize[c]++;
		// since the original parent mught have vanished, it is possible
		// that c == F1(f), in which case we leave it in place

		if (F1(f) != c) {
			if (F2(f) != c) {
				if (CSize[c] > 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[CEnd[c]] = e;
		CNext[e] = null;
		CPrev[e] = CEnd[c];
		CEnd[c] = e;
		CMember[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;

		c = CMember[e];
		right = CNext[e];
		if (right != null)
			rgap = GMember(right);
		egap = GMember(e);

		CMember[e] = null; // removing e from class c
		CSize[c]--;        // class c shrinks
		// if a class in a family shrinks, it must be the parent, i.e.
		// the first class in the family
		if ((f = FMember(c)) != null) {
			if (FStart[f] != c) {
				printf("removeFromClass error\n");
				getchar();
			}
		}

		if (CSize[c] == 0) {     // class vanishes, must be removed from family
			if (f != null) {
				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;
			}
			CEmptyPush(c);
			CStart[c] = null;
			number_of_classes--;
		}else{
			if (CStart[c] == e) {
				e1 = CNext[e];
				CStart[c] = e1;
				CPrev[e1] = null;
			}else if (CEnd[c] == e) {
				e1 = CPrev[e];
				CEnd[c] = e1;
				CNext[e1] = null;
			}else{
				e1 = CPrev[e];
				e2 = CNext[e];
				CNext[e1] = e2;
				CPrev[e2] = e1;
			}
		}

		// 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 (GNext[e] == null) {  // the list is {e}
					Gap[egap] = null;
				}else{
					Gap[egap]=GNext[e];
					GPrev[Gap[egap]]=null;
					GNext[e]=null;
				}
			}else if (GNext[e] == null) { // e is the last in Gap
				// e has previous, otherwise e is the first as well
				GNext[GPrev[e]] = null;
				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, sc;
		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
					CMember[CStart[c]] = null;  // remove the singleton class
					CStart[c] = null;
					CSize[c] = 0;
					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
							CMember[CStart[c]] = null;
							CStart[c] = null;   // remove the class
							CSize[c] = 0;
							CEmptyPush(c); 
							// do not put in snapshot as it is big
						}else{
							SelIn(CStart[c]);  // put in snapshot
							ScIn(CStart[c]);
							// this class will have to be removed during refinement
							/*
							CMember[CStart[c]] = null; // remove the class
							CStart[c] = null;  
							CSize[c] = 0;
							CEmptyPush(c);
							*/
						}
					}else{						// thick class
						RStackPush(c);         // make seed
						if (c != big) {			// put in snapshot
							for(sc = e = CStart[c]; e != null; sc = e, e = CNext[e])
								SelIn(e);
							ScIn(sc);
						}
					}
					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) {
		ulong g, p;

		fprintf(fp,"Gaps:\n");
		for(g = 0; g < N; g++) {
			if (Gap[g]==null) continue;
			fprintf(fp,"gap %u:",g);
			for(p = Gap[g]; p != null; p = GNext[p])
				fprintf(fp,"%d ",p);
			fprintf(fp,"\n");
		}
	}//end showGaps

	// method insertGap ---------------------------------------------------------------------
	void insertGap(ulong p,ulong g) { // insert position p into Gap g
		if (Gap[g]==null) {
			Gap[g]=p;
			GNext[p]=GPrev[p]=null;
		}else{
			GPrev[p]=null;
			GNext[p]=Gap[g];
			GPrev[Gap[g]]=p;
			Gap[g]=p;
		}
	}//end insertGap

	// method removeGap --------------------------------------------------------------------
	void removeGap(ulong p,ulong g) { // remove position p from Gap g
		if (Gap[g] == p) {            // p is first
			if (GNext[p] == null)
				Gap[g]=null;
			else{
				Gap[g] = GNext[p];
				GPrev[Gap[g]]=null;
				GNext[p]=null;
			}
		}else if (GNext[p]==null) {   // p is last
			GNext[GPrev[p]]=null;
			GPrev[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) {
		ulong p, g, last, first;
		bool bad=false;

		// check links
		for(g = 0; g < N; g++) {
			if (Gap[g] == null) continue;
			// traverse the list in both directions
			for(p = Gap[g]; p != null; p=GNext[p]) {
				if (GMember(p) != g) {
					printf("position %u with gap %u in Gap[%u]\n",p,GMember(p),g);
				    bad=true;
				}
				last=p;
			}
			for(p = last; p != null; p=GPrev[p]) {
				first=p;
			}
			if (first != Gap[g]) {
				printf("Gap[%u] wrong links\n",g);
				bad=true;
			}
		}
		if (! bad) fprintf(fp,"Gaps integrity OK\n");
		if (bad) 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;
		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] = CEnd[c] = i;
				CNext[i] = CPrev[i] = null;
				CMember[i] = c;
				CSize[c] = 1;
				c1 = CEmptyPop();
				number_of_classes++;
			}else{ // class c already exists
				CNext[CEnd[c]] = i;
				CNext[i] = null;
				CPrev[i] = CEnd[c];
				CSize[c]++;
				CEnd[c] = i;
				CMember[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];
			SelIn(j);
			while((j = CNext[j]) != null) {
				SelIn(j);
				last = j;
			}
			ScIn(last);
			if (CSize[i] == 1) { // singleton class cannot be removed, no room in Sc
				count++;
				/*
				CMember[CStart[i]] = null;
				CStart[i] = null;
				CSize[i] = 0;
				CEmptyPush(i);
				number_of_classes--;
				*/
			}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}
				SelOut();
				// now we have room in CEmpty, so we can remove this class
				c = CMember[0];
				CMember[0] = null;
				CStart[c] = null; 
				// it is clear that CNext[c]=CPrev[c]=null; 
				CSize[c] = 0;
				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 = CMember[s];
							if (c != null) {
								CStart[c] = null;
								// it is clear that CNext[c]=CPrev[c]=null; 
								CSize[c] = null;
								CMember[s] = null;
								CEmptyPush(c);
								number_of_classes--;
							}
						}
						cleanRefine();
						ssize = 0;
						break;
					}else
						continue;
				e1 = e-1;
				c = CMember[e1];    // e1 is a member of class c
				if (c == null) {
					if (e == s) {
						if (ssize == 1) { // remove singleton small class
							c = CMember[s];
							if (c != null) {
								CStart[c] = null;
								CSize[c] = null;
								CMember[s] = 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;

		first = last = p;
		RStackPush(p);
		Refine[p]=1;
		while((q = CPrev[first]) != null) {
			if ((first-q) == g) {
				first = q;
				if (GMember(first) != null) {
					RStackPush(first);
					Refine[first]=1;
				}
			}else
				break;
		}//endwhile
		// so we have first
			
		while((q = CNext[last]) != null) {
			if ((q-last) == g) {
				last = q;
				if (GMember(last) != null) {
					RStackPush(last);
					Refine[last]=1;
				}
			}else
				break;
		}//endwhile
		// 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;
		
		// 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; // 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)
					showRun(first,g,(last-first+1)/g,(last-first+1)%g);
				else
					showRun(string,first,g,(last-first+1)/g,(last-first+1)%g);
		}//end for
		cleanRefine();

		return count;
	}//end traceRuns

	// method showRuns --------------------------------------------------------------------
	void showRuns(ulong g,FILE* fp=stdout) {
		traceRuns(0,g,fp,true);
	}

	// method showRuns --------------------------------------------------------------------
	void showRuns(char* string,ulong g,FILE* fp=stdout) {
		traceRuns(string,g,fp,true);
	}

	// method countRuns --------------------------------------------------------------------
	ulong countRuns(ulong g) {
		return traceRuns(0,g,stdout,false);
	}

	// method showRun ------------------------------------------------------------------
	void showRun(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[] = "aababaababbabaababb";
	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;
}