pltobtree.h

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.
***
***
***************************************************************************/


#ifndef PLTOBTREE_H
#define PLTOBTREE_H

#include "basepacking.h"
#include "btree.h"

#include <vector>
using namespace std;

// --------------------------------------------------------
class Pl2BTree
{
public:
   enum AlgoType {HEURISTIC, TCG};

   inline Pl2BTree(const vector<double>& n_xloc,
                   const vector<double>& n_yloc,
                   const vector<double>& n_widths,
                   const vector<double>& n_heights,
                   AlgoType algo);

   inline const vector<BTree::BTreeNode>& btree() const;
   inline const vector<int>& getXX() const;
   inline const vector<int>& getYY() const;
   
   static const double INFTY;
   static const int UNDEFINED; // = basepacking_h::Dimension::UNDEFINED;
   static const double EPSILON_ACCURACY; // = basepacking_h::Dimension::EPSILON_ACCURACY;
   
private:
   const vector<double>& _xloc;
   const vector<double>& _yloc;
   const vector<double>& _widths;
   const vector<double>& _heights;
   const int _blocknum;
   const double _epsilon;

   vector<BTree::BTreeNode> _btree;

   inline void initializeTree();
   inline double get_epsilon() const;

   // heuristic O(n^2) algo, usu. works for compacted packings
   class BuildTreeRecord
   {
   public:
      int parent;
      int treeLocIndex;
      double distance;
      double yDistance;

      double xStart;
      double xEnd;
      double yStart;
      double yEnd;
      bool used;

      bool operator <(const BuildTreeRecord& btr) const;      

      static double _epsilon;
      static double getDistance(const BuildTreeRecord& btr1,
                                const BuildTreeRecord& btr2);
   };
   
   class ValidCriterion // only compare relevant elements
   {
   public:
      inline ValidCriterion(const vector<BuildTreeRecord>& new_btr_vec);
      bool operator ()(const BuildTreeRecord& btr1,
                       const BuildTreeRecord& btr2) const;
      
      const vector<BuildTreeRecord>& btr_vec;
   };
   
   void heuristic_build_tree();   
   void build_tree_add_block(const BuildTreeRecord& btr);
   
   // tcg-based algo, always work
   int _count;
   vector<int> _XX;
   vector<int> _YY;
   void TCG_build_tree();

   // DP to find TCG
   void TCG_DP(vector< vector <bool> >& TCGMatrix); 
   void TCGDfs(vector< vector <bool> >& TCGMatrix, 
               const vector< vector <bool> >& adjMatrix,
               int v, 
               vector<int>& pre);

   class SPXRelation
   {
   public:
      SPXRelation(const vector< vector<bool> >& TCGMatrixHorizIP, 
                  const vector< vector<bool> >& TCGMatrixVertIP)
         : TCGMatrixHoriz(TCGMatrixHorizIP),
           TCGMatrixVert(TCGMatrixVertIP)
         {}

      inline bool operator ()(int i, int j) const;
         
   private:
      const vector< vector<bool> >& TCGMatrixHoriz;
      const vector< vector<bool> >& TCGMatrixVert;      
   };

   class SPYRelation
   {
   public:
      SPYRelation(const vector< vector<bool> >& TCGMatrixHorizIP, 
                  const vector< vector<bool> >& TCGMatrixVertIP)
         : TCGMatrixHoriz(TCGMatrixHorizIP),
           TCGMatrixVert(TCGMatrixVertIP)
         {}
      
      inline bool operator ()(int i, int j) const;

   private:
      const vector< vector<bool> >& TCGMatrixHoriz;
      const vector< vector<bool> >& TCGMatrixVert;      
   };
};
// --------------------------------------------------------

// ===============
// IMPLEMENTATIONS
// ===============
Pl2BTree::Pl2BTree(const vector<double>& n_xloc,
                   const vector<double>& n_yloc,
                   const vector<double>& n_widths,
                   const vector<double>& n_heights,
                   Pl2BTree::AlgoType algo)
   : _xloc(n_xloc),
     _yloc(n_yloc),
     _widths(n_widths),
     _heights(n_heights),
     _blocknum(n_xloc.size()),
     _epsilon(get_epsilon()),
     _btree(n_xloc.size()+2),
     _count(UNDEFINED),
     _XX(_blocknum, UNDEFINED),
     _YY(_blocknum, UNDEFINED)
{
   initializeTree();
   switch (algo)
   {
   case HEURISTIC:
      heuristic_build_tree();
      break;

   case TCG:
      TCG_build_tree();
      break;
      
   default:
      cout << "ERROR: invalid algorithm specified for Pl2BTree()." << endl;
      exit(1);
   }
}
// --------------------------------------------------------
void Pl2BTree::initializeTree()
{
   int vec_size = int(_btree.size());
   for (int i = 0; i < vec_size; i++)
   {
      _btree[i].parent = _blocknum;
      _btree[i].left = UNDEFINED;
      _btree[i].right = UNDEFINED;
      _btree[i].block_index = i;
      _btree[i].orient = 0;
   }

   _btree[_blocknum].parent = UNDEFINED;
   _btree[_blocknum].left = UNDEFINED;
   _btree[_blocknum].right = UNDEFINED;
   _btree[_blocknum].block_index = _blocknum;
   _btree[_blocknum].orient = UNDEFINED;

   _btree[_blocknum+1].parent = _blocknum;
   _btree[_blocknum+1].left = UNDEFINED;
   _btree[_blocknum+1].right = UNDEFINED;
   _btree[_blocknum+1].block_index = _blocknum+1;
   _btree[_blocknum+1].orient = UNDEFINED;
}
// --------------------------------------------------------
double Pl2BTree::get_epsilon() const
{
   double ep = INFTY;
   for (int i = 0; i < _blocknum; i++)
      ep = min(ep, min(_widths[i], _heights[i]));
   ep /= EPSILON_ACCURACY;
   return ep;
}
// --------------------------------------------------------
const vector<BTree::BTreeNode>& Pl2BTree::btree() const
{   return _btree; }
// --------------------------------------------------------
const vector<int>& Pl2BTree::getXX() const
{   return _XX; }
// --------------------------------------------------------
const vector<int>& Pl2BTree::getYY() const
{   return _YY; }
// --------------------------------------------------------
Pl2BTree::ValidCriterion::ValidCriterion(
   const vector<BuildTreeRecord>& new_btr_vec)
   : btr_vec(new_btr_vec)
{}
// --------------------------------------------------------
bool Pl2BTree::SPXRelation::operator ()(int i, int j) const
{
   if (TCGMatrixHoriz[i][j])
      return true;
   else if (TCGMatrixHoriz[j][i])
      return false;
   else if (TCGMatrixVert[j][i])
      return true;
   else if (TCGMatrixVert[i][j])
      return false;
   else
      return i < j;
}
// --------------------------------------------------------
bool Pl2BTree::SPYRelation::operator ()(int i, int j) const
{
   if (TCGMatrixHoriz[i][j])
      return true;
   else if (TCGMatrixHoriz[j][i])
      return false;
   else if (TCGMatrixVert[j][i])
      return false;
   else if (TCGMatrixVert[i][j])
      return true;
   else
      return i < j;
}
// --------------------------------------------------------

#endif

---