import java.util.ArrayList;
import java.io.*;

 class Node {
//  public Node parent = null;
  private ArrayList<Node> childrenList = new ArrayList<Node>();
  private String word;  
  private int wordIndex;
  private boolean isRoot = false;
  public Node() {
  	word="";
  	wordIndex=0;
  }
  public Node(String word,int wordIndex) {
    this.word = word;
    this.wordIndex=wordIndex;
  }
  public void addChild(Node child) {
    childrenList.add(child);
  }
  public boolean isInternalNode() {
    if (childrenList != null)
        return true;
    else
        return false;
  }
  public boolean isLeaf() {
    if (childrenList == null)
        return true;
    else
        return false;
  }
  public boolean isRoot() {
    return isRoot;
  }
  public void removeChildAt(int index) {
    childrenList.remove(index);
  }
  public void setRoot() {
    isRoot = true;
  }
  public ArrayList<Node> getChildrenList() {
    return childrenList;
  }
  public String getWord() {
	return word;
  }  
  public int getWordIndex() {	
	return wordIndex;
  }
}


public class IndexTree{
	private Node root;	
	public IndexTree(){
	}
	public Node genarateTree(File indexFile){
		indexFile=new File("index.txt");
		try{
			BufferedReader br=new BufferedReader(new FileReader(indexFile));
			String line=br.readLine();
			String word=line.substring(0,line.indexOf(" "));
			int wordIndex=Integer.parseInt(line.substring(line.indexOf(" ")+1));
			root=new Node(word,wordIndex);
			root.setRoot();
//			ArrayList<Node>  rootChildList=root.getChildrenList();
			char lastRootChar='0';
			Node middleNode=null;
			char cstart='1';
			while(line!=null){
				word=line.substring(0,line.indexOf(" "));
				wordIndex=Integer.parseInt(line.substring(line.indexOf(" ")+1));
				Node newNode=new Node(word,wordIndex);

				cstart=word.charAt(0);
				if (Character.isUpperCase(cstart))
				   cstart=Character.toLowerCase(cstart);

				if(cstart!=lastRootChar){
					lastRootChar=cstart;
				    middleNode=new Node(newNode.getWord(),newNode.getWordIndex());
				    root.addChild(middleNode);	
				}
			    middleNode.addChild(newNode);
			    
			    line=br.readLine();
			}
			br.close();
		}
		catch(IOException e){
			e.printStackTrace();
		}
		return root;
	}
	
	
	private boolean checkWord(String word){
		String stemp=word.trim().toLowerCase();
		for(int i=0;i<stemp.length();i++){
			if(stemp.charAt(i)>'z'||stemp.charAt(i)<'a')
			return false;
		}
		return true;
	}
	
	
	public int GetIndex(String word){
		if(!checkWord(word)){
			System.out.println("not a English word...");
			return -2;
		}
		char startChar=word.charAt(0);
		Node middleNode=null;
		ArrayList rootList=root.getChildrenList();
		if (Character.isUpperCase(startChar))
			startChar=Character.toLowerCase(startChar);
		for(int i=0;i<rootList.size();i++){
			char mchar=((Node)rootList.get(i)).getWord().charAt(0);
			if (Character.isUpperCase(mchar))
			    mchar=Character.toLowerCase(mchar);
			if(mchar==startChar){
			    middleNode=(Node)rootList.get(i);
			}
		}
//		Node middleNode=(Node)root.getChildrenList().get(startChar-'a');
		ArrayList<Node> middleNodeList=middleNode.getChildrenList();
		int end=middleNodeList.size()-1;//System.out.println(end);
/*		for(int i=0;i<=end;i++){
			System.out.print(((Node)middleNodeList.get(i)).getWord());
			System.out.print("  ");
			System.out.println(((Node)middleNodeList.get(i)).getWordIndex());
		}*/
		int start=0;
		int middle=(start+end)/2;
		boolean find=false;
		int wordIndex=-1;
		Node leafNode=(Node)middleNodeList.get(end);
			if(leafNode.getWord().equals(word)){
				wordIndex=leafNode.getWordIndex();
//				System.out.println(word+" "+wordIndex);
				find=true;
			}
		while(end>start+1){//System.out.print("start"+start);System.out.print("  end"+end);System.out.print("  middle  "+middle);System.out.println();
		    leafNode=(Node)middleNodeList.get(middle);
			if(leafNode.getWord().equals(word)){
				wordIndex=leafNode.getWordIndex();
//				System.out.println(word+" "+wordIndex);
				find=true;
				break;
			}
			else{
				if(word.compareTo(leafNode.getWord())<0){
					end=middle;
					middle=(start+end)/2;
				}
				else{
					start=middle;
					middle=(start+end)/2;
				}				    
		    }   
	   }
	   if(find==true){
//	   	 System.out.println("找到....");
	   }
	   else{
//	     System.out.println("未找到，準備加入詞典");
//	     if(((Node)middleNodeList.get(end)).getWord().compareTo(word)<0)
//	     	wordIndex=-((Node)middleNodeList.get(end)).getWordIndex()-1;
//	     else
//	        wordIndex=-((Node)middleNodeList.get(start)).getWordIndex()-1;
	   }
	   return wordIndex;
   }
   public String lookUp(int wordIndex){
   	  File dicFile=new File("dictionary.txt");
   	  String result="";
   	  String phoneticSymbol="";
   	  String part="";
   	  String explanation="";
   	  try{
	   	  RandomAccessFile raf=new RandomAccessFile(dicFile,"rw");
	   	  raf.seek(wordIndex);
	   	  result=new String(raf.readLine().getBytes("ISO8859-1"),"GB2312");
	   	  String word=result.substring(0,result.indexOf("["));
	   	  phoneticSymbol=result.substring(result.indexOf("["),result.indexOf("]")+1);
	   	  part=result.substring(result.indexOf("]")+1,result.indexOf(".")+1);
	   	  explanation=result.substring(result.lastIndexOf(".")+1);
	   	  raf.close();
	   	  System.out.println("單詞： "+word);
	   	  System.out.println("音標： "+phoneticSymbol);
	   	  System.out.println("詞性： "+part);
	   	  System.out.println("解釋： "+explanation);
	  }catch(IOException e){
	  	e.printStackTrace();
	  }          
   	  return result;
   }
   public boolean lookUpInExtra(String word){
   	  File extraFile=new File("extra.txt");
   	  String result="";
   	  String phoneticSymbol="";
   	  String part="";
   	  String explanation="";
   	  try{
   	  	BufferedReader br=new BufferedReader(new FileReader(extraFile));
   	  	String line="";
   	  	while((line=br.readLine())!=null){
   	  		if(line.substring(0,line.indexOf("[")).trim().equals(word)){
   	  			result=line;
   	  			phoneticSymbol=result.substring(result.indexOf("["),result.indexOf("]")+1);
			   	part=result.substring(result.indexOf("]")+1,result.indexOf(".")+1);
			   	explanation=result.substring(result.lastIndexOf(".")+1);
			   	  System.out.println("單詞： "+word);
			   	  System.out.println("音標： "+phoneticSymbol);
			   	  System.out.println("詞性： "+part);
			   	  System.out.println("解釋： "+explanation);
			   	br.close();  
   	  			return true;
   	  		}
   	  	}  	  	
   	  }catch(IOException e){
	  	e.printStackTrace();
	  }
	  return false;
   }

}