ece368/Spring 2014/PA04/packing.c~

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "packing.h"

// read file and set node values
Node *load_file(char *filename){
	// open file for reading
	FILE *fptr = NULL;
	fptr = fopen(filename, "r");
	if (fptr == NULL){ // check for error
      printf("File name error.\n");
      return NULL;
    }
    
    // initialize variables and pointers
    Stack *stack = NULL; // used to store nodes and determine their order
    char curr = 0;

    // read values for each node
    while(!feof(fptr)){
		if(fscanf(fptr, "%c", &curr) == EOF){}
		else{
		Node *node = malloc(sizeof(Node));
		// check if parent or child node
		if(curr == '('){
		// child node
			// read values
			if(fscanf(fptr, "%le,%le)", &node->width, &node->height) == EOF){
				printf("Error reading file.\n");
				free(node);
				return NULL;
			}
			// initialize remaining values
			node->cutline = '-';
			node->xcord = 0;
			node->ycord = 0;
			node->left = NULL;
			node->right = NULL;
		} 
		else{
		// parent node
			// initialize values
			node->cutline = curr; // already read
			node->width = '-';
			node->height = '-';
			node->xcord = 0;
			node->ycord = 0;
			node->right = pop(stack);
			node->left = pop(stack);
		}
		push(stack, node);
    }
    Node *root = pop(stack);
    // clean up
	if(!fclose(fptr) == 0){
		printf("File close error.");
		return NULL;
	}
	return root;
}

void push(Stack *stack, Node *node){
	Stack *new = malloc(sizeof(Stack));
	new->node = node;
	new->next = stack;
}

Node *pop(Stack *stack){
	if(stack == NULL){
		return NULL;
	}
	Node *temp = stack->node;
	free(stack);
	return temp;
}

void free_stack(Stack *stack)
{
	Stack *temp = NULL;
	while(stack != NULL){
		free(stack->node);
		temp = stack;
		stack = stack->next;
		free(temp);
	}
}

// calculate dimensions based on binary tree structure
void set_dimensions(Node *root){
	// end recursion
	if(root->left == NULL && root->right == NULL){
		return;
	}
		
	// recurse
	set_dimensions(root->left);
	set_dimensions(root->right);
	
	if(root->cutline == 'V'){
		// add widths for vertzical cut	
		root->width = root->left->width + root->right->width;
		if(root->left->height >= root->right->height){
			root->height = root->left->height;
		}
		else{
			root->height = root->right->height;
		}
	}
	if(root->cutline == 'H'){
		// add heights for horizontal cut
		root->height = root->left->height + root->right->height;
		if(root->left->width >= root->right->width){
			root->width = root->left->width;
		}
		else{
			root->width = root->right->width;
		}
	}
}

// calculate coordinates based on binary tree structure
void set_coordinates(Node *root){
	// end recursion
	if(root->left == NULL && root->right == NULL){
		return;
	}
	
	if(root->cutline == 'V'){
		// left stays, right moves
		root->left->xcord = root->xcord;
		root->left->ycord = root->ycord;
		root->right->xcord = root->xcord + root->left->width;
		root->right->ycord = root->ycord;
	}
	
	if(root->cutline == 'H'){
		// right stays, left moves
		root->left->xcord = root->xcord;
		root->left->ycord = root->ycord + root->right->height;;
		root->right->xcord = root->xcord;
		root->right->ycord = root->ycord;
	}
		
	// recurse
	set_coordinates(root->left);
	set_coordinates(root->right);
}

// recursively reroot tree
void find_best_fit(Node *root, double *best_width, double *best_height){
	if(root == NULL){
		return;
	}
	set_dimensions(root);
	set_coordinates(root);
	if((((*best_width * *best_height) < (root->width * root->height))
		|| (((*best_width * *best_height) == (root->width * root->height)
		&& (*best_width < root->width)))) && root->cutline != '-'){
		*best_width = root->width;
		*best_height = root->height;
	}
	find_best_fit(root->left, best_width, best_height);
	find_best_fit(root->right, best_width, best_height);
}

// print nodes
void print_nodes_preorder(Node *root){
	if(root == NULL){
		return;
	}
	if(root->cutline == '-'){
		printf("(%le,%le)", root->width, root->height);
    }
    else{
    	printf("%c", root->cutline);
    }
	print_nodes_preorder(root->left);
	print_nodes_preorder(root->right);
}
void print_nodes_inorder(Node *root){
	if(root == NULL){
		return;
	}
	print_nodes_inorder(root->left);
	if(root->cutline == '-'){
		printf("(%le,%le)", root->width, root->height);
    }
    else{
    	printf("%c", root->cutline);
    }
	print_nodes_inorder(root->right);
}
void print_nodes_postorder(Node *root){
	if(root == NULL){
		return;
	}
	print_nodes_postorder(root->left);
	print_nodes_postorder(root->right);
	if(root->cutline == '-'){
		printf("(%le,%le)", root->width, root->height);
    }
    else{
    	printf("%c", root->cutline);
    }
}

// recurse through tree and save each node that represents a box
void save_boxes(char *filename, Node *root){
	// end recursion
	if(root == NULL){
		return;
	}

	// write to file
	FILE *fptr = fopen(filename, "w");
	if(root->cutline == '-'){
		fprintf(fptr, "%le %le %le %le\n", 
			root->width, 
			root->height, 
			root->xcord, 
			root->ycord);
	}
	
	// close file
	if(!fclose(fptr) == 0){ 
		printf("File close error.");
		return;
	}
	
	save_boxes(filename, root->left);
	save_boxes(filename, root->right);
}

// recursively free tree from memory
void free_tree(Node *root){
	// end recursion
	if(root == NULL){
		return;
	}
	
	// recurse
	free_tree(root->left);
	free_tree(root->right);
	
	// clean up
	free(root);
}