/* File: Floorplan.cpp * Author: Dan Gibson *         ECE 556 HW 3 * Contents: * Class Floorplan, representing a circuit * floorplan, and vital member functions * * Last modified: * Development platforms: Solaris 9, MS-DOS, WINNT * Intended platforms: Solaris 9 */#include <stdio.h>
#include <stdlib.h>#include "Floorplan.h"Floorplan::Floorplan() {  // panic - this shouldn't be called  list = tree = NULL;}/********************************************************** * Function name: Floorplan() - Constructor * Author: Dan Gibson * * Parameters: * * first_index		An integer, the index value of the *					first module * first_height		An integer, the height of the first mod. * first_width		An integer, the width of the first mod. * second_index		An integer, the index value of the *					second mod. * second_height	An integer, the height of the second mod. * second_width		An integer, the width of the second mod. * * Return value * * **********************************************************/Floorplan::Floorplan(int first_index,					 int first_height,					 int first_width,					 int second_index,					 int second_height,					 int second_width) {	tree = new Operator();	tree->myLeftChild = new Module();	tree->myRightChild = new Module();	// setup first node	tree->myLeftChild->myIndex = first_index;	tree->myLeftChild->myHeight = first_height;	tree->myLeftChild->myWidth = first_width;	// setup second node	tree->myRightChild->myIndex = second_index;	tree->myRightChild->myHeight = second_height;	tree->myRightChild->myWidth = second_width;	// setup primary operator	tree->myIndex = (rand()%2==0) ? 'V' : 'H';	GenerateList();	stack = NULL;}Floorplan::Floorplan(Operator * newTree) {	tree = newTree;	GenerateList();	stack = NULL;}Floorplan::~Floorplan() {	Module * current = list;	// seek to end of list	while(current->myNext!=NULL) current=current->myNext;	// iteratively delete the end of the list	while(current!=list) {		current = current->myPrev;		if(current->myNext->myType==OperatorType) {			delete ((Operator *)current->myNext);		} else {			delete ((Module *)current->myNext);		}			}	delete list;	if(stack!=NULL) delete stack;}void Floorplan::AddModule(int index, int width, int height) {	Operator * op = new Operator();	op->myLeftChild = tree;	op->myIndex = (rand()%2==0) ? 'V' : 'H';	tree = op;	tree->myRightChild = new Module();	tree->myRightChild->myIndex = index;	tree->myRightChild->myWidth = width;	tree->myRightChild->myHeight = height;	GenerateList();	return;	}// arg index_of_first is from 1 to nModules,// and represents the MODULE index, ignoring// the role of operators completelybool Floorplan::M1(unsigned int index_of_first) {	return SwapAdjacentOperands(index_of_first);}bool Floorplan::SwapAdjacentOperands(unsigned int index_of_first) {	Module * first, *second;	Operator *first_parent, *second_parent;	first = list->FindModuleWithIndex(index_of_first);	// index cannot be found	if(first==NULL) return false;	second = first->myNext;	while(second!=NULL) {		if(second->myType==ModuleType) {			// second op has been found			break;		}		second = second->myNext;	};	// can't swap the last module	if(second==NULL) return false;	// now have the two operands to be swapped,	// so do the swapping!	first_parent = (Operator *) first->FindParent();	second_parent = (Operator *) second->FindParent();	// now replace "first" with "second"	if(first_parent->myRightChild == first) {		// first is the right child of its parent		first_parent->myRightChild = second;	} else {		// first is the left child of its parent		first_parent->myLeftChild = second;	}	// now replace "second" with "first"	if(second_parent->myRightChild == second ) {		// second is the right child of its parent		second_parent->myRightChild = first;	} else {		// second is the left child of its parent		second_parent->myLeftChild = first;	}	// all this tree restructuring has made the list	// pointers out-of-date, so regenerate the list	// from the tree	GenerateList();	return true;}// both of these return the # of inversions done,// so 0 is an erroneous return valueunsigned int Floorplan::M2(unsigned int first_operator) {	return ChainInvert(first_operator);}unsigned int Floorplan::ChainInvert(unsigned int first_operator) {	// number of inversions performed	unsigned int inversions = 0;	// can't invert operators that don't exist	if(first_operator>=nOperators) return inversions;	// seek to the correct operator	Module * current = list; 	int current_number = -1;	// iterate to the correct operator	while((unsigned int)current_number!=first_operator) {				// advance to the next operator if needed		if(current_number!=-1) current = current->myNext;		// iterate to the next operator		while(current!=NULL && current->myType==ModuleType) {			current = current->myNext;				}		current_number++;		if(current==NULL) {			// this should theoretically never happen,			// that is, the first operator couldn't be found			return inversions;		}	}	// iterate now points to the specified operator	// but that may not be the first operator in a chain--	// if its not, just seek backward to the first operator	while(current->myType==OperatorType) current = current->myPrev;	current = current->myNext;	// current now points to the first operator to be inverted	while(current!=NULL && current->myType==OperatorType) {		// this is an operator in the chain:		// invert it!!		if(current->myIndex == 'V') {			current->myIndex = 'H';		} else {			current->myIndex = 'V';		}		current = current->myNext;		inversions++;	}	return inversions;}bool Floorplan::M3OK() {	return list->M3OK(false,false);}unsigned int Floorplan::M3(unsigned int index) {	return SwapAdjacentOperandAndOperator(index);}unsigned int Floorplan::SwapAdjacentOperandAndOperator(unsigned int index) {	Module *first, *second, *current;	bool mod_before_op;	// can't find operands/operators that don't exist	if(index>nModules+nOperators) return 1;	// find the first to swap	first = list->FindNthModule(index,0);	if(first==NULL) {		// this should theoretically never happen		return 2;	}//	fprintf(stdout,"Looking for the next...\n");	if(first->myType==ModuleType) {		// next must be an operator for this to be		// a potentially valid swap		if(first->myNext==NULL || first->myNext->myType==ModuleType) {			// can't swap two modules in this function--call M1			return 3;		} else {			second = first->myNext;			mod_before_op = true;		}	} else {		// next must be an operand for this to be		// a potentially valid swap		if(first->myNext==NULL || first->myNext->myType==OperatorType) {			// can't swap two operators			return 4;		} else {			second = first->myNext;			mod_before_op = false;		}	}//	fprintf(stdout,"Discovered that the %s is before the %s\n",//		(mod_before_op) ? "Module" : "Operator",//		(mod_before_op) ? "Operator" : "Module");	// A legitimate operand/operator pair or	// operator/operand pair has been found.	// check to ensure that e(i-1)!=e(i+1)	// AKA that swapping the two will yield a	// normalized tree	if(mod_before_op) {		// first is a module		// second is an operator		if(first->myPrev!=NULL) {			if(first->myPrev->myType==OperatorType) {				if(first->myPrev->myIndex==second->myIndex) {					// swap will create a non-normalized tree					return 5;				}			}		}	} else {		// first is an operator		// second is a module		if(second->myNext!=NULL) {			if(second->myNext->myType==OperatorType) {				if(second->myNext->myIndex==first->myIndex) {					// swap will create a non-normalized tree					return 6;				}			}		}	}//	fprintf(stdout,"Normalization property OK\n");	// check the balloting property: do balloting up to	// this point, do some special handling for mod and op,	// then finish the balloting	int ballot = 0;	current = list;	while(current!=NULL) {		if(current==first) {			// pretend that first and second			// have been interchanged			// If first is an operand, decrement the ballot,			// otherwise second is the operand, so decrement			// the ballot			if(mod_before_op)				ballot--;			else				ballot++;		} else if (current==second) {			// pretend that mod and op			// have been interchanged			if(mod_before_op)				ballot++;			else				ballot--;		} else {			// do normal balloting			if(current->myType==ModuleType) {				ballot++;			} else {				ballot--;			}		}		if(ballot<=0) return 7; // balloting failed		current = current->myNext;	}//	fprintf(stdout,"Balloting property OK\n");	// if we get here, then both the normalized	// and balloting properties hold for the proposed move,	// so the move is legal and should be accepted.	// So do the swap!!	// put second into first's place	if(first->myPrev==NULL) {		list = second;	} else {		first->myPrev->myNext = second;	}	first->myNext = second->myNext;	second->myNext = first;	GenerateListBackward();	// We've now done terrible things to the tree,	// so we have to regrow it//	fprintf(stdout,"Swap complete...Dumping list:\n");//	dumpList();//	fprintf(stdout,"Generating tree...\n");	GenerateTree();	return 0;}bool Floorplan::M4(unsigned int index_of_module) {	return RotateModule(index_of_module);}bool Floorplan::RotateModule(unsigned int index_of_module) {	Module * mod = list->FindModuleWithIndex(index_of_module);	if(mod==NULL) return false;	// got the module, now rotate it	unsigned short temp;	temp = mod->myHeight;	mod->myHeight = mod->myWidth;	mod->myWidth = temp;	return true;}int Floorplan::getArea() {
	Rect * myRects = tree->getRectangles();
	Rect * rect = myRects; // current rectangle
	int min_area = rect->x * rect->y;
	
	while(rect!=NULL) {
		// see if current rect smaller than
		// min_area
		if(min_area> rect->x * rect->y)
			min_area = rect->x * rect->y;

		rect = rect->myNext;
	}

	// cleanup the last of the memory
	rect = myRects;
	myRects = rect->myNext;
	while(rect!=NULL) {
		delete rect;
		rect = myRects;
		if(myRects!=NULL) myRects = myRects->myNext;
	}

	return min_area;
/*	return tree->getWidth() * tree->getHeight(); */}/********************************************************** * Function name: Clone() * Author: Dan Gibson * * Parameters: * * Return value * * Clone() returns a new Floorplan object, identical to * (this) * **********************************************************/Floorplan * Floorplan::Clone() {	Operator * newTree;	newTree = tree->Clone();	Floorplan * retval = new Floorplan(newTree);	return retval;	}void Floorplan::dumpTree() {	tree->dumpTree();}void Floorplan::dumpList() {	list->dumpList();}void Floorplan::GenerateListBackward() {	list->myPrev = NULL;	Module * current = list;	nModules = 0; nOperators = 0;	while(current!=NULL) {	//	printf("Visiting ");		// tally the operators and modules along the way		if(current->myType==OperatorType) {			nOperators++;		//	printf("Operator ");		} else {			nModules++;		//	printf("Module   ");		}	//	int printed = printf("%i ",current->myIndex);	//	for(int i=0;i<3-printed;i++) printf(" ");		if(current->myNext!=NULL) {			current->myNext->myPrev = current;	//		printed = printf(": %i",current->myNext->myIndex);	//		for(int j=0;j<4-printed;j++) printf(" ");	//		printf(" is myNext",current->myNext->myIndex);		}	//	printf("\n");		current = current->myNext;	}/*	while(!current->myNext==NULL) {		printf("Visiting current = %i:",current->myIndex);		if(current->myType==OperatorType) {			printf("Operator\n");			nOperators++;		} else {			printf("Module\n");			nModules++;		}		current->myNext->myPrev = current;		current = current->myNext;		int a = 0;		for(int i=0;i<100000000;i++) { a++; }	}*/	nOperators++; // count the last operator (the root)}void Floorplan::GenerateList() {		list = tree->GenerateListForward(NULL);		GenerateListBackward();	}void Floorplan::GenerateTree() {	// going to need a stack for this	if(stack==NULL) {		stack = new ModuleStack(getLength());	}	// add all the nodes to the stack	Module * current = list;	while(current!=NULL) {		stack->push(current);		current = current->myNext;	}	// Pop the root of the tree from the stack	tree = (Operator *) stack->pop();	// Recursively regenerate the tree	tree->GenerateTree(stack);}unsigned int Floorplan::getLength() {	return nModules+nOperators;}unsigned int Floorplan::getModuleCount() {	return nModules;}unsigned int Floorplan::getOperatorCount() {	return nOperators;}