//setProcessing.cpp

#include "stdio.h"
#include "iostream.h"
#include "stdlib.h"
#include "math.h"
#include "string.h"
#include "assert.h"

#include "SetDef.h"
#include "rankedSetDef.h"
#include "subsetHolder.h"

//Object constructors and destructors

RankedSet::RankedSet()
{
	Ecount++;
	topLevelNr = 0;
	nrInSet = 0;
	nrInFirstLevel = 0;
	cursorCount=0;
	smhPtr = NULL;
	sshPtr = NULL;
	firstLooseCursor = NULLCursor;
	destroyInstructionNE = ErrorIfNotEmpty;
	destroyInstructionCC = ErrorIfContainsCursors;
}

RankedSet::RankedSet(DestroyInstructionNE dINE, 
					 DestroyInstructionCC dICC)
{
	Ecount++;
	topLevelNr = 0;
	nrInSet = 0;
	nrInFirstLevel = 0;
	cursorCount=0;
	smhPtr = NULL;
	sshPtr = NULL;
	firstLooseCursor = NULLCursor;
	destroyInstructionNE = dINE;
	destroyInstructionCC = dICC;

}


RankedSet::~RankedSet()
					             
{
	Ecount--;
	DestroyInstructionNE diNE;
	DestroyInstructionCC diCC;
	Cursor * cuPtr;

	diNE = destroyInstructionNE;
	diCC = destroyInstructionCC;

	if (nrInSet>0)
	{
		switch(diNE)
		{
			case(WarnIfNotEmpty):
				fprintf(stderr, 
					"Warning:  destroying a ranked set with members.");
				break;
			case(ErrorIfNotEmpty):
				fprintf(stderr, 
					"Error:  destroying a ranked set with members.");
				_exit(8);
			case(OKtoDestroyIfNotEmpty):
				break;
		}
	}

	//Regardless..
	if (smhPtr != NULL)
//		smhPtr->~setMemberHolder();
		delete smhPtr;
	if (sshPtr != NULL)
//		sshPtr->~subsetHolder();
		delete sshPtr;

//The above will move bound cursors to loose cursors
//The following tests whether there are any such and 
//whether or not that's OK.

	if (cursorCount>0)
	{
		switch(diCC)
		{
		case(ErrorIfContainsCursors):
			fprintf(stderr, 
				"Error:  destroying a ranked set containin cursors.");
			_exit(9);
		case(DestroyWithoutRemovingCursors):
			break;
		case(RemoveCursorsAndWarnIfCC):
			fprintf(stderr, 
				"Warning:  destroying a ranked set containin cursors.");
		//no break; proceed to next case...
		case(RemoveCursorsAndDontWarnIfCC):
			while (firstLooseCursor != NULLCursor)
			{
				cuPtr = removeFirstCursorFromLooseCursors();
				cuPtr->cuState = NotInSet;
			} //bound cursors will be handled in ~setMemberHolder()
			break;
		}
	}

}

setMemberHolder::setMemberHolder(RankedSet * rs){

		if ((int)this==0x00324320)
	{
		printf(" \n SMH 0x00324320 is being created\n");
	}

//Set attribut values.	
	assert( (partOf = rs)!=NULL); //assigns partOf and tests rs!=NULL
	Ecount++;
	nrAtThisLevel = 0;
	firstInUseNr = -1;
	lastInUseNr = -1;
	firstFreeNr = 0;
	minRA = largeRA;
	maxRA = smallRA;
	mIDofMin = NULLmID;
	mIDofMax = NULLmID;


//Allocate space for arrays

	rankingAtt = new RAType[membersPerHolder];
	memberID = new memberType[membersPerHolder];
	nextEnrollmentNr = new int[membersPerHolder];
	priorEnrollmentNr = new int[membersPerHolder];

//Continue initialization
	for (int i = 0; i < membersPerHolder - 1; i++)
			nextEnrollmentNr[i] = i+1;
	nextEnrollmentNr[membersPerHolder - 1] = -1;
	firstBoundCursor = NULLCursor;
}

setMemberHolder::~setMemberHolder()
{
	Cursor * cuPtr;
	Ecount--;
	if ((int)this==0x00324320)
	{
		printf(" \n SMH 0x00324320 is being destroyed\n");
	}

	while (this->firstBoundCursor != NULLCursor)
	{
		cuPtr = this->removeFirstCursorFromBoundCursors();
		assert(cuPtr!=NULLCursor);
		(this->partOf)->fileCursorInLooseCursors(cuPtr);
	}

//Deallocate space for arrays
	delete [] rankingAtt;
	delete [] memberID;
	delete [] nextEnrollmentNr;
	delete [] priorEnrollmentNr;
}

fileReturnCode RankedSet::fileMemberIntoSet(RAType RA,memberType mID)
{
	subsetHolder *oldSSHP;
	fileReturnCode fRC;

	if (topLevelNr == 0)
	{	
		if (smhPtr==NULL) //No member holder yet. Create one.
		assert((smhPtr = new setMemberHolder(this))!= NULL);				

		//Now has (or had) members holder	

		//If member holder is full, create a new level
		//and proceed to case with subset holder at top
		if (nrInFirstLevel >= membersPerHolder)
		{		
			assert((sshPtr = new subsetHolder(1, this))!=NULL);
			sshPtr->fileSmhFirstOrLastInSsh(smhPtr, First);
			nrInFirstLevel = 1;
			topLevelNr = 1;
			smhPtr = NULL;			
			goto containsSubsets; 		
		}

		//Else, still room in member holder. File member.

		assert((smhPtr->fileIntoMemberSubset(RA, mID)) == filed);
		minRA = smhPtr->minRA;
		mIDofMin = smhPtr->mIDofMin;
		maxRA = smhPtr->maxRA;
		mIDofMax = smhPtr->mIDofMax;
		nrInSet++;
		nrInFirstLevel++;
		assert(nrInFirstLevel == smhPtr->nrAtThisLevel);
		return filed;
	}
	
//else topLevelNr >= 1
containsSubsets:
	fRC = sshPtr->fileMemberIntoSubsetHolder(RA, mID);
	assert (fRC != error);
	if (fRC == filed) 
	{
		nrInSet++;
		nrInFirstLevel = sshPtr->nrAtThisLevel;
		minRA = sshPtr->grandMinRA;
		mIDofMin = sshPtr->mIDofGrandMin;
		maxRA = sshPtr->grandMaxRA;
		mIDofMax = sshPtr->mIDofGrandMax;
		return filed;
	}
	//else:   
	assert (fRC == blocked);
	//add new level; old subsetHolder will be only member of highest SSH
	oldSSHP = sshPtr;
	assert((sshPtr = new subsetHolder(++topLevelNr, this))!=NULL);
	sshPtr->fileLowerSshFirstOrLastInSsh(oldSSHP, First);
	nrInFirstLevel = 1;
	assert((sshPtr->fileMemberIntoSubsetHolder(RA, mID))==filed);
	nrInSet++;
	minRA = sshPtr->grandMinRA;
	mIDofMin = sshPtr->mIDofGrandMin;
	maxRA = sshPtr->grandMaxRA;
	mIDofMax = sshPtr->mIDofGrandMax;
	return filed;

}

RAandMID RankedSet::removeFirstFromSet()
{
	return removeFOrLFromSet(First);
}

RAandMID RankedSet::removeLastFromSet()
{
	return removeFOrLFromSet(Last);
}

RAandMID RankedSet::removeFOrLFromSet(insertLocType ilt)
{
	setMemberHolder *smhP;
	subsetHolder *sshP;
	RAandMID RM;

	assert(nrInSet > 0);
	if (topLevelNr == 0)
	{
		assert((smhP = smhPtr) != NULL);
		assert(nrInFirstLevel > 0);
		if (ilt == First)
			RM = smhP->removeFirstFromMemberSubset();
		else
			RM = smhP->removeLastFromMemberSubset();
		nrInFirstLevel--;
		//leave top Smh, even if empty
	}
	else
	{
		assert((sshP = sshPtr) != NULL);
		RM = sshP->removeFOrLMemberFromSubsetHolder(ilt);
		assert((nrInFirstLevel = sshP->nrAtThisLevel)>0); //See next
	 
//Delete levels while top SSH has only nrInFirstLevel = 1
		while((topLevelNr>0) && (nrInFirstLevel == 1))
		{
			if (topLevelNr == 1)
			{
				smhPtr = sshP->removeFOrLSmhFromSsh(First);
				nrInFirstLevel = smhPtr->nrAtThisLevel;
				sshPtr = NULL;
			}
			else
			{
				sshPtr = sshP->removeFOrL_LowerSshFromSsh(First);
				nrInFirstLevel = sshPtr->nrAtThisLevel;
			}
//			sshP->~subsetHolder();
			delete sshP;
			topLevelNr--;
			if(topLevelNr>0) assert((sshP=sshPtr)>0);
		}
		
	}
		assert(RM.RM_memberID>=0);
		nrInSet--;
		if (topLevelNr == 0)
		{
			minRA = smhPtr->minRA;
			mIDofMin = smhPtr->mIDofMin;
			maxRA = smhPtr->maxRA;
			mIDofMax = smhPtr->mIDofMax;
		}
		else
		{
			minRA = sshPtr->grandMinRA;
			mIDofMin = sshPtr->mIDofGrandMin;
			maxRA = sshPtr->grandMaxRA;
			mIDofMax = sshPtr->mIDofGrandMax;
		}
		return RM;	
}

removeReturnCode RankedSet::removeThisFromSet(RAandMID RM)
{
	return removeThisFromSet(RM.RM_rankingAtt, RM.RM_memberID);
}

removeReturnCode RankedSet::removeThisFromSet(RAType RA,memberType mID)
{
	removeReturnCode RCC;
	setMemberHolder *smhP;
	subsetHolder *sshP;

	if(nrInSet == 0) return notFound;

	if (topLevelNr == 0)
	{
		assert((smhP = smhPtr) != NULL);
		assert(nrInFirstLevel > 0);
		RCC = smhP->removeThisFromMemberSubset(RA, mID);
		if (RCC == removed) 
		{
			nrInFirstLevel--;
			nrInSet--;
			minRA = smhP->minRA;
			mIDofMin = smhP->mIDofMin;
			maxRA = smhP->maxRA;
			mIDofMax = smhP->mIDofMax;
		}				//leave top Smh, even if empty
		return RCC;
	}
	else
	{
		assert((sshP = sshPtr) != NULL);
		RCC = sshP->removeThisMemberFromSubsetHolder(RA, mID);
		assert((nrInFirstLevel = sshP->nrAtThisLevel)>0); //See next
	 
//Delete levels while top SSH has only nrInFirstLevel = 1
		while((topLevelNr>0) && (nrInFirstLevel == 1))
		{
			if (topLevelNr == 1)
			{
				smhPtr = sshP->removeFOrLSmhFromSsh(First);
				nrInFirstLevel = smhPtr->nrAtThisLevel;
				sshPtr=NULL;
			}
			else
			{
				sshPtr = sshP->removeFOrL_LowerSshFromSsh(First);
				nrInFirstLevel = sshPtr->nrAtThisLevel;
			}
//			sshP->~subsetHolder();
			delete sshP;
			topLevelNr--;
			if(topLevelNr>0) assert((sshP=sshPtr)>0);
		}
		
	}
		if (RCC == removed) 
		{
			nrInSet--;
			if (topLevelNr>0) //This may have changed
			{
				minRA = sshPtr->grandMinRA;
				mIDofMin = sshPtr->mIDofGrandMin;
				maxRA = sshPtr->grandMaxRA;
				mIDofMax = sshPtr->mIDofGrandMax;
			}
			else
			{
				minRA = smhPtr->minRA;
				mIDofMin = smhPtr->mIDofMin;
				maxRA = smhPtr->maxRA;
				mIDofMax = smhPtr->mIDofMax;
			}
		}

		return RCC;	
}


void setMemberHolder::copyMemberToSmhSlot(int place, RAType RA, memberType mID)
//MUST be called AFTER filing into InUse
{
	memberID[place]=mID;
	rankingAtt[place]=RA;
	if (priorEnrollmentNr[place]==-1)
	{
		minRA = RA;
		mIDofMin = mID;
	}
	if (nextEnrollmentNr[place]==-1)
	{
		maxRA = RA;
		mIDofMax = mID;
	}
	return;
}


RAandMID setMemberHolder::dropMemberFromSmhSlot(int slotNr)
{
	RAandMID RM;
	int priorSlotNr, nextSlotNr;
	Cursor * cuPtr;

	RM.RM_rankingAtt = rankingAtt[slotNr];
	RM.RM_memberID   = memberID[slotNr];
	memberID[slotNr] = NULLmID;
	priorSlotNr = priorEnrollmentNr[slotNr];
	nextSlotNr =  nextEnrollmentNr[slotNr];
	if ((priorSlotNr<0)&&(nextSlotNr<0))
	{
		minRA = smallRA;
		maxRA = largeRA;
		mIDofMin = NULLmID;
		mIDofMax = NULLmID;
		goto PerhapsRemoveCursorsFromBoundCursors;
	}
	if(priorSlotNr<0)
	{
		assert(firstInUseNr == slotNr);
		minRA = rankingAtt[nextSlotNr];
		mIDofMin = memberID[nextSlotNr];
	}
	if (nextSlotNr<0)
	{
		assert(lastInUseNr == slotNr);
		maxRA = rankingAtt[priorSlotNr];
		mIDofMax = memberID[priorSlotNr];
	}

PerhapsRemoveCursorsFromBoundCursors:
	for (cuPtr=firstBoundCursor; cuPtr!=NULLCursor; cuPtr=cuPtr->nextCursor)
	{
		if (cuPtr->slotWhereBound==slotNr)
		{
			assert(cuPtr->SetBeingExplored!=NULL);
			removeThisCursorFromBoundCursors(cuPtr);
			(cuPtr->SetBeingExplored)->fileCursorInLooseCursors(cuPtr);
		}
	}
			

	return RM;
}


fileReturnCode setMemberHolder::fileIntoMemberSubset(RAType RA,memberType mID)
{
	
int enrollNr, priorEnrollNr, nextEnrollNr;	

	enrollNr = removeFreeSlotNr();
	assert(enrollNr>=0);

//  Find proper place for newcomer.
	
//Does newcomer go to front of set?
	if ((firstInUseNr < 0) ||
		(rankingAtt[firstInUseNr] > RA) ||
		((rankingAtt[firstInUseNr] == RA) &&
			 (memberID[firstInUseNr] > mID)))
	{
		fileSlotNrFirstIntoInUse(enrollNr);
		copyMemberToSmhSlot(enrollNr, RA, mID);
		return filed;			
	}
//Does newcomer go to back of set?
	else if((rankingAtt[lastInUseNr] < RA) ||
			((rankingAtt[lastInUseNr] == RA) &&
				 (memberID[lastInUseNr] < mID)))
	{
		fileSlotNrLastIntoInUse(enrollNr);
		copyMemberToSmhSlot(enrollNr, RA, mID);
		return filed;			
	}
	else
	{
		priorEnrollNr = firstInUseNr;
		while ((nextEnrollNr = nextEnrollmentNr[priorEnrollNr])
					>= 0 )
		{
			if ((rankingAtt[nextEnrollNr] > RA)  ||
					( (rankingAtt[nextEnrollNr] == RA) &&
					  (memberID[nextEnrollNr] > mID)))
			{
				fileSlotNr1AfterSlotNr2InUse(enrollNr, priorEnrollNr);
				copyMemberToSmhSlot(enrollNr, RA, mID);
				return filed;
			}
			/*else*/ priorEnrollNr = nextEnrollNr;
		}
			assert(0==1);  //This point should not be reached
			return error;
		}		
}



RAandMID setMemberHolder::removeFirstFromMemberSubset()
{
	RAandMID RM;
	int i;

	assert(nrAtThisLevel>0);
	RM = dropMemberFromSmhSlot(firstInUseNr);
	i = removeFirstSlotNrFromInUse();
	fileFreeSlotNr(i);
	return RM;	
}
	
RAandMID setMemberHolder::removeLastFromMemberSubset()
{
	RAandMID RM;
	int i;

	assert(nrAtThisLevel>0);
	RM = dropMemberFromSmhSlot(lastInUseNr);
	i = removeLastSlotNrFromInUse();
	fileFreeSlotNr(i);
	return RM;	
}

RAandMID setMemberHolder::removeThisFromMemberSubset(int place)
  //There is also routine with this name with RA and mID as arguments
{
	RAandMID RM;

	RM = dropMemberFromSmhSlot(place);
	assert(RM.RM_memberID > NULLmID);
	removeThisSlotNrFromInUse(place);
	fileFreeSlotNr(place);
	return RM;	
}

removeReturnCode setMemberHolder::removeThisFromMemberSubset
	(RAType RA,memberType mID) //Above is version with place as argument
{
	int place;
	RAandMID RM;
	
	for (place = firstInUseNr; place>=0; place = nextEnrollmentNr[place])
	{
		if ((rankingAtt[place] > RA) ||
			((rankingAtt[place]==RA)&&(memberID[place]>mID)))
			return notFound;
		if ((rankingAtt[place] == RA)&&(memberID[place]==mID))
		{
//Member found, now remove
			RM = dropMemberFromSmhSlot(place);
			assert((RM.RM_rankingAtt == RA ) &&
				(RM.RM_memberID == mID));
			removeThisSlotNrFromInUse(place);
			fileFreeSlotNr(place);
			return removed;
		}
	}
	return notFound;  
}

			
inline void setMemberHolder::fileFreeSlotNr(int slotNr)
{
	nextEnrollmentNr[slotNr] = firstFreeNr;
	firstFreeNr = slotNr;
}

inline int setMemberHolder::removeFreeSlotNr()
{
	int i;
	i = firstFreeNr;
	assert(i >= 0);
	firstFreeNr = nextEnrollmentNr[i];
	return i;
}

inline void setMemberHolder::fileSlotNrFirstIntoInUse(int i)
{
	if (firstInUseNr < 0)
	{
		lastInUseNr = i;
		nextEnrollmentNr[i] = -1;
	}
	else
	{
		nextEnrollmentNr[i] = firstInUseNr;
		priorEnrollmentNr[firstInUseNr] = i;
	}
	priorEnrollmentNr[i] = -1;
	firstInUseNr = i;
	nrAtThisLevel++;
	return;
}

inline void setMemberHolder::fileSlotNrLastIntoInUse(int i)
{
	if (firstInUseNr < 0)
	{
		firstInUseNr = i;
		priorEnrollmentNr[i] = -1;
	}
	else
	{
		priorEnrollmentNr[i] = lastInUseNr;
		nextEnrollmentNr[lastInUseNr] = i;
	}
	nextEnrollmentNr[i] = -1;
	lastInUseNr = i;
	nrAtThisLevel++;
	return;
}

inline void setMemberHolder::fileSlotNr1AfterSlotNr2InUse(int newNr, int oldNr)
{
	nextEnrollmentNr[newNr] = nextEnrollmentNr[oldNr];
	nextEnrollmentNr[oldNr] = newNr;
	priorEnrollmentNr[newNr] = oldNr;
	if (nextEnrollmentNr[newNr] >=0)
		priorEnrollmentNr[nextEnrollmentNr[newNr]] = newNr;
	else
		lastInUseNr = newNr;
	//In either case:
	nrAtThisLevel++;
	return;
}

inline int setMemberHolder::removeFirstSlotNrFromInUse()
{	
	int i;

	assert (firstInUseNr >= 0);
	i = firstInUseNr;
	firstInUseNr = nextEnrollmentNr[i];
	if (firstInUseNr < 0)
		lastInUseNr = -1;
	else
		priorEnrollmentNr[firstInUseNr] = -1;
	//regardless
	nrAtThisLevel--;
	return i;
}

inline int setMemberHolder::removeLastSlotNrFromInUse()
{	
	int i;

	assert (firstInUseNr >= 0);
	i = lastInUseNr;
	lastInUseNr = priorEnrollmentNr[i];
	if (lastInUseNr < 0)
		firstInUseNr = -1;
	else
		nextEnrollmentNr[lastInUseNr] = -1;
	//regardless
	nrAtThisLevel--;
	return i;
}

void setMemberHolder::removeThisSlotNrFromInUse(int slotNr)
{	
	int nextSlotNr, priorSlotNr;

	assert (firstInUseNr >= 0);

	priorSlotNr = priorEnrollmentNr[slotNr];
	nextSlotNr = nextEnrollmentNr[slotNr];

	if(priorSlotNr < 0)
		firstInUseNr = nextSlotNr;
	else
		nextEnrollmentNr[priorSlotNr] = nextSlotNr;
	if(nextSlotNr < 0)
		lastInUseNr = priorSlotNr;
	else
		priorEnrollmentNr[nextSlotNr] = priorSlotNr;
	//regardless	
	nrAtThisLevel--;
	return;
}


//Ranked set routines involving Cursors,e.g., findFirst,
//are located in the Cursor.cpp file