Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. import util.*;
  2. import java.util.*;
  3. public class Search{
  4.     private TreeNode root;
  5.     private boolean []isAdded;
  6.  
  7.     private boolean [][]isUsed;
  8.  
  9.     private StringBuffer sb;
  10.     public Search(String [][]path){
  11.         constructTree(path);
  12.     }
  13.  
  14.     public void constructTree(String [][]path){
  15.         isAdded=new boolean[path.length];
  16.         for(int i=0;i<path.length;i++){
  17.             isAdded[i]=false;
  18.         }
  19.         root=new TreeNode(path[0][0]);
  20.         ArrayList sn=new ArrayList();
  21.         ArrayList se=new ArrayList();
  22.         ArrayList de=new ArrayList();
  23.  
  24.         sn.add(root);
  25.         se.add(path[0][0]);
  26.         TreeNode temp=root;
  27.  
  28.         for(int i=1;sn.size()>0;i++){
  29.             temp=(TreeNode)sn.get(0);
  30.             for(int j=0;j<path.length;j++){
  31.  
  32.                 if(path[j][0].equals(se.get(0))&&!isAdded[j]){
  33.  
  34.                     temp.addChild(path[j][1]);
  35.                     sn.add(temp.getChild(temp.count()-1));
  36.                     se.add(path[j][1]);
  37.                     isAdded[j]=true;;
  38.  
  39.                 }
  40.  
  41.             }
  42.             de.add(se.get(0));
  43.             sn.remove(0);
  44.             se.remove(0);
  45.         }
  46.     }
  47.  
  48.     public ArrayList BFS(String goal){
  49.         TreeNode current=null;
  50.         ArrayList opened=new ArrayList();
  51.         ArrayList closed=new ArrayList();
  52.  
  53.         opened.add(root);
  54.         sb=new StringBuffer();
  55.         sb.append(String.format("%-10s","EN")+String.format("%-25s","Opened")+"Closed");
  56.         sb.append("\n"+String.format(" %-10s","--")+String.format("%-25s","------")+"------");
  57.         sb.append(String.format("\n %-10s",""));
  58.         sb.append(String.format("%-25s",convertToString(opened))+convertToString(closed));
  59.         while(!opened.isEmpty()){
  60.  
  61.             current=(TreeNode)opened.get(0);
  62.             opened.remove(0);
  63.  
  64.             if(String.valueOf(current.getData()).equals(goal)){
  65.                 closed.add(current);
  66.                 sb.append(String.format("\n %-10s",current.getData()));
  67.                 sb.append(String.format("%-25s",convertToString(opened))+convertToString(closed));
  68.                 break;
  69.             }
  70.             for(int i=0;i<current.count();i++){
  71.                 opened.add(current.getChild(i));
  72.  
  73.             }
  74.             closed.add(current);
  75.             sb.append(String.format("\n %-10s",current.getData()));
  76.             sb.append(String.format("%-25s",convertToString(opened))+convertToString(closed));
  77.         }
  78.  
  79.         return closed;
  80.     }
  81.  
  82.     public ArrayList DFS(String goal){
  83.         TreeNode current=null;
  84.         ArrayList opened=new ArrayList();
  85.         ArrayList closed=new ArrayList();
  86.  
  87.         opened.add(root);
  88.         sb=new StringBuffer();
  89.         sb.append(String.format("%-10s","EN")+String.format("%-25s","Opened")+"Closed");
  90.         sb.append("\n"+String.format(" %-10s","--")+String.format("%-25s","------")+"------");
  91.         sb.append(String.format("\n %-10s",""));
  92.         sb.append(String.format("%-25s",convertToString(opened))+convertToString(closed));
  93.         while(!opened.isEmpty()){
  94.  
  95.             current=(TreeNode)opened.get(0);
  96.             opened.remove(0);
  97.  
  98.             if(String.valueOf(current.getData()).equals(goal)){
  99.                 closed.add(current);
  100.                 sb.append(String.format("\n %-10s",current.getData()));
  101.                 sb.append(String.format("%-25s",convertToString(opened))+convertToString(closed));
  102.                 break;
  103.             }
  104.             for(int i=current.count()-1;i>=0;i--){
  105.                 opened.add(0,current.getChild(i));
  106.  
  107.             }
  108.             closed.add(current);
  109.             sb.append(String.format("\n %-10s",current.getData()));
  110.             sb.append(String.format("%-25s",convertToString(opened))+convertToString(closed));
  111.         }
  112.  
  113.         return closed;
  114.     }
  115.  
  116.     public String getProcess(){
  117.         return sb.toString();
  118.     }
  119.  
  120.     public static String convertToString(ArrayList list){
  121.         String  str="[";
  122.         if(list.size()>0){
  123.             str+=((TreeNode)list.get(0)).getData();
  124.             for(int i=1;i<list.size();i++){
  125.                 str+=", "+((TreeNode)list.get(i)).getData();
  126.             }
  127.         }
  128.         str+="]";
  129.  
  130.         return str;  
  131.     }
  132.  
  133.     public TreeNode getTree(){
  134.         return root;
  135.     }
  136.    
  137. }