package org.biohackathon.SPARQLBuilder.OWL;

import java.io.Serializable;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class SimpleTree <N extends Serializable >  {

        // children key, parent value
	    private final Map<N, N> nodeParent = new HashMap<N, N>();
	    
	    
	    //all nodes list
	    private final LinkedHashSet<N> nodeList = new LinkedHashSet<N>();

	    public void add (N parent, N node) {
        
	      nodeList.add(node);
	      nodeList.add(parent);
	 	  nodeParent.put(node, parent);
	 
	       
	    }
   	   
	    //for unstrict tree:multi-root
	    public List<N> getRoots () {
	        return getChildren(null);
	    }
     
	    // for strict tree: one root
	    public N getRoot () {
	    	
	    	List<N> list = getRoots();
	    	return list.get(0);
	    	
	    }
	    
     
	  
	    public N getParent (N node) {
	        return nodeParent.get(node);
	    }

	    public List<N> getChildren (N node) {
	        List<N> children = new LinkedList<N>();
	        for (N n : nodeList) {
	            N parent = nodeParent.get(n);
	            if (node == null && parent == null) {
	                children.add(n);
	            } else if (node != null && parent != null && parent.equals(node)) {
	                children.add(n);
	            }
	        }
	        return children;
	    }

	   
	    public String toString () {
	        StringBuilder builder = new StringBuilder();
	        dumpNodeStructure(builder, null, "- ");
	        return builder.toString();
	    }

	    private void dumpNodeStructure (StringBuilder builder, N node, String prefix) {
	        if (node != null) {
	            builder.append(prefix);
	            builder.append(node.toString());
	            builder.append('\n');
	            prefix = "    " + prefix;
	        }
	        for (N child : getChildren(node)) {
	            dumpNodeStructure(builder, child, prefix);
	        }
	    }    
	    
	    private N findMinAncestorIntenal(N node1,N node2){
	    	
	   	    N root = getRoot();
	    
		    
	  	    for ( N parent1 = node1;parent1!=root;parent1=getParent(parent1))
	    { 	
	    	
	    	for ( N parent2=node2;parent2!=root;parent2=getParent(parent2))
	    	{
	    		
	    		if(parent1==parent2) return parent1;
	       		  		
	    	}
	     	
	    }
	    
	   	return root;
    
	
	    }
	    public N findMinAncestor(N... node){
	    	int length = node.length;
	    	if (length<=1) return node[0];
	    	
	    	N ancestor=node[0];
	    	
	    	for(int i=0;i<length-1;i++)
	    	{
	    		ancestor=findMinAncestorIntenal(ancestor,node[i+1]);
	    	}
	    	
	    	return ancestor;
	    }
	    	
	    
	    /*     H
	     *    /  \
	     *    D   K
	     *   /  \
	     *   E   F
	     *  /  \  \
	     *  A  B  C
	     * 
	    */
	    
	    public static void main (String[] args) {

	    	SimpleTree<String> tree = new SimpleTree<String>();
	    	
	        tree.add("D", "E");
	        tree.add("D", "F");
	        tree.add("E", "A");
	        tree.add("E", "B");
	        tree.add("E", "L");
	        tree.add("F", "C");
	        tree.add("H", "D");
		    tree.add("H", "K");
	     
	        System.out.println(tree.nodeParent.toString());
	        
	      List<String> list= tree.getRoots();
	      System.out.println(list.toString());
	      
	       String ance=tree.findMinAncestor("A","B","F","E"); 
	       System.out.println(ance);
	       

	    }
	
}