btree.cpp

两种btree算法

	//}

	return;



//  int p,n;
//  n = rand()%modules_N;
//
////  changed_nodes.clear();
////  changed_root = NIL;
//
//
//  if(rotate_rate > rand_01()){
////    changed_nodes.push_back(nodes[n]);
//    nodes[n].rotate = !nodes[n].rotate;
//    if(rand_bool()) nodes[n].flip = !nodes[n].flip;
//  }
//  else{ 	
//
//    if(swap_rate >rand_01()){
//      do{
//        p = rand()%modules_N;
//      }while(n==p||nodes[n].parent==p||nodes[p].parent==n);
//
////      changed_nodes.push_back(nodes[p]);
////      changed_nodes.push_back(nodes[n]);
//
//      swap_node(nodes[p],nodes[n]);
//
//    }else{
//      do{
//        p = rand()%modules_N;
//      }while(n==p);
//
////      changed_nodes.push_back(nodes[p]);
////      changed_nodes.push_back(nodes[n]);
//
//      delete_node(nodes[n]);
//      insert_node(nodes[p],nodes[n]);
//    }
//  }
}

void B_Tree::swap_node(Node &n1, Node &n2)
{

	if(n1.left!=NIL)
	{  
		nodes[n1.left].parent  = n2.id;
	}
	if(n1.right!=NIL)
	{
		nodes[n1.right].parent = n2.id;  
	}
	if(n2.left!=NIL)
	{
		nodes[n2.left].parent  = n1.id;
	}
	if(n2.right!=NIL)
	{
		nodes[n2.right].parent = n1.id;  
	}

	if( n1.parent != n1.id )
	{
		if( n1.parent != n1.id && n1.parent != NIL)
		{
			//add_changed_nodes(n1.parent);
			if(nodes[n1.parent].left==n1.id)
				nodes[n1.parent].left  = n2.id;
			else
				nodes[n1.parent].right = n2.id; 
		}
		else
		{
			changed_root = n1.id;
			nodes_root = n2.id;
		}
	}

	if( n2.parent != n2.id )
	{
		if( n2.parent != NIL )
		{
			if(nodes[n2.parent].left==n2.id)
				nodes[n2.parent].left  = n1.id;
			else
				nodes[n2.parent].right = n1.id; 
		}
		else
		{
			nodes_root = n1.id;
		}
	}

	swap(n1.left,n2.left);
	swap(n1.right,n2.right);
	swap(n1.parent,n2.parent);
}

void B_Tree::swap_node2( Node &n1, Node &n2)
{
	if( n1.parent != n2.id && n2.parent != n1.id )
		swap_node( n1, n2 );
	else
	{
		bool leftChild;
		bool parentN1 = ( n1.id == n2.parent );
		if( parentN1 )
		{
			if( n1.left == n2.id )
			{
				n1.left = NIL;
				leftChild = true;
			}
			else
			{
				n1.right = NIL;
				leftChild = false;
			}
			n2.parent = n2.id;
		}
		else
		{
			if( n2.left == n1.id )
			{
				n2.left = NIL;
				leftChild = true;
			}
			else
			{
				n2.right = NIL;
				leftChild = false;
			}
			n1.parent = n1.id;
		}

		swap_node( n1, n2 );
		if( parentN1 )
		{
			n1.parent = n2.id;
			if( leftChild )
			{
				n2.left = n1.id;
			}
			else
			{
				n2.right = n1.id;
			}
		}
		else
		{
			n2.parent = n1.id;
			if( leftChild )
			{
				n1.left = n2.id;
			}
			else
			{
				n1.right = n2.id;
			}
		}
	}
}

void B_Tree::insert_node(Node &parent, Node &node)
{
	node.parent = parent.id;
	bool edge = rand_bool();

	if(edge)
	{
		// place left

		//add_changed_nodes(parent.left);
		node.left  = parent.left;
		node.right = NIL;
		if(parent.left!=NIL)
			nodes[parent.left].parent = node.id;

		parent.left = node.id;
	}
	else
	{
		// place right

		//add_changed_nodes(parent.right);
		node.left  = NIL;
		node.right = parent.right;
		if(parent.right!=NIL)
			nodes[parent.right].parent = node.id;

		parent.right = node.id;
	}
}

void B_Tree::delete_node(Node &node)
{
	int child    = NIL;		// pull which child
	int subchild = NIL;		// child's subtree
	int subparent= NIL; 

	if(!node.isleaf())
	{
		bool left = rand_bool();			// choose a child to pull up
		if(node.left ==NIL) left=false;
		if(node.right==NIL) left=true;

		//add_changed_nodes(node.left);
		//add_changed_nodes(node.right);

		if(left)
		{
			child = node.left;			// child will never be NIL
			if(node.right!=NIL)
			{
				subchild  = nodes[child].right;
				subparent = node.right;
				nodes[node.right].parent = child; 
				nodes[child].right = node.right;	// abut with node's another child
			}
		}
		else
		{
			child = node.right;
			if(node.left!=NIL)
			{
				subchild  = nodes[child].left;
				subparent = node.left;
				nodes[node.left].parent = child;
				nodes[child].left = node.left;
			}
		}
		//add_changed_nodes(subchild);
		nodes[child].parent = node.parent;
	}

	if(node.parent == NIL)			// root
	{			
		// changed_root = nodes_root;
		nodes_root = child;
	}
	else								// let parent connect to child
	{					
		//add_changed_nodes(node.parent);
		if(node.id == nodes[node.parent].left)
			nodes[node.parent].left  = child;
		else
			nodes[node.parent].right = child;
	}

	// place subtree
	if(subchild != NIL)
	{
		Node &sc = nodes[subchild];
		assert(subparent != NIL);

		while(1)
		{
			Node &p = nodes[subparent];

			// 2003/11/19
			// if both left and right child NIL, place with equal probability
			if( p.left == NIL && p.right == NIL )
			{
				sc.parent = p.id;
				if( rand_bool() )
				{
					p.left = sc.id;
				}
				else
				{
					p.right = sc.id;
				}
				break;
			}
			else if( p.left == NIL )		// place left 
			{
				sc.parent = p.id;
				p.left = sc.id;
				break;
			}
			else if( p.right == NIL )		// place right
			{
				sc.parent = p.id;
				p.right = sc.id;
				break;
			}
			else
			{
				subparent = (rand_bool() ? p.left : p.right);
			}
		}
	}

}


bool B_Tree::delete_node2( Node &node, DIR pull )
{
	DIR npull = !pull;

	int p  = node.parent;
	int n  = node.id;
	int c  = child( n, pull );
	int cn = child( n, npull );

	assert( n!= nodes_root ); // not root;

	DIR p2c = ( nodes[p].left == n ? LEFT : RIGHT );	// current DIR, LEFT or RIGHT

	if(c == NIL)
	{
		// Pull child, but NIL, so pull the other child
		wire_nodes( p, cn, p2c );
		return ( cn!=NIL );   // folding
	}
	else
	{
		wire_nodes( p, c, p2c );
	}

	while( c != NIL )
	{
		int k = child( c, npull );
		wire_nodes( c, cn, npull );
		cn = k;
		n = c;
		c = child(c,pull);
	}

	if(cn != NIL)
	{
		wire_nodes(n,cn,pull);
		return true;
	}
	else 
		return false;

}

/*
   Insert node into parent's left or right subtree according by "edge".
   Push node into parent's subtree in  "push" direction.

   if "fold" is true, then fold the leaf.
   (for the boundary condition of "delete" operation)

   delete <==> insert are permutating operations that can be recoved.
*/

void B_Tree::insert_node2(Node &parent,Node &node,
                        DIR edge=LEFT,DIR push=LEFT,bool fold/*=false*/){
  DIR npush = !push;
  int p= parent.id;
  int n= node.id;
  int c= child(p,edge);

  wire_nodes(p,n,edge);
  wire_nodes(n,c,push);
    
  while(c!=NIL)
  {
    wire_nodes(n,child(c,npush) ,npush);
    n= c;
    c= child(c,push);
  }
  wire_nodes(n,NIL,npush);

  if(fold)
  {
    wire_nodes(nodes[n].parent,NIL,push);
    wire_nodes(nodes[n].parent,n,npush); 
  }
}

void B_Tree::setOrientation()
{
    if( outline_ratio <= 0 )
        return;


    for( int i=0; i<modules_N; i++ )
    {
        if( modules[i].width > outline_width || modules[i].height > outline_height )
        {
            // rotate it
            nodes[i].rotate = true;
            modules[i].no_rotate = true;
            printf( "fix module %d\n", i );
    
            if( modules[i].height > outline_width || modules[i].width > outline_height )
            {
                printf( "impossible to legal module %d\n", i );
            }

        }
        if( modules[i].height > outline_width || modules[i].width > outline_height )
        {
            modules[i].no_rotate = true;
            printf( "fix module %d\n", i );
        }



    }

}