DB.cxx

Go to the documentation of this file.

/**************************************************************************
***    
*** Copyright (c) 1995-2000 Regents of the University of California,
***               Andrew E. Caldwell, Andrew B. Kahng and Igor L. Markov
*** Copyright (c) 2000-2004 Regents of the University of Michigan,
***               Saurabh N. Adya, Jarrod A. Roy and Igor L. Markov
***
***  Contact author(s): abk@cs.ucsd.edu, imarkov@umich.edu
***  Original Affiliation:   UCLA, Computer Science Department,
***                          Los Angeles, CA 90095-1596 USA
***
***  Permission is hereby granted, free of charge, to any person obtaining 
***  a copy of this software and associated documentation files (the
***  "Software"), to deal in the Software without restriction, including
***  without limitation 
***  the rights to use, copy, modify, merge, publish, distribute, sublicense, 
***  and/or sell copies of the Software, and to permit persons to whom the 
***  Software is furnished to do so, subject to the following conditions:
***
***  The above copyright notice and this permission notice shall be included
***  in all copies or substantial portions of the Software.
***
*** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
*** EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
*** OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
*** IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
*** CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
*** OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
*** THE USE OR OTHER DEALINGS IN THE SOFTWARE.
***
***
***************************************************************************/
// 040608 hhchan modified how it plots:
//                  plot terminals only when plotNets, "set size ratio -1"

#include <map>
#include <algorithm>
#include <climits>
#include <cfloat>

#include "FPcommon.h"
#include "DB.h"
#include "PlToSP.h"
#include "SPeval.h"
#include "ABKCommon/abkassert.h"

using namespace parquetfp; 
using std::min;

//ctor
DB::DB(char* baseName)
{
   cout << "Reading Nodes (files " << baseName << ".blocks and "
        << baseName << ".pl)" << endl;
   _nodes = new Nodes(baseName);

   cout << "Reading Nets (file " << baseName << ".nets)" 
        << endl; 
   _nets =  new Nets(baseName);
   
   _nets->updateNodeInfo(*_nodes);
   _nodes->updatePinsInfo(*_nets);
   _nodes->initNodesFastPOAccess(*_nets, false);

   cout << "Done creating DB " << endl;

   _nodesBestCopy = new Nodes();
   //_nodesBestCopy = new Nodes(baseName);
   //_nodesBestCopy->updatePinsInfo(*_nets);

   _initArea = 0;
   successAR = 0;
   _rowHeight = 0;
   _siteSpacing = 0;
}

DB::DB()
{
   _nodes = new Nodes();
   _nets =  new Nets();
   _nodesBestCopy = new Nodes();

   _initArea = 0;
   successAR = 0;
   _rowHeight = 0;
   _siteSpacing = 0;
}

DB::DB(DB * db, vector<int>& subBlocksIndices, Point& dbLoc, double reqdAR)
{
   _nodes = new Nodes();
   _nets =  new Nets();
   _nodesBestCopy = new Nodes();
   _initArea = 0;
   successAR = 0;
   _rowHeight = 0;
   _siteSpacing = 0;

   Nodes* origNodes = db->getNodes();
   Nets* origNets = db->getNets();

   map<unsigned, unsigned> mapping;
   unsigned numOrigNodes = origNodes->getNumNodes();
   vector<bool> seenNodes(numOrigNodes, false);

   double nodesArea = 0;
   for(unsigned i=0; i<subBlocksIndices.size(); ++i)
   {
      Node& origNode = origNodes->getNode(subBlocksIndices[i]);
      nodesArea += origNode.getArea();
      Node tempNode(origNode.getName(), origNode.getArea() , 
                    origNode.getminAR(), origNode.getmaxAR(), i, false);
      tempNode.addSubBlockIndex(subBlocksIndices[i]);
      tempNode.putX(origNode.getX());
      tempNode.putY(origNode.getY());
      _nodes->putNewNode(tempNode);
      seenNodes[subBlocksIndices[i]] = true;
      mapping[subBlocksIndices[i]] = i;
   }

   double reqdHeight = sqrt(nodesArea/reqdAR);
   double reqdWidth = reqdHeight*reqdAR;
   double termXLoc, termYLoc;
   double minXLoc = dbLoc.x;
   double maxXLoc = minXLoc + reqdWidth;
   double minYLoc = dbLoc.y;
   double maxYLoc = minYLoc + reqdHeight;

   unsigned numOrigNets = origNets->getNumNets();
   vector<bool> seenNets(numOrigNets, false);

   unsigned newNetCtr=0;
   unsigned newTermCtr = 0;

   itNodePin origNodePin;
   Net tempEdge;
  
   for(unsigned i=0; i<subBlocksIndices.size(); ++i)
   {
      Node& origNode = origNodes->getNode(subBlocksIndices[i]);
      for(origNodePin = origNode.pinsBegin(); 
          origNodePin != origNode.pinsEnd(); ++origNodePin)
      {
         Net& origNet = origNets->getNet(origNodePin->netIndex);
         if(!seenNets[origNet.getIndex()])
         {
            seenNets[origNet.getIndex()] = true;
            tempEdge.putName(origNet.getName());
            tempEdge.putIndex(newNetCtr);
            for(itPin netPin = origNet.pinsBegin(); 
                netPin != origNet.pinsEnd(); ++netPin)
            {
               double poffsetX, poffsetY;
               unsigned origNodeIdx = netPin->getNodeIndex();
               if(!netPin->getType()) //not a terminal
               {
                  if(seenNodes[origNodeIdx])
                  {
                     unsigned newNodeIdx = mapping[origNodeIdx];
                     poffsetX = netPin->getXOffset();
                     poffsetY = netPin->getYOffset();

                     Node& newNode = _nodes->getNode(newNodeIdx);
                     pin tempPin(newNode.getName(), false, poffsetX, 
                                 poffsetY, newNetCtr);
                     tempPin.putNodeIndex(newNodeIdx);
                     tempEdge.addNode(tempPin);
                  }
                  else //need terminal propagation
                  {
                     Node& origTerm = 
                        origNodes->getNode(netPin->getNodeIndex());
                          
                     Node tempTerm(origTerm.getName(), 0, 1, 1, 
                                   newTermCtr, true);
                     tempTerm.addSubBlockIndex(origTerm.getIndex());

                     //terminal propagation
                     if(origTerm.getX() < minXLoc)
                        termXLoc = 0;
                     else if(origTerm.getX() > maxXLoc)
                        termXLoc = reqdWidth;
                     else
                        termXLoc = origTerm.getX() - minXLoc;

                     if(origTerm.getY() < minYLoc)
                        termYLoc = 0;
                     else if(origTerm.getY() > maxYLoc)
                        termYLoc = reqdHeight;
                     else
                        termYLoc = origTerm.getY() - minYLoc;

                     tempTerm.putX(termXLoc);
                     tempTerm.putY(termYLoc);

                     _nodes->putNewTerm(tempTerm);
                          
                     pin tempPin(origTerm.getName(), true, 0, 0, newNetCtr);
                     tempPin.putNodeIndex(newTermCtr);
                     tempEdge.addNode(tempPin);
                     newTermCtr++;                        
                  }
               }
               else //actual terminal
               {
                  Node& origTerm = 
                     origNodes->getTerminal(netPin->getNodeIndex());

                  Node tempTerm(origTerm.getName(), 0, 1, 1, newTermCtr,
                                true);
                  tempTerm.addSubBlockIndex(origTerm.getIndex());


                  //terminal propagation
                  if(origTerm.getX() < minXLoc)
                     termXLoc = 0;
                  else if(origTerm.getX() > maxXLoc)
                     termXLoc = reqdWidth;
                  else
                     termXLoc = origTerm.getX() - minXLoc;
                      
                  if(origTerm.getY() < minYLoc)
                     termYLoc = 0;
                  else if(origTerm.getY() > maxYLoc)
                     termYLoc = reqdHeight;
                  else
                     termYLoc = origTerm.getY() - minYLoc;
                      
                  tempTerm.putX(termXLoc);
                  tempTerm.putY(termYLoc);
                      
                  _nodes->putNewTerm(tempTerm);

                  pin tempPin(origTerm.getName(), true, 0, 0, newNetCtr);
                  tempPin.putNodeIndex(newTermCtr);
                  tempEdge.addNode(tempPin);
                  newTermCtr++;
               }
            }
            _nets->putNewNet(tempEdge);
            ++newNetCtr;
            tempEdge.clean();
         }
      }
   }
   _nodes->updatePinsInfo(*_nets);
   _nodes->initNodesFastPOAccess(*_nets, false);
   *_nodesBestCopy = *_nodes;
}

DB::~DB()
{
   if(_nodes) delete _nodes;
   if(_nets) delete _nets;
   if(_nodesBestCopy) delete _nodesBestCopy;
}

DB& DB::operator=(DB& db2)
{
   if(this != &db2)
   {
      if(_nodes) delete _nodes;
      if(_nets) delete _nets;
      if(_nodesBestCopy) delete _nodesBestCopy;
      
      _nodes = new Nodes();
      _nets = new Nets();
      _nodesBestCopy = new Nodes();
      
      *(_nodes) = *(db2.getNodes());
      *(_nets) = *(db2.getNets());
      *(_nodesBestCopy) = *(db2._nodesBestCopy);
  
      _area = db2._area;
      _initArea = db2._initArea;
      _rowHeight = db2._rowHeight;
      _siteSpacing = db2._siteSpacing;
   }
   return *this;
}


struct sortFnPairFirst
{
  bool operator()(const pair<unsigned, double> &elem1, 
                  const pair<unsigned, double> &elem2)
  { return(elem1.first < elem2.first); }
};


DB::DB(DB& db2, bool compressDB)
{
   if(this != &db2)
   {
     /*
     if(_nodes) delete _nodes;
     if(_nets) delete _nets;
     if(_nodesBestCopy) delete _nodesBestCopy;
     */
     _nodes = new Nodes();
     _nets = new Nets();
     _nodesBestCopy = new Nodes();
     
     *(_nodes) = *(db2.getNodes());
     *(_nodesBestCopy) = *(db2._nodesBestCopy);
     
     _area = db2._area;
     _initArea = db2._initArea;
     _rowHeight = db2._rowHeight;
     _siteSpacing = db2._siteSpacing;

     if(!compressDB)
       {
         *(_nets) = *(db2.getNets());
       }
     else
       {
         //any net connected to a macro or terminal is added as is
         //only nets between normal blocks are compressed
         int netCtr=0;
         Nets* oldNets = db2.getNets();
         Nodes* oldNodes = db2.getNodes();
         vector<bool> seenNets(oldNets->getNumNets(), false);
         for(itNode term=oldNodes->terminalsBegin(); 
             term != oldNodes->terminalsEnd(); ++term)
           {
             for(itNodePin pin=term->pinsBegin(); pin!=term->pinsEnd(); ++pin)
               {
                 unsigned netId = pin->netIndex;
                 if(!seenNets[netId])
                   {
                     Net& origNet = oldNets->getNet(netId);
                     Net tempEdge;
                     tempEdge.putName(origNet.getName());
                     tempEdge.putIndex(netCtr);
                     tempEdge.putWeight(origNet.getWeight());
                     for(itPin netPin = origNet.pinsBegin(); 
                         netPin != origNet.pinsEnd(); ++netPin)
                       {
                         unsigned currNodeIdx = netPin->getNodeIndex();
                         double poffsetX = 0, poffsetY = 0;
                         poffsetX = netPin->getXOffset();
                         poffsetY = netPin->getYOffset();
                         if(!netPin->getType())
                           {
                             Node& oldNode = oldNodes->getNode(currNodeIdx);
                             parquetfp::pin tempPin(oldNode.getName(), false, poffsetX, 
                                         poffsetY, netCtr);
                             tempPin.putNodeIndex(currNodeIdx);
                             tempEdge.addNode(tempPin);
                           }
                         else
                           {
                             Node& oldTerm = oldNodes->getTerminal(currNodeIdx);
                             parquetfp::pin tempPin(oldTerm.getName(), true, poffsetX, 
                                         poffsetY, netCtr);
                             tempPin.putNodeIndex(currNodeIdx);
                             tempEdge.addNode(tempPin);
                           }
                       }
                     seenNets[netId] = true;
                     _nets->putNewNet(tempEdge);
                     ++netCtr;
                   }
               }
           }

         for(itNode node=oldNodes->nodesBegin(); 
             node != oldNodes->nodesEnd(); ++node)
           {
                 for(itNodePin pin=node->pinsBegin(); pin!=node->pinsEnd(); ++pin)
                   {
                     unsigned netId = pin->netIndex;
                     Net& origNet = oldNets->getNet(netId);
                     if(!seenNets[netId] 
                        /*&& ( node->isMacro() || origNet.getDegree() > 2)*/)
                       {
                         Net tempEdge;
                         bool atleast1PinOffsetNotZero=false;
                         tempEdge.putName(origNet.getName());
                         tempEdge.putIndex(netCtr);
                         tempEdge.putWeight(origNet.getWeight());
                         for(itPin netPin = origNet.pinsBegin(); 
                             netPin != origNet.pinsEnd(); ++netPin)
                           {
                             unsigned currNodeIdx = netPin->getNodeIndex();
                             double poffsetX = 0, poffsetY = 0;
                             poffsetX = netPin->getXOffset();
                             poffsetY = netPin->getYOffset();
                             if(!(fabs(poffsetX-0) < 1e-5 && fabs(poffsetY-0) < 1e-5))
                               atleast1PinOffsetNotZero = true;

                             if(!netPin->getType())
                               {
                                 Node& oldNode = oldNodes->getNode(currNodeIdx);
                                 parquetfp::pin tempPin(oldNode.getName(), false, poffsetX, 
                                             poffsetY, netCtr);
                                 tempPin.putNodeIndex(currNodeIdx);
                                 tempEdge.addNode(tempPin);
                               }
                             else
                               {
                                 Node& oldTerm = oldNodes->getTerminal(currNodeIdx);
                                 parquetfp::pin tempPin(oldTerm.getName(), true, poffsetX, 
                                             poffsetY, netCtr);
                                 tempPin.putNodeIndex(currNodeIdx);
                                 tempEdge.addNode(tempPin);
                               }
                           }
                         if(atleast1PinOffsetNotZero || origNet.getDegree()>2)
                           {
                             seenNets[netId] = true;
                             _nets->putNewNet(tempEdge);
                             ++netCtr;
                           }
                       }
                   }
           }

         //now add the compressing code
         vector< vector< pair<unsigned,double> > > nodeConnections(oldNodes->getNumNodes());

         for(itNode node=oldNodes->nodesBegin(); 
             node != oldNodes->nodesEnd(); ++node)
           {
             //if(!node->isMacro())
               {
                 unsigned currNodeIdx = node->getIndex();

                 for(itNodePin pin=node->pinsBegin(); pin!=node->pinsEnd(); ++pin)
                   {
                     unsigned netId = pin->netIndex;
                     Net& origNet = oldNets->getNet(netId);
                     if(!seenNets[netId] && origNet.getDegree() == 2)
                       {
                         for(itPin netPin = origNet.pinsBegin(); 
                             netPin != origNet.pinsEnd(); ++netPin)
                           {
                             unsigned nextNodeIdx = netPin->getNodeIndex();
                             //following cond ensures that we go over each
                             //net only once
                             if(nextNodeIdx > currNodeIdx)
                               {
                                 pair<unsigned, double> elem(nextNodeIdx, origNet.getWeight());
                                 nodeConnections[currNodeIdx].push_back(elem);
                               }
                           }
                       }
                   }
               } 
           }

         for(unsigned i=0; i<nodeConnections.size(); ++i)
           std::sort(nodeConnections[i].begin(), nodeConnections[i].end(), sortFnPairFirst());
         
         char netName [100];
         for(int i=0; i<int(nodeConnections.size()); ++i)
           {
             int j=0;
             while(j<int(nodeConnections[i].size()))
               {
                 unsigned numConn=1;
                 double sumOfWts=nodeConnections[i][j].second;
                 if(j != (int(nodeConnections[i].size())-1))
                   {
                     while(j<(int(nodeConnections[i].size())-1) &&
                           nodeConnections[i][j].first == nodeConnections[i][j+1].first)
                       {
                         ++numConn;
                         ++j;
                         sumOfWts+=nodeConnections[i][j].second;
                       }
                   }

                 Net tempEdge;
                 sprintf(netName, "clusteredNet_%d",netCtr);
                 tempEdge.putName(netName);
                 tempEdge.putIndex(netCtr);
                 double poffsetX = 0, poffsetY = 0;
                 Node& node1 = _nodes->getNode(i);
                 Node& node2 = _nodes->getNode(nodeConnections[i][j].first);

                 pin tempPin1(node1.getName(), false, poffsetX, 
                              poffsetY, netCtr);
                 tempPin1.putNodeIndex(i);
                 tempEdge.addNode(tempPin1);

                 pin tempPin2(node2.getName(), false, poffsetX, 
                              poffsetY, netCtr);
                 tempPin2.putNodeIndex(nodeConnections[i][j].first);
                 tempEdge.addNode(tempPin2);

                 //tempEdge.putWeight(numConn);
                 tempEdge.putWeight(sumOfWts);
                 _nets->putNewNet(tempEdge);

                 ++netCtr;
                 ++j;
               }
           }
         //_nets->updateNodeInfo(*_nodes);
         _nodes->updatePinsInfo(*_nets);
         _nodes->initNodesFastPOAccess(*_nets, false);

         /*
         cout<<"Initial #Nets "<<oldNets->getNumNets()<<" Initial #Pins "
             <<oldNets->getNumPins()<<" Compressed #Nets "<<_nets->getNumNets()
             <<" Compressed #Pins "<<_nets->getNumPins()<<endl;
         */
       }
   }
}


void DB::clean(void)
{
   if(_nodes) _nodes->clean();
   if(_nets) _nets->clean();
   if(_nodesBestCopy) _nodesBestCopy->clean();
}

Nodes* DB::getNodes(void)
{ return _nodes; }

Nets* DB::getNets(void) 
{ return _nets; }

unsigned DB::getNumNodes(void) const
{
   return _nodes->getNumNodes();
}

vector<double> DB::getNodeWidths(void) const
{
   return _nodes->getNodeWidths();
}

vector<double> DB::getNodeHeights(void) const
{
   return _nodes->getNodeHeights();
}

vector<double> DB::getXLocs(void) const
{
   return _nodes->getXLocs();
}

vector<double> DB::getYLocs(void) const
{
   return _nodes->getYLocs();
}

Point DB::getBottomLeftCorner() const
{
   vector<double> nodesXLocs(_nodes->getXLocs());
   vector<double> nodesYLocs(_nodes->getYLocs());
   
   vector<double>::iterator xMin = min_element(nodesXLocs.begin(),
                                               nodesXLocs.end());
   vector<double>::iterator yMin = min_element(nodesYLocs.begin(),
                                               nodesYLocs.end());

   Point bottomLeft;
   bottomLeft.x = *xMin;
   bottomLeft.y = *yMin;
   return bottomLeft;
}

Point DB::getTopRightCorner() const
{
   vector<double> nodesXLocs(_nodes->getXLocs());
   vector<double> nodesYLocs(_nodes->getYLocs());
   for (unsigned int i = 0; i < _nodes->getNumNodes(); i++)
   {
      nodesXLocs[i] += _nodes->getNodeWidth(i);
      nodesYLocs[i] += _nodes->getNodeHeight(i);
   }
   
   vector<double>::iterator xMax = max_element(nodesXLocs.begin(),
                                               nodesXLocs.end());
   vector<double>::iterator yMax = max_element(nodesYLocs.begin(),
                                               nodesYLocs.end());

   Point topRight;
   topRight.x = *xMax;
   topRight.y = *yMax;
   return topRight;
}

void DB::packToCorner(vector< vector<double> >& xlocsAt,
                      vector< vector<double> >& ylocsAt) const
{
   const Point topRightCorner(getTopRightCorner());
   const Point bottomLeftCorner(getBottomLeftCorner());
   
   const vector<double> xlocs(getXLocs());
   const vector<double> ylocs(getYLocs());
   const vector<double> widths(getNodeWidths());
   const vector<double> heights(getNodeHeights());

   // naive FP representation independent way of determining slacks
   vector<double> xRightSlacks(getNumNodes());
   vector<double> xLeftSlacks(getNumNodes());
   
   vector<double> yTopSlacks(getNumNodes());
   vector<double> yBottomSlacks(getNumNodes());
   for (unsigned i = 0; i < getNumNodes(); i++)
   {
      xRightSlacks[i] = topRightCorner.x - xlocs[i] - widths[i];
      xLeftSlacks[i] = xlocs[i] - bottomLeftCorner.x;
      
      yTopSlacks[i] = topRightCorner.y - ylocs[i] - heights[i];
      yBottomSlacks[i] = ylocs[i] - bottomLeftCorner.y;
      
      for (unsigned j = 0; j < getNumNodes(); j++)
      {
         if (i != j)
         {
            // have x-overlap 
            if ((xlocs[i] < xlocs[j] + widths[j])
                && (xlocs[j] < xlocs[i] + widths[i]))
            {
               if (ylocs[j] > ylocs[i])
               {
                  // [j] is above [i]
                  yTopSlacks[i] = min(yTopSlacks[i],
                                      ylocs[j] - (ylocs[i]+heights[i]));
               }
               else
               {
                  // [j] is below [i]
                  yBottomSlacks[i] = min(yBottomSlacks[i],
                                         ylocs[i] - (ylocs[j]+heights[j]));
               }
            }

            // have y-overlap
            if ((ylocs[i] < ylocs[j] + heights[j])
                && (ylocs[j] < ylocs[i] + heights[i]))
            {
               if (xlocs[j] > xlocs[i])
               {
                  // [j] is right of [i]
                  xRightSlacks[i] = min(xRightSlacks[i],
                                        xlocs[j] - (xlocs[i]+widths[i]));
               }
               else
               {
                  // [j] is left of [i]
                  xLeftSlacks[i] = min(xLeftSlacks[i],
                                       xlocs[i] - (xlocs[j]+widths[j]));
               }
            }
         }
      }
   }

   // set the locations
   for (unsigned i = 0; i < getNumNodes(); i++)
   {
      xlocsAt[BOTTOM_LEFT][i] = xlocs[i] - xLeftSlacks[i];
      ylocsAt[BOTTOM_LEFT][i] = ylocs[i] - yBottomSlacks[i];
      
      xlocsAt[BOTTOM_RIGHT][i] = xlocs[i] + xRightSlacks[i];
      ylocsAt[BOTTOM_RIGHT][i] = ylocs[i] - yBottomSlacks[i];
      
      xlocsAt[TOP_LEFT][i] = xlocs[i] - xLeftSlacks[i];
      ylocsAt[TOP_LEFT][i] = ylocs[i] + yTopSlacks[i];

      xlocsAt[TOP_RIGHT][i] = xlocs[i] + xRightSlacks[i];
      ylocsAt[TOP_RIGHT][i] = ylocs[i] + yTopSlacks[i];
   }         
}

void DB::cornerOptimizeDesign()
{
   const vector<double> origXLocs(getXLocs());
   const vector<double> origYLocs(getYLocs());

   vector< vector<double> > xlocsAt(NUM_CORNERS,
                                    vector<double>(getNumNodes()));
   vector< vector<double> > ylocsAt(NUM_CORNERS,
                                    vector<double>(getNumNodes()));
   packToCorner(xlocsAt, ylocsAt);

   static int ORIGINAL = -1;
   int minCorner = ORIGINAL;
   double minHPWL = evalHPWL();
   cout << "Original HPWL: " << minHPWL << endl;
   
   for (unsigned i = 0; i < NUM_CORNERS; i++)
   {
      updatePlacement(xlocsAt[i], ylocsAt[i]);

      double currHPWL = evalHPWL();
      if (currHPWL < minHPWL)
      {
         minHPWL = currHPWL;
         minCorner = i;
      }
      cout << toString(Corner(i)) << " HPWL: " << currHPWL << endl;
   }
   cout << "minimum HPWL: " << minHPWL;
   if (minCorner == ORIGINAL)
      cout << " in the original position." << endl;
   else
      cout << " at " << toString(Corner(minCorner)) << endl;

   cout << "packing design towards "
        << ((minCorner==ORIGINAL)
            ? string("the original position")
            : toString(Corner(minCorner))) << endl;
   if (minCorner == ORIGINAL)
      updatePlacement(origXLocs, origYLocs);
   else
      updatePlacement(xlocsAt[minCorner], ylocsAt[minCorner]);
   cout << "final HPWL: " << evalHPWL() << endl;
}

double DB::getNodesArea(void) const
{
   if(_initArea)
      return _area;
   else
   {
      _area=_nodes->getNodesArea();
      _initArea = 1;
      return _area;
   }
}

double DB::getRowHeight(void) const
{
   return _rowHeight;
}

double DB::getSiteSpacing(void) const
{
   return _siteSpacing;
}

void DB::setRowHeight(double rowHeight)
{
   _rowHeight = rowHeight;
}

void DB::setSiteSpacing(double siteSpacing)
{
   _siteSpacing = siteSpacing;
}

double DB::getAvgHeight(void) const
{
   itNode node;
   double avgHeight = 0;
   for(node = _nodes->nodesBegin(); node != _nodes->nodesEnd(); ++node)
      avgHeight += node->getHeight();
   avgHeight /= getNumNodes();
   return(avgHeight);
}

void DB::updatePlacement(const vector<double>& xloc,
                         const vector<double>& yloc)
{
   unsigned int numNodes = _nodes->getNumNodes();
   unsigned int size = min(unsigned(xloc.size()), numNodes);
   abkwarn(size >= numNodes, "Too few locations specified.");

   for(unsigned i = 0; i < size; i++)
   {
      _nodes->getNode(i).putX(xloc[i]);
      _nodes->getNode(i).putY(yloc[i]);
   }
}

void DB::initPlacement(const Point& loc)
{
   itNode node;
   for(node = _nodes->nodesBegin(); node != _nodes->nodesEnd(); ++node)
   {
      node->putX(loc.x);
      node->putY(loc.y);
   }
}

void DB::updateSlacks(const vector<double>& xSlack,
                      const vector<double>& ySlack)
{
   for(unsigned i=0; i<xSlack.size(); ++i)
   {
      _nodes->getNode(i).putslackX(xSlack[i]);
      _nodes->getNode(i).putslackY(ySlack[i]);
   }  
}

double DB::evalHPWL(bool useWts) const
{
   itNet net;
   itPin pin;
   unsigned nodeIndex;
   //BBox netBBox;
   Point tempPoint;
   double HPWL=0;
   double width;
   double height;
   double absOffsetX;
   double absOffsetY;
   double xloc;
   double yloc;
   Point llc;
   Point trc;

   for(net = _nets->netsBegin(); net != _nets->netsEnd(); ++net)
   {
     llc.x=llc.y=1e306;
     trc.x=trc.y=-1e306;
     unsigned netDegree = net->getDegree();
     if(netDegree <= 1)
       continue;
     else if(netDegree == 2)//special casing for 2 pin nets
       {
         itPin pin1 = net->pinsBegin();
         itPin pin2 = pin1+1;
         
         unsigned nodeIndex1 = pin1->getNodeIndex();
         unsigned nodeIndex2 = pin2->getNodeIndex();
         
         if(!pin1->getType())        //if not terminal
           {
             Node& node = _nodes->getNode(nodeIndex1);
             width = node.getWidth();
             height = node.getHeight();
             xloc = node.getX();
             yloc = node.getY();

             if(!node.allPinsAtCenter)
               {
                 absOffsetX = 0.5*width + (pin1->getXOffset()*width);
                 absOffsetY = 0.5*height + (pin1->getYOffset()*height);
                 llc.x = xloc + absOffsetX;
                 llc.y = yloc + absOffsetY;
               }
             else
               {
                 llc.x = xloc + 0.5*width;
                 llc.y = yloc + 0.5*height;
               }
           }                      
         else
           {
             Node& node = _nodes->getTerminal(nodeIndex1);
             width = node.getWidth();
             height = node.getHeight();
             xloc = node.getX();
             yloc = node.getY();

             absOffsetX = 0.5*width + (pin1->getXOffset()*width);
             absOffsetY = 0.5*height + (pin1->getYOffset()*height);
             llc.x = xloc + absOffsetX;
             llc.y = yloc + absOffsetY;
           }

         if(!pin2->getType())        //if not terminal
           {
             Node& node = _nodes->getNode(nodeIndex2);
             width = node.getWidth();
             height = node.getHeight();
             xloc = node.getX();
             yloc = node.getY();

             if(!node.allPinsAtCenter)
               {
                 absOffsetX = 0.5*width + (pin2->getXOffset()*width);
                 absOffsetY = 0.5*height + (pin2->getYOffset()*height);
                 trc.x = xloc + absOffsetX;
                 trc.y = yloc + absOffsetY;
               }
             else
               {
                 trc.x = xloc + 0.5*width;
                 trc.y = yloc + 0.5*height;
               }
           }                      
         else
           {
             Node& node = _nodes->getTerminal(nodeIndex2);
             width = node.getWidth();
             height = node.getHeight();
             xloc = node.getX();
             yloc = node.getY();

             absOffsetX = 0.5*width + (pin2->getXOffset()*width);
             absOffsetY = 0.5*height + (pin2->getYOffset()*height);
             trc.x = xloc + absOffsetX;
             trc.y = yloc + absOffsetY;
           }
         
         double swapVar;
         if(trc.x < llc.x )
           {
             swapVar = llc.x;
             llc.x = trc.x;
             trc.x = swapVar;
           }
         if(trc.y < llc.y )
           {
             swapVar = llc.y;
             llc.y = trc.y;
             trc.y = swapVar;
           }
       }
     else
       {
         for(pin = net->pinsBegin(); pin != net->pinsEnd(); ++pin)
           {
             nodeIndex = pin->getNodeIndex();
             if(!pin->getType())        //if not terminal
               {
                 Node& node = _nodes->getNode(nodeIndex);
                 width = node.getWidth();
                 height = node.getHeight();
                 xloc = node.getX();
                 yloc = node.getY();

                 if(!node.allPinsAtCenter)
                   {
                     absOffsetX = 0.5*width + (pin->getXOffset()*width);
                     absOffsetY = 0.5*height + (pin->getYOffset()*height);
                     tempPoint.x = xloc + absOffsetX;
                     tempPoint.y = yloc + absOffsetY;
                   }
                 else
                   {
                     tempPoint.x = xloc + 0.5*width;
                     tempPoint.y = yloc + 0.5*height;
                   }
               }                      
             else
               {
                 Node& node = _nodes->getTerminal(nodeIndex);
                 width = node.getWidth();
                 height = node.getHeight();
                 xloc = node.getX();
                 yloc = node.getY();

                 absOffsetX = 0.5*width + (pin->getXOffset()*width);
                 absOffsetY = 0.5*height + (pin->getYOffset()*height);
                 tempPoint.x = xloc + absOffsetX;
                 tempPoint.y = yloc + absOffsetY;
               }
             //netBBox.put(tempPoint);
             
             if(tempPoint.x < llc.x)
               llc.x = tempPoint.x;
             if(tempPoint.x > trc.x)
               trc.x = tempPoint.x;
             if(tempPoint.y < llc.y)
               llc.y = tempPoint.y;
             if(tempPoint.y > trc.y)
               trc.y = tempPoint.y;
           }
       }
     
     //if(netDegree > 1)
     if(useWts)
       HPWL += net->getWeight()*(trc.x-llc.x + trc.y-llc.y);
     else
       HPWL += (trc.x-llc.x + trc.y-llc.y);

     //if(netBBox.isValid())
     //HPWL += netBBox.getHPWL();
     //netBBox.clear();  
   }
   return HPWL;    
}

double DB::evalHPWL(double xSize, double ySize, bool useWts) const
{
   itNet net;
   itPin pin;
   unsigned nodeIndex;
   BBox netBBox;
   Point tempPoint;
   double HPWL=0;
   double width;
   double height;
   double absOffsetX;
   double absOffsetY;
   double xloc;
   double yloc;
  
   for(net = _nets->netsBegin(); net != _nets->netsEnd(); ++net)
   {
      for(pin = net->pinsBegin(); pin != net->pinsEnd(); ++pin)
      {
         nodeIndex = pin->getNodeIndex();
         if(!pin->getType())        //if not terminal
         {
            Node& node = _nodes->getNode(nodeIndex);
            width = node.getWidth();
            height = node.getHeight();
            xloc = node.getX();
            yloc = node.getY();
         }                      
         else
         {
            Node& node = _nodes->getTerminal(nodeIndex);
            width = node.getWidth();
            height = node.getHeight();
            xloc = node.getX();
            yloc = node.getY();
            if(xloc > xSize)
               xloc = xSize;
            if(yloc > ySize)
               yloc = ySize;
         }
         absOffsetX = 0.5*width + (pin->getXOffset()*width);
         absOffsetY = 0.5*height + (pin->getYOffset()*height);
          
         tempPoint.x = xloc + absOffsetX;
         tempPoint.y = yloc + absOffsetY;
         netBBox.put(tempPoint);
      }
      if(netBBox.isValid())
      {
         //cout<<net->getName()<<" "<<netBBox.getHPWL()<<" "<<HPWL<<endl;
        if(useWts)
          HPWL += net->getWeight()*netBBox.getHPWL();
        else
          HPWL += netBBox.getHPWL();
      }
      netBBox.clear();  
   }
   return HPWL;    
}

double DB::evalArea(void) const
{
   BBox area;
   itNode node;
   Point P;
   for(node = const_cast<DB*>(this)->getNodes()->nodesBegin();
       node != const_cast<DB*>(this)->getNodes()->nodesEnd(); ++node)
   {
      P.x = node->getX();
      P.y = node->getY();
      area.put(P);
      P.x = node->getX()+node->getWidth();
      P.y = node->getY()+node->getHeight();
      area.put(P);
   }
   return(area.getXSize()*area.getYSize());
}

double DB::getXSize(void) const
{
   BBox xSize;
   itNode node;
   Point P;
   for(node = const_cast<DB*>(this)->getNodes()->nodesBegin();
       node != const_cast<DB*>(this)->getNodes()->nodesEnd(); ++node)
   {
      P.x = node->getX();
      P.y = 0;
      xSize.put(P);
      P.x = node->getX()+node->getWidth();
      P.y = 0;
      xSize.put(P);
   }
   return(xSize.getXSize());
}

double DB::getYSize(void) const
{
   BBox ySize;
   itNode node;
   Point P;
   for(node = const_cast<DB*>(this)->getNodes()->nodesBegin();
       node != const_cast<DB*>(this)->getNodes()->nodesEnd(); ++node)
   {
      P.y = node->getY();
      P.x = 0;
      ySize.put(P);
      P.y = node->getY()+node->getHeight();
      P.x = 0;
      ySize.put(P);
   }
   return(ySize.getYSize());
}

void DB::plot(char* fileName, double area, double whitespace, 
              double aspectRatio, double time, double HPWL, bool plotSlacks,
              bool plotNets, bool plotNames) const
{
   double x=0;
   double y=0;
   double w=0;
   double h=0;
   double nodesArea = getNodesArea();
   double starDelta = sqrt(nodesArea) / 200;
   itNode it;

   cout<<"OutPut Plot file is "<<fileName<<endl;
   ofstream gpOut(fileName);
   if (!gpOut.good())
   {
      cout << "Warning: output file " << fileName
           << " can't be opened" << endl;
   }

   gpOut<<"#Use this file as a script for gnuplot"<<endl;
   gpOut<<"#(See http://www.gnuplot.info/ for details)"<<endl;
   gpOut << "set nokey"<<endl;

   gpOut << "set size ratio -1" << endl;
   gpOut << "set title ' " << fileName
         << " area= " << area << " WS= " << whitespace << "%" << " AR= " << aspectRatio
         << " time= " << time << "s" << " HPWL= " << HPWL << endl << endl;

   gpOut<<"#   Uncomment these two lines starting with \"set\""<<endl ;
   gpOut<<"#   to save an EPS file for inclusion into a latex document"<<endl;
   gpOut << "# set terminal postscript eps color solid 10"<<endl;
   gpOut << "# set output \"out.eps\""<<endl<<endl<<endl;

   gpOut<<"#   Uncomment these two lines starting with \"set\""<<endl ;
   gpOut<<"#   to save a PS file for printing"<<endl;
   gpOut<<"# set terminal postscript portrait color solid 8"<<endl;
   gpOut << "# set output \"out.ps\""<<endl<<endl<<endl;

   if(plotNames)
   {
      for(it=_nodes->nodesBegin();it!=_nodes->nodesEnd();++it)
      {
                gpOut<<"set label \""<<it->getName()<<"("<<(it-_nodes->nodesBegin())<<"),vdd=" << it->getVoltage() 
              <<"\" at "<<it->getX()+it->getWidth()/4<<" , "<<it->getY()+it->getHeight()/4<<endl;
      }

      // plot terminals only when Net is plotted
      if (plotNets)
      {
         for(it=_nodes->terminalsBegin();it!=_nodes->terminalsEnd();++it)
         {
            gpOut<<"set label \""<<it->getName()<<"\" at "<<it->getX()+it->getWidth()/4<<" , "<<it->getY()+it->getHeight()/4<<endl;
         }
      }
   }
            
  
   if(plotSlacks)
   {
      for(it=_nodes->nodesBegin();it!=_nodes->nodesEnd();++it)
      {
         double xSlack = it->getslackX();
         double ySlack = it->getslackY();
         if(xSlack < 1e-5)
            xSlack = 0;
         if(ySlack < 1e-5)
            ySlack = 0;
 
         gpOut.precision(4);
         gpOut<<"set label \"x "<<xSlack<<"\" at "<<it->getX()+it->getWidth()/6<<" , "<<it->getY()+it->getHeight()/2<<endl;
         gpOut<<"set label \"y "<<ySlack<<"\" at "<<it->getX()+it->getWidth()/6<<" , "<<it->getY()+it->getHeight()*3/4<<endl;
      }
   }

   gpOut.precision(6);
   gpOut << "plot '-' w l";
   if (plotNets)
      gpOut << ", '-' w l 3";
   gpOut << endl;

   for(it=_nodes->nodesBegin();it!=_nodes->nodesEnd();++it)
   {
      x=it->getX();
      y=it->getY();
      w=it->getWidth();
      h=it->getHeight();

      gpOut<<x<<" "<<y<<endl;
      gpOut<<x+w<<" "<<y<<endl;
      gpOut<<x+w<<" "<<y+h<<endl;
      gpOut<<x<<" "<<y+h<<endl;
      gpOut<<x<<" "<<y<<endl<<endl;
   }
   gpOut << "EOF"<<endl;

   if(plotNets)
   {
      double width;
      double height;
      double absOffsetX;
      double absOffsetY;
 
      itNet net;
      itPin netPin;
      for(net = _nets->netsBegin(); net != _nets->netsEnd(); ++net)
      {
         Point starPoint;
         starPoint.x = 0;
         starPoint.y = 0;
         unsigned netDegree = 0;
         for(netPin = net->pinsBegin(); netPin != net->pinsEnd(); netPin++)
         {
            Node node;
            if(!netPin->getType())  //if not terminal
               node = _nodes->getNode(netPin->getNodeIndex());
            else
               node = _nodes->getTerminal(netPin->getNodeIndex());

            width = node.getWidth();
            height = node.getHeight();
            absOffsetX = width/2 + (netPin->getXOffset()*width);
            absOffsetY = height/2 + (netPin->getYOffset()*height);
            starPoint.x += node.getX() + absOffsetX;
            starPoint.y += node.getY() + absOffsetY;
            ++netDegree;
         }
         
         if(netDegree != 0)
         {
            starPoint.x /= netDegree;
            starPoint.y /= netDegree;
            for(netPin = net->pinsBegin(); netPin != net->pinsEnd(); netPin++)
            {
               Node node;
               if(!netPin->getType())
                  node = _nodes->getNode(netPin->getNodeIndex());
               else
                  node = _nodes->getTerminal(netPin->getNodeIndex());
               width = node.getWidth();
               height = node.getHeight();
               absOffsetX = width/2 + (netPin->getXOffset()*width);
               absOffsetY = height/2 + (netPin->getYOffset()*height);
               gpOut<<starPoint.x<<"  "<<starPoint.y<<endl;
               gpOut<<node.getX()+absOffsetX<<"  "<<node.getY()+absOffsetY<<endl;
               gpOut<<starPoint.x<<"  "<<starPoint.y<<endl<<endl;

               gpOut<<starPoint.x-starDelta<<"  "<<starPoint.y<<endl;
               gpOut<<starPoint.x<<"  "<<starPoint.y+starDelta<<endl;
               gpOut<<starPoint.x+starDelta<<"  "<<starPoint.y<<endl;
               gpOut<<starPoint.x<<"  "<<starPoint.y-starDelta<<endl;
               gpOut<<starPoint.x-starDelta<<"  "<<starPoint.y<<endl<<endl;

            }
         }
         else
         {
            cout << "Warning: net with zero degree detected." << endl;
         }
      }
      gpOut << "EOF"<<endl<<endl; 
   }
   gpOut << "pause -1 'Press any key' "<<endl;
   gpOut.close();  
}


void DB::saveCapo(char* baseFileName,
                  double reqdAR, double reqdWS) const
{
   cout<<"Saving in Capo Format "<<baseFileName<<endl;
   _nodes->saveCapoNodes(baseFileName);
   _nodes->saveCapoPl(baseFileName);
   saveCapoNets(baseFileName);
   _nodes->saveCapoScl(baseFileName, reqdAR, reqdWS);

   //save the aux file now
   char fileName[1024];
   strcpy(fileName, baseFileName);
   strcat(fileName, ".aux");
   ofstream aux(fileName);
   aux<<"RowBasedPlacement : "<<baseFileName<<".nodes "<<baseFileName<<".nets "<<
      baseFileName<<".scl "<<baseFileName<<".pl "<<endl;
   aux.close();     
}

void DB::save(char* baseFileName) const
{
   cout<<"Saving in Floorplan Format "<<baseFileName<<endl;
   _nodes->saveNodes(baseFileName);
   _nodes->savePl(baseFileName);
   saveNets(baseFileName);
   saveWts(baseFileName);
}

void DB::saveCapoNets(char* baseFileName) const
{
   Nets* nets;
   nets = const_cast<DB*>(this)->getNets();
   double absOffsetX;
   double absOffsetY;
   double width;
   double height;
   double temp;
   int nodeIndex;
  
   char fileName[1024];
   strcpy(fileName, baseFileName);
   strcat(fileName, ".nets");
   ofstream file(fileName);

   file<<"UCLA nets   1.0"<<endl<<endl<<endl;
   file<<"NumPins : "<<nets->getNumPins()<<endl<<endl;
  
   itNet net;
   itPin pin;
   for(net = nets->netsBegin(); net != nets->netsEnd(); ++net)
   {
      file<<"NetDegree : "<<net->_pins.size()<<"\t"<<net->getName()<<endl;
      for(pin = net->pinsBegin(); pin != net->pinsEnd(); ++pin)
      {
         nodeIndex = pin->getNodeIndex();
         if(!pin->getType())        //if not terminal
         {
            Node& node = _nodes->getNode(nodeIndex);
            width = node.getWidth();
            height = node.getHeight();
         }                      
         else
         {
            Node& node = _nodes->getTerminal(nodeIndex);
            width = node.getWidth();
            height = node.getHeight();
         }
         if(int(pin->getOrient())%2 == 1)
         {
            temp = width;
            width = height;
            height = temp;
         }
         absOffsetX = (pin->getOrigXOffset()*width);
         absOffsetY = (pin->getOrigYOffset()*height);
          
         file<<"\t"<<pin->getName()<<" B : \t"<<absOffsetX<<"\t "<<absOffsetY<<endl;
      }
   }
   file.close();
}

void DB::saveNets(char* baseFileName) const
{
   Nets* nets;
   nets = const_cast<DB*>(this)->getNets();

   char fileName[1024];
   strcpy(fileName, baseFileName);
   strcat(fileName, ".nets");
   ofstream file(fileName);

   file<<"UCLA nets   1.0"<<endl<<endl<<endl;
   file<<"NumNets : "<<nets->getNumNets()<<endl;
   file<<"NumPins : "<<nets->getNumPins()<<endl<<endl;
  
   itNet net;
   itPin pin;
   for(net = nets->netsBegin(); net != nets->netsEnd(); ++net)
   {
     file<<"NetDegree : "<<net->_pins.size()<<"  "<<net->getName()<<endl;
      for(pin = net->pinsBegin(); pin != net->pinsEnd(); ++pin)
      {
         file<<pin->getName()<<" B : \t%"<<pin->getOrigXOffset()*100<<
            "\t %"<<pin->getOrigYOffset()*100<<endl;
      }
   }
   file.close();
}

void DB::saveWts(char* baseFileName) const
{
   Nets* nets;
   nets = const_cast<DB*>(this)->getNets();

   char fileName[1024];
   strcpy(fileName, baseFileName);
   strcat(fileName, ".wts");
   ofstream file(fileName);

   file<<"UCLA wts   1.0"<<endl<<endl<<endl;
  
   itNet net;
//   itPin pin;
   for(net = nets->netsBegin(); net != nets->netsEnd(); ++net)
     {
       file<<net->getName()<<"\t"<<net->getWeight()<<endl;
     }
   file.close();
}

void DB::shiftDesign(Point& offset)
{
   itNode node;
   for(node = _nodes->nodesBegin(); node != _nodes->nodesEnd(); ++node)
   {
      node->putX(node->getX() + offset.x);
      node->putY(node->getY() + offset.y);
   }
}

void DB::expandDesign(double maxWidth, double maxHeight)
{
   double currWidth = getXSize();
   double currHeight = getYSize();
   if(currWidth > maxWidth && currHeight > maxHeight)
      return;

   double xExpRatio=1;
   double yExpRatio=1;

   if(currWidth < maxWidth)
      xExpRatio = maxWidth/currWidth;
   if(currHeight < maxHeight)
      yExpRatio = maxHeight/currHeight;

   itNode node;
   double newLoc;
   for(node = getNodes()->nodesBegin(); node != getNodes()->nodesEnd(); ++node)
   {
      newLoc = node->getX()*xExpRatio;
      node->putX(newLoc);
      newLoc = node->getY()*yExpRatio;
      node->putY(newLoc);
   }
}


void DB::saveInBestCopy(void)
{
   successAR = 1;
   itNode node;
   itNode nodeBest;
   nodeBest = _nodesBestCopy->nodesBegin();
   for(node = _nodes->nodesBegin(); node != _nodes->nodesEnd(); node++)
   {
      nodeBest->putX(node->getX());
      nodeBest->putY(node->getY());
      nodeBest->putWidth(node->getWidth());
      nodeBest->putHeight(node->getHeight());
      nodeBest->putOrient(node->getOrient());
      nodeBest++;
   }
}

void DB::saveBestCopyPl(char* fileName) const
{
   _nodesBestCopy->savePl(fileName);
}

void DB::markTallNodesAsMacros(double maxHeight)
{
   itNode node;
   for(node = _nodes->nodesBegin(); node != _nodes->nodesEnd(); ++node)
   {
      if(node->getHeight() > maxHeight)
         node->updateMacroInfo(true);
   }
}

void DB::reduceCoreCellsArea(double layoutArea, double maxWS)
{
   double currNodesArea = getNodesArea();
   double currWS = (layoutArea - currNodesArea)/currNodesArea;

   if(currWS > maxWS)
      return;

   double macroArea = 0;
   itNode node;
   for(node = _nodes->nodesBegin(); node != _nodes->nodesEnd(); ++node)
   {
      if(node->isMacro())
         macroArea += node->getHeight()*node->getWidth();
   }

   double newCtoOldCRatio = ((layoutArea - (1+maxWS)*macroArea)*(1+currWS))/
      ((layoutArea - (1+currWS)*macroArea)*(1+maxWS));

   for(node = _nodes->nodesBegin(); node != _nodes->nodesEnd(); ++node)
   {
      if(!node->isMacro())
      {
         double nodeWidth = node->getWidth();
         double newNodeWidth = nodeWidth*newCtoOldCRatio;
         node->putWidth(newNodeWidth);
      }
   }
  
   _initArea = false;
   double newNodesArea = getNodesArea();

   currWS = (layoutArea - newNodesArea)/newNodesArea;
}

double DB::getXMaxWMacroOnly(void)
{
   //double xMin = DBL_MAX;
   double xMax = -1e20;
   itNode node;
   double value;
   bool valid=false;
   for(node = _nodes->nodesBegin(); node != _nodes->nodesEnd(); ++node)
   {
      if(node->isMacro())
      {
         valid = true;
         //value = node->getY();
         //if(value < xMin)
         //  xMin = value;

                 value = node->getX()+node->getWidth();
         if(value > xMax)
           xMax = value;
     }
   }
   if(valid)
      return (xMax);
   else
      return 0;
}

double DB::getXSizeWMacroOnly(void)
{

   BBox xSize;
   itNode node;
   Point P;
   for(node = _nodes->nodesBegin(); node != _nodes->nodesEnd(); ++node)
   {
      if(node->isMacro())
      {
         P.x = node->getX();
         P.y = 0;
         xSize.put(P);
         P.x = node->getX()+node->getWidth();
         P.y = 0;
         xSize.put(P);
      }
   }
   if(xSize.isValid())
      return (xSize.getXSize());
   else
      return 0;
}

double DB::getYMaxWMacroOnly(void)
{
   //double yMin = DBL_MAX;
   double yMax = -1e20;
   itNode node;
   double value;
   bool valid=false;
   for(node = _nodes->nodesBegin(); node != _nodes->nodesEnd(); ++node)
   {
      if(node->isMacro())
      {
         valid = true;
     //value = node->getY();
         //if(value < yMin)
         //  yMin = value;

         value = node->getY()+node->getHeight();
         if(value > yMax)
           yMax = value;
     }
   }
   if(valid)
      return (yMax);
   else
      return 0;
}

double DB::getYSizeWMacroOnly(void)
{
   BBox ySize;
   itNode node;
   Point P;
   for(node = _nodes->nodesBegin(); node != _nodes->nodesEnd(); ++node)
   {
      if(node->isMacro())
      {
         P.y = node->getY();
         P.x = 0;
         ySize.put(P);
         P.y = node->getY()+node->getHeight();
         P.x = 0;
         ySize.put(P);
     }
   }
   if(ySize.isValid())
      return (ySize.getYSize());
   else
      return 0;
}

// --------------------------------------------------------
void DB::shiftOptimizeDesign(double outlineWidth,
                             double outlineHeight)
{
   if (_nodes->getNumTerminals() == 0)
      return;   

   // original bottomLeft corner of the floorplan
   Point outlineBottomLeft(getBottomLeftCorner());
   Point outlineTopRight;
   outlineTopRight.x = outlineBottomLeft.x + outlineWidth;
   outlineTopRight.y = outlineBottomLeft.y + outlineHeight;

   shiftOptimizeDesign(outlineBottomLeft, outlineTopRight);
}
// --------------------------------------------------------
void DB::shiftOptimizeDesign(const Point& outlineBottomLeft,
                             const Point& outlineTopRight)
{
   double designWidth = getXSize();
   double designHeight = getYSize();

   double outlineWidth = outlineTopRight.x - outlineBottomLeft.x;
   double outlineHeight = outlineTopRight.y - outlineBottomLeft.y;

   if (designWidth < outlineWidth &&
       designHeight < outlineHeight)
   {
      Point currBottomLeft(getBottomLeftCorner());
      Point minOffset;
      minOffset.x = outlineBottomLeft.x - currBottomLeft.x;
      minOffset.y = outlineBottomLeft.y - currBottomLeft.y;

      Point currTopRight(getTopRightCorner());
      Point maxOffset;
      maxOffset.x = outlineTopRight.x - currTopRight.x;
      maxOffset.y = outlineTopRight.y - currTopRight.y;

      double xRangeStart = getOptimalRangeStart(true);
      xRangeStart = max(xRangeStart, minOffset.x);
      xRangeStart = min(xRangeStart, maxOffset.x);

      double yRangeStart = getOptimalRangeStart(false);
      yRangeStart = max(yRangeStart, minOffset.y);
      yRangeStart = min(yRangeStart, maxOffset.y);

      // the magnitude of shifting (not the final pos)
      Point offset;
      offset.x = xRangeStart;
      offset.y = yRangeStart;

      printf("currBBox: %.2f %.2f %.2f %.2f\n",
             currBottomLeft.x, currBottomLeft.y,
             currTopRight.x, currTopRight.y);
      printf("outBBox: %.2f %.2f %.2f %.2f\n",
             outlineBottomLeft.x, outlineBottomLeft.y,
             outlineTopRight.x, outlineTopRight.y);
      cout << "offset.x: " << offset.x
           << " offset.y: " << offset.y << endl;

      double origHPWL = evalHPWL();
      cout << "HPWL before shifting: " << origHPWL << endl;

      shiftDesign(offset);

      double newHPWL = evalHPWL();
      cout << "HPWL after shifting: " << newHPWL << endl;

      if (origHPWL < newHPWL)
      {
         cout << "Undo-ing the shift..." << endl;
         offset.x = -offset.x;
         offset.y = -offset.y;
         shiftDesign(offset);
      }

      double finalHPWL = evalHPWL();
      cout << "Final HPWL: " << finalHPWL << endl;
   }
   else
     {
       /* Saurabh: The below code is not general enough. only valid
          when relevant nodes are marked as macros. So I am connenting
          it out. only used for printing out a message anyway */
       /*
       double tempXSize = getXSizeWMacroOnly();
       double tempYSize = getYSizeWMacroOnly();
       if(tempXSize > 1e-5 && tempYSize > 1e-5)
         {
           designHeight = tempYSize;
           designWidth = tempXSize;
         }
       if (!(designWidth <= outlineWidth &&
             designHeight <= outlineHeight))
       */
       cout << "No shifting for HPWL minimization is performed. " << endl;
     }
}
// --------------------------------------------------------
double DB::getOptimalRangeStart(bool horizontal)
{
   double center = (horizontal)
      ? getXSize() / 2 : getYSize() / 2;
   
   vector<double> endPoints;
   for (itNode currBlk = _nodes->nodesBegin();
        currBlk != _nodes->nodesEnd(); currBlk++)
   {
      double currNodeLength = (horizontal)
         ? currBlk->getWidth() : currBlk->getHeight();

      double currNodeLocAbs = (horizontal)
         ? currBlk->getX() : currBlk->getY();
      
      for (itNodePin currNodePin = currBlk->pinsBegin();
           currNodePin != currBlk->pinsEnd(); currNodePin++)
      {
         // find the net in which this pin lies
         unsigned currNetIndex = currNodePin->netIndex;
         Net& currNet = _nets->getNet(currNetIndex);

         // index number for the pin in its net
         unsigned currPinOffset = currNodePin->pinOffset;

         // pins offset from the center
         double pinOffset = (horizontal)
            ? currNet.getPin(currPinOffset).getXOffset()
            : currNet.getPin(currPinOffset).getYOffset();

         // absolute location of the pin
         double pinLocationAbs =
            currNodeLocAbs +
            currNodeLength/2 + (currNodeLength * pinOffset);

         // relative location wrt center of the FLOORPLAN
         double pinLocationWrtCenter = pinLocationAbs - center;

         // span of the net in this direction wrt this pin
         double spanStart = 1e90;
         double spanEnd = -1e90;
         
         for (itPin currPad = currNet.pinsBegin();
              currPad != currNet.pinsEnd(); currPad++)
         {
            if (currPad->getType()) // true: pad/terminal
            {
               int padIndex = currPad->getNodeIndex();
               Node& currTerm = _nodes->getTerm(padIndex);

               double padLoc = (horizontal)
                  ? currTerm.getX() : currTerm.getY();

               double padAdjusted = padLoc - pinLocationWrtCenter;

               spanStart = min(spanStart, padAdjusted);
               spanEnd = max(spanEnd, padAdjusted);
            }
         } // end for each pin in currNet

         if (spanStart <= spanEnd)
         {
            endPoints.push_back(spanStart);
            endPoints.push_back(spanEnd);
         }
      } // end for each pin in currNode
   } // end for each node

   sort(endPoints.begin(), endPoints.end());

   // return the median, assuming endPoints[] has even size
   int endPointNum = endPoints.size();
   if(endPointNum < 2)
      {
        abkwarn(0,"Could not find optimal ranges.");
        return 0;
      }
   abkwarn(endPointNum % 2 == 0, "size of endPoints is not even.");
   return (endPoints[(endPointNum/2) - 1] + endPoints[endPointNum/2]) / 2;
}
// --------------------------------------------------------
               

---