/*!
 * \brief Cleans up the object and frees up memory used by the solution tree.
 * \param processEvents If set to \c true then \link QCoreApplication::processEvents() QCoreApplication::processEvents(QEventLoop::ExcludeUserInputEvents)\endlink will be called from time to time while cleaning up.
 * \warning After call to this function a solution tree returned by the solve() function is no longer valid.
 * \note It is not required to call this function manually. This function is always called by solve() at the beginning of the solution process.
 *
 * \sa solve(), setCleanupOnCancel()
 */
void CTSPSolver::cleanup(bool processEvents)
{
    route.clear();
    mayNotBeOptimal = false;
    if (root != NULL)
        deleteTree(root, processEvents);
}

MathExpr * mathexpr_create(char *formula, int (*getVar) (char *))
{
    ExprTree *tree;
    MathExpr *expr = NULL;
	MathExpr *result = NULL;
    getVariableIndex = getVar;
    Err = 0;
    PrevLex = 0;
    CurLex = 0;
    S = formula;
    Len = strlen(S);
    Pos = 0;
    Bc = 0;
    tree = getTree();
    if (Bc == 0 && Err == 0)
	{
		traverseTree(tree, &expr);
		while (expr)
		{
			result = expr;
			expr = expr->prev;
		}
	}
	deleteTree(tree);
    return result;
}

//traverse list inorder and add elements to the array
int BST::sortHelper(TreeItemType a[], int i, TreeNode* t)
{
	TreeNode* curr = t;
        TreeItemType x;

        if(t->leftChildPtr != NULL)
        {
            curr = curr->leftChildPtr;
            sortHelper(a,i,curr);
        }

        x = curr->item;
        a[i] = x;
	i++;

        if(t->rightChildPtr != NULL)
        {
            curr = curr->rightChildPtr;
            sortHelper(a,i,curr);
        }
	if(i == (size() - 1))
	{
	    int j,k;
	    deleteTree(root);
	    j = sizeof(a);
	    k = ceil(j/2);

		buildHelper(a,k,0,j-1,root);
	}
}

/*
void MovieTree::deleteTree(Movie*)

Description:
Private, recursive function called in the destructor to properly deallocate
memory used by the tree.

Precondition:
The ends of the tree are nil.

Postcondition:
Each movie in the tree is deleted, using post-order traversal.
*/
void MovieTree::deleteTree(Movie *m)
{
    if (m == nil) {
        return;
    }

    if (m->left != nil) {
        deleteTree(m->left);
    }

    if (m->right != nil) {
        deleteTree(m->right);
    }

    delete m;
}

//! destructor
COctTreeSceneNode::~COctTreeSceneNode()
{
	//if (Mesh)
	//	Mesh->drop();

	deleteTree();
}

main()
{
	struct node *T;
	root =NULL;
	T=root;
	insert(root,5);
	insert(root,9);
	insert(root,4);
	insert(root,5);
	insert(root,2);
	insert(root,2);
	insert(root,7);

	traverseAndDisplay(root);

	deleteNode(root,5);
	traverseAndDisplay(root);
	
	deleteNode(root,2);
	traverseAndDisplay(root);

	deleteTree(root);
	traverseAndDisplay(root);
	return 0;
}

void clean_up(RBTree *tree)
{
  if ( tree != NULL )
  {
    deleteTree(tree);
    free(tree);
  }
}

void Lexicon::deleteTree(TrieNode* node) {
    if (node != NULL) {
        for (char letter = 'a'; letter <= 'z'; letter++) {
            deleteTree(node->child(letter));
        }
        delete node;
    }
}

void Profiler::deleteTree( Node* node )
{
	for (auto it = node->children.begin(); it != node->children.end(); ++it)
	{
		deleteTree(*it);
	}
	delete node;
}

	static void deleteTreeAr( std::vector<TreeNode*>& ar)
	{
		std::vector<TreeNode*>::iterator ai = ar.begin(), ae = ar.end();
		for (; ai != ae; ++ai)
		{
			deleteTree( *ai);
		}
	}

void deleteTree(treenode_t ** root_ptr) {
    if (*root_ptr == NULL) {
        return;
    }
    else {
        // go left first
        deleteTree(&(*root_ptr)->left);

        // go right second
        deleteTree(&(*root_ptr)->right);

        // delete root
        (*root_ptr)->left = NULL;
        (*root_ptr)->right = NULL;
        free (*root_ptr);
        (*root_ptr) = NULL;
    }
}

void deleteTree(node * root)
{
	for(int i=0;i<10;i++)
	{
		if(root->child[i])
			deleteTree(root->child[i]);
	}
	delete root;
}

  virtual ~BST() {

    //Call to clear
    deleteTree(root);

    //set root equal to nullptr
    root = nullptr;

  }

 void clear() {
   
     //Delete the tree Post Order Traversal
     deleteTree(root);
   
     //Set root to nullptr
     root = nullptr;
   
 }

void KDTree::rebuildTree(vector<Drawable *> objList) {
    assert(objList.size() > 0);

    deleteTree(this->root);
    root = new KDNode;
    root->objects = objList;
    bounds = findBounds(objList);
    buildTree(root, bounds, 0);
}

KDTree & KDTree::operator=(const KDTree &other) {
    if(this != &other) {
        deleteTree(this->root);
        this->root = copyTree(other.root);
        this->bounds = other.bounds;
    }

    return *this;
}

// compute the cdf given a tree
void pmsBP_C(double *weights, double * grid, int * ngrid, int *maxS, double * out, int *log_p)
{
	struct bintree *w = new struct bintree;
	setTree(1.0, w);
	//struct bintree *w = newtree(1);
	array2tree(weights, maxS[0], w);
	pmsBP(w, out, grid, ngrid, log_p);
	deleteTree(w);
}

// random sample from a msBP density
void rsample_msBP_C(int *N, double * Rvec, double *Svec, double *a, double *b, int * maxS, double *ans)
{
	int i = 0;	
	struct bintree * Stree = new struct bintree;
	struct bintree * Rtree = new struct bintree;
	setTree(1.0, Stree);
	setTree(1.0, Rtree);
	//struct bintree *Stree = newtree(1);
	//struct bintree *Rtree = newtree(1);
	array2tree(Svec, maxS[0], Stree);
	array2tree(Rvec, maxS[0], Rtree);
	for(i=0; i<N[0]; i++)
	{
		ans[i] = rsample_msBP(Rtree,Stree,a[0],b[0]);
	}
	deleteTree(Rtree);
	deleteTree(Stree);
}

// compute the weigths given a tree 
void computeprob_C(double *S, double * R, int *maxS, double *a, double *b, double *ans, int *root)
{
	struct bintree *Stree = new struct bintree;
	struct bintree *Rtree = new struct bintree;
	setTree(1.0, Stree);
	setTree(1.0, Rtree);
///	struct bintree *Stree = newtree(1);
//	struct bintree *Rtree = newtree(1);
//	struct bintree *anstree = newtree(1);
	if(root[0]==0) S[0] = 0;
	array2tree(S, maxS[0], Stree);
	array2tree(R, maxS[0], Rtree);
	struct bintree *anstree = computeprob(Stree, Rtree, a[0], b[0], maxS[0], 1);
	tree2array(anstree, ans, maxS[0], 0);
	deleteTree(Stree);
	deleteTree(Rtree);
	deleteTree(anstree);
} 

//compute the posterior cluster allocation with slice sampler [Algorithm 2]
void postCluster_C(int *s, int *h, double *y, double *pi, int *maxS, int *N, int *printscreen)
{
	struct bintree *pitree = new struct bintree;
	setTree(1.0, pitree);
	//struct bintree *pitree = newtree(1);
	array2tree(pi, maxS[0], pitree);
	postCluster(s, h, y, pitree, *maxS, *N, *printscreen);
	deleteTree(pitree);
}