btreestring.java

简易模拟电梯系统

/**
 *  FIle name BTreeString.java
 *  @auther caiwanfu
 *  @auther [e-mail]
 *  @Copyright jiaben software_NJU
 *  @Team member:jiaben
 *               may i
 *               icecreame
 *               yymycabbage
 */
 /**
  *  This is the file used to set out tree
  *  It is a B+tree.
  */
package ulang;

import java.io.*;
import java.util.Vector;

/**
 *  Class Name: BTreeStrin
 *  The power of read is public.
 */
public class BTreeString
{
    /**
     *  Constructors.
     */
     /**
      *  Constructor with a string as its parameter.
      *  @param str A String object.
      *  @see java.lang.String
      *  The BigString information should the the same as the str.
      */
    public BTreeString(String str)
    {
    	/** 
    	 *  Declaration of some variable.
    	 */
            long prePost,post,nextPost;
            long nodeCount=0;
            
         /**
          *  Change the member variable of the class.
          */   
            StringLength=str.length();
            char []array=new char[LEAF_LENGTH];

         /**
          *  Set the ParNode and the tree.
          */
            if(StringLength<LEAF_LENGTH)
            {
                nextPost=StringLength;
            }
            else
            {
                    nextPost=LEAF_LENGTH;
            }
            for(post=0;post<nextPost;post++)
            {
                    array[(int)(post)]=str.charAt((int)post);
            }

         /**
          *  Set the LeafNode of the tree.
          */
            leafRoot=new LeafNode(array,nodeCount);
            this.height=1;
            nodeCount++;
            while (nextPost < StringLength)
            {
            	        //System.out.println(nodeCount);
                        prePost = post;
                        char [] ch = new char[LEAF_LENGTH];

                        nodeCount++;
                        if (StringLength < (nodeCount*LEAF_LENGTH))
                                nextPost = StringLength;
                        else
                                nextPost = nodeCount * LEAF_LENGTH;

                        for (int i = 0; i < (nextPost-prePost); i++) {
                                ch[i] = str.charAt(((int)post));
                                post++;
                        }
                        append(ch, nodeCount-1);
                        //System.out.print(str.charAt(((int)post)));
                }

    }
    /**
     *  Constructor with none parameter.
     *  To set a empty tree.
     */
    public BTreeString()
    {
            this("");
    }
    
    /**
     *  This method used to get a substring from the whole tree.
     *  The char to get should the the one before the end index.
     *  @return String  
     *  <br>The string with the first char at index 
     *  beginIndex and the last char at endIndex-1;
     *  @param beginIndex The first Index of the string, A long type value 
     *  @param endIndex The last Index of the string, A long type value
     */
    public String getString(long beginIndex,long endIndex)throws 
                  StringIndexOutOfBoundsException
    {
            long beginKey,endKey,myNewRememberKey;
            String str="";
            
            LeafNode lf;
            lf=searchLeaf(beginIndex);
            
            beginKey=(long)Math.floor(beginIndex/LEAF_LENGTH);
            endKey  =(long)Math.floor(endIndex/LEAF_LENGTH);
            if(beginKey==endKey)
            
                    return lf.stringBetween(
                    	(int)(beginIndex-beginKey*LEAF_LENGTH),
                        (int)(endIndex-endKey*LEAF_LENGTH));
            
            else
            {
            	//System.out.println(str.length()+"aa1");
                    str+=lf.stringBetween(
                    	(int)(beginIndex-beginKey*LEAF_LENGTH),
                        LEAF_LENGTH);
             //System.out.println(str.length()+"aa1");
            }
            myNewRememberKey=beginKey;
             
            while(myNewRememberKey<(endKey-1))
            { 
               		//str+=this.searchLeaf(beginIndex).toString();
                    lf=lf.getNext();
                    str+=lf.toString();//toString();
                    myNewRememberKey++;
                    //beginKey+=BTreeString.LEAF_LENGTH;
                   
            }
            if((endIndex-endKey*LEAF_LENGTH)>0)
            {
            	
                    lf=lf.getNext();
			        str += lf.stringBetween(0, 
				(int)(endIndex - endKey * LEAF_LENGTH));
				//System.out.println(str.length()+"aa2");
            }
            
            return str;
    }
    
    /**
     *  The method used as the method at String.java
     *  At the use can be hypothesize from the name.
     *  @see java.lang.String#charAt(int)
     *  @return char
     *  <br>The charactor which you want to get at the 
     *  Index of number index.
     *  @param index A long type value
     */
    public char charAt(long index)
    {
            char c = ' ';
            LeafNode ln;
            long beginKey;
            ln=searchLeaf(index);
            beginKey=(long)Math.floor(index/LEAF_LENGTH);
            c=ln.getElementAt((int)(index-beginKey*LEAF_LENGTH));
            return c;
    }
    
    /**
     *  the get method.
     */
     /**
      *  @return long 
      *  <br>return the length of string.
      */ 
    public long getLength()
    {
            return this.StringLength;
    }
    
    /**
     *  The compare method to judge whether the two are the same.
     *  @return int
     *  <br>If the two are not of the same length, when the actual lenght
     *  smaller than bs, return i, if great, return -1;
     *  else if the content are the same return 0,else return -1;
     */
    public int compareTo(BTreeString bs)
    {
            if(this.StringLength<bs.getLength())
            {
                    return 1;
            }
            else if(this.StringLength>bs.getLength())
            {
                    return -1;
            }
            else
            {
                if(this.toString().equals(bs.toString()))
                    return 0;
                    else
                    return -1;
            }
    }
    
    /**
     *  Add a node at the end of the tree.
     *  The method use as a special example of concat method;
     *  the return is this object itself.
     *  @param valve A char array
     *  @param numNodes And the node after it
     */
    private void append(char[]value,long numNodes){
            Vector v;
            
            if(numNodes>0)
                {
                	v=findLeaf(numNodes-1);
                	//System.out.print(v.size());
                }
            else
               return;//System.out.print(v.size());
            LeafNode lastNode=(LeafNode)v.elementAt(height-1);
            LeafNode newLastNode=new LeafNode(value,numNodes);
            lastNode.setNext(newLastNode);
            //Addnew node to the end of the tree.
            updateTree(v,newLastNode,null,(height-1),numNodes);
    }
    
    /**
     *  Private method.Used to change the last node.
     *  And when we need to set the concat method it is much 
     *  Useful. And we think we need not to explain the method 
     *  clearly. Because the method is transparent.
     */
     private void updateTree(Vector v, LeafNode leaf, ParNode par, 
	 				int curLevel, long key) 
	 {
		int pos;
		//Exception solving			
		if (curLevel > (height-1) || (leaf != null && par != null)  || (parRoot != null && leafRoot != null) 
				|| (leaf == null && par == null) || key <= 0 || (parRoot == null && leafRoot == null))
			System.out.println("updateTree: wrong in parameters!");
		if (leaf != null && height == 1) 
		{
			if (leafRoot == null) 
			{
				//System.out.print(123);
				return;
			}
			//System.out.print(123);			
			parRoot = new ParNode();
			//System.out.print(123);
			LeafNode aLeaf = leafRoot;
			//System.out.print(123);
			// let the new root point to its children.
			parRoot.setLeafNode((key-1), aLeaf);
			//System.out.print(123);			
			parRoot.setLeafNode(key, leaf);
			//System.out.print(123);
			leafRoot = null;
			height++;
			//System.out.print(123);
			if (!this.isAParRoot)
				this.isAParRoot= true;
			//System.out.print(123);
			return;
		}
		//System.out.print(123);
		
		else if (curLevel == 1) // My parent is a parRoot.
		{
			if (parRoot == null) 
			{
				// System.out.println("parRoot is null!");
				return;