btree.cpp

两种btree算法

// Project: B*-trees floorplanning
// Advisor: Yao-Wen Chang  <[e-mail]>
// Authors: Jer-Ming Hsu   <[e-mail]>
// 	    Hsun-Cheng Lee <[e-mail]>
// Sponsor: Arcadia Inc.
// Date:    7/19/2000 ~

// 2003/11/19	Modify perturb(), use one random number
//              Modify swap_node() and add swap_node2(), can swap parent and child
//              Modify delete_node(), place subtree with equal probability for left/right child

//---------------------------------------------------------------------------
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;

#include "btree.h"
//---------------------------------------------------------------------------
double move_rate = 0.33;
double swap_rate = 0.67;

//---------------------------------------------------------------------------
//   Initialization
//---------------------------------------------------------------------------

void B_Tree::clear()
{
  // initial contour value
  contour_root = NIL;
  FPlan::clear();
}

void B_Tree::init()
{
  // initialize contour structure
  contour.resize(modules_N);
    
  // initialize b*tree by complete binary tree
  nodes.resize(modules_N);
  nodes_root=0;
  for(int i=0; i < modules_N; i++)
  {
    nodes[i].id = i;
    nodes[i].parent = (i+1)/2-1;
    nodes[i].left   = (2*i+1 < modules_N ? 2*i+1 : NIL);
    nodes[i].right  = (2*i+2 < modules_N ? 2*i+2 : NIL);
  }
  nodes[0].parent = NIL;
  best_sol.clear();
  last_sol.clear();
  clear();
  normalize_cost(30);
} 

//---------------------------------------------------------------------------
//   Testing, Debuging tools
//---------------------------------------------------------------------------

bool B_Tree::legal()
{
  int num=0;
  return legal_tree(NIL,nodes_root,num);
}

bool B_Tree::legal_tree(int p,int n,int &num)
{
  num++;
  if(nodes[n].parent!=p) return false;
  if(nodes[n].left != NIL)
    if(legal_tree(n,nodes[n].left,num) != true) return false;

  if(nodes[n].right != NIL)
    if(legal_tree(n,nodes[n].right,num) != true) return false;

  if(p==NIL) // root
    return (num==modules_N);
  return true;
}

void B_Tree::testing()
{
  int p,n;
  Solution E;

  do
  {

    n = rand()%modules_N;
    p = rand()%modules_N;

    while(n==nodes_root)		// n is not root
      n = rand()%modules_N;

    while(n==p||nodes[n].parent==p||nodes[p].parent==n)	// n != p & n.parent != p
      p = rand()%modules_N;
   
    Node &node = nodes[n];
    Node &parent = nodes[p];
    get_solution(E);
    swap_node(parent,node);

  }while(legal());

  cout << "p=" << p << ", n=" << n << endl;
  recover(E);
  show_tree();
  cout << "\n  p=" << p << ", n=" << n << endl;
  swap_node(nodes[p],nodes[n]);
  show_tree();
}

void B_Tree::show_tree()
{
  cout << "root: " << nodes_root << endl;
  for(int i=0; i < modules_N; i++)
  {
    cout << nodes[i].id << ": ";
    cout << nodes[i].left << " ";
    cout << nodes[i].parent << " ";
    cout << nodes[i].right << endl;
  }
}

//---------------------------------------------------------------------------
//   Placement modules
//---------------------------------------------------------------------------

void B_Tree::packing()
{
  stack<int> S;

  clear();
  int p = nodes_root;

  place_module(p,NIL);
  Node &n = nodes[p];
  if(n.right != NIL)      S.push(n.right);
  if(n.left  != NIL)      S.push(n.left);

  // inorder traverse
  while(!S.empty())
  {
    p = S.top();
    S.pop();
    Node &n = nodes[p];

    assert(n.parent != NIL);
    bool is_left = (nodes[n.parent].left == n.id);
    place_module(p,n.parent,is_left);

    if(n.right != NIL)      S.push(n.right);
    if(n.left  != NIL)      S.push(n.left);
  }

  // compute Width, Height
  double max_x=-1,max_y=-1;
  for(int p= contour_root; p != NIL; p=contour[p].front)
  {
    max_x = max(max_x,double(modules_info[p].rx));  
    max_y = max(max_y,double(modules_info[p].ry));
  }

  Width  = max_x;
  Height = max_y;
  Area   = Height*Width;

  FPlan::packing(); 	// for wirelength  
}

// is_left: default is true
void B_Tree::place_module(int mod,int abut,bool is_left)
{
  Module_Info &mod_mf = modules_info[mod];
  mod_mf.rotate       = nodes[mod].rotate;
  mod_mf.flip         = nodes[mod].flip;

  int w =  modules[mod].width;
  int h =  modules[mod].height;
  if(nodes[mod].rotate)
    swap(w,h);
  
  if(abut==NIL)			// root node
  {
    contour_root = mod;
    contour[mod].back = NIL;
    contour[mod].front = NIL;
    mod_mf.x  = mod_mf.y = 0;
    mod_mf.rx = w, mod_mf.ry = h;
    return;
  }
  
  int p;   // trace contour from p

  if(is_left)	// left
  {
    int abut_width = (nodes[abut].rotate ? modules[abut].height : 
                                           modules[abut].width);
    mod_mf.x  = modules_info[abut].x + abut_width;
    mod_mf.rx = mod_mf.x + w;
    p = contour[abut].front;

    contour[abut].front = mod;
    contour[mod].back = abut;

    if(p==NIL)  // no obstacle in X axis
	{
      mod_mf.y = 0;
      mod_mf.ry = h;
      contour[mod].front = NIL;
      return;
    }
  }
  else
  {
	// upper
    mod_mf.x = modules_info[abut].x;
    mod_mf.rx = mod_mf.x + w;
    p = abut;
     
    int n=contour[abut].back;

    if(n==NIL)
	{ // i.e, mod_mf.x==0
      contour_root = mod;
      contour[mod].back = NIL;
    }
    else
	{
      contour[n].front = mod;
      contour[mod].back = n;
    }
  }
  
  int min_y = INT_MIN;
  int bx,by;
  assert(p!=NIL);
    
  for(; p!=NIL ; p=contour[p].front)
  {
    bx = modules_info[p].rx;
    by = modules_info[p].ry;
    min_y = max(min_y, by);
      
    if(bx >= mod_mf.rx)			 	// update contour
	{
      mod_mf.y = min_y;
      mod_mf.ry = mod_mf.y + h;
      if(bx > mod_mf.rx)
	  {
        contour[mod].front = p;
        contour[p].back = mod;
      }
	  else							// bx==mod_mf.rx
	  { 
        int n= contour[p].front;
        contour[mod].front = n;
        if(n!=NIL)
          contour[n].back = mod;
      }
      break;     
    }
  }

  if(p==NIL)
  {
    mod_mf.y  = (min_y==INT_MIN? 0 : min_y);
    mod_mf.ry = mod_mf.y + h;
    contour[mod].front = NIL;
  }
}

//---------------------------------------------------------------------------
//   Manipulate B*Tree auxilary procedure
//---------------------------------------------------------------------------

// place child in parent's edge
void B_Tree::wire_nodes( int parent, int child, DIR edge )		
{
	assert(parent!=NIL);
	(edge == LEFT ? nodes[parent].left : nodes[parent].right) = child;
	if(child!=NIL) 
		nodes[child].parent = nodes[parent].id;
}

// get node's child
inline int B_Tree::child( int node, DIR d )		
{
	assert( node!=NIL );
	return ( d==LEFT ? nodes[node].left : nodes[node].right);  
}


//---------------------------------------------------------------------------
//   Simulated Annealing Temporal Solution
//---------------------------------------------------------------------------

void B_Tree::get_solution(Solution &sol)
{
  sol.nodes_root = nodes_root;
  sol.nodes = nodes;
  sol.cost = getCost();
}

void B_Tree::keep_sol()
{
  get_solution(last_sol);
}

void B_Tree::keep_best()
{
  get_solution(best_sol);
}

void B_Tree::recover()
{
  recover(last_sol);
  // recover_partial();
}

void B_Tree::recover_best()
{
  recover(best_sol);
}

void B_Tree::recover(Solution &sol)
{
  nodes_root = sol.nodes_root;
  nodes = sol.nodes;
}

void B_Tree::recover_partial()
{
  if(changed_root != NIL)
    nodes_root = changed_root;
  
  for(int i=0; i < changed_nodes.size(); i++)
  {
    Node &n = changed_nodes[i];
    nodes[n.id] = n;
  }
}

void B_Tree::add_changed_nodes(int n)
{
  if(n==NIL) return;

  for(int i=0; i < changed_nodes.size(); i++)
    if(changed_nodes[i].id == n)
	  return;
  changed_nodes.push_back(nodes[n]);
}

//---------------------------------------------------------------------------
//   Simulated Annealing Permutation Operations
//---------------------------------------------------------------------------

void B_Tree::perturb()
{

	int p,n;
	n = rand()%modules_N;

	double r = rand_01();

	if( r < move_rate )
	{														// delete & insert
		// choose different module
		do
		{
			p = rand()%modules_N;	
		} while( n==p );

		delete_node(nodes[n]);
		insert_node(nodes[p], nodes[n]);
	}
	else if( r < swap_rate )
	{														// swap node
		// choose different module
		do
		{
			p = rand()%modules_N;
		}while( n==p );

		swap_node2( nodes[p], nodes[n] );

	}
	else //if( r < rotate_rate )
	{							
        // rotate node
        int count =0;
		while( modules[n].no_rotate == true )
        {
            count++;
            n = rand()%modules_N;
            if( count > 10 )
            {
                printf( "WARN: perturb() rotation\n" );
                break;
            }
        }
        nodes[n].rotate = !nodes[n].rotate;
	}
	//else
	//{														// resize soft module
	//	if( modules_soft_N != 0 )
	//	{
	//		n = modules_soft[ rand()%modules_soft_N ];
	//		B_Tree::soft_resize( n );
	//	}
	//	else
	//		nodes[n].rotate = !nodes[n].rotate;