1 /************************************************************************** 2 *** 3 *** Copyright (c) 2000-2006 Regents of the University of Michigan, 4 *** Saurabh N. Adya, Hayward Chan, Jarrod A. Roy 5 *** and Igor L. Markov 6 *** 7 *** Contact author(s): sadya@umich.edu, imarkov@umich.edu 8 *** Original Affiliation: University of Michigan, EECS Dept. 9 *** Ann Arbor, MI 48109-2122 USA 10 *** 11 *** Permission is hereby granted, free of charge, to any person obtaining 12 *** a copy of this software and associated documentation files (the 13 *** "Software"), to deal in the Software without restriction, including 14 *** without limitation 15 *** the rights to use, copy, modify, merge, publish, distribute, sublicense, 16 *** and/or sell copies of the Software, and to permit persons to whom the 17 *** Software is furnished to do so, subject to the following conditions: 18 *** 19 *** The above copyright notice and this permission notice shall be included 20 *** in all copies or substantial portions of the Software. 21 *** 22 *** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 23 *** EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 24 *** OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 25 *** IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY 26 *** CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT 27 *** OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR 28 *** THE USE OR OTHER DEALINGS IN THE SOFTWARE. 29 *** 30 *** 31 ***************************************************************************/ 32 33 #ifndef PLTOSP_H 34 #define PLTOSP_H 35 36 #include <algorithm> 37 #include <cmath> 38 #include <cstdlib> 39 #include <fstream> 40 #include <vector> 41 42 namespace parquetfp { 43 enum PL2SP_ALGO 44 { 45 NAIVE_ALGO, 46 TCG_ALGO 47 }; 48 49 class Pl2SP 50 { 51 private: 52 std::vector<float> _xloc; 53 std::vector<float> _yloc; 54 std::vector<float> _widths; 55 std::vector<float> _heights; 56 57 std::vector<unsigned> _XX; 58 std::vector<unsigned> _YY; 59 60 int _cnt; 61 62 public: 63 Pl2SP(std::vector<float>& xloc, 64 std::vector<float>& yloc, 65 std::vector<float>& widths, 66 std::vector<float>& heights, 67 PL2SP_ALGO whichAlgo); 68 ~Pl2SP()69 ~Pl2SP() {} 70 71 void naiveAlgo(void); 72 void TCGAlgo(void); 73 74 // Floyd Marshal to find TCG 75 void TCG_FM(std::vector<std::vector<bool>>& TCGMatrixHoriz, 76 std::vector<std::vector<bool>>& TCGMatrixVert); 77 78 // DP to find TCG 79 void TCG_DP(std::vector<std::vector<bool>>& TCGMatrixHoriz, 80 std::vector<std::vector<bool>>& TCGMatrixVert); 81 void TCGDfs(std::vector<std::vector<bool>>& TCGMatrix, 82 std::vector<std::vector<bool>>& adjMatrix, 83 int v, 84 std::vector<int>& pre); 85 getXSP(void)86 const std::vector<unsigned>& getXSP(void) const { return _XX; } 87 getYSP(void)88 const std::vector<unsigned>& getYSP(void) const { return _YY; } 89 90 void print(void) const; 91 }; 92 93 struct RowElem 94 { 95 unsigned index; 96 float xloc; 97 }; 98 99 struct less_mag 100 { operatorless_mag101 bool operator()(const RowElem& elem1, const RowElem& elem2) 102 { 103 return (elem1.xloc < elem2.xloc); 104 } 105 }; 106 107 class SPXRelation 108 { 109 const std::vector<std::vector<bool>>& TCGMatrixHoriz; 110 const std::vector<std::vector<bool>>& TCGMatrixVert; 111 112 public: SPXRelation(const std::vector<std::vector<bool>> & TCGMatrixHorizIP,const std::vector<std::vector<bool>> & TCGMatrixVertIP)113 SPXRelation(const std::vector<std::vector<bool>>& TCGMatrixHorizIP, 114 const std::vector<std::vector<bool>>& TCGMatrixVertIP) 115 : TCGMatrixHoriz(TCGMatrixHorizIP), TCGMatrixVert(TCGMatrixVertIP) 116 { 117 } 118 operator()119 bool operator()(const unsigned i, const unsigned j) const 120 { 121 if (i == j) { 122 return false; 123 } else if (TCGMatrixHoriz[i][j]) { 124 return true; 125 } else if (TCGMatrixHoriz[j][i]) { 126 return false; 127 } else if (TCGMatrixVert[j][i]) { 128 return true; 129 } else if (TCGMatrixVert[i][j]) { 130 return false; 131 } else { 132 // cout<<"ERROR IN PL2SP SPX "<<i<<"\t"<<j<<endl; 133 if (i < j) { 134 return true; 135 } else { 136 return false; 137 } 138 } 139 } 140 }; 141 142 class SPYRelation 143 { 144 const std::vector<std::vector<bool>>& TCGMatrixHoriz; 145 const std::vector<std::vector<bool>>& TCGMatrixVert; 146 147 public: SPYRelation(const std::vector<std::vector<bool>> & TCGMatrixHorizIP,const std::vector<std::vector<bool>> & TCGMatrixVertIP)148 SPYRelation(const std::vector<std::vector<bool>>& TCGMatrixHorizIP, 149 const std::vector<std::vector<bool>>& TCGMatrixVertIP) 150 : TCGMatrixHoriz(TCGMatrixHorizIP), TCGMatrixVert(TCGMatrixVertIP) 151 { 152 } operator()153 bool operator()(const unsigned i, const unsigned j) const 154 { 155 if (i == j) { 156 return false; 157 } 158 if (TCGMatrixHoriz[i][j]) 159 return true; 160 else if (TCGMatrixHoriz[j][i]) 161 return false; 162 else if (TCGMatrixVert[j][i]) 163 return false; 164 else if (TCGMatrixVert[i][j]) 165 return true; 166 else { 167 // cout<<"ERROR IN PL2SP SPY "<<i<<"\t"<<j<<endl; 168 if (i < j) 169 return true; 170 else 171 return false; 172 } 173 } 174 }; 175 } // namespace parquetfp 176 // using namespace parquetfp; 177 178 #endif 179