void crossover (int j)
{	
	struct node *p1_node = NULL;
	struct node *p2_node = NULL;
	struct node *t1_node = NULL;

	int point1 = 0;
	int point2 = 0;
	int p1 = tournament_selection();
	int p2 = p1;
	int i = 0;

	if(number_of_nondominated > 1) while (p1 == p2)	p2 = tournament_selection();
	point1 = (rand() % population[p1].size) + 1;
	point2 = (rand() % population[p2].size) + 1;
	population[j].root = copy_tree(population[p1].root);
	p1_node = find_node(point1,&i,population[j].root);
	i = 0;
	p2_node = find_node(point2,&i,population[p2].root);
	t1_node = copy_tree(p2_node);
	destroy_tree(p1_node -> left);
	destroy_tree(p1_node -> right);
	p1_node -> key_type = t1_node -> key_type;
	p1_node -> key_value = t1_node -> key_value;
	p1_node -> left = t1_node -> left;
	p1_node -> right = t1_node -> right;
	free(t1_node);
}

at *copy_tree(at *p)
{
   MM_ENTER;
   
   if (CONSP(p)) {
      /* detect circular lists */
      at *p0 = p;
      bool move_p0 = false;
      at *q = NIL;
      at **qp = &q;
      while (CONSP(p)) {
         *qp = new_cons(Car(p), NIL);
         qp = &Cdr(*qp);
         p = Cdr(p);
         if (p == p0)
            RAISEF("can't do circular structures", NIL);
         move_p0 = !move_p0;
         if (move_p0)
            p0 = Cdr(p0);
      }
      *qp = copy_tree(p);

      /* descend */
      p = q;
      while (CONSP(p)) {
         AssignCar(p, copy_tree(Car(p)));
         p = Cdr(p);
      }
      MM_RETURN(q);
    
   } else
       MM_RETURN(p);
}

/* copy */
static Node *copy_tree(Node *parent, Node *self)
{
    Node *n = new_node(parent, self->key);
    n->value = self->value;
    n->color = self->color;
    if (self->left)  n->left = copy_tree(n, self->left);
    if (self->right) n->right = copy_tree(n, self->right);
    return n;
}

struct node *copy_tree(struct node *tree_node)
{
	if (tree_node == NULL) return NULL;
	struct node *n_node = (struct node *)malloc(sizeof(struct node));
	n_node -> left = copy_tree(tree_node -> left);
	n_node -> right = copy_tree(tree_node -> right);
	n_node -> key_type = tree_node -> key_type;
	n_node -> key_value = tree_node -> key_value;
	return n_node;
}

	void quadtree::copy_tree(std::unique_ptr<node> & copy, std::unique_ptr<node> & original)
	{
		if(!original)
			return;
		copy.reset(new node());
		copy->element = original->element;
		copy_tree(copy->northwest, original->northwest);
		copy_tree(copy->northeast, original->northeast);
		copy_tree(copy->southwest, original->southwest);
		copy_tree(copy->southeast, original->southeast);
	}

splay_tree copy_tree(splay_tree t1){
  splay_tree t2=create_tree(t1->data);
  t2->left=t1->left;
  t2->right=t1->right;
  t2->data=t1->data;
  t2->nb_left=t1->nb_left;
  t2->nb_right=t1->nb_right;
  if (t1->left !=NULL){
    t2->left=copy_tree(t1->left);}
  if (t1->right !=NULL){
    t2->right=copy_tree(t1->right);}
  return t2;
}

/*
 * copy_dir - copy a directory
 *
 *	Copy a directory (recursively) from src to dst.
 *
 *	statp, mt, uid, gid are used to set the access and modification and the
 *	access rights.
 *
 *	Return 0 on success, -1 on error.
 */
static int copy_dir (const char *src, const char *dst,
                     const struct stat *statp, const struct timeval mt[],
                     long int uid, long int gid)
{
	int err = 0;

	/*
	 * Create a new target directory, make it owned by
	 * the user and then recursively copy that directory.
	 */

#ifdef WITH_SELINUX
	selinux_file_context (dst);
#endif
	if (   (mkdir (dst, statp->st_mode) != 0)
	    || (chown (dst,
	               (uid == - 1) ? statp->st_uid : (uid_t) uid,
	               (gid == - 1) ? statp->st_gid : (gid_t) gid) != 0)
	    || (chmod (dst, statp->st_mode) != 0)
	    || (copy_tree (src, dst, uid, gid) != 0)
	    || (utimes (dst, mt) != 0)) {
		err = -1;
	}

	return err;
}

int main(int argc, char *argv[]) {
	size_t ct_size = 4;
	ContextTree ctw(ct_size);
	//Runs a coinflip example if the agent guesses randomly and the coin is random
	for(int i = 0; i < 1000; i++) {
	    int guess = rand01() < 0.5 ? 1 : 0;
	    int coin = rand01() < 0.5 ? 1 : 0;
		ctw.update(guess);
		ctw.update(coin);
		ctw.update(coin==guess ? 1 : 0);
	}
	
	//Action and observation are 0, 1 so ctw_tree would predict reward 0 if it "understood" the game
// 	std::cout << ctw->prettyPrint();
// 	std::cout << "Sequence: " << ctw->printHistory() << std::endl;
// 	std::cout << "Next: "<< ctw->predictNext() << std::endl;
	std::cout << "Original:" << std::endl << ctw.prettyPrint();
	ContextTree copy_tree(ctw);
	std::cout << "Copy:" << std::endl << copy_tree.prettyPrint();

	ctw.update(0);
	copy_tree.update(1);
	std::cout << "Original + 0:" << std::endl << ctw.prettyPrint();
	//std::cout << "Sequence: " << ctw.printHistory() << std::endl;
	std::cout << "Copy + 1:" << std::endl << copy_tree.prettyPrint();
	//std::cout << "Sequence: " << copy_tree.printHistory() << std::endl;
}

int main(int argc, char *argv[]) {
    xfs_mount_t	*mp;
    xfs_inode_t *inode = NULL;
    char *progname;
    char *source_name;
    char *parent;
    int r;

    if (argc != 3) {
        printf("Usage: xfs-rcopy raw_device directory\n");
        printf("Copies the named directory from an XFS file system to the current directory\n");
        return 1;
    }
    progname = argv[0];
    source_name = argv[1];
    parent = argv[2];
    
    mp = mount_xfs(progname, source_name);
    
    if (mp == NULL) 
        return 1;
    
    r = find_path(mp, parent, &inode);
    if (r) {
        printf("Can't find %s\n", parent);
        libxfs_umount(mp);
        return 1;
    }

    copy_tree(mp, parent, last(parent), inode);
    libxfs_iput(inode, 0);
    libxfs_umount(mp);
    return 0;
}

static void
copy_tree (GConfClient     *src,
	   const char      *path,
	   GConfChangeSet  *changes,
	   const char     **excludes)
{
	GSList *list, *l;
	GConfEntry *entry;

	if (path_is_excluded (path, excludes))
		return;

	list = gconf_client_all_entries (src, path, NULL);
	for (l = list; l; l = l->next) {
		entry = l->data;
		if (!path_is_excluded (entry->key, excludes))
			gconf_change_set_set (changes, entry->key, entry->value);
	}
	g_slist_foreach (list, (GFunc)gconf_entry_free, NULL);
	g_slist_free (list);

	list = gconf_client_all_dirs (src, path, NULL);
	for (l = list; l; l = l->next)
		copy_tree (src, (const char *)l->data, changes, excludes);
	g_slist_foreach (list, (GFunc)g_free, NULL);
	g_slist_free (list);
}

void mutate (int j)
{
	int p = tournament_selection();
	population[j].root = copy_tree(population[p].root);
	int ind = (rand() % get_tree_size(population[j].root)) + 1;

	struct node *n_node = NULL;
	struct node *e_node = NULL;
	if ( ind == 1 )
	{
		destroy_tree(population[j].root);
		population[j].root = create_random_node();
		population[j].age = 0;
	}
	else
	{
		int i = 0;
		n_node = find_node(ind,&i,population[j].root);
		e_node = create_random_node();

		destroy_tree(n_node -> left);
		destroy_tree(n_node -> right);
		n_node -> key_type = e_node -> key_type;
		n_node -> key_value = e_node -> key_value;
		n_node -> left = e_node -> left;
		n_node -> right = e_node -> right;
		free(e_node);
	}
}

cons_t* copy_tree(cons_t* tree_head)
{
    cons_t* copied_tree_head = NULL;
    assert(tree_head != NULL);
    copied_tree_head = copy_cell(tree_head);
    if(tree_head->cdr != NULL){
        copied_tree_head->cdr = copy_tree(tree_head->cdr);
    }
    return copied_tree_head;
}

/*
 * mount 'source_mnt' under the destination 'dest_mnt' at
 * dentry 'dest_dentry'. And propagate that mount to
 * all the peer and slave mounts of 'dest_mnt'.
 * Link all the new mounts into a propagation tree headed at
 * source_mnt. Also link all the new mounts using ->mnt_list
 * headed at source_mnt's ->mnt_list
 *
 * @dest_mnt: destination mount.
 * @dest_dentry: destination dentry.
 * @source_mnt: source mount.
 * @tree_list : list of heads of trees to be attached.
 */
int propagate_mnt(struct mount *dest_mnt, struct mountpoint *dest_mp,
		    struct mount *source_mnt, struct hlist_head *tree_list)
{
	struct user_namespace *user_ns = current->nsproxy->mnt_ns->user_ns;
	struct mount *m, *child;
	int ret = 0;
	struct mount *prev_dest_mnt = dest_mnt;
	struct mount *prev_src_mnt  = source_mnt;
	HLIST_HEAD(tmp_list);

	for (m = propagation_next(dest_mnt, dest_mnt); m;
			m = propagation_next(m, dest_mnt)) {
		int type;
		struct mount *source;

		if (IS_MNT_NEW(m))
			continue;

		source =  get_source(m, prev_dest_mnt, prev_src_mnt, &type);

		/* Notice when we are propagating across user namespaces */
		if (m->mnt_ns->user_ns != user_ns)
			type |= CL_UNPRIVILEGED;

		child = copy_tree(source, source->mnt.mnt_root, type);
		if (IS_ERR(child)) {
			ret = PTR_ERR(child);
			tmp_list = *tree_list;
			tmp_list.first->pprev = &tmp_list.first;
			INIT_HLIST_HEAD(tree_list);
			goto out;
		}

		if (is_subdir(dest_mp->m_dentry, m->mnt.mnt_root)) {
			mnt_set_mountpoint(m, dest_mp, child);
			hlist_add_head(&child->mnt_hash, tree_list);
		} else {
			/*
			 * This can happen if the parent mount was bind mounted
			 * on some subdirectory of a shared/slave mount.
			 */
			hlist_add_head(&child->mnt_hash, &tmp_list);
		}
		prev_dest_mnt = m;
		prev_src_mnt  = child;
	}
out:
	lock_mount_hash();
	while (!hlist_empty(&tmp_list)) {
		child = hlist_entry(tmp_list.first, struct mount, mnt_hash);
		umount_tree(child, 0);
	}
	unlock_mount_hash();
	return ret;
}

/*
 * mount 'source_mnt' under the destination 'dest_mnt' at
 * dentry 'dest_dentry'. And propagate that mount to
 * all the peer and slave mounts of 'dest_mnt'.
 * Link all the new mounts into a propagation tree headed at
 * source_mnt. Also link all the new mounts using ->mnt_list
 * headed at source_mnt's ->mnt_list
 *
 * @dest_mnt: destination mount.
 * @dest_dentry: destination dentry.
 * @source_mnt: source mount.
 * @tree_list : list of heads of trees to be attached.
 */
int propagate_mnt(struct mount *dest_mnt, struct dentry *dest_dentry,
		    struct mount *source_mnt, struct list_head *tree_list)
{
	struct user_namespace *user_ns = current->nsproxy->mnt_ns->user_ns;
	struct mount *m, *child;
	int ret = 0;
	struct mount *prev_dest_mnt = dest_mnt;
	struct mount *prev_src_mnt  = source_mnt;
	LIST_HEAD(tmp_list);
	LIST_HEAD(umount_list);

	for (m = propagation_next(dest_mnt, dest_mnt); m;
			m = propagation_next(m, dest_mnt)) {
		int type;
		struct mount *source;

		if (IS_MNT_NEW(m))
			continue;

		source =  get_source(m, prev_dest_mnt, prev_src_mnt, &type);

		/* Notice when we are propagating across user namespaces */
		if (m->mnt_ns->user_ns != user_ns)
			type |= CL_UNPRIVILEGED;

		child = copy_tree(source, source->mnt.mnt_root, type);
		if (IS_ERR(child)) {
			ret = PTR_ERR(child);
			list_splice(tree_list, tmp_list.prev);
			goto out;
		}

		if (is_subdir(dest_dentry, m->mnt.mnt_root)) {
			mnt_set_mountpoint(m, dest_dentry, child);
			list_add_tail(&child->mnt_hash, tree_list);
		} else {
			/*
			 * This can happen if the parent mount was bind mounted
			 * on some subdirectory of a shared/slave mount.
			 */
			list_add_tail(&child->mnt_hash, &tmp_list);
		}
		prev_dest_mnt = m;
		prev_src_mnt  = child;
	}
out:
	br_write_lock(&vfsmount_lock);
	while (!list_empty(&tmp_list)) {
		child = list_first_entry(&tmp_list, struct mount, mnt_hash);
		umount_tree(child, 0, &umount_list);
	}
	br_write_unlock(&vfsmount_lock);
	release_mounts(&umount_list);
	return ret;
}

void Scm_TreeCoreCopy(ScmTreeCore *dst, const ScmTreeCore *src)
{
    if (ROOT(src)) {
        SET_ROOT(dst, copy_tree(NULL, ROOT(src)));
    } else {
        SET_ROOT(dst, NULL);
    }
    dst->cmp = src->cmp;
    dst->num_entries = src->num_entries;
    dst->data = src->data;
}

/*************************************************************************
 * Deep copy a tree. Assume memory is already allocated.
 *************************************************************************/
void copy_tree
  (TREE_T * source_tree,
   TREE_T * dest_tree)
{
  memcpy(dest_tree, source_tree, sizeof(TREE_T));
  int i;
  for (i = 0; i < dest_tree->num_children; i++) {
    dest_tree->children[i] = allocate_tree();
    copy_tree(source_tree->children[i], dest_tree->children[i]);
  }
}

void duplicate_individual ( individual *to, individual *from )
{
     int j;
     for ( j = 0; j < tree_count; ++j )
          copy_tree ( to->tr+j, from->tr+j );
     to->r_fitness = from->r_fitness;
     to->s_fitness = from->s_fitness;
     to->a_fitness = from->a_fitness;
     to->hits = from->hits;
     to->evald = from->evald;
     to->flags = from->flags;
}

static int propagate_one(struct mount *m)
{
	struct mount *child;
	int type;
	/* skip ones added by this propagate_mnt() */
	if (IS_MNT_NEW(m))
		return 0;
	/* skip if mountpoint isn't covered by it */
	if (!is_subdir(mp->m_dentry, m->mnt.mnt_root))
		return 0;
	if (m->mnt_group_id == last_dest->mnt_group_id) {
		type = CL_MAKE_SHARED;
	} else {
		struct mount *n, *p;
		for (n = m; ; n = p) {
			p = n->mnt_master;
			if (p == dest_master || IS_MNT_MARKED(p)) {
				while (last_dest->mnt_master != p) {
					last_source = last_source->mnt_master;
					last_dest = last_source->mnt_parent;
				}
				if (n->mnt_group_id != last_dest->mnt_group_id) {
					last_source = last_source->mnt_master;
					last_dest = last_source->mnt_parent;
				}
				break;
			}
		}
		type = CL_SLAVE;
		/* beginning of peer group among the slaves? */
		if (IS_MNT_SHARED(m))
			type |= CL_MAKE_SHARED;
	}
		
	/* Notice when we are propagating across user namespaces */
	if (m->mnt_ns->user_ns != user_ns)
		type |= CL_UNPRIVILEGED;
	child = copy_tree(last_source, last_source->mnt.mnt_root, type);
	if (IS_ERR(child))
		return PTR_ERR(child);
	child->mnt.mnt_flags &= ~MNT_LOCKED;
	mnt_set_mountpoint(m, mp, child);
	last_dest = m;
	last_source = child;
	if (m->mnt_master != dest_master) {
		read_seqlock_excl(&mount_lock);
		SET_MNT_MARK(m->mnt_master);
		read_sequnlock_excl(&mount_lock);
	}
	hlist_add_head(&child->mnt_hash, list);
	return 0;
}

exp_tree_t* copy_tree(exp_tree_t *src)
{
	exp_tree_t et = new_exp_tree(src->head_type, src->tok);
	int i;

	for (i = 0; i < src->child_count; ++i)
		if (src->child[i]->child_count == 0)
			add_child(&et, alloc_exptree(*src->child[i]));
		else
			add_child(&et, copy_tree(src->child[i]));

	return alloc_exptree(et);
}

END_TEST

START_TEST(test_simple_copy)
{
    int ret;
    char origpath[PATH_MAX+1];
    char *tmp;
    int fd = -1;

    errno = 0;
    fail_unless(getcwd(origpath, PATH_MAX) == origpath, "Cannot getcwd\n");
    fail_unless(errno == 0, "Cannot getcwd\n");

    /* create a file */
    ret = chdir(dir_path);
    fail_if(ret == -1, "Cannot chdir1\n");

    ret = create_simple_file("bar", "bar");
    fail_if(ret == -1, "Cannot create file1\n");

    /* create a subdir and file inside it */
    ret = mkdir("subdir", 0700);
    fail_if(ret == -1, "Cannot create subdir\n");

    ret = chdir("subdir");
    fail_if(ret == -1, "Cannot chdir\n");

    ret = create_simple_file("foo", "foo");
    fail_if(ret == -1, "Cannot create file\n");

    /* go back */
    ret = chdir(origpath);
    fail_if(ret == -1, "Cannot chdir\n");

    /* and finally copy.. */
    DEBUG(SSSDBG_FUNC_DATA,
          "Will copy from '%s' to '%s'\n", dir_path, dst_path);
    ret = copy_tree(dir_path, dst_path, 0700, uid, gid);
    fail_unless(ret == EOK, "copy_tree failed\n");

    /* check if really copied */
    ret = access(dst_path, F_OK);
    fail_unless(ret == 0, "destination directory not there\n");

    tmp = talloc_asprintf(test_ctx, "%s/bar", dst_path);
    ret = check_and_open_readonly(tmp, &fd, uid, gid, 0700, CHECK_REG);
    fail_unless(ret == EOK, "Cannot open %s\n");
    close(fd);
    talloc_free(tmp);
}