floorplan.cpp

test the resut l llke mjhue hbjhw hhww

/* 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 completely

bool 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 value
unsigned 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;
}