#include "Col.ph"
#ifdef __GNUG__
#pragma implementation
#endif

#include "RunArray.h"

#include "Class.h"
#include "Error.h"
#include "String.h"
#include "Invariant.h"
#include "Math.h"
#include "ET_stdio.h"

InvariantChecker(RunArray);

const int cRunArrExpandFactor= 2;   // increment of expansion during Shift

static const char *cOutOfRangeMsg= "out of range from= %d to= %d length= %d";

inline bool OutOfRange(int from, int to, int len= cMaxInt)
	{ return from < 0 || from > to || to > len; }

inline bool HighWaterMark(int level, int size)
	{ return level > size; }

inline bool LowWaterMark(int level, int size)
	{ return level < (size/4 -1); }

//---- RunArray ----------------------------------------------------------------

NewMetaImpl(RunArray,Object, (TVP(cont, count), TV(runs, count), T(size),
				T(count), T(length), T(theRun), T(runOffset)));

RunArray::RunArray(int elements)
{
	cont= new Object* [size= elements];
	runs= new int[size];
	length= theRun= runOffset= count= 0;
}

RunArray::~RunArray()
{
	SafeDelete(cont);
	SafeDelete(runs);
}

void RunArray::OutOfRangeError(char *where, int at)
{
	Error(where, "out of range at %d (length %d)", at, length);
}

Object*& RunArray::operator[](int i)
{
	if (OutOfRange(i, length-1))
		OutOfRangeError("operator[]", i);
	MoveTo(i);
	return cont[theRun];
}

void RunArray::Insert(Object *op, int from, int to, int len)
{
	AssertInvariant(RunArray);
	if (OutOfRange(from, to, length)) {
		Error("Insert", cOutOfRangeMsg, from, to, length);
		return;
	}
	if (len < 0 || op == 0) {
		Error("Insert", "op == 0");
		return;
	}
	if (len == 0)      // store the run
		Cut(from, to);
	else {
		InsertRuns(from, to, &op, &len, 1);
		length+= len - to + from;
	}
}

void RunArray::ChangeRunSize(int i, int shift, RArrayGrowDir gd)
{
	AssertInvariant(RunArray);
	if (OutOfRange(i,length) || -shift > i) {
		OutOfRangeError("ChangeRunSize", i);
		return;
	}
	MoveTo(i);
	if (i == runOffset && i > 0 && gd == eRALeft)
		// |xxxxx|yyyyy|     grow at left margin
		//       v
		// |xxxxxv|yyyyy|
		PrevRun();
	if (i + shift >= runOffset) {
		runs[theRun]+= shift;
		length+= shift;
	} else
		Cut(i + shift, i);
}

void RunArray::Cut(int from, int to)
{
	AssertInvariant(RunArray);
	if (OutOfRange(from, to, length)) {
		Error("Cut", cOutOfRangeMsg, from, to, length);
		return;
	}
	InsertRuns(from, to, 0, 0, 0);
	length-= to-from;
}

void RunArray::Paste(RunArray *paste, int from, int to)
{
	ReplaceRange(from, to, paste, 0, paste->Size());
}

void RunArray::Copy(RunArray *save, int from, int to)
{
	save->ReplaceRange(0, save->Size(), this, from, to);
}

void RunArray::FreeAll()
{
	Cut(0, Size());
}

RunArray *RunArray::Save(int from, int to)
{
	RunArray *save= new RunArray;
	Copy(save, from, to);
	return save;
}

Object *RunArray::RunAt(int i, int *start, int *end, int *runsize, int *lenat)
{
	if (OutOfRange(i, length-1)) {
		OutOfRangeError("RunAt", i);
		return 0;
	}
	MoveTo(i);
	*start= runOffset;
	*end= EndOfRun();
	*runsize= runs[theRun];
	*lenat= *end - i;
	return cont[theRun];
}

int RunArray::LengthAt(int i)
{
	if (OutOfRange(i, length-1)) {
		OutOfRangeError("LengthAt", i);
		return 0;
	}
	MoveTo(i);
	return EndOfRun() - i;
}

int RunArray::RunSizeAt(int i)
{
	if (OutOfRange(i, length-1)) {
		OutOfRangeError("RunSizeAt", i);
		return 0;
	}
	MoveTo(i);
	return runs[theRun];
}

OStream &RunArray::PrintOn(OStream &s)
{
	AssertInvariant(RunArray);
	Object::PrintOn(s);
	s << count SP;
	for (int i= 0; i < count; i++)
		s << cont[i] SP << runs[i] SP;
	return s;
}

IStream &RunArray::ReadFrom(IStream &s)
{
	AssertInvariant(RunArray);
	theRun= runOffset= length= 0;
	Object::ReadFrom(s);
	s >> count;
	if (size < count) {
		delete cont;
		delete runs;
		cont= new Object*[size= count];
		runs= new int[count];
	}
	length= theRun= runOffset= 0;
	for (int i= 0; i < count; i++) {
		s >> cont[i] >> runs[i];
		length+= runs[i];
	}
	return s;
}

void RunArray::CheckInvariant()
{
	// sum of runlengths == length
	if (GetAssertLevel() > 10)
		return;
	int s= 0;
	for (int i= 0; i < count; i++)
		s+= runs[i];
	if (length != s)
		fprintf(stderr, "!!!RunArray Invariant: length %d runs %d\n", length, s);
}

void RunArray::ReplaceRange(int from, int to, RunArray *src, int sfrom, int sto)
{
	AssertInvariant(RunArray);
	if (OutOfRange(from, to, length)) {
		Error("ReplaceRange", cOutOfRangeMsg, from, to, length);
		return;
	}
	src->MoveTo(sfrom);
	int fromindex= src->theRun;
	int fromoffset= sfrom-src->runOffset;
	int fromlen= src->runs[src->theRun];
	src->MoveTo(Math::Max(0, sto-1));
	int toindex= src->theRun;
	int tooffset= sto-src->runOffset;
	int tolen= src->runs[src->theRun];
	if (fromindex != toindex) {
		src->runs[fromindex]= fromlen-fromoffset;
		src->runs[toindex]= tooffset;
	} else
		src->runs[fromindex]= sto-sfrom;
		
	InsertRuns(from, to, &src->cont[fromindex], &src->runs[fromindex],
												toindex-fromindex+1);
	length+= from-to + sto-sfrom;
	src->runs[fromindex]= fromlen;
	src->runs[toindex]= tolen;
}

//---- private methods ---------------------------------------------------------

inline void RunArray::CopyRuns(Object **desto, int *desti, int from, int to, int len)
{
	MemCpy(&desto[to], &cont[from], len * sizeof(Object*));
	MemCpy(&desti[to], &runs[from], len * sizeof(int));
}

void RunArray::MoveTo(int to)
{
	if (IsInRun(to))
		return;
	// find best start
	if (to < runOffset) {
		if (to < runOffset/2)
			theRun= runOffset= 0;
	} else {
		if (to > (length+runOffset)/2) {
			theRun= count -1;
			runOffset= length - runs[theRun];
		}
	}
	if (to < runOffset)
		// go left
		while (!IsInRun(to))
			PrevRun();
	else
		while (theRun < count  && !IsInRun(to))
			NextRun();
}

void RunArray::Shift(int at, int shift)
{
	Object **tmpop;
	int *tmpint;

	if (shift == 0)
		return;
	if (-shift > at) {
		OutOfRangeError("Shift", at);
		return;
	}
	if (HighWaterMark(count + shift, size)) {
		// expand
		if (size)
			size= Math::Max(size * cRunArrExpandFactor,count + shift);
		else
			size= 16;
		tmpop= new Object*[size];
		tmpint= new int[size];
		CopyRuns(tmpop, tmpint, 0, 0, at);
		CopyRuns(tmpop, tmpint, at, at + shift, count - at);
		delete cont;
		delete runs;
		cont= tmpop;
		runs= tmpint;
	} else {
		if (LowWaterMark(count + shift, size)) {
			//--- shrink
			size= size / cRunArrExpandFactor;
			tmpop= new Object*[size];
			tmpint= new int[size];
			CopyRuns(tmpop, tmpint, 0, 0, at + shift);
			CopyRuns(tmpop, tmpint, at, at + shift, count - at);
			delete cont;
			delete runs;
			cont= tmpop;
			runs= tmpint;
		} else
			CopyRuns(cont, runs, at, at + shift, count -at);
	}
	count+= shift;
}

void RunArray::InsertRuns(int from, int to, Object **value,
											int *run, int inssize)
{
	// Insert 'inssize' runs pointed to by 'value' between 'from' and 'to'

	int insert= inssize;
	int rightindex, rightlen, leftindex, leftlen;
	int i, j, firstlen= -1, lastlen= -1;
	Object *blankobj= 0;
	int    blankint= 0;

	if (!inssize) {
		// nothing to insert
		MoveTo(to);
		if (IsInRun(from) && to - from < runs[theRun]) {
			runs[theRun]-= to - from;
			return;
		}
		value= &blankobj;
		run= &blankint;
		if (to < EndOfRun()) {
			// set 'value' and 'run' to run right of 'to' and move right to the end of this run
			value[0]= cont[theRun];
			run[0]= EndOfRun() - to;
			to= EndOfRun();
			inssize= insert= 1;
		}
	}

	MoveTo(Math::Max(from-1,0));
	leftindex= theRun;            // index of run left of 'from'
	leftlen= from - runOffset;        // new length of run left of 'from'

	// delete runs between from and to
	while (!IsInRun(to)) {
		if (runOffset >= from)
			insert--;
		NextRun() ;
	}

	rightindex= theRun;           // index of run right of 'to'
	rightlen= EndOfRun() - to;     // new length of run right of 'to'

	theRun= leftindex;
	runOffset= from - leftlen;
	if (inssize) {
		firstlen= run[0];          // save length of first and last run
		lastlen= run[inssize-1];   // to insert
	}
	if (leftlen && rightlen && leftindex == rightindex)
		// insert new runs into one run ==> split this run
		insert++;
	if (inssize && leftlen && cont[leftindex]->IsEqual(value[0])) {
		// left run is equal to the first run to insert
		// add his length to it
		run[0]+= leftlen;
		leftlen= 0;
		insert--;
	}
	if (inssize && rightlen && cont[rightindex]->IsEqual(value[inssize-1])) {
		// right run is equal to the last run to insert
		// add his length to it
		run[inssize-1]+= rightlen;
		rightlen= 0;
		insert--;
	}

	Shift(rightindex, insert);
	i= leftindex;

	// adjust length of left and right run and insert new runs
	if (leftlen) {
		if (leftindex == rightindex)  // we had to split this run
			cont[i]= cont[leftindex+insert];
		runs[i]= leftlen;
		i++;
	}
	for (j= 0; j < inssize; i++, j++) {
		cont[i]= value[j];
		runs[i]= run[j];
	}
	if (rightlen)
		runs[i]= rightlen;

	if (inssize) {
		// restore length of first and last run to insert
		run[0]= firstlen;
		run[inssize-1]= lastlen;
	}
}

void RunArray::InspectorId (char *buf, int)
{
	sprintf(buf, "Size %d", length);
}

//---- RunArrayIter ------------------------------------------------------------

RunArrayIter::RunArrayIter(RunArray *ra)
{
	cs= ra;
	ce= ci= cp= 0;
}

Object *RunArrayIter::operator()()
{
	if (ci >= cs->length)
		return (0);
	if (ci >= cp + cs->runs[ce]) {
		cp+= cs->runs[ce];
		ce++;
	}
	ci++;
	return cs->cont[ce];
}

Object *RunArrayIter::Run(int *start, int *end, int *size)
{
	if (ci >= cs->length)
		return (0);

	*start= cp;
	*size= cs->runs[ce];
	*end= *start + *size;
	cp+= *size;
	ci= cp;
	return cs->cont[ce++];
}

Object **RunArrayIter::RunPtr(int *start, int *end, int *size)
{
	if (ci >= cs->length)
		return (0);

	*start= cp;
	*size= cs->runs[ce];
	*end= *start + *size;
	cp+= *size;
	ci= cp;
	return &cs->cont[ce++];
}