void destroy_tree(struct tree_node *node,
		  tree_fn fnptr)
{
	if (node) {
		struct tree_node *left = node->left, *right = node->right;
		if (fnptr) {
			fnptr(node->data);
		}
		free(node);
		destroy_tree(left,fnptr);
		destroy_tree(right,fnptr);
	}
}

/* Deallocate all of the memory used by a BusinessNode BST, without memory
 * leaks.
 */
void destroy_tree(BusinessNode * root)
{
    if(root == NULL)
    {
        return;
    }
    destroy_tree(root->left);
    destroy_tree(root->right);
    free(root->name);
    free(root->stars);
    free(root->address);
    free(root);
}

void destroy_tree(BusinessNode * node)
{
    if(node == NULL)
	return;

    free(node -> name);
    free(node -> stars);
    free(node -> address);

    destroy_tree(node -> left);
    destroy_tree(node -> right);

    free(node);
}

void destroy_tree(Node * root)
{//recursively frees all memory associated with the binary tree
	if (root == NULL)
	{
		return;
	}

	destroy_tree(root -> left);
	destroy_tree(root -> right);

	free(root);

	return;
}

void destroy_tree(binary_tree_s* psNode)
{
	binary_tree_s** ppsCur;

	ppsCur = &psNode;

	if (*ppsCur != NULL)
	{
		destroy_tree((*ppsCur)->m_psLeftNode);	
		destroy_tree((*ppsCur)->m_psRightNode);	
		free((*ppsCur));
		ppsCur = NULL;
	}
}

void ADT::destroy_tree(Node *&leaf)
{
    if (leaf != NULL)
    {
        destroy_tree(leaf->left);
        destroy_tree(leaf->right);
        
        if (leaf->p != NULL)
        {
            delete leaf->p;
        }
        
        delete leaf;
        leaf = NULL;
    }
}

int	main(void)
{
	char	*key;
	char	*value;
	char	*tmp;
	int		read;
	t_node	*root;

	read = 1;
	root = 0;
	while (read)
	{
		get_next_line(0, &key);
		read = get_next_line(0, &value);
		if (!ft_strcmp(key, ""))
			read = 0;
		else
			add_node(&root, key, value);
	}
	if (*value)
	{
		search_key(root, value);
		while (get_next_line(0, &tmp) > 0)
			search_key(root, tmp);
	}
	destroy_tree(&root);
	return (0);
}

int main(int argc, char *argv[])
{
	struct rooted_tree *tree;	
	struct parameters params;
	static struct rooted_tree * (*process_tree)(struct rooted_tree *, set_t *);
	
	params = get_params(argc, argv);

	switch (params.mode) {
	case PRUNE_DIRECT:
		process_tree = process_tree_direct;
		break;
	case PRUNE_REVERSE:
		process_tree = process_tree_reverse;
		break;
	default:
		assert (0);
	}

	while (NULL != (tree = parse_tree())) {
		tree = process_tree(tree, params.prune_labels);
		dump_newick(tree->root);
		destroy_all_rnodes(NULL);
		destroy_tree(tree);
	}

	destroy_set(params.prune_labels);

	return 0;
}

static struct rooted_tree * process_tree_reverse(
		struct rooted_tree *tree, set_t *prune_labels)
{
	struct list_elem *el = tree->nodes_in_order->head;
	struct rnode *current;
	char *label;

	for (; NULL != el; el = el->next) {
		current = el->data;
		if (is_root(current)) break;
		label = current->label;
		/* mark this node (to keep it) if its label is on the CL */
		if (set_has_element(prune_labels, label)) {
			current->seen = true;
			struct prune_data *pdata =
				malloc(sizeof(struct prune_data));
			if (NULL == pdata) {perror(NULL); exit(EXIT_FAILURE); }
			pdata->kept_descendant = true;
			current->data = pdata;
		}
		/* and propagate 'seen' to parent (kept_descendant is
		 * propagated to children (not parents), see
		 * prune_predicate_keep_clade() */
		if (current->seen) {
			current->parent->seen = true;	/* inherit mark */
		}
	}

	struct rooted_tree *pruned = clone_tree_cond(tree,
			prune_predicate_keep_clade, prune_labels);	
	destroy_tree(tree);
	return pruned;
}

int main(int argc, char **argv)
{
    if(argc < 2)
    {
        printf("Usage: %s forwarding_table_file\n\n", argv[0]);
        exit(0);
    }

    FILE *fp = fopen(argv[1], "r");
    if(fp == NULL)
    {
        printf("Unable to open '%s'\n\n", argv[1]);
        exit(-1);
    }

    /* load the list file to a binary tree data structure */

    node * tree = loadToTree(fp, argv);

    /* ORTC - step 1: discard interior next-hops */

    clear_interior_next_hops(tree);

    /* ORTC - step 2: calculate most frequent next-hops by traversing bottom up */

    percolate_tree(tree);

    /* ORTC - step 3: */

    clean_redundancy(tree, NULL);


    /* print to file */

    char destination[128];
    sprintf(destination, "%s.compressed", argv[1]);
    FILE * destination_file = fopen(destination, "w");
    if(fp == NULL)
    {
        printf("Unable to open '%s'\n\n", argv[1]);
        exit(-1);
    }

    printToFile(tree, destination_file);

#ifdef DEBUG
    printf("final tree (pre-order traversal): ");
    print_tree(tree);
    puts("\n");
#endif

    destroy_tree(tree);
    LSTdestroy(queue, destroyItem);
    fclose(fp);
    fclose(destination_file);

    puts("done.\n");

    exit(0);
}

void c_test_ins_tree_height(void) {
  int sizeOfElement = sizeof(struct complexThing);
  Tree tree = new_tree(sizeOfElement, navigateComplex, copyComplex, destroyComplex, NULL);
  CU_ASSERT_TRUE(get_tree_height(tree) == 0);

  Complex *c = malloc(sizeof(struct complexThing));
  c->int_regular = 10;
  c->int_pointer = malloc(sizeof(int));
  *c->int_pointer = 15;

  tree_insert(&tree, c, NULL);

  CU_ASSERT_TRUE(get_tree_height(tree) == 1);

  if (tree != NULL) {
    destroy_tree(&tree); 
  }

  if (c != NULL) {
    if (c->int_pointer != NULL) {
      free(c->int_pointer);
    }

    free(c);
  }
 
}

void destroy_tree(node *root)
{
	node *n, *p;
	uint32_t i;

	for (n = root->children; n != NULL; n = p) {
		p = n->next;

		destroy_tree(n);
	}
	
	for (i = 0; i < root->n_attrs; ++i) {
		lwc_string_unref(root->attrs[i].name);
		lwc_string_unref(root->attrs[i].value);
	}
	free(root->attrs);

	if (root->classes != NULL) {
		for (i = 0; i < root->n_classes; ++i) {
			lwc_string_unref(root->classes[i]);
		}
		free(root->classes);
	}

	if (root->libcss_node_data != NULL) {
		css_libcss_node_data_handler(&select_handler, CSS_NODE_DELETED,
				NULL, root, NULL, root->libcss_node_data);
	}

	lwc_string_unref(root->name);
	free(root);
}

int main(int argc, char *argv[])
{
	struct rooted_tree *tree;	
	struct hash *rename_map;
	struct parameters params;
	
	params = get_params(argc, argv);

	rename_map = read_map(params.map_filename);

	while (NULL != (tree = parse_tree())) {
		process_tree(tree, rename_map, params);
		destroy_tree(tree, DONT_FREE_NODE_DATA);
	}

	struct llist *keys = hash_keys(rename_map);
	if (NULL == keys) { perror(NULL); exit(EXIT_FAILURE); }
	struct list_elem *e;
	for (e = keys->head; NULL != e; e = e->next) {
		char *key = (char *) e->data;
		char *val = hash_get(rename_map, key);
		free(val);
	}
	destroy_llist(keys);
	destroy_hash(rename_map);

	return 0;
}

void IntervalMap::freeIntervalMap() {
	/*for (int i = 0; i < numberOfIntervalls; i++) {
	 delete map[i];
	 }
	 delete[] this->map;*/
	destroy_tree(map);
}

void find_three_layer()
{
	int i=0;
	int j=0;
	int k=0;
	FILE *f_results;
	f_results = fopen(nondom_file, "a");
	for(i=1 ; i<=number_of_features ; i++)
	{
		current_round = i;
		printf("\n\n###################### ROUND %d ########################\n",i);
		find_a_layer();
		final_pareto_front();
		k=0;
		for(j=0 ; j<population_size ; j++)
		{
			if(dominated[j]==False)
			{
				pop[i][k].root = population[j].root;
				pop[i][k].fitness = population[j].fitness;
				pop[i][k].cost = population[j].cost;
				k++;
			}
			else
				destroy_tree(population[j].root);
		}
		pop_count[current_round]=k;
		fprintf(f_results,"\nthe number of solutions = %d\n",pop_count[current_round]);
	}
	fclose(f_results);
}

void s_test_tree_balance(void) {

  int items = 500;

  int sizeOfElement = sizeof(int);
  Tree tree = new_tree(sizeOfElement, navigateItem, NULL, NULL, NULL);
  int b = 0;
  
  double d = 1.44;
  double f = 0.328;
  double g = log2(items+2);
  double res = (d*g) - f;

  for (int i = 0; i < items; i++) {
    b = i;
    tree_insert(&tree, &b, NULL);
    CU_ASSERT_TRUE(get_tree_height(tree) <= res);
  }

  //An AVL tree height should be strictly lower than 1.44log2(n+2)-0.328 where n = the number of items.
 
  //printTest(&tree, printInt);
  if (tree != NULL) {
    destroy_tree(&tree); 
  }

}

void
free_atomic_trees ()
{
  //size_t i;
  struct atomic_tree *at, *tmp;

  /*for (i = 0; i < atomic_trees_idx; i++)
    {
      assert (TREE_CODE (atomic_trees[i]) == EMPTY_MARK, 0);
      free (atomic_trees[i]);
    }

  if (atomic_trees)
    free (atomic_trees);*/
  HASH_ITER (hh, atomic_trees, at, tmp)
    {
      if (TREE_CODE (at->value) == EMPTY_MARK)
        {
          free (at->value);
          HASH_DEL (atomic_trees, at);
          free (at);
        }
      else
        destroy_tree (at->value);
    }
 
  HASH_ITER (hh, atomic_trees, at, tmp)
    {
      assert (TREE_CODE (at->value) == EMPTY_MARK, 0);
      free (at->value);
      HASH_DEL (atomic_trees, at);
      free (at);
    }

int main(void)
{
	void print_tree2(BusinessNode * tree,int i);
	printf("\e[1;1H\e[2J"); // clears screen
	//BusinessNode *Node,*Node1, *Node2, *Node3, *Node4, *Holder;
	
	//Node = create_node(strdup("4.5"),strdup("Awesome Business"),strdup("Purdue"));
	//Node1 = create_node(strdup("3.2"),strdup("Yummy"),strdup("here"));
	//Node2 = create_node(strdup("3.9"),strdup("K"),strdup("There"));
	//Node3 = create_node(strdup("5.0"),strdup("La sta"),strdup("DC"));
	//Node4 = create_node(strdup("0.9"),strdup("App"),strdup("Gary"));
	
	
	//print_node(Node);
	//print_node(Node1);
	//print_node(Node2);
	//print_node(Node3);
	//print_node(Node4);
	//printf("\n------------\n");

	//Holder = tree_insert(Node1,Node);
	//Holder = tree_insert(Node2,Node);
	//Holder = tree_insert(Node3,Node);
	//Holder = tree_insert(Node4,Node);
	//print_tree2(Holder,0);
	//destroy_tree(Holder);
	
	BusinessNode *SmallFile = load_tree_from_file("yelp_businesses.tsv");
	print_tree2(SmallFile,0);
	printf("%p\n",(tree_search_name("Oriental Supermarket", SmallFile)));
	destroy_tree(SmallFile);
	
	
	return EXIT_SUCCESS;
}

void c_test_tree_delete(void) {
  
  int items = 2;
  int sizeOfElement = sizeof(struct complexThing);
  Tree tree = new_tree(sizeOfElement, navigateComplex, copyComplex, destroyComplex, NULL);
  
  for (int i = 1; i < items; i++) {
    Complex *c = malloc(sizeof(struct complexThing));

    c->int_regular = i;
    c->int_pointer = malloc(sizeof(int));
    *c->int_pointer = i+i;

    tree_insert(&tree, c, NULL);
     
    if (c != NULL) {
      if (c->int_pointer != NULL) {
	free(c->int_pointer);
      }
      free(c);
    }
  }
 

  for (int d = items - 1; d >= 0; d--) {
    tree_delete(&tree, &d, navigateSearchComplex);
  }

  CU_ASSERT_EQUAL(get_tree_height(tree), 0);

  if (tree != NULL) {
    destroy_tree(&tree); 
  }

}

void c_test_ins_tree_equal(void) {

  int sizeOfElement = sizeof(struct complexThing);
  Tree tree = new_tree(sizeOfElement, navigateComplex, copyComplex, destroyComplex, eq_handler);
  

  Complex *c = malloc(sizeof(struct complexThing));
  c->int_regular = 10;
  c->int_pointer = malloc(sizeof(int));
  *c->int_pointer = 15;

  tree_insert(&tree, c, NULL);
  *c->int_pointer = 25;
  tree_insert(&tree, c, NULL);
  
  void *upd = tree_search(&tree, cb, c, NULL);
  
  CU_ASSERT_EQUAL(*c->int_pointer, *(((Complex*)upd)->int_pointer));
  


  if (tree != NULL) {
    destroy_tree(&tree); 
  }

  if (c != NULL) {
    if (c->int_pointer != NULL) {
      free(c->int_pointer);
    }

    free(c);
  }
 
}