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 PLTOBTREE_H
34 #define PLTOBTREE_H
35
36 #include "basepacking.h"
37 #include "btree.h"
38
39 namespace parquetfp {
40
41 // --------------------------------------------------------
42 class Pl2BTree
43 {
44 public:
45 enum AlgoType
46 {
47 HEURISTIC,
48 TCG
49 };
50
51 inline Pl2BTree(const std::vector<float>& n_xloc,
52 const std::vector<float>& n_yloc,
53 const std::vector<float>& n_widths,
54 const std::vector<float>& n_heights,
55 AlgoType algo);
56
57 inline const std::vector<BTree::BTreeNode>& btree() const;
58 inline const std::vector<int>& getXX() const;
59 inline const std::vector<int>& getYY() const;
60
61 static const float Infty;
62 static const int Undefined; // = basepacking_h::Dimension::Undefined;
63 static const float
64 Epsilon_Accuracy; // = basepacking_h::Dimension::Epsilon_Accuracy;
65
66 private:
67 const std::vector<float>& _xloc;
68 const std::vector<float>& _yloc;
69 const std::vector<float>& _widths;
70 const std::vector<float>& _heights;
71 const int _blocknum;
72 const float _epsilon;
73
74 std::vector<BTree::BTreeNode> _btree;
75
76 inline void initializeTree();
77 inline float get_epsilon() const;
78
79 // heuristic O(n^2) algo, usu. works for compacted packings
80 class BuildTreeRecord
81 {
82 public:
83 int parent;
84 int treeLocIndex;
85 float distance;
86 float yDistance;
87
88 float xStart;
89 float xEnd;
90 float yStart;
91 float yEnd;
92 bool used;
93
94 bool operator<(const BuildTreeRecord& btr) const;
95
96 static float _epsilon;
97 static float getDistance(const BuildTreeRecord& btr1,
98 const BuildTreeRecord& btr2);
99 };
100
101 class ValidCriterion // only compare relevant elements
102 {
103 public:
104 inline ValidCriterion(const std::vector<BuildTreeRecord>& new_btr_vec);
105 bool operator()(const BuildTreeRecord& btr1,
106 const BuildTreeRecord& btr2) const;
107
108 const std::vector<BuildTreeRecord>& btr_vec;
109 };
110
111 void heuristic_build_tree();
112 void build_tree_add_block(const BuildTreeRecord& btr);
113
114 // tcg-based algo, always work
115 int _count;
116 std::vector<int> _XX;
117 std::vector<int> _YY;
118 void TCG_build_tree();
119
120 // DP to find TCG
121 void TCG_DP(std::vector<std::vector<bool>>& TCGMatrix);
122 void TCGDfs(std::vector<std::vector<bool>>& TCGMatrix,
123 const std::vector<std::vector<bool>>& adjMatrix,
124 int v,
125 std::vector<int>& pre);
126
127 class SPXRelation
128 {
129 public:
SPXRelation(const std::vector<std::vector<bool>> & TCGMatrixHorizIP,const std::vector<std::vector<bool>> & TCGMatrixVertIP)130 SPXRelation(const std::vector<std::vector<bool>>& TCGMatrixHorizIP,
131 const std::vector<std::vector<bool>>& TCGMatrixVertIP)
132 : TCGMatrixHoriz(TCGMatrixHorizIP), TCGMatrixVert(TCGMatrixVertIP)
133 {
134 }
135
136 inline bool operator()(int i, int j) const;
137
138 private:
139 const std::vector<std::vector<bool>>& TCGMatrixHoriz;
140 const std::vector<std::vector<bool>>& TCGMatrixVert;
141 };
142
143 class SPYRelation
144 {
145 public:
SPYRelation(const std::vector<std::vector<bool>> & TCGMatrixHorizIP,const std::vector<std::vector<bool>> & TCGMatrixVertIP)146 SPYRelation(const std::vector<std::vector<bool>>& TCGMatrixHorizIP,
147 const std::vector<std::vector<bool>>& TCGMatrixVertIP)
148 : TCGMatrixHoriz(TCGMatrixHorizIP), TCGMatrixVert(TCGMatrixVertIP)
149 {
150 }
151
152 inline bool operator()(int i, int j) const;
153
154 private:
155 const std::vector<std::vector<bool>>& TCGMatrixHoriz;
156 const std::vector<std::vector<bool>>& TCGMatrixVert;
157 };
158 };
159 // --------------------------------------------------------
160
161 // ===============
162 // IMPLEMENTATIONS
163 // ===============
Pl2BTree(const std::vector<float> & n_xloc,const std::vector<float> & n_yloc,const std::vector<float> & n_widths,const std::vector<float> & n_heights,Pl2BTree::AlgoType algo)164 Pl2BTree::Pl2BTree(const std::vector<float>& n_xloc,
165 const std::vector<float>& n_yloc,
166 const std::vector<float>& n_widths,
167 const std::vector<float>& n_heights,
168 Pl2BTree::AlgoType algo)
169 : _xloc(n_xloc),
170 _yloc(n_yloc),
171 _widths(n_widths),
172 _heights(n_heights),
173 _blocknum(n_xloc.size()),
174 _epsilon(get_epsilon()),
175 _btree(n_xloc.size() + 2),
176 _count(Undefined),
177 _XX(_blocknum, Undefined),
178 _YY(_blocknum, Undefined)
179 {
180 initializeTree();
181 switch (algo) {
182 case HEURISTIC:
183 heuristic_build_tree();
184 break;
185
186 case TCG:
187 TCG_build_tree();
188 break;
189
190 default:
191 std::cout << "ERROR: invalid algorithm specified for Pl2BTree()."
192 << std::endl;
193 exit(1);
194 }
195 }
196 // --------------------------------------------------------
initializeTree()197 void Pl2BTree::initializeTree()
198 {
199 int vec_size = int(_btree.size());
200 for (int i = 0; i < vec_size; i++) {
201 _btree[i].parent = _blocknum;
202 _btree[i].left = Undefined;
203 _btree[i].right = Undefined;
204 _btree[i].block_index = i;
205 _btree[i].orient = 0;
206 }
207
208 _btree[_blocknum].parent = Undefined;
209 _btree[_blocknum].left = Undefined;
210 _btree[_blocknum].right = Undefined;
211 _btree[_blocknum].block_index = _blocknum;
212 _btree[_blocknum].orient = Undefined;
213
214 _btree[_blocknum + 1].parent = _blocknum;
215 _btree[_blocknum + 1].left = Undefined;
216 _btree[_blocknum + 1].right = Undefined;
217 _btree[_blocknum + 1].block_index = _blocknum + 1;
218 _btree[_blocknum + 1].orient = Undefined;
219 }
220 // --------------------------------------------------------
get_epsilon()221 float Pl2BTree::get_epsilon() const
222 {
223 float ep = Infty;
224 for (int i = 0; i < _blocknum; i++)
225 ep = std::min(ep, std::min(_widths[i], _heights[i]));
226 ep /= Epsilon_Accuracy;
227 return ep;
228 }
229 // --------------------------------------------------------
btree()230 const std::vector<BTree::BTreeNode>& Pl2BTree::btree() const
231 {
232 return _btree;
233 }
234 // --------------------------------------------------------
getXX()235 const std::vector<int>& Pl2BTree::getXX() const
236 {
237 return _XX;
238 }
239 // --------------------------------------------------------
getYY()240 const std::vector<int>& Pl2BTree::getYY() const
241 {
242 return _YY;
243 }
244 // --------------------------------------------------------
ValidCriterion(const std::vector<BuildTreeRecord> & new_btr_vec)245 Pl2BTree::ValidCriterion::ValidCriterion(
246 const std::vector<BuildTreeRecord>& new_btr_vec)
247 : btr_vec(new_btr_vec)
248 {
249 }
250 // --------------------------------------------------------
operator()251 bool Pl2BTree::SPXRelation::operator()(int i, int j) const
252 {
253 if (TCGMatrixHoriz[i][j])
254 return true;
255 else if (TCGMatrixHoriz[j][i])
256 return false;
257 else if (TCGMatrixVert[j][i])
258 return true;
259 else if (TCGMatrixVert[i][j])
260 return false;
261 else
262 return i < j;
263 }
264 // --------------------------------------------------------
operator()265 bool Pl2BTree::SPYRelation::operator()(int i, int j) const
266 {
267 if (TCGMatrixHoriz[i][j])
268 return true;
269 else if (TCGMatrixHoriz[j][i])
270 return false;
271 else if (TCGMatrixVert[j][i])
272 return false;
273 else if (TCGMatrixVert[i][j])
274 return true;
275 else
276 return i < j;
277 }
278 // --------------------------------------------------------
279
280 } // namespace parquetfp
281 #endif
282