btreestring.java

简易模拟电梯系统

			}		
			
			pos = parRoot.nextAvailable();
			//System.out.print(123);
			if (pos >= 0) 
			{
				
				if (leaf != null) //if the children are leaves.
					parRoot.setLeafNode(key, leaf);
				//System.out.print(123);
			
				else 	//if the children are parrent nodes.
					parRoot.setParNode(key, par);
			}
			
			
			else // we shiuld create a new parRoot.
			{
				ParNode p = new ParNode();	// the new root
				long rootKey = parRoot.getLastKey();
				ParNode pNode = new ParNode();	
				
				if (leaf != null)// it is a leaf.					
						pNode.setLeafNode(key, leaf);
				else 
					pNode.setParNode(key,par);// it is a parent node.
					
				// let the new root point to its children.	
				p.setParNode(rootKey, parRoot);
				p.setParNode(key, pNode);
					
				// update height and add parRoot to new root
				height++;					
				parRoot = p;
			}
			
			return;
		}

		
		// I am a leafNode and my parent is not the root.
		else if (leaf != null && (height-1) == curLevel && curLevel > 1)
		{
			//System.out.print(123);
			ParNode pNode = (ParNode)v.elementAt(curLevel - 1);
			pos = pNode.nextAvailable();
			
			if (pos >= 0) {
				pNode.setLeafNode(key, leaf);
				// update the key of the upper level.
				updateKey(v, curLevel-1, key);
				return;
			}
			
			// We need a new parNode.
			else {
				ParNode newParNode = new ParNode();
				newParNode.setLeafNode(key, leaf);
				// update the upper level.
				updateTree(v, null, newParNode, curLevel-1, 
					key);
			}
			//System.out.print(123);
		}
		
		// I am a ParNode and my parent is not the root.
		else if (par != null && curLevel > 1) {
			ParNode pNode = (ParNode)v.elementAt(curLevel - 1);
			pos = pNode.nextAvailable();
			
			if (pos >= 0) {
				pNode.setParNode(key, par);
				// update the key of the upper level.
				updateKey(v, curLevel-1, key);
				return;
			}
			
			// We need a new parNode.
			else {
				ParNode newParNode = new ParNode();
				newParNode.setParNode(key, par);
				// update the upper level.
				updateTree(v, null, newParNode, curLevel-1,
					key);
			}
		}
		
		// something wrong, should never happen.
		else {
			/*
			System.out.println("wrong in the bottom of updateTree");
			*/
			return;
		}
	}       
	   
	    /**
         *  Private method.
         *  Used to update the last key when we append the tree.
         *  And we will not explain this method clearly.
         */
	private void updateKey(Vector v, int curLevel, long key) {
		int level = curLevel;
		
		// Go all the way up until the root, and update the 
		// key.
		while (level >= 0) {
			ParNode par = (ParNode)v.elementAt(level);
			par.updateLastKey(key);
			level--;
		}
	 }
        
        /**
         *  Searsh the LeafNode that the special index may in.
         *  @return LeafNode
         *  @param index It is a long tpye value.
         */
        private LeafNode searchLeaf(long index)
        {
                if(!this.isAParRoot)
                    return leafRoot;
                LeafNode leaf = null;
                ParNode par = parRoot;
                long key = (long) Math.floor(index/LEAF_LENGTH);
                while(leaf == null)
                {
                      int k;
                        boolean find = false;
                        for(k = 0; k < ORDER_BTREE && !find; k++)
                        {
                                if(par.getKeyAt(k) >= key)
                                {
                                        find = true;
                                        if(par.getLeafAt(0) == null)
                                                par = par.getNextLevelAt(k);
                                      else
                                              leaf = par.getLeafAt(k);
                                      //return leaf;
                                }
                     	}//return leaf;
                }return leaf;
                
         }
        
        //Override the toString() method;
        public String toString()
        {
        	String str="";
        	LeafNode lf=this.leafRoot;
        	while(lf!=null)
        	{
        		str+=lf.toString();
        		lf=lf.getNext();
        	}
        	return str;
        }
        /*
        public String toString()
        {
        	String str="";
        	for(long i=0;i<this.StringLength;i++)
        	{
        	    str+=charAt(i);	
        	}
        	return str;
        }*/
         /**
          *  Private method.
          *  Put a leafNode in to a vector that the leafNode contains
          *  A special index LeafNode.
          *  @return Vector
          *  @see java.util.Vector
          *  @Parameter long.
          */
         private Vector findLeaf(long beginKey)
         {
                 Vector vec=new Vector();
                 if(!this.isAParRoot)
                 {
                         vec.addElement(leafRoot);
                         return vec;
                 }
                 LeafNode leaf=null;
                 ParNode  par =parRoot;
                 vec.addElement(parRoot);
                 while(leaf==null)
                 {
                         int k=0;
                         boolean find=false;
                         while(k < ORDER_BTREE && !find) {
	           			if(par.getKeyAt(k) == beginKey) 
		     				find = true;
					    else
						   k++;
		 	        	}
                         if(par.getLeafAt(0)==null)
                         {
                                 par=par.getNextLevelAt(k);
                                 vec.addElement(par);
                                 //return vec;
                         }
                         else
                         {
                                 leaf=par.getLeafAt(k);
                                 vec.addElement(leaf);
                                 //return vec;
                         }
                         
                 }
                 return vec;
         }
         
    /**
     *  The long number of our string length.
     *  The number of the charactors that our BTreeString contains.
     */
	private long StringLength;
	
	/**
	 *  The hight of our BTreeString.
	 */
	private int  height;
	
	/**
	 *  The LeafNode used to line search.
	 */
	private LeafNode leafRoot;
	
	/**
	 *  The ParNode used to ramdom search.
	 */
	private ParNode  parRoot;
	
	/**
	 *  A boolean type judge whether a node is a parNode.
	 */
	private boolean  isAParRoot;
	
	/**
	 *  A const number that limit the size of each leafNode.
	 *  The same as the size of the leafNode.
	 */
    private final static int LEAF_LENGTH=LeafNode.SMALL_STRING_LENGTH;
    
    /**
     *  A const number used as the order of the tree.
     *  The same as the order of the parNode.
     */
    private final static int ORDER_BTREE=ParNode.ORDER_BTREE;
    
    /**
     *  File name: LeafNode.java
     *  Nested class of the B+Tree that hold the elements 
     *  of the BigString.
     */
	public class LeafNode {
		/**
		 *  Construct a new leaf.
		 *  attention: value.length <= SMALL_STRING_LENGTH.
		 */
		public LeafNode(char [] value, long k) 
		{
			elements = value;
			nextNode = null;
			key = k;
		}
		
		/**
		 *  @return LeafNode
		 *  Return my younger sibling.
		 */
		public LeafNode getNext() 
		{
			 return nextNode; 
		}
		
		/**
		 *  @return void
		 *  Link me and my younger sibling.
		 */
		public void setNext(LeafNode theNext)
		{ 
			nextNode = theNext;
		}