rbtree.java

关于用java实现的程序

           	else{
       			RBNode w = x.Parent().Left();

               		if (w.IsRed()){
               			w.SetColorBlack();
                		x.Parent().SetColorRed();
                  		RotateRight(x.Parent(), g);
                  		w = x.Parent().Left();
                  		}
               		if (w.Right().IsBlack() && w.Left().IsBlack()){
               			w.SetColorRed();        
                  		x = x.Parent(); 
                  		}       
               		else{   
                                        
               			if (w.Left().IsBlack()){
                  			w.Right().SetColorBlack();
                     			w.SetColorRed();
                     			RotateLeft(w, g);
			                w = x.Parent().Left();
                     			}
                               
                  		if (x.Parent().IsBlack()) 
					w.SetColorBlack();
                  		else w.SetColorRed();
                  		x.Parent().SetColorBlack();
                  		w.Left().SetColorBlack();
		                RotateRight(x.Parent(), g);
                  		x = root;
                  		}
 
	        	}
        	}
        x.SetColorBlack();

	}

	/* obtain the blackheight of the tree */
	public int BlackHeight(){
		RBNode x;
		RBNode xl, xr;
		int pos_x = 200, pos_y = 20;
		int height = 0;
		
		x = root;
		
		while (x != sentinel){
 			x = x.Right();
			if (x.IsBlack()) {
				height++;
				}
			}
		
		return height; 	
		}

	private void SetPositions(RBNode n, int h, int w) {
		RBNode xl, xr;
		Edge e;
		int dx = 20, dy = 50, y_init, width;
		int bh;

		width = w;
		bh = BlackHeight();
		y_init = h/(2*bh);
		
		if (n.Parent()==null) { //root node, level 1 node
			n.x = width/2;
			n.y = y_init;
			}
		else if (n.Parent().Parent() == null){ //level 2 node
			if (n == n.Parent().Left()) {
				n.x = width/4;
				n.y = y_init*2 ;
				}
				if (n == n.Parent().Right()) {
					n.x = 3*width/4;
					n.y = y_init*2;
					}
			}
		else{
			if (n == n.Parent().Left()) {
				n.x = n.Parent().x - Math.abs(n.Parent().x - n.Parent().Parent().x)/2;
				n.y = n.Parent().y + y_init;
				}
			if (n == n.Parent().Right()) {
				n.x = n.Parent().x + Math.abs(n.Parent().x - n.Parent().Parent().x)/2;
				n.y = n.Parent().y + y_init;
				}															 
			}
		}
	
	private void Reset( RBNode n, int k  ) {
		int pos;

		pos = k - 1;
		buffer[pos] = n;

		System.out.println("RBTree: Reset: (2*k)-1 = " +((2*k)-1));		

		buffer[(2*k)-1] = n.Left();
		System.out.println("RBTree: Reset: after left "+((2*k)-1));
		buffer[2*k] = n.Right();
		System.out.println("RBTree: Reset: after right "+(2*k));
	
		if (n.Left() != sentinel) {
			Reset( n.Left(), 2*k );
			}
		if (n.Right() != sentinel) {
			Reset( n.Right(), (2*k)+1 );
			}
		
		}

	public void setPanel( DrawingPanel dp ) {
		this.dpAfter = dp;
		g = dp.getGraphics();
		}
	
	public void drawRBTree(AlgAnimFrame frame) {
		int i, k, x, max_x = 0, min_x = 0, max_y = 0, cnt;
		int h, w;
		RBNode temp;
		double x_scale, y_scale;
		Edge e;
		int buf_size;

		dpAfter = frame.getDrawingPanel();
		g = dpAfter.getGraphics();
		h = dpAfter.getPanelHeight();
		w = dpAfter.getPanelWidth();
		
				

		Dimension d = dpAfter.size();
		
		System.out.println("In DT");

		if(d.width < 1 || d.height < 1){
			System.out.println("d.height: "+d.height+ ", d.width: " +d.width);
			//return;
			}

		
		if((offscreen == null) || (d.width != offscreensize.width) || (d.height != offscreensize.height)) {
			System.out.println("DrawRBTree: Creating offscreen");
			offscreen = dpAfter.createImage(d.width, d.height);
			offscreensize = d;
			if(offscreen == null) System.out.println("Offscreen still null");
			offGraphics = offscreen.getGraphics();
			}
			if(offscreen == null) System.out.println("Offscreen still null");

		offGraphics.setColor(dpAfter.getBackground());
		offGraphics.fillRect(0, 0, d.width, d.height);

		if (!v_rbnodes.isEmpty()) {
			System.out.println("not empty");
			//get the root node
			temp = Root_RBNode();
			if (SetSubRBTreePos( temp, h, w )) {
				
				for (i = 0; i < v_rbnodes.size(); i++) {
	   	   			temp = (RBNode)(v_rbnodes.elementAt(i));
					x = temp.x;
	   	   			if ( x > max_x ) max_x = x;
					if ( x < min_x ) min_x = x;
			   		x = temp.y;
			   		if ( x > max_y ) max_y = x;
	   				}
				x_scale = (double)w / ( max_x + padding );
		   		y_scale = (double)h/ ( max_y + padding );
			
					
				System.out.println("RBTree: drawRBTree: size is "+v_rbnodes.size());
				buf_size = Buf_Size(v_rbnodes.size());
				buffer = new RBNode[buf_size];
				Init_Buffer(buf_size);
				System.out.println("BRTree: drawRBTree: buf_size is "+buf_size);
				temp = Root_RBNode();
				buffer[0] = temp;
				k = 1;
				Reset( temp, k );
				
				for (i = 0; i < buf_size; i++) {
					temp = buffer[i];
					//if ( temp != sentinel ) {
	  		 			temp.Set_Scale( x_scale, y_scale );
						//System.out.println("RBTree: drawRBTree: node "+temp.Cost()+", "+temp.x+", "+temp.y);
						if (temp.Parent() != null) {
							System.out.println("parent "+temp.Parent().Cost());
							}
						//System.out.println("x scale "+x_scale+", y scale "+y_scale);
						//System.out.println("h "+h+", w "+w);
						temp.show_cost = true;
						temp.ans_colour = Color.yellow;
						temp.show_id = false;
						if (temp != sentinel) {
							temp.Draw_Node(offGraphics, dpAfter); 
							//offscreen = temp.getOffscreen();
							if (temp.Parent() != null ) {
								e = new Edge(temp.Parent(), temp, 0);
								e.show_cost = false;
								e.Draw_Edge(offGraphics, 1, 0);
								temp.Parent().Redraw_Node(offGraphics, dpAfter);
								//offscreen = temp.getOffscreen();
								}
							temp.Redraw_Node(offGraphics, dpAfter);
							//offscreen = temp.getOffscreen();
							}
					}
				}
			}
		}

	private int Buf_Size( int i ) {
		int cnt = 0;
		int two = 2;
		int value;
		int total;
		int temp;
		int same, extra;
		
		value = (int)(Math.pow(two, cnt));
		while ( i >= value ) {
			cnt++;
			value = (int)(Math.pow(two, cnt) - 1);
			}
		/*
		same = value - i;
		extra = i - ((int)(Math.pow(two, cnt-1)) - 1);
		extra = extra*2;
		total = same + extra + i;
		*/
		total = (int)(Math.pow(two, cnt+1)) - 1;
		return total;
		}
	
	private void Init_Buffer(int cnt) {
		int i;

		for (i = 0; i < cnt; i++) {
			buffer[i] = sentinel;
			}
		}
	
/*	private void Draw_From_Root(Graphics g, RBNode n, double xs, double ys, DrawingPanel dp) {
		Edge e;
		
		n.Set_Scale(xs, ys);
		n.show_cost = true;
		n.ans_colour = Color.yellow;
		n.show_id = false;
		n.Draw_Node(g, dp);
		System.out.println("n "+n.Cost()+", "+n.x+", "+n.y);
		if (n.Left() != sentinel) {
			System.out.println("n.Left "+n.Left().Cost()+", "+n.Left().x+", "+n.Left().y);
			n.Left().Set_Scale(xs, ys);
			n.Left().show_cost = true;
			n.Left().ans_colour = Color.yellow;
			n.Left().show_id = false;
			n.Left().Draw_Node(g, dp);
			e = new Edge(n, n.Left(), 0);
			e.show_cost = false;
			e.Draw_Edge(offGraphics, 1, 0);
			n.Redraw_Node(g, dp);
			n.Left().Redraw_Node(g, dp);
			Draw_From_Root(g, n.Left(), xs, ys, dp);
			}
		if (n.Right() != sentinel) {
			System.out.println("n.Right "+n.Right().Cost()+", "+n.Right().x+", "+n.Right().y);
			n.Right().Set_Scale(xs, ys);
			n.Right().show_cost = true;
			n.Right().ans_colour = Color.yellow;
			n.Right().show_id = false;
			n.Right().Draw_Node(g, dp);
			e = new Edge(n, n.Right(), 0);
			e.show_cost = false;
			e.Draw_Edge(g, 1, 0);
			n.Redraw_Node(g, dp);	
			n.Right().Redraw_Node(g, dp);
			Draw_From_Root(g, n.Right(), xs, ys, dp);
			}
		}*/
	
	
	private boolean SetSubRBTreePos( RBNode n, int h, int w ){
		
		SetPositions(n, h , w);
		if (n.Left() != sentinel) {
			SetSubRBTreePos(n.Left(), h, w);
			}
		if (n.Right() != sentinel) {
			SetSubRBTreePos(n.Right(), h, w);
			}
	
		return true;

		}
						  


	private RBNode Root_RBNode() {
		int i;
		RBNode temp_root = new RBNode(-1, -1, -1);;

		temp_root = (RBNode)(v_rbnodes.firstElement());
		for (i = 0; i < v_rbnodes.size(); i++) {
			temp_root = (RBNode)(v_rbnodes.elementAt(i));
			if (temp_root.Parent()==null) {
				break;
				}
			}
		return temp_root;
		}
	
		
	public int RedCount(){
   	RBNode x;
      int redct = 0;

      x = root;
      while (x != sentinel){
      	x = x.Right();
         if (x.IsRed()) redct++;

        }
      return redct;
		}



	public void PrintNode(RBNode x){
   	if (x == sentinel) System.out.println("x is a sentinel node.");
      else{
      	System.out.print("Node has data: "); 
			System.out.println(x.Cost());
			System.out.print("Color: ");
			if(x.IsBlack()) System.out.println("Black");
			else System.out.println("Red");
 
         System.out.print("Left child:  ");
         if (x.Left() == sentinel) System.out.println(" is a sentinel node.");
			else System.out.println(x.Left().Cost());
			System.out.print("Color: ");
         if(x.Left().IsBlack()) System.out.println("Black");
         else System.out.println("Red");		

			System.out.print("Right child:  ");
			if (x.Right() == sentinel) System.out.println(" is a sentinel node.");
         else System.out.println(x.Right().Cost());
			System.out.print("Color: ");            
         if(x.Right().IsBlack()) System.out.println("Black");
         else System.out.println("Red");

			System.out.print("Parent:  ");
			if(x.Parent() != null){
		
      	   if (x.Parent() == sentinel) System.out.println(" is a sentinel node.");
      	   else System.out.println(x.Parent().Cost());
				System.out.print("Color: ");            
         	if(x.Parent().IsBlack()) System.out.println("Black");
         	else System.out.println("Red");
				}	
			else System.out.println("Null parent ie. root reached!");
      		}
		}


	public void PrintCoverage(){
		System.out.println("case1 count: "+case1ct);
		System.out.println("case2 count: "+case2ct);
		System.out.println("case3 count: "+case3ct);
		System.out.println("case4 count: "+case4ct);
		System.out.println("case5 count: "+case5ct);
		System.out.println("case6 count: "+case6ct);
		System.out.println("case7 count: "+case7ct);
		System.out.println("case8 count: "+case8ct);
		}

	public void drawLabel(ShadowLabel label, int x, int y, AlgAnimFrame frame) {
		FontMetrics fm = frame.getDrawingPanel().getFontMetrics(label.getFont());
		int str_width = fm.stringWidth(label.getText());
		int x1 = (frame.getDrawingPanel().getPanelHeight() - str_width)/2;

		drawRBTree(frame);
		label.move(x1, y);
		label.draw(offGraphics);
		Graphics g = dpAfter.getGraphics();
		g.drawImage(GetOffscreen(), 0, 0, null);
		}

	public void drawBeforeLabel(ShadowLabel label, int x, int y, AlgAnimFrame frame) {
		FontMetrics fm = frame.getBeforeDp().getFontMetrics(label.getFont());
		int str_width = fm.stringWidth(label.getText());
		int x1 = (frame.getBeforeDp().getPanelHeight() - str_width)/2;

		drawRBTree(frame);
		beforeOffSc = GetOffscreen();
		beforeOffGraphics = GetOffGraphics();
		label.move(x, y);
		label.draw(beforeOffGraphics);
		Graphics g = dpBefore.getGraphics();
		g.drawImage(beforeOffSc, 0, 0, null);
		}



	public void initBeforeOffsc(AlgAnimFrame frame, RBTree tree) {
		int h, w;
	
		dpBefore = frame.getBeforeDp();
		g = dpBefore.getGraphics();
		h = dpBefore.getPanelHeight();
		w = dpBefore.getPanelWidth();

		Dimension d = dpBefore.size();

		if(d.width < 1 || d.height < 1){
			System.out.println("d.height: "+d.height+ ", d.width: " +d.width);
			//return;
			}

		
		if((beforeOffSc == null) || (d.width != beforeOffSize.width) || (d.height != beforeOffSize.height)) {
			System.out.println("DrawRBTree: Creating offscreen");
			beforeOffSc = dpBefore.createImage(d.width, d.height);
			beforeOffSize = d;
			if(beforeOffSc == null) System.out.println("Offscreen still null");
			beforeOffGraphics = beforeOffSc.getGraphics();
			}
			if(beforeOffSc == null) System.out.println("Offscreen still null");

		beforeOffGraphics.setColor(dpBefore.getBackground());
		beforeOffGraphics.fillRect(0, 0, d.width, d.height);
		g.drawImage(beforeOffSc, 0 ,0, null);
		}
	
	public void DrawOffScreen(AlgAnimFrame frame, RBTree tree) {
		drawRBTree(frame);
		g.drawImage(tree.GetOffscreen(), 0, 0, null);
		}

	public Image GetOffscreen() {
		return offscreen;
		}

	public Graphics GetOffGraphics() {
		return offGraphics;
		}	
	
	public Image GetBeforeOffSc() {
		return beforeOffSc;
		}

	public Graphics GetBefOffGraphics() {
		return beforeOffGraphics;
		}	


	}