btreecompact.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 BTREECOMPACT_H
#define BTREECOMPACT_H

#include "btree.h"

#include <vector>
#include <algorithm>
using namespace std;

// --------------------------------------------------------
class BTreeCompactor : public BTree
{
public:
   inline BTreeCompactor(const BTree& orig_tree);
   inline void operator =(const BTree& new_tree);
   inline void slimAssign(const BTree& new_tree); // suffices if evaluation
                                                  // follows
   
   inline int compact();
   void build_orth_tree();
   
   const vector<BTreeNode>& orth_tree;

private:
   vector<BTreeNode> in_orth_tree; // [NUM_BLOCKS] ~ in_tree[NUM_BLOCKS+1]
                                   // [NUM_BLOCKS+1] ~ in_tree[NUM_BLOCKS]

   void build_orth_tree_add_block(int treePtr);

   // (a) swap NUM_BLK vs. NUM_BLK+1
   // (b) fix parent of BL-block
   // used by build_orth_tree() only!!!
   inline static void fix_orth_tree(vector<BTreeNode>& orth_tree);
};
// --------------------------------------------------------

// =========================
//      IMPLEMENTATIONS
// =========================
BTreeCompactor::BTreeCompactor(const BTree& orig_tree)
   : BTree(orig_tree),
     orth_tree(in_orth_tree),
     in_orth_tree(orig_tree.tree.size())
{
   int vec_size = in_orth_tree.size();
   for (int i = 0; i < vec_size; i++)
   {
      in_orth_tree[i].parent = UNDEFINED;
      in_orth_tree[i].left = UNDEFINED;
      in_orth_tree[i].right = UNDEFINED;
      in_orth_tree[i].block_index = orig_tree.tree[i].block_index;
      in_orth_tree[i].orient =
         OrientedPacking::flip(OrientedPacking::ORIENT(orig_tree.tree[i].orient));
   }
}
// --------------------------------------------------------
inline void BTreeCompactor::operator =(const BTree& new_tree)
{
   this->BTree::operator =(new_tree);
   for (unsigned int i = 0; i < in_orth_tree.size(); i++)
   {
      in_orth_tree[i].parent = UNDEFINED;
      in_orth_tree[i].left = UNDEFINED;
      in_orth_tree[i].right = UNDEFINED;
      in_orth_tree[i].block_index = new_tree.tree[i].block_index;
      in_orth_tree[i].orient =
         OrientedPacking::flip(OrientedPacking::ORIENT(new_tree.tree[i].orient));
   }      
}
// --------------------------------------------------------
inline void BTreeCompactor::slimAssign(const BTree& new_tree)
{
   in_tree = new_tree.tree;
   in_blockArea = new_tree.blockArea();
   for (unsigned int i = 0; i < in_orth_tree.size(); i++)
   {
      in_orth_tree[i].parent = UNDEFINED;
      in_orth_tree[i].left = UNDEFINED;
      in_orth_tree[i].right = UNDEFINED;
      in_orth_tree[i].block_index = new_tree.tree[i].block_index;
      in_orth_tree[i].orient =
         OrientedPacking::flip(OrientedPacking::ORIENT(new_tree.tree[i].orient));
   }      
}
// --------------------------------------------------------
inline int BTreeCompactor::compact()
{
   vector<double> orig_xloc(in_xloc);
   vector<double> orig_yloc(in_yloc);

   build_orth_tree();
   swap_ranges(in_tree.begin(), in_tree.end(),
              in_orth_tree.begin());
//    cout << "-----here1: after build_orth_tree()-----" << endl;
//    cout << "in_tree: " << endl;
//    OutputBTree(cout, in_tree);
//    cout << endl << endl;
//    cout << "in_orth_tree:" << endl;
//    OutputBTree(cout, in_orth_tree);
//    cout << endl << endl;

   build_orth_tree();
   swap_ranges(in_tree.begin(), in_tree.end(),
              in_orth_tree.begin());
//    cout << "-----here2: after build_orth_tree()-----" << endl;
//    cout << "in_tree: " << endl;
//    OutputBTree(cout, in_tree);
//    cout << endl << endl;
//    cout << "in_orth_tree: " << endl;
//    OutputBTree(cout, in_orth_tree);
//    cout << endl << endl;
//    cout << "-----flipped packing-----" << endl;
//    OutputPacking(cout, BTreeOrientedPacking(*this));

//    ofstream outfile;
//    outfile.open("dummy_flipped");
//    Save_bbb(outfile, BTreeOrientedPacking(*this));
//    outfile.close();

   build_orth_tree();

   int count = 0;
   for (int i = 0; i < NUM_BLOCKS; i++)
   {
      if ((orig_xloc[i] != in_xloc[i]) ||
          (orig_yloc[i] != in_yloc[i]))
         count ++;
   }
   return count;
}
// --------------------------------------------------------
inline void BTreeCompactor::fix_orth_tree(vector<BTree::BTreeNode>& orth_tree)
{   
   // fix the tree s.t. in_tree[NUM_BLOCKS] corresponds to the root
   const int NUM_BLOCKS = orth_tree.size() - 2;
   int bottomLeftBlock = orth_tree[NUM_BLOCKS+1].left;
   
   orth_tree[bottomLeftBlock].parent = NUM_BLOCKS;
   iter_swap(&(orth_tree[NUM_BLOCKS]), &(orth_tree[NUM_BLOCKS+1]));
}
// --------------------------------------------------------
#endif

---