##' merge two tree object
 ##'
 ##' 
 ##' @title merge_tree
 ##' @param obj1 tree object 1
 ##' @param obj2 tree object 2
 ##' @return tree object
 ##' @importFrom magrittr %<>%
 ##' @importFrom ape Ntip
 ##' @export
 ##' @author Guangchuang Yu
 merge_tree <- function(obj1, obj2) {

     ##
     ## INFO:
     ## ape::all.equal.phylo can be used to test equal phylo topology.
     ##

     
     if (has.slot(obj1, "extraInfo") == FALSE) {
         stop("input tree object is not supported...")
     }
     
     if ((is.tree(obj1) & is.tree(obj2)) == FALSE) {
         stop("input should be tree objects...")
     }
 
     tr1 <- get.tree(obj1)
     tr2 <- get.tree(obj2)
 
     if (getNodeNum(tr1) != getNodeNum(tr2)) {
         stop("number of nodes not equals...")
     }
 
     if (Ntip(tr1) != Ntip(tr2)) {
         stop("number of tips not equals...")
     }
     
     if (all(tr1$tip.label %in% tr2$tip.label) == FALSE) {
         stop("tip names not match...")
     }
 
 
     ## order tip.label in tr2 as in tr1
     ## mapping corresponding ID
     idx <- match(tr2$tip.label, tr1$tip.label)
     tr2$edge[match(1:Ntip(tr2), tr2$edge[,2]), 2] <- idx
     tr2$tip.label <- tr1$tip.label
 
     node_map <- list()
     node_map$from %<>% c(1:Ntip(tr2))
     node_map$to %<>% c(idx)
 
     root <- getRoot(tr1)
     root.2 <- getRoot(tr2)
     tr2$edge[tr2$edge[,1] == root.2, 1] <-  root
 
     node_map$from %<>% c(root.2)
     node_map$to %<>% c(root)
 
     
     currentNode <- 1:Ntip(tr1)
     while(length(currentNode)) {
         p1 <- sapply(currentNode, getParent, tr=tr1)
         p2 <- sapply(currentNode, getParent, tr=tr2)
 
         if (length(p1) != length(p2)) {
             stop("trees are not identical...")
         }
 
         jj <- match(p2, tr2$edge[,1])
         if (length(jj)) {
             notNA <- which(!is.na(jj))
             jj <- jj[notNA]
         }
         if (length(jj)) {
             tr2$edge[jj,1] <- p1[notNA]
         }
 
         
         ii <- match(p2, tr2$edge[,2])
         if (length(ii)) {
             notNA <- which(!is.na(ii))
             ii <- ii[notNA]
         }
         if (length(ii)) {
             tr2$edge[ii,2] <- p1[notNA]
         }
 
         node_map$from %<>% c(p2)
         node_map$to %<>% c(p1)
         
         ## parent of root will return 0, which is in-valid node ID
         currentNode <- unique(p1[p1 != 0])
     }
 
     if ( any(tr2$edge != tr2$edge) ) {
         stop("trees are not identical...")
     }
     
     node_map.df <- do.call("cbind", node_map)
     node_map.df <- unique(node_map.df)
     node_map.df <- node_map.df[node_map.df[,1] != 0,]
     i <- order(node_map.df[,1], decreasing = FALSE)
     node_map.df <- node_map.df[i,]
 
     info2 <- fortify(obj2)
     info2$node <- node_map.df[info2$node, 2]
     info2$parent <- node_map.df[info2$parent, 2]
 
     cn <- colnames(info2)

     i <- match(c("x", "y", "isTip", "label", "branch", "branch.length", "angle"), cn)

     i <- i[!is.na(i)]
     info2 <- info2[, -i]
 
     extraInfo <- obj1@extraInfo
     if (nrow(extraInfo) == 0) {
         obj1@extraInfo <- info2
     } else {
         info <- merge(extraInfo, info2, by.x =c("node", "parent"), by.y = c("node", "parent"))
         obj1@extraInfo <- info
     }
     
     return(obj1)
 }