// Project: B*-trees floorplanning// Advisor: Yao-Wen Chang  <ywchang@cis.nctu.edu.tw>// Authors: Jer-Ming Hsu   <barz@cis.nctu.edu.tw>// 	    Hsun-Cheng Lee <gis88526@cis.nctu.edu.tw>// 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 truevoid 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 edgevoid 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 childinline 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;