root/BH13SPARQLBuilder/src/org/biohackathon/SPARQLBuilder/OWL/SimpleTree.java @ 190

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);
               

            }
        
}