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