/* procedure printTree prints a syntax tree to the
 * listing file using indentation to indicate subtrees
 */
void printTree( TreeNode * tree )
{ int i;
  INDENT;
  while (tree != NULL) {
    printSpaces();
    if (tree->nodekind==StmtK){
      switch (tree->kind.stmt) {
        case IfK:
          fprintf(listing,"If\n");
          break;
        case RepeatK:
          fprintf(listing,"Repeat\n");
          break;
        case ForK:
          fprintf(listing,"For\n");
          break;
        case AssignK:
          fprintf(listing,"Assign to: %s\n",tree->attr.name);
          break;
        case ReadK:
          fprintf(listing,"Read: %s\n",tree->attr.name);
          break;
        case WriteK:
          fprintf(listing,"Write\n");
          break;
        default:
          fprintf(listing,"Unknown ExpNode kind\n");
          break;
      }
    }
    else if (tree->nodekind==ExpK){
      switch (tree->kind.exp) {
        case OpK:
          fprintf(listing,"Op: ");
          printToken(tree->attr.op,"\0");
          break;
        case ConstK:
          fprintf(listing,"Const: %d\n",tree->attr.val);
          break;
        case IdK:
          fprintf(listing,"Id: %s\n",tree->attr.name);
          break;
        default:
          fprintf(listing,"Unknown ExpNode kind\n");
          break;
      }
    }
    else fprintf(listing,"Unknown node kind\n");
    for (i=0;i<MAXCHILDREN;i++)
         printTree(tree->child[i]);
    tree = tree->sibling;
  }
  UNINDENT;
}

int search(Board b, int maxDepth, int m, int n)
{
	searchNode* head = new searchNode(b);
	nodeCounter = 0;
	std::cout << "\n** R.Reti Endgame Board **\n";
	head->printBoardImage();
	int topHeurisic = _search(head,maxDepth,0,UNSET);
	printTree(head,m,n);
	printBest(head);
	return topHeurisic;
}

void Test(char* testName, BinaryTreeNode* pRootOfTree)
{
    if(testName != NULL)
        printf("%s begins:\n", testName);

    printTree(pRootOfTree);

    BinaryTreeNode* pHeadOfList = convertBSTToList(pRootOfTree);

    PrintDoubleLinkedList(pHeadOfList);
}

// Prints the tree to the screen in a readable fashion. It should look just like
// Racket code; use parentheses to indicate subtrees.
void printTree(Value *tree) {    
    Value *list_pointer = tree;
    
    // handle printing dependent on what type the item in the list is.
    while ((*list_pointer).type == CONS_TYPE) {
        Value *car_of_list_pointer = car(list_pointer);
        //printf("%u", (*car_of_list_pointer).type);
        
        switch ((*car_of_list_pointer).type) {
            case STR_TYPE:
                printf("%s", (*car_of_list_pointer).s);
                break;
            case DOUBLE_TYPE:
                printf("%f", (*car_of_list_pointer).d);
                break;
            case INT_TYPE:
                printf("%i", (*car_of_list_pointer).i);
                break;
            case CONS_TYPE:
                printf("(");
                printTree(car_of_list_pointer);
                printf(")");
                break;
            case NULL_TYPE:
                printf("()");
                break;
            case OPEN_TYPE:
                // do nothing.
                break;
            case CLOSE_TYPE:
                // do nothing.
                break;
            case BOOL_TYPE:
                if ((*car_of_list_pointer).i == 1) {
                    printf("#t");
                } else {
                    printf("#f");
                }
                break;
            case SYMBOL_TYPE:
                printf("%s", (*car_of_list_pointer).s);
                break;
            case PTR_TYPE:
                break;
        }
        
        if ((*((*list_pointer).c).cdr).type != NULL_TYPE) {
            printf(" ");
        }
        
        
        list_pointer = ((*list_pointer).c).cdr;
    }
}

int main(int argc, char *argv[])
{	
  struct Tree *gameTree	= malloc (sizeof(struct Tree));
	gameTree->root = parseFile();
	
	if (DEBUG) printTree(gameTree);
	play (gameTree);
	writeFile(gameTree);
  clearTree(gameTree);
	return 0;
}

int main( int argc, char * argv[] )
{ TreeNode * syntaxTree;
  char pgm[120]; /* source code file name */
  if (argc != 2)
    { fprintf(stderr,"usage: %s <filename>\n",argv[0]);
      exit(1);
    }
  strcpy(pgm,argv[1]) ;
  if (strchr (pgm, '.') == NULL)
     strcat(pgm,".cm");
  source = fopen(pgm,"r");
  if (source==NULL)
  { fprintf(stderr,"File %s not found\n",pgm);
    exit(1);
  }
  listing = stdout; /* send listing to screen */
  fprintf(listing,"\nTINY COMPILATION: %s\n",pgm);
#if NO_PARSE
  while (getToken()!=ENDFILE);
#else
  syntaxTree = parse();
  if (TraceParse) {
    fprintf(listing,"\nSyntax tree:\n");
    printTree(syntaxTree);
  }
#if !NO_ANALYZE
  if (! Error)
  { if (TraceAnalyze) fprintf(listing,"\nBuilding Symbol Table...\n");
    buildSymtab(syntaxTree);
    if (TraceAnalyze) fprintf(listing,"\nChecking Types...\n");
    typeCheck(syntaxTree);
    if (TraceAnalyze) fprintf(listing,"\nType Checking Finished\n");
  }
#if !NO_CODE
  if (! Error)
  { char * codefile;
    int fnlen = strcspn(pgm,".");
    codefile = (char *) calloc(fnlen+4, sizeof(char));
    strncpy(codefile,pgm,fnlen);
    strcat(codefile,".tm");
    code = fopen(codefile,"w");
    if (code == NULL)
    { printf("Unable to open %s\n",codefile);
      exit(1);
    }
    codeGen(syntaxTree,codefile);
    fclose(code);
  }
#endif
#endif
#endif
  fclose(source);
  return 0;
}

void printTree(huffmanTree* completed)
{
	if(isLeaf(completed))
	{
		printdepthOfNode(completed);
		return;
	}

	if(completed->left!=NULL)
	{
		printTree(completed->left);
	}

	if(completed->right!=NULL)
	{
		printTree(completed->right);
	}

	return;
}

int main(int argc, const char * argv[]) {
    node<int> *root = new node<int>;
    root->data = 0;
    node<int> *child1 = new node<int>;
    child1->data = 1;
    node<int> *child5 = new node<int>;
    child5->data = 5;
    node<int> *child3 = new node<int>;
    child3->data = 3;
    node<int> *child4 = new node<int>;
    child4->data = 4;
    node<int> *child2 = new node<int>;
    child2->data = 2;
    node<int> *child12 = new node<int>;
    child12->data = 12;
    node<int> *child6 = new node<int>;
    child6->data = 6;
    node<int> *child9 = new node<int>;
    child9->data = 9;
    node<int> *child8 = new node<int>;
    child8->data = 8;
    node<int> *child7 = new node<int>;
    child7->data = 7;

    child6->left = child4;
    child4->parent = child6;
    child6->right = child9;
    child9->parent = child6;
    child4->left = child3;
    child3->parent = child4;
    child4->right = child5;
    child5->parent = child4;
    child3->left = child1;
    child1->parent = child3;
    child9->left = child7;
    child7->parent = child9;


    printTree(child6);

    node<int> *ancestor = findCommonAncestor(child1, child9);
    if ( ancestor )
        std::cout << "\nfound common ancestor = " << ancestor->data << "\n";
    else
        std::cout << "\nno common ancestor found\n";

    ancestor = findCommonAncestor(child9, child1);
    if ( ancestor )
        std::cout << "\nsearching the other way = " << ancestor->data << "\n";
    else
        std::cout << "\nno common ancestor found\n";

    return 0;
}

void printTreeList(ListObject * trees, int indent)
{

    if (trees == 0) {

        return;

    }

    printTree(trees->value, indent);

    while (trees->next != 0) {

        trees = trees->next;

        printTree(trees->value, indent);

    }

}

void XMLParser::printTree(xmlNodePtr start, int depth) const
{
	for(int i=0;i<depth;i++)
		printf("%d",(i+1)%10);
	printf("\"%s\":\"%s\"\n",(start->name),this->getNodeContent(start).c_str());
	xmlNodePtr i = this->getChild(start);
	for(;i;i= this->getNext(i))
	{
		printTree(i,depth+1);
	}
}

void bipartGraphPrint(bpGraph_t *pGraph)
{
	printf("Vertices:\n");
	printf("Part 1:\n");
    printTree(pGraph->vpVertsP1);
    printf("\n");

	printf("Part 2:\n");
    printTree(pGraph->vpVertsP2);
	printf("\n");

	printf("Edges:\n");
	/* partite 1 to partite 2 edges. */
	printf("Part 1 to 2:\n");
	printLList(pGraph->vpVertsP1);
	
	/* partite 2 to partite 1 edges. */
	printf("Part 2 to 1:\n");
	printLList(pGraph->vpVertsP2);
} /* end of bipartGraphPrint() */

int main(void) {
	BST<int> myTree;
	myTree.insert(3);

	for (int32_t k = 20; k < 100; k += 1) {
		myTree.insert(k);
	}

	printTree(myTree);

}

void printTree (tree t) {
	if (t == NULL) return;
	for (; t != NULL; t = t->next) {
		printf ("%*s%s", indent, "", tokName[t->kind]);
		switch (t->kind) {
			case Ident:
				printf ("		%s (%d)\n", id_name(t->value), t->value);
				break;
			case IntConst:
				printf ("		%d\n", t->value);
				break;
			default:
				printf ("\n");
				indent += 2;
				printTree (t->first);
				printTree (t->second);
				printTree (t->third);
				indent -= 2;
		} // end switch
	} // end for loop
} // end printTree()

void imprime_hash(Thash *hash) {

	int i;
    unsigned int cont=0;

	for(i = 0; i < TAM_HASH; i++) {

    	printTree(hash[i].raiz,&cont);
	}
	printf("n_uniq %u\n",cont);
	printf("sum_uniq %llu\n",numdist);
}

//Prints the bit representation of the given leaf
void printTree(TREE *fir)
{
    //postorder print of the path to the given leaf
    if(getParent(fir)!=NULL)
    {
        printTree(getParent(fir));
        if(getLeft(getParent(fir))==fir)
            printf("0");
        else
            printf("1");
    }
}

int main()
{
    char *values;
    int size;
    readExpression(&values, &size);

    initStack(size);
    createTree(values, size);
    printTree("tree.txt");

    return EXIT_SUCCESS;
}

/*==============================================
Prints the Tree
==============================================*/
void printTree(TreeBranch * cur, int indent)
{
	int i = 0;
	while(i < indent)								
	{
		printf(" ");
		i++;
	}
	if(cur->type != NULL)
		printf("%s ", cur->type);
	if(cur->subtype != NULL)
		printf("%s ", cur->subtype);
	if(cur->attribute != NULL)
		printf("[%s]\n", cur->attribute);
	else if(cur->flag == 1)
		printf("%i\n", cur->num);
	else printf("\n");

	if(cur->child1 != NULL)
    {
	    printf("child1:  ");
		printTree(cur->child1, (indent+2));
	}
	if(cur->child2 != NULL)
	{
	    printf("child2:  ");
		printTree(cur->child2, (indent+2));
	}
	if(cur->child3 != NULL)
	{
	    printf("child3:  ");
		printTree(cur->child3, (indent+2));
    }
    if(cur->sibling != NULL)
	{
	    printf("sibling: ");
		printTree(cur->sibling, indent);
	}
	return;
}

void BinarySearchTree<T>::printTree(Node<T>* subTree, Order order) const
{
    if (subTree == nullptr) return;

    switch (order)
    {
    case Order::PRE_ORDER:
            std::cout<<subTree->getValue()<<" ";

            printTree(subTree->getLeft(), order);

            printTree(subTree->getRight(),order);

            break;

     case 1:
            printTree(subTree->getLeft(), order);

            std::cout<<subTree->getValue()<<" ";

            printTree(subTree->getRight(),order);

            break;

     case 2:
            printTree(subTree->getLeft(), order);

            printTree(subTree->getRight(),order);

            std::cout<<subTree->getValue()<<" ";

            break;
     }

}

int main(int argc, char **argv)
{
	//Checking error
	if (argc < 2)
	{
		printf("usage: %s <input_filename>\n", argv[0]);
		return 0;
	}
	//Open file
	FILE *in = fopen(argv[1], "r");
	if (in == NULL) return 0;
	//Declaration of variable
	int i, size,level;
	//Scanning size from file
	fscanf(in, "%d", &size);
	//allocating memory for array
	int *array = malloc(size * sizeof(int));
	//Scanning number from the file
	for (i=0; i<size; i++)
		fscanf(in, "%d", &array[i]);
	//Declaring a node
	bst *root =NULL;
	//Creating BST
	root=createBST(array,size);
	//print in-order,pre-order,post-order tree traversal
	printf("Creating Binary Search Tree...\n");
	printf("In-order traversal: "); 
	printInorder(root); 
	printf("\n");
	printf("Pre-order traversal: ");
	printPreorder(root);
	printf("\n");
	printf("Post-order traversal: ");
	printPostorder(root);
	printf("\n");
	//Sort arrat
	sort(array,size);
	//Creatin binary tree with minimum level
	root=createMinBST(array,0,size-1);
	//printing BST
	printf("Minimum Height BST\n");
	printTree(root);
	//Bonus
	printf("Bonus.Please enter level of the tree:");
	scanf("%d",&level);
	if(level>height(root))
	printf("\nThe maximum height of this tree is %d",height(root));
	else
	printGivenLevel(root,level);

 return 0;
}

int testmain()
{

    Object *root = CreateObject("Undefined", "Undefined", 0, CodeBlock, "int");
    Object *basetype = CreateObject("BaseType", "BaseType", 0, Type, 0);
    Object *rect = CreateObject("Rectangle", "BaseType_Rectangle", basetype, Type, 0);
    Object *rectConst =
        CreateObject("Rectangle", "Rectangle_Rectangle_Rectangle_int_int", 0,
                     Constructor, "Rectangle");
    Object *subexpr = CreateObject(0, 0, 0, Expression, "float");
    addCode(subexpr, "3.14159");
    addParam(rectConst, "int");
    addParam(rectConst, "int");
    addSymbol(rectConst, CreateObject("width", "width", 0, Variable, "int"));
    addSymbol(rectConst, CreateObject("height", "height", 0, Variable, "int"));
    addSymbol(rectConst, CreateObject("self", "self", 0, Variable, "Rectangle*"));
    addCode(rectConst,
            "Rectangle * Rectangle_Rectangle_Rectangle_int_int(int width, int height) {");
    addCode(rectConst, "    Rectangle * self = (Rectangle*)malloc(sizeof(Rectangle));");
    addCode(rectConst, "    self->w = width;");
    addCode(rectConst, "    self->h = height;");
    addCode(rectConst, "    return self;");

    addCode(rectConst, "}");

    addSymbol(rect, CreateObject("w", "w", 0, Variable, "int"));

    addSymbol(rect, CreateObject("h", "h", 0, Variable, "int"));

    addSymbol(rect, rectConst);

    addCode(rect, "typedef struct {");

    addCode(rect, "    BaseType parent;");

    addCode(rect, "    int w;");

    addCode(rect, "    int h;");

    addCode(rect, "} Rectangle;");

    addSymbol(root, basetype);

    addSymbol(root, rect);

    addSymbol(root, subexpr);

    printTree(root, 0);

    return 0;

}