//subsetHolder.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"

subsetHolder::subsetHolder(int levelNumber, RankedSet * rs) {
	Ecount++;
	assert( (partOf = rs)!=NULL );
	levelNr = levelNumber;
	nrAtThisLevel = 0;
	grandNrSpanned = 0;
	grandMinRA = largeRA;
	mIDofGrandMin = NULLmID;
	grandMaxRA = smallRA;
	mIDofGrandMax = NULLmID;
	firstInUseNr = -1;
	lastInUseNr = -1;
	firstFreeNr = 0;

//Allocate space for arrays

//Old definitions, in version with memory leak.
/*	RAType minRA[subsetsPerHolder];
	memberType mIDofMin[subsetsPerHolder];
	RAType maxRA[subsetsPerHolder];
	memberType mIDofMax[subsetsPerHolder];
	int nextRepNr[subsetsPerHolder];
	int priorRepNr[subsetsPerHolder];
	int nrAtLevelRepd[subsetsPerHolder];
	long nrSpanned[subsetsPerHolder];	
	union 
	{
		setMemberHolder *smhPtr;
		subsetHolder *sshPtr;

	}repPtr[subsetsPerHolder];
 */

	minRA = new RAType[subsetsPerHolder];
	mIDofMin = new memberType[subsetsPerHolder];
	maxRA = new RAType[subsetsPerHolder];
	mIDofMax = new memberType[subsetsPerHolder];
	nextRepNr = new int[subsetsPerHolder];
	priorRepNr = new int[subsetsPerHolder];
	nrAtLevelRepd = new int[subsetsPerHolder];
	nrSpanned = new long[subsetsPerHolder];
	repPtr = new SMHorSSH[subsetsPerHolder];

//Continue initializing
	for (int i = 0; i < subsetsPerHolder - 1; i++)
		nextRepNr[i] = i+1;
	nextRepNr[subsetsPerHolder - 1] = -1;
}


subsetHolder::~subsetHolder()
{
	Ecount--;
	setMemberHolder *smh;
	subsetHolder *ssh;

	while (firstInUseNr >= 0)
	{
		if (levelNr == 1)
		{
			smh = removeFOrLSmhFromSsh(First);
//			smh->~setMemberHolder();
			delete smh;
		}
		else
		{
			ssh = removeFOrL_LowerSshFromSsh(First);
//			ssh->~subsetHolder();
			delete ssh;
		}
	}
//Deallocate arrays
	delete [] minRA;
	delete [] mIDofMin;
	delete [] maxRA;
	delete [] mIDofMax;
	delete [] nextRepNr;
	delete [] priorRepNr;
	delete [] nrAtLevelRepd;
	delete [] nrSpanned;
	delete [] repPtr;
}

fileReturnCode subsetHolder::fileMemberIntoSubsetHolder
						(RAType RA,memberType mID)
{
	int i, n, currentSSNr, nextSSNr;
	insertLocType ilt;
	setMemberHolder *smh, *newSmh;
	subsetHolder *ssh, *newSsh, *tempSsh;
	RAandMID RM;
	fileReturnCode FRC;
	
// *************************************************************
//
//Find insertion location and type
//
// *************************************************************
	if(nrAtThisLevel==0)
	{
		assert(grandNrSpanned == 0);
		ilt = Empty;
		goto InsertMember;
	}
	if ((RA < minRA[firstInUseNr]) ||
		((RA == minRA[firstInUseNr]) &&
		(mID < mIDofMin[firstInUseNr])))
	{
		currentSSNr = firstInUseNr;
		ilt = atFront;
		goto InsertMember;
	}
	if ((RA > maxRA[lastInUseNr]) ||
		( (RA == maxRA[lastInUseNr]) &&
		  (mID > mIDofMax[lastInUseNr])))
	{
		currentSSNr = lastInUseNr;
		ilt = atBack;
		goto InsertMember;
	}

	for (currentSSNr=firstInUseNr; currentSSNr >=0;
							currentSSNr = nextRepNr[currentSSNr])
		{
			if ((RA < maxRA[currentSSNr]) ||
				( (RA == maxRA[currentSSNr]) &&
				  ( mID < mIDofMax[currentSSNr])))
			{
				ilt = internal;
				goto InsertMember;
			}
			
			nextSSNr = nextRepNr[currentSSNr];
			if ((nextSSNr >= 0) && 
				((RA < minRA[nextSSNr]) ||
				 (RA == minRA[nextSSNr]) &&
				 (mID < mIDofMin[nextSSNr])))
			{
				ilt = between;
				goto InsertMember;
			}
		}
	assert(0==1);  //This point should not be reached

// *************************************************************
//
// Insert Member Into Subset Holder At Position Determined Above
//
// *************************************************************

InsertMember:
	if (levelNr == 1)
	{

//****************************************************
//
// Subset points to SetMemberHolders: SMH
//
//****************************************************

//If SSH is not empty and insertion point is front, 
// back or internal and there is room in Smh referred to by 
// currentSSNr: file
	if ((ilt != Empty) && (ilt != between) && 
		(nrAtLevelRepd[currentSSNr] < membersPerHolder))
		{
			assert((fileMemberIntoSmhInUse(currentSSNr, RA, mID))==filed);
			return filed;
		}
//If insertion point is "between" and either Smh, fore or aft, has room
//file into member holder with more room (if either has room)
	if (ilt == between)
	{
		if (nrAtLevelRepd[currentSSNr] < nrAtLevelRepd[nextSSNr])
		{	
			assert(fileMemberIntoSmhInUse(currentSSNr, RA, mID)==filed);
			return filed;
		}
		if (nrAtLevelRepd[nextSSNr] < membersPerHolder)
		{
			assert(fileMemberIntoSmhInUse(nextSSNr, RA, mID)==filed);
			return filed;
		}
	}

//else either SSH has no SMH or relevant member holder(s) full. 
// Create another if room. Insert where appropriate
	if(nrAtThisLevel == subsetsPerHolder)
		return blocked;

	//else:  room for new Smh
	assert( (newSmh = new setMemberHolder(partOf) )!= NULL);
	
	switch(ilt)
	{
		case atFront:
		case atBack:
		case Empty:
			
			assert(newSmh->fileIntoMemberSubset(RA, mID)== filed);	
			fileSmhFirstOrLastInSsh(newSmh, ilt);
			return filed;			

		case internal: //move some members from old (full) to new (empty) Smh			
							
			n = membersPerHolder/2;
			for (i=0; i<n; i++)
			{
				RM = removeFOrLMemberFromSmhInUse(currentSSNr, Last);
				newSmh->fileIntoMemberSubset(RM.RM_rankingAtt, RM.RM_memberID);
			}
		//file member into old or new, as appropriate
			if ((RA > maxRA[currentSSNr]) ||
				((RA == maxRA[currentSSNr]) && 
				(mID > mIDofMax[currentSSNr])))
					newSmh->fileIntoMemberSubset(RA,mID);
			else
					fileMemberIntoSmhInUse(currentSSNr, RA, mID);
			//In either case:
			fileSmhAfterArg2Slot(newSmh, currentSSNr);
			return filed;			
			
		case between:
			
			//In this case, we know that member will go into new Smh
			assert ((newSmh->fileIntoMemberSubset(RA, mID)) == filed);
			for ( i = 0; i < aFewMembers; i++)
			{
				RM = removeFOrLMemberFromSmhInUse(currentSSNr, Last);
				assert(RM.RM_memberID >= 0);
				newSmh->fileIntoMemberSubset(RM.RM_rankingAtt, 
					RM.RM_memberID);
				RM = removeFOrLMemberFromSmhInUse(nextSSNr, First);
				assert(RM.RM_memberID >= 0);
				newSmh->fileIntoMemberSubset(RM.RM_rankingAtt, 
					RM.RM_memberID);
			}
			fileSmhAfterArg2Slot(newSmh, currentSSNr);
			return filed;
		}	
		
	}

// *****************************************************
//
// ELSE  Subset points to Subset Holders, SSH
//
// ******************************************************

//If insertion point is front, back or internal and there is 
// room in Ssh referred to by currentSSNr: file

	if((ilt != Empty) && (ilt != between) && 
		((FRC=fileMemberIntoLowerSshInUse(currentSSNr, RA, mID))==filed))	
		return filed;

//If insertion point is "between", try both fore and aft subsetHolders
//starting with the one which spans fewer members
	if (ilt == between)
	{
 		if (nrSpanned[currentSSNr] < nrSpanned[nextSSNr])  //try currentSSNr first
		{
			if((fileMemberIntoLowerSshInUse(currentSSNr, RA, mID))==filed)		
				return filed;
			else
				if((fileMemberIntoLowerSshInUse(nextSSNr, RA, mID))==filed)
					return filed;
		}
		else  //try nextSSNr first. Do try currentSSNr if nextSSNr blocked.
		{
			if((fileMemberIntoLowerSshInUse(nextSSNr, RA, mID))==filed)			
				return filed;
			else
				if((fileMemberIntoLowerSshInUse(currentSSNr, RA, mID))==filed)		
					return filed;
		}
	}

// CurrentSSNr (or "Fore" and "Aft" subset holders, when ilt == between)	
// are blocked.  Is there room for another (lower level) 
// Ssh within "this" Ssh?
	if (nrAtThisLevel == subsetsPerHolder)
		return blocked;

//There is room for another lower level Ssh within "this" Ssh
	assert((newSsh = new subsetHolder(levelNr-1, partOf))!=NULL);

//Insert new Ssh as appropriate
	switch(ilt)
	{
	case atFront:
	case atBack:
	case Empty:
		assert((newSsh->fileMemberIntoSubsetHolder(RA, mID)) == filed);			
		assert((fileLowerSshFirstOrLastInSsh(newSsh, ilt)) == filed);						
		return filed;
			
	case internal:					
		n = subsetsPerHolder/2;
		if (levelNr == 2)
		{
			for (i=0; i<n; i++)
			{
				smh = removeFOrLSmhFromSshInUse(currentSSNr, Last);
				newSsh->fileSmhFirstOrLastInSsh(smh, First);					
			}
		}
		else
		{	
			assert (levelNr>2);
			for (i=0; i<n; i++)
			{
				tempSsh = removeFOrL_LowerSshFromSshInUse(currentSSNr, Last);
				newSsh->fileLowerSshFirstOrLastInSsh(tempSsh, First);
				
			}
		}
		//file member into old or new, as appropriate
		if ((RA > maxRA[currentSSNr]) ||
			((RA == maxRA[currentSSNr]) && 
			(mID > mIDofMax[currentSSNr])))
				newSsh->fileMemberIntoSubsetHolder(RA,mID);
		else
				fileMemberIntoLowerSshInUse(currentSSNr, RA, mID);
		//In either case:
			fileSshAfterArg2Slot(newSsh, currentSSNr);
			return filed;
	

	case between:

		n = subsetsPerHolder/4;
		if (levelNr == 2)
		{
			for (i=0; i<n; i++)
			{
				smh = removeFOrLSmhFromSshInUse(currentSSNr, Last);
				newSsh->fileSmhFirstOrLastInSsh(smh, First);	
				smh = removeFOrLSmhFromSshInUse(nextSSNr, First);
				newSsh->fileSmhFirstOrLastInSsh(smh, Last);			
				
			}

		}
		else //level number > 2, presumably; i.e., 
			 // represented sshs point to still lower sshs.
		{
			assert (levelNr>2);
			for (i=0; i<n; i++)
			{
				ssh = removeFOrL_LowerSshFromSshInUse(currentSSNr, Last);
				newSsh->fileLowerSshFirstOrLastInSsh(ssh, First);	
				ssh = removeFOrL_LowerSshFromSshInUse(nextSSNr, First);
				newSsh->fileLowerSshFirstOrLastInSsh(ssh, Last);			
			}
		}
		// When ilt = between we know new member goes into new Ssh
			assert(newSsh->fileMemberIntoSubsetHolder(RA, mID) == filed);
			fileSshAfterArg2Slot(newSsh, currentSSNr);
			return filed;
	default:
		return error;
	}	
}

fileReturnCode subsetHolder::fileMemberIntoSmhInUse(int repNr, RAType RA, memberType mID)
{
	setMemberHolder * smh;

	assert (levelNr == 1);
	smh = repPtr[repNr].smhPtr;
	assert ((smh ->fileIntoMemberSubset(RA, mID))==filed);
	nrSpanned[repNr]++;
	nrAtLevelRepd[repNr] = nrSpanned[repNr];
	grandNrSpanned++;
	minRA[repNr] = smh->minRA;
	mIDofMin[repNr] = smh->mIDofMin;
	maxRA[repNr] = smh->maxRA;
	mIDofMax[repNr] = smh->mIDofMax;
	if ((minRA[repNr] < grandMinRA) ||
		( (minRA[repNr]==grandMinRA) &&
		(mIDofMin[repNr] < mIDofGrandMin)))
	{
		grandMinRA = minRA[repNr];
		mIDofGrandMin = mIDofMin[repNr];
	}
	if ((maxRA[repNr] > grandMaxRA) ||
		( (maxRA[repNr]==grandMaxRA) &&
		(mIDofMax[repNr] > mIDofGrandMax)))
	{
		grandMaxRA = maxRA[repNr];
		mIDofGrandMax = mIDofMax[repNr];
	}
	return filed;
}

fileReturnCode subsetHolder::fileMemberIntoLowerSshInUse(int repNr, RAType RA, memberType mID)
{
	subsetHolder * ssh;
	fileReturnCode frc;

	assert (levelNr > 1);
	ssh = repPtr[repNr].sshPtr;
	frc = ssh ->fileMemberIntoSubsetHolder(RA, mID);
	if (frc != filed)
		return frc;
	//else...
	nrSpanned[repNr]++;
	grandNrSpanned++;
	nrAtLevelRepd[repNr] = ssh->nrAtThisLevel;
	minRA[repNr] = ssh->grandMinRA;
	mIDofMin[repNr] = ssh->mIDofGrandMin;
	maxRA[repNr] = ssh->grandMaxRA;
	mIDofMax[repNr] = ssh->mIDofGrandMax;
	if ((minRA[repNr] < grandMinRA) ||
		( (minRA[repNr]==grandMinRA) &&
		(mIDofMin[repNr] < mIDofGrandMin)))
	{
		grandMinRA = minRA[repNr];
		mIDofGrandMin = mIDofMin[repNr];
	}
	if ((maxRA[repNr] > grandMaxRA) ||
		( (maxRA[repNr]==grandMaxRA) &&
		(mIDofMax[repNr] > mIDofGrandMax)))
	{
		grandMaxRA = maxRA[repNr];
		mIDofGrandMax = mIDofMax[repNr];	
	}
	return filed;
}

fileReturnCode subsetHolder::fileSmhFirstOrLastInSsh
		(setMemberHolder * smhP, insertLocType ilt)
{
	int repNr;

	repNr = removeFreeSlotNr();
	copySmhToRep(repNr, smhP);

	if (ilt==First)	
		fileSlotNrFirstIntoInUse(repNr);
	else  //ilt = Last or Empty
		fileSlotNrLastIntoInUse(repNr);		
	return filed;			
}

fileReturnCode subsetHolder::fileSmhAfterArg2Slot(setMemberHolder *smh, int slotNr)
{
	int i;
	i = removeFreeSlotNr();
	assert(i >= 0);
	fileSlotNr1AfterSlotNr2InUse(i, slotNr);
	copySmhToRep(i, smh);
	return filed;
}

fileReturnCode subsetHolder::fileSshAfterArg2Slot(subsetHolder *ssh, int slotNr)
{
	int i;
	i = removeFreeSlotNr();
	assert(i >= 0);
	fileSlotNr1AfterSlotNr2InUse(i, slotNr);
	copySshToRep(i, ssh);
	return filed;
}

fileReturnCode subsetHolder::fileLowerSshFirstOrLastInSsh
		(subsetHolder * sshP, insertLocType ilt)

{
	int repNr;

	if ((ilt==First)||(ilt==Empty))
	{
		assert((firstInUseNr < 0) ||
			(sshP->grandMaxRA < grandMinRA) ||
			(sshP->grandMaxRA == grandMinRA &&
			sshP->mIDofGrandMax < mIDofGrandMin));
		
		repNr= removeFreeSlotNr();
		copySshToRep(repNr, sshP);
		fileSlotNrFirstIntoInUse(repNr);
		return filed;
	}
	//else FLC = Last
		assert((firstInUseNr < 0) ||
			(sshP->grandMaxRA > grandMaxRA) ||
			(sshP->grandMaxRA == grandMaxRA &&
			sshP->mIDofGrandMax > mIDofGrandMax));

		repNr = removeFreeSlotNr();
		copySshToRep(repNr, sshP);
		fileSlotNrLastIntoInUse(repNr);		
		return filed;							

}
		

void subsetHolder::copySmhToRep(int repNr, setMemberHolder * smhP)
{
	assert (levelNr == 1);

	repPtr[repNr].smhPtr = smhP;
	nrSpanned[repNr] = smhP->nrAtThisLevel;
	nrAtLevelRepd[repNr] = smhP->nrAtThisLevel;
	grandNrSpanned += nrAtLevelRepd[repNr];
	minRA[repNr] = smhP->minRA;
	mIDofMin[repNr] = smhP->mIDofMin;
	maxRA[repNr] = smhP->maxRA;
	mIDofMax[repNr] = smhP->mIDofMax;
	if ((minRA[repNr] < grandMinRA) ||
		( (minRA[repNr]==grandMinRA) &&
		(mIDofMin[repNr] < mIDofGrandMin)))
	{
		grandMinRA = minRA[repNr];
		mIDofGrandMin = mIDofMin[repNr];
	}
	if ((maxRA[repNr] > grandMaxRA) ||
		( (maxRA[repNr]==grandMaxRA) &&
		(mIDofMax[repNr] > mIDofGrandMax)))
	{
		grandMaxRA = maxRA[repNr];
		mIDofGrandMax = mIDofMax[repNr];
	}
	return;
}


void subsetHolder::copySshToRep(int repNr, subsetHolder * sshP)
{
	assert (levelNr > 1);

	repPtr[repNr].sshPtr = sshP;
	nrSpanned[repNr] = sshP->grandNrSpanned;
	nrAtLevelRepd[repNr] = sshP->nrAtThisLevel;
	grandNrSpanned += nrSpanned[repNr];
	minRA[repNr] = sshP->grandMinRA;
	mIDofMin[repNr] = sshP->mIDofGrandMin;
	maxRA[repNr] = sshP->grandMaxRA;
	mIDofMax[repNr] = sshP->mIDofGrandMax;
	if ((minRA[repNr] < grandMinRA) ||
		( (minRA[repNr]==grandMinRA) &&
		(mIDofMin[repNr] < mIDofGrandMin)))
	{
		grandMinRA = minRA[repNr];
		mIDofGrandMin = mIDofMin[repNr];
	}
	if ((maxRA[repNr] > grandMaxRA) ||
		( (maxRA[repNr]==grandMaxRA) &&
		(mIDofMax[repNr] > mIDofGrandMax)))
	{
		grandMaxRA = maxRA[repNr];
		mIDofGrandMax = mIDofMax[repNr];
	}
	return;
}


setMemberHolder * subsetHolder::dropSmhFromRep(int repNr)
//MUST BE CALLED BEFORE REMOVING SLOT FROM INUSE !!!!!!!!!!!!!!
{
	setMemberHolder * smhP;
	assert (levelNr == 1);

	smhP = repPtr[repNr].smhPtr;
	grandNrSpanned -= nrAtLevelRepd[repNr];
	nrSpanned[repNr] = 0;
	nrAtLevelRepd[repNr] = 0;
	mIDofMin[repNr] = NULLmID;
	mIDofMax[repNr] = NULLmID;
	if(priorRepNr[repNr] == -1)
	{
		if (nextRepNr[repNr] == -1)
		{
			assert (grandNrSpanned==0);
			mIDofGrandMin = NULLmID;
			mIDofGrandMax = NULLmID;
			return smhP;
		}
		//else
		grandMinRA = minRA[nextRepNr[repNr]];
		mIDofGrandMin = mIDofMin[nextRepNr[repNr]];
	}

	//Case in which repNr is the only member is handled above
	//and control is returned to calling routine

	if (nextRepNr[repNr] == -1)
	{
		grandMaxRA = maxRA[priorRepNr[repNr]];
		mIDofGrandMax = mIDofMax[priorRepNr[repNr]];
	}
	return smhP;
}


subsetHolder * subsetHolder::dropSshFromRep(int repNr)
//MUST BE CALLED BEFORE REMOVING SLOT FROM INUSE !!!!!!!!!!!!!!
{
	subsetHolder * sshP;
	assert (levelNr > 1);

	sshP = repPtr[repNr].sshPtr;
	grandNrSpanned -= nrSpanned[repNr];
	nrSpanned[repNr] = 0;
	nrAtLevelRepd[repNr] = 0;
	mIDofMin[repNr] = NULLmID;
	mIDofMax[repNr] =NULLmID;
	if(priorRepNr[repNr] == -1)
	{
		if (nextRepNr[repNr] == -1)
		{
			assert (grandNrSpanned==0);
			mIDofGrandMin = NULLmID;
			mIDofGrandMax = NULLmID;
			return sshP;
		}
		//else
		grandMinRA = minRA[nextRepNr[repNr]];
		mIDofGrandMin = mIDofMin[nextRepNr[repNr]];
	}

	//Case in which repNr is the only member is handled above
	//and control is returned to calling routine

	if (nextRepNr[repNr] == -1)
	{
		grandMaxRA = maxRA[priorRepNr[repNr]];
		mIDofGrandMax = mIDofMax[priorRepNr[repNr]];
	}
	return sshP;
}


inline void subsetHolder::fileFreeSlotNr(int slotNr)
{
	nextRepNr[slotNr] = firstFreeNr;
	firstFreeNr = slotNr;
}

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

inline void subsetHolder::fileSlotNrFirstIntoInUse(int i)
{
	if (firstInUseNr < 0)
	{
		firstInUseNr = i;
		lastInUseNr = i;
		nextRepNr[i] = -1;
		priorRepNr[i] = -1;
		nrAtThisLevel++;
		return;
	}
	//else
	nextRepNr[i] = firstInUseNr;
	priorRepNr[firstInUseNr] = i;
	priorRepNr[i] = -1;
	firstInUseNr = i;
	nrAtThisLevel++;
	return;
}

inline void subsetHolder::fileSlotNrLastIntoInUse(int i)
{
	if (firstInUseNr < 0)
	{
		firstInUseNr = i;
		lastInUseNr = i;
		nextRepNr[i] = -1;
		priorRepNr[i] = -1;
		nrAtThisLevel++;
		return;
	}
	priorRepNr[i] = lastInUseNr;
	nextRepNr[lastInUseNr] = i;
	nextRepNr[i] = -1;
	lastInUseNr = i;
	nrAtThisLevel++;
	return;
}

inline void subsetHolder::fileSlotNr1AfterSlotNr2InUse(int newNr, int oldNr)
{
	nextRepNr[newNr] = nextRepNr[oldNr];
	nextRepNr[oldNr] = newNr;
	priorRepNr[newNr] = oldNr;
	if (nextRepNr[newNr] >=0)
		priorRepNr[nextRepNr[newNr]] = newNr;
	else
		lastInUseNr = newNr;
	//regardless
	nrAtThisLevel++;
	return;
}

int subsetHolder::removeFirstSlotNrFromInUse()
{
	int i;
	assert(firstInUseNr >=0);
	i = firstInUseNr;
	firstInUseNr = nextRepNr[i];
	if(firstInUseNr >=0) 
		priorRepNr[firstInUseNr] = -1;
	else 
		lastInUseNr = -1;
	//In either case
	nrAtThisLevel--;
	return i;
}

int subsetHolder::removeLastSlotNrFromInUse()
{
	int i;
	assert(lastInUseNr >=0);
	i = lastInUseNr;
	lastInUseNr = priorRepNr[i];
	if(lastInUseNr >=0) 
		nextRepNr[lastInUseNr] = -1;
	else 
		firstInUseNr = -1;
	//In either case
	nrAtThisLevel--;
	return i;
}

void subsetHolder::removeThisSlotNrFromInUse(int slotNr)
{
	int nextSlotNr, priorSlotNr;
	nextSlotNr = nextRepNr[slotNr];
	priorSlotNr = priorRepNr[slotNr];
	if (nextSlotNr >=0)
		priorRepNr[nextSlotNr] = priorSlotNr;
	else
		lastInUseNr = priorSlotNr;
	if (priorSlotNr >= 0)
		nextRepNr[priorSlotNr] = nextSlotNr;
	else
		firstInUseNr = nextSlotNr;
	//In either case
	nrAtThisLevel--;
	return;
}

RAandMID subsetHolder::removeFOrLMemberFromSmhInUse(int slotNr, insertLocType ilt)
{
	RAandMID RM;
	setMemberHolder * smh;
	assert(levelNr == 1);
	smh= repPtr[slotNr].smhPtr;
	if (ilt ==First)
		RM = smh->removeFirstFromMemberSubset();
	else
		RM = smh->removeLastFromMemberSubset();
	//regardless
		grandNrSpanned--;
		nrSpanned[slotNr]--;
		nrAtLevelRepd[slotNr]--;
		assert(nrAtLevelRepd[slotNr]==smh->nrAtThisLevel);
	if(smh->nrAtThisLevel ==0)
		return RM;
	//else
	minRA[slotNr] = smh->minRA;
	mIDofMin[slotNr] = smh->mIDofMin;
	maxRA[slotNr] = smh->maxRA;
	mIDofMax[slotNr] = smh->mIDofMax;

//In case grand min or max has changed:
	grandMinRA = minRA[firstInUseNr];
	mIDofGrandMin = mIDofMin[firstInUseNr];
	grandMaxRA = maxRA[lastInUseNr];
	mIDofGrandMax = mIDofMax[lastInUseNr];	

	return RM;
}

removeReturnCode subsetHolder::removeThisMemberFromSmhInUse(int slotNr, 
												RAType RA, memberType mID)
{
	removeReturnCode RCC;
	setMemberHolder * smh;
	assert(levelNr == 1);
	smh= repPtr[slotNr].smhPtr;
	RCC= smh->removeThisFromMemberSubset(RA, mID);
	if (RCC!=removed) return RCC;
//  else, this member removed..
	grandNrSpanned--;
	nrSpanned[slotNr]--;
	nrAtLevelRepd[slotNr]--;
		
	if(smh->nrAtThisLevel ==0) 	return RCC;
//	else
	minRA[slotNr] = smh->minRA;
	mIDofMin[slotNr] = smh->mIDofMin;
	maxRA[slotNr] = smh->maxRA;
	mIDofMax[slotNr] = smh->mIDofMax;
	
	assert(firstInUseNr>=0);
	if ((minRA[firstInUseNr] < grandMinRA) ||
		( (minRA[firstInUseNr]==grandMinRA) &&
		(mIDofMin[firstInUseNr] < mIDofGrandMin)))
	{
		grandMinRA = minRA[firstInUseNr];
		mIDofGrandMin = mIDofMin[firstInUseNr];
	}

	assert(lastInUseNr >= 0);
	if ((maxRA[lastInUseNr] > grandMaxRA) ||
		( (maxRA[lastInUseNr]==grandMaxRA) &&
		(mIDofMax[lastInUseNr] > mIDofGrandMax)))
	{
		grandMaxRA = maxRA[lastInUseNr];
		mIDofGrandMax = mIDofMax[lastInUseNr];	
	}
	return RCC;
}

RAandMID subsetHolder::removeFOrLMemberFromSshInUse(int slotNr, insertLocType ilt)
{
	RAandMID RM;
	subsetHolder * ssh;
	assert(levelNr > 1);
	ssh= repPtr[slotNr].sshPtr;
	assert(nrSpanned[slotNr] >0);
	RM = ssh->removeFOrLMemberFromSubsetHolder(ilt);
	grandNrSpanned--;
	nrSpanned[slotNr]--;
	nrAtLevelRepd[slotNr] = ssh->nrAtThisLevel;
	assert(nrSpanned[slotNr] == ssh->grandNrSpanned);
	if(ssh->grandNrSpanned ==0) 
	{
		minRA[slotNr]=largeRA;
		maxRA[slotNr]= smallRA;
		mIDofMin[slotNr] = NULLmID;
		mIDofMax[slotNr] = NULLmID;
		return RM;
	}
	else
	{
		minRA[slotNr] = ssh->grandMinRA;
		mIDofMin[slotNr] = ssh->mIDofGrandMin;
		maxRA[slotNr] = ssh->grandMaxRA;
		mIDofMax[slotNr] = ssh->mIDofGrandMax;
	}
	
	assert(grandNrSpanned > 0);
	assert(firstInUseNr>=0);

//In case grand min or max has changed:
	grandMinRA = minRA[firstInUseNr];
	mIDofGrandMin = mIDofMin[firstInUseNr];
	grandMaxRA = maxRA[lastInUseNr];
	mIDofGrandMax = mIDofMax[lastInUseNr];	

	return RM;
}

removeReturnCode subsetHolder::removeThisMemberFromSshInUse(int slotNr, 
										RAType RA, memberType mID)
{
	removeReturnCode RCC;
	subsetHolder * ssh;
	assert(levelNr > 1);
	ssh= repPtr[slotNr].sshPtr;
	assert(nrSpanned[slotNr] >0);
	RCC = ssh->removeThisMemberFromSubsetHolder(RA, mID);
	grandNrSpanned--;
	nrSpanned[slotNr]--;
	nrAtLevelRepd[slotNr] = ssh->nrAtThisLevel;
	assert(nrSpanned[slotNr] == ssh->grandNrSpanned);
	if(ssh->grandNrSpanned ==0) 
	{
		minRA[slotNr]=largeRA;
		maxRA[slotNr]= smallRA;
		mIDofMin[slotNr] = NULLmID;
		mIDofMax[slotNr] = NULLmID;
		return RCC;
	}
//	else....
	minRA[slotNr] = ssh->grandMinRA;
	mIDofMin[slotNr] = ssh->mIDofGrandMin;
	maxRA[slotNr] = ssh->grandMaxRA;
	mIDofMax[slotNr] = ssh->mIDofGrandMax;
	
	assert(grandNrSpanned > 0);
	assert(firstInUseNr>=0);

//In case grand min or max has changed:
	grandMinRA = minRA[firstInUseNr];
	mIDofGrandMin = mIDofMin[firstInUseNr];
	grandMaxRA = maxRA[lastInUseNr];
	mIDofGrandMax = mIDofMax[lastInUseNr];	

	return RCC;
}



setMemberHolder * subsetHolder::removeFOrLSmhFromSsh(insertLocType ilt)
{
	setMemberHolder *smh;
	int i;

	assert((firstInUseNr>-1) && (levelNr==1) );
	if (ilt == atFront)
	{
		smh = dropSmhFromRep(firstInUseNr);
		i = removeFirstSlotNrFromInUse();
		fileFreeSlotNr(i);
	}
	else
	{
		smh = dropSmhFromRep(lastInUseNr);
		i = removeLastSlotNrFromInUse();
		fileFreeSlotNr(i);
	}

//In case grand min or max has changed:
	grandMinRA = minRA[firstInUseNr];
	mIDofGrandMin = mIDofMin[firstInUseNr];
	grandMaxRA = maxRA[lastInUseNr];
	mIDofGrandMax = mIDofMax[lastInUseNr];
	
	return smh;
}

setMemberHolder * subsetHolder::removeFOrLSmhFromSshInUse(int slotNr, insertLocType ilt)
{
	subsetHolder * ssh;
	setMemberHolder * smh;
	long nrLowerSshFormerlySpanned;

	assert (levelNr == 2);
	ssh = repPtr[slotNr].sshPtr;
	nrLowerSshFormerlySpanned = ssh->grandNrSpanned;
	smh = ssh ->removeFOrLSmhFromSsh(ilt);
	assert(smh != NULL);

	nrSpanned[slotNr] = ssh->grandNrSpanned;
	grandNrSpanned -= nrLowerSshFormerlySpanned - nrSpanned[slotNr];
	nrAtLevelRepd[slotNr] = ssh->nrAtThisLevel;
	minRA[slotNr] = ssh->grandMinRA;
	mIDofMin[slotNr] = ssh->mIDofGrandMin;
	maxRA[slotNr] = ssh->grandMaxRA;
	mIDofMax[slotNr] = ssh->mIDofGrandMax;

//In case grand min or max has changed:
	grandMinRA = minRA[firstInUseNr];
	mIDofGrandMin = mIDofMin[firstInUseNr];
	grandMaxRA = maxRA[lastInUseNr];
	mIDofGrandMax = mIDofMax[lastInUseNr];	

	return smh;
}

subsetHolder * subsetHolder::removeFOrL_LowerSshFromSsh(insertLocType ilt)
{
	subsetHolder * ssh;
	int i;

	assert(levelNr >=2);
	if (ilt == First)
	{
		ssh = dropSshFromRep(firstInUseNr);
		i = removeFirstSlotNrFromInUse();
	}
	else
	{
		ssh = dropSshFromRep(lastInUseNr);
		i = removeLastSlotNrFromInUse();
	}
	fileFreeSlotNr(i);
	return ssh;
}

subsetHolder * subsetHolder::removeFOrL_LowerSshFromSshInUse
									(int slotNr, insertLocType ilt)
{
	subsetHolder * ssh, * evenLowerSsh;
	long nrLowerSshFormerlySpanned;

	assert (levelNr > 2);
	ssh = repPtr[slotNr].sshPtr;
	nrLowerSshFormerlySpanned = ssh->grandNrSpanned;
	evenLowerSsh = ssh ->removeFOrL_LowerSshFromSsh(ilt);
	assert(evenLowerSsh != NULL);

	nrSpanned[slotNr] = ssh->grandNrSpanned;
	grandNrSpanned -= nrLowerSshFormerlySpanned - nrSpanned[slotNr];
	nrAtLevelRepd[slotNr] = ssh->nrAtThisLevel;
	minRA[slotNr] = ssh->grandMinRA;
	mIDofMin[slotNr] = ssh->mIDofGrandMin;
	maxRA[slotNr] = ssh->grandMaxRA;
	mIDofMax[slotNr] = ssh->mIDofGrandMax;

//In case grand min or max has changed:
	grandMinRA = minRA[firstInUseNr];
	mIDofGrandMin = mIDofMin[firstInUseNr];
	grandMaxRA = maxRA[lastInUseNr];
	mIDofGrandMax = mIDofMax[lastInUseNr];	

	return evenLowerSsh;
}

setMemberHolder * subsetHolder::removeThisSmhFromSsh
					(int slotNr)
{
	setMemberHolder * smh;
	smh = dropSmhFromRep(slotNr);
	removeThisSlotNrFromInUse(slotNr);
	fileFreeSlotNr(slotNr);
	return smh;
}

/*
subsetHolder * subsetHolder::removeThisLowerSshFromSsh  //NEVER CALLED
				(int slotNr)	//done by would-be caller. Save in case useful someday
{
	subsetHolder * ssh;
	ssh = dropSshFromRep(slotNr);
	removeThisSlotNrFromInUse(slotNr);
	fileFreeSlotNr(slotNr);
	return ssh;
}
*/

RAandMID subsetHolder::removeFOrLMemberFromSubsetHolder(insertLocType ilt)
{
	RAandMID RM, RM2;
	int i, count, slotNr;
	setMemberHolder * smh;
	subsetHolder * ssh;

	if (ilt == First)
		slotNr = firstInUseNr;
	else
		slotNr = lastInUseNr;

	if (levelNr == 1)  //contains SMHs
	{
		RM = removeFOrLMemberFromSmhInUse(slotNr, ilt);
		if (nrAtLevelRepd[slotNr] > 0)
			goto updateGrandMinMax;

		//else:  First or last slot is empty. 
		//       Delete or use to rebalance inventory
		if (nrAtThisLevel==1)  //No inventory to rebalance
			goto DeleteSmh;

        //else...
		if (ilt == First)
			i = nextRepNr[slotNr];
		else
			i = priorRepNr[slotNr];
		assert(i >=0);

		if (nrAtLevelRepd[i] < aLotOfMembers)   //Proceed to delete
		{
DeleteSmh:		
			smh= dropSmhFromRep(slotNr);
			removeThisSlotNrFromInUse(slotNr);
			fileFreeSlotNr(slotNr);
//			smh->~setMemberHolder();
			delete smh;
			goto updateGrandMinMax;
		}
		//else rebalance inventory:
		
		for (count=0;count<aFewMembers;count++)
		{
			RM2 = removeFOrLMemberFromSmhInUse(i,ilt);
			fileMemberIntoSmhInUse(slotNr, 
					RM2.RM_rankingAtt, RM2.RM_memberID);
		}	
		goto updateGrandMinMax;
	}

	//else contains SSHs
	assert (levelNr > 1);

	RM = removeFOrLMemberFromSshInUse(slotNr, ilt);
	if (nrAtLevelRepd[slotNr] > 0)
	goto updateGrandMinMax;
	
	//else  delete SSH or use to rebalance load
	if (nrAtThisLevel == 1)  //nothing to rebalance
		goto deleteSSH;

	if (ilt == First)
		i = nextRepNr[slotNr];
	else
		i = priorRepNr[slotNr];
	assert(i >=0);

	if (nrAtLevelRepd[i] < aLotOfSubsets)  //proceed to delete SSH
	{
deleteSSH:
	ssh= dropSshFromRep(slotNr);
	removeThisSlotNrFromInUse(slotNr);
	fileFreeSlotNr(slotNr);
//	ssh->~subsetHolder();
	delete ssh;
	goto updateGrandMinMax;
	}
		
	//else rebalance
		
	for (count=0;count<aFewSubsets;count++)
	{
		RM2 = removeFOrLMemberFromSshInUse(i,ilt);
		fileMemberIntoLowerSshInUse(slotNr, 
				RM2.RM_rankingAtt, RM2.RM_memberID);
	}
		
	goto updateGrandMinMax;

updateGrandMinMax:
	if(nrAtThisLevel==0)
	{
		grandMinRA = largeRA;
		grandMaxRA = smallRA;
		mIDofGrandMin = NULLmID;
		mIDofGrandMax = NULLmID;
		return RM;
	}
	
	//else...
	assert(firstInUseNr>-1 && lastInUseNr>-1);
	grandMinRA = minRA[firstInUseNr];
	mIDofGrandMin = mIDofMin[firstInUseNr];
	grandMaxRA = maxRA[lastInUseNr];
	mIDofGrandMax = mIDofMax[lastInUseNr];
	return RM;
}


removeReturnCode subsetHolder::removeThisMemberFromSubsetHolder(RAType RA,memberType mID)
{
	removeReturnCode RCC;
	int place, nextPlace;
	setMemberHolder * smh;
	subsetHolder * ssh;

//Find slot where member may be located
	if ((RA<minRA[firstInUseNr]) || ((RA==minRA[firstInUseNr])&&
		(mID < mIDofMin[firstInUseNr])))
		return notFound;
	for (place = firstInUseNr; place>=0; place = nextPlace)
	{
		if((RA<maxRA[place]) || ((RA==maxRA[place])&&
			(mID <= mIDofMax[place]))) 
			goto MayHaveFound_TryRemoving;
		nextPlace = nextRepNr[place];
		if ((nextPlace<0) || 
			(RA<minRA[nextPlace]) || 
			((RA==minRA[nextPlace]) && 	(mID<mIDofMin[nextPlace])))
			return notFound;
	}
	assert(0==1); //should not reach this point

MayHaveFound_TryRemoving:
	if (levelNr == 1)  //contains SMHs
	{
		RCC = removeThisMemberFromSmhInUse(place, RA, mID);
			if (nrAtLevelRepd[place] > 0)
			goto updateGrandMinMax;

		//else:  Slot is empty.  Delete 
		smh= dropSmhFromRep(place);
		removeThisSlotNrFromInUse(place);
		fileFreeSlotNr(place);
//		smh->~setMemberHolder();
		delete smh;
		goto updateGrandMinMax;
	}
		
	//else contains SSHs
	assert (levelNr > 1);

	RCC = removeThisMemberFromSshInUse(place, RA, mID);
	if (nrAtLevelRepd[place] > 0)
		goto updateGrandMinMax;
	
	//else lower SSH is empty.  Delete
	assert (nrSpanned[place]==0);
	ssh= dropSshFromRep(place);
	removeThisSlotNrFromInUse(place);
	fileFreeSlotNr(place);
//	ssh->~subsetHolder();
	delete ssh;
	goto updateGrandMinMax;

updateGrandMinMax:
	if(nrAtThisLevel==0)
	{
		grandMinRA = largeRA;
		grandMaxRA = smallRA;
		mIDofGrandMin = NULLmID;
		mIDofGrandMax = NULLmID;
		return RCC;
	}
	
	//else...
	assert(firstInUseNr>-1 && lastInUseNr>-1);
	grandMinRA = minRA[firstInUseNr];
	mIDofGrandMin = mIDofMin[firstInUseNr];
	grandMaxRA = maxRA[lastInUseNr];
	mIDofGrandMax = mIDofMax[lastInUseNr];
	return RCC;
			
}