/* trees.cpp
 *
 * J Scott Cameron adapted for Genetic Images
 * from Hans Kuhlmann / Mike Hollick
 * available at
 * http://www.cis.upenn.edu/~hollick/genetic/paper2.html
 *
 * This file contains constructors for node types 
 */


#include <stdio.h>
#include <string.h>
#include "trees.h"


// node class constructor.  right now just initializes some common variables
Node::Node(void)
{ 
    // set number of children
    n_children = 0;
	
    // make this number invalid
    n_valid = 0;
	
    // set the parent ref to null
    parent = NULL;
}

// node class destructor.  this will reset the parent's pointer to this node
// to NULL, so nothing bad happens in the future.  it also invalidate's
// the parent's child count
Node::~Node(void)
{
    // reset the parent's pointer to this one.
	
    // if there is no parent, no problemo
    if (!parent)
		return;
	
    // if the parent is unary, this is easy
    if (parent->type == NODE_UNARY)
		// reset it
		((Unary_Node *)parent)->set_child(NULL);
	
    else {
        // in this case (binary) we need to figure out if this was the left or 
        // right child
        if (((Binary_Node *)parent)->get_left() == this)
			((Binary_Node *)parent)->set_left(NULL);
        else
			((Binary_Node *)parent)->set_right(NULL);
    }
	
	// force a new count
    parent->invalidate_count();
}




// this is called when the number of children of a node has changed.  it
// sets the invalid flag of this node and its parent to force a recalculation
// when the time comes
void Node::invalidate_count(void)
{
    // set the flag
    n_valid = 0;
	
    // if there is a parent, call the function
    if (parent)
		parent->invalidate_count();
}


// binary node constructor - takes the parent node and the function of this 
// node
Binary_Node::Binary_Node(Node *parent_node, Binary_Func *func)
{
    // just store the args
    parent = parent_node;
    f = func;
	
    // set the type
    type = NODE_BINARY;
	
    // set left and right to null initially
    left = right = NULL;
}

// destructor - deletes the right and left subtrees
Binary_Node::~Binary_Node(void)
{
    // delete the left
    delete left;
	
    // delete the right
    delete right;
}


// binary node counter
int Binary_Node::count(void)
{
    // if the current count is valid, return that value
    if (n_valid)
		return n_children;
    
    // otherwise recalculate
	
    // sum up the left and right (if they exist yet)
    n_children = 0;
    if (left)
		n_children += left->count();
    if (right)
		n_children += right->count();
	
    // count this node
    n_children++;
	
    // this is now valid
    n_valid = 1;
	
    return n_children;
}


// binary node finder function
Node *Binary_Node::find(int number)
{
    // if the number is 1, return this node
    if (number==1)
		return this;
	
    // decrement the number, to count this node
    number--;
	
    // check this value against the number of children in the left subtree.
    // if it is less or equal, the target node is in that subtree, so we 
    // should look there
    if ((left) && (number <= left->count()))
		return (left->find(number));
	
    // if its not in the left, subtract the number of children of the left
    // from the count
    if (left)
		number -= left->count();
	
    // check this against the number of children of the right subtree.
    // if it is less or equal, we will find it there
    if ((right) && (number <= right->count()))
		return (right->find(number));
	
    // if its not in the left or right, we are not going to find it
    return NULL;
}

// value function - pretty simple, just evaluate the function using the 
// left and right children's values
Val Binary_Node::value(void)
{
    // if the left or right does not exist, generate an error and return
    // zero
    if ((!left) || (!right)) {
        fprintf(stderr,"A binary node is missing a child!\n");
        return Val(0,0,0);
    }
	
    // return it
    return (f->eval(left->value(),right->value()));
}


// print function - prints the subtree's expression to a string.
char *Binary_Node::print(void)
{
    // if one of the children is missing, there is an error
    if ((!left) || (!right)) {
        char msg[80];
        sprintf(msg,"BINARY NODE MISSING CHILD");
        return (strdup(msg));
    }
	
    // get the left and right children's print strings
    char *left_str = left->print();
    char *right_str = right->print();
	
    // make a new string to hold the composite string
    // (left length + operator length + right length + 2 for the paren's)
    int newlength = strlen(left_str) + strlen(f->sign) + strlen(right_str) +
		2 + 1;
    char *newstr = new char[newlength];
	
    // print into it
    sprintf(newstr,"%s(%s,%s)",f->sign,left_str,right_str);
	
    // delete the 2 child strings
	//   delete left_str;
	//   delete right_str;
	
    // return the new string
    return (newstr);
}


// unary node constructor - like the binary one, but a different function type
Unary_Node::Unary_Node(Node *parent_node, Unary_Func *func)
{
    // just store the args
    parent = parent_node;
    f = func;
	
    // set the child to null initially
    child = NULL;
	
    // set the type
    type = NODE_UNARY;
}

// destructor deletes the child subtree
Unary_Node::~Unary_Node(void)
{
    // delete the child
    delete child;
}


// unary node counter
int Unary_Node::count(void)
{
    // if the current count is valid, return that value
    if (n_valid)
		return n_children;
	
    // otherwise recalculate
    n_children = 0;
	
    // add in the child size (if it exists yet)
    if (child)
		n_children += child->count();
	
    // count this node
    n_children++;
	
    // this is valid now
    n_valid = 1;
	
    return n_children;
}


// unary node finder function
Node *Unary_Node::find(int number)
{
    // if the number is 1, return this node
    if (number==1)
		return this;
	
    // decrement the number, to count this node
    number--;
	
    // check this value against the number of nodes in the child subtree.
    // if it is less or equal, the target node is below this node.
    if ((child) && (number <= child->count()))
		return (child->find(number));
	
    // if its not in the child subtree, we are not going to find it
    return NULL;
}


// unary node value function.  checks for a child, and evaluates f using
// its value
Val Unary_Node::value(void)
{
    // check for missing child
    if (!child) {
        fprintf(stderr,"A unary node is missing its child!\n");
        return Val(0,0,0);
    }
	
    return (f->eval(child->value()));
}


// print function - prints the subtree's expression to a string.
char *Unary_Node::print(void)
{
    // if one the child is missing, there is an error
    if (!child) {
        char msg[80];
        sprintf(msg,"UNARY NODE MISSING CHILD");
        return (strdup(msg));
    }
	
    // get the child's print string
    char *child_str = child->print();
	
    // make a new string to hold the composite string
    // (operator length + child length + 2 for the paren's)
    int newlength = strlen(child_str) + strlen(f->sign) + 2 + 1;
    char *newstr = new char[newlength];
	
    // print into it
    sprintf(newstr,"%s(%s)",f->sign,child_str);
	
    // delete the child's string
	//    delete child_str;
	
    // return the new string
    return (newstr);
}



// constant terminal node constructor.  takes parent and const value
Terminal_Const::Terminal_Const(Node *parent_node, Val c)
{
    // just store them again
    parent = parent_node;
    constant = c;
	
    // set the type
    type = NODE_CONST;
}


// constant terminal node find function
Node *Terminal_Const::find(int i)
{
    if (i==1)
		return this;
    else
		return NULL;
}


// constant terminal node print function
char *Terminal_Const::print(void)
{
    // just print the value to a string
    char prn[40];
    sprintf(prn,"#(%f,%f,%f)",constant.r,constant.g,constant.b);
	
    // make a copy of it
    char *newstr = new char[strlen(prn)+1];
    strcpy(newstr,prn);
    
    // return the copy
    return newstr;
}




// variable terminal node constructor.  like the above, but stores a ref
Terminal_Var::Terminal_Var(Node *parent_node, Variable *v)
{
    // uh, store them
    parent = parent_node;
    var = v;
	
    // set the type
    type = NODE_VAR;
}

// constant terminal node find function
Node *Terminal_Var::find(int i)
{
    if (i==1)
		return this;
    else
		return NULL;
}

// variable terminal node print function
char *Terminal_Var::print(void)
{
    // make a copy of the variable name
    char *newstr = new char[strlen(var->name)+1];
    strcpy(newstr,var->name);
	
    // return the copy
    return newstr;
}


// this recursively copies a tree.  it takes a pointer to the tree to be
// copied and a pointer to the parent of the new tree.  it returns a pointer
// to the new tree.  
Node *tree_copy(Node *src, Node *parent)
{
    // make a new node of the correct type, then go to the children if needed
    switch (src->type) {
        
        Node *dest;
		
	case NODE_BINARY: {
		// less casting
		Binary_Node *bn = (Binary_Node *)src;
		// make the new node
		dest = (Node *)new Binary_Node(parent,bn->get_func());
		
		// do the left child
		((Binary_Node *)dest)->set_left(tree_copy(bn->get_left(),dest));
		
		// do the right child
		((Binary_Node *)dest)->set_right(tree_copy(bn->get_right(),dest));
        
		return dest;
					  }
		
	case NODE_UNARY: {
		// less casting
		Unary_Node *un = (Unary_Node *)src;
		// make the new node
		dest = (Node *)new Unary_Node(parent,un->get_func());
		
		// do the child
		((Unary_Node *)dest)->set_child(tree_copy(un->get_child(),dest));
		
		return dest;
					 }
		
	case NODE_CONST:
        // make the new node
        dest = (Node *)new Terminal_Const(parent,src->value());
		
        return dest;
		
        
	case NODE_VAR:
        // make the new node
        dest = (Node *)new Terminal_Var(parent,((Terminal_Var *)src)->val_p());
		
        return dest;
    }
}