1 /* Authors: Lutong Wang and Bangqi Xu */
2 /*
3  * Copyright (c) 2019, The Regents of the University of California
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions are met:
8  *     * Redistributions of source code must retain the above copyright
9  *       notice, this list of conditions and the following disclaimer.
10  *     * Redistributions in binary form must reproduce the above copyright
11  *       notice, this list of conditions and the following disclaimer in the
12  *       documentation and/or other materials provided with the distribution.
13  *     * Neither the name of the University nor the
14  *       names of its contributors may be used to endorse or promote products
15  *       derived from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS BE LIABLE FOR ANY DIRECT,
21  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 #ifndef _FR_LOOKUP_TBL_H_
30 #define _FR_LOOKUP_TBL_H_
31 
32 // #include <map>
33 #include <iostream>
34 
35 #include "frBaseTypes.h"
36 
37 namespace fr {
38 enum class frInterpolateType
39 {
40   frcSnapDown,
41   frcSnapUp,
42   frcLinear
43 };
44 
45 enum class frExtrapolateType
46 {
47   frcSnapDown,
48   frcSnapUp,
49   frcLinear
50 };
51 
52 // fr1DLookupTbl
53 template <class rowClass, class valClass>
54 class fr1DLookupTbl
55 {
56  public:
57   // constructor
58 
fr1DLookupTbl(const fr1DLookupTbl & in)59   fr1DLookupTbl(const fr1DLookupTbl& in)
60       : rows(in.rows),
61         vals(in.vals),
62         rowName(in.rowName),
63         interpolateTypeRow(in.interpolateTypeRow),
64         interpolateTypeCol(in.interpolateTypeCol),
65         extrapolateTypeRowLower(in.extrapolateTypeRowLower),
66         extrapolateTypeRowUpper(in.extrapolateTypeRowUpper),
67         lowerBound(in.lowerBound)
68   {
69   }
70   fr1DLookupTbl(const frString& rowNameIn,
71                 const frCollection<rowClass>& rowsIn,
72                 const frCollection<valClass>& valsIn,
73                 bool lowerBoundIn = true)
74   {
75     rowName = rowNameIn;
76     rows = rowsIn;
77     vals = valsIn;
78     interpolateTypeRow = frInterpolateType::frcSnapDown;
79     interpolateTypeCol = frInterpolateType::frcSnapDown;
80     extrapolateTypeRowLower = frExtrapolateType::frcSnapUp;
81     extrapolateTypeRowUpper = frExtrapolateType::frcSnapUp;
82     lowerBound = lowerBoundIn;
83   }
84 
85   // getters
getRowName()86   frString getRowName() const { return rowName; }
getRows()87   frCollection<rowClass> getRows() const { return rows; }
getValues()88   frCollection<valClass> getValues() const { return vals; }
89 
90   // others
find(const rowClass & rowVal)91   valClass find(const rowClass& rowVal) const
92   {
93     valClass retVal;
94     frUInt4 rowIdx = getRowIdx(rowVal);
95     retVal = vals[rowIdx];
96     return retVal;
97   }
findMin()98   valClass findMin() const { return vals.front(); }
findMax()99   valClass findMax() const { return vals.back(); }
getMinRow()100   rowClass getMinRow() const { return rows.front(); }
getMaxRow()101   rowClass getMaxRow() const { return rows.back(); }
102 
103  private:
getRowIdx(const rowClass & rowVal)104   frUInt4 getRowIdx(const rowClass& rowVal) const
105   {
106     // currently only implement spacingtable style
107     // interpolation
108     frUInt4 retIdx;
109     if (rowVal >= rows.front() && rowVal <= rows.back()) {
110       if (lowerBound) {
111         // if (interpolateTypeRow == frInterpolateType::frcSnapDown) {
112         auto pos = lower_bound(rows.begin(), rows.end(), rowVal);
113         // if (*pos != rowVal && pos != rows.begin()) {
114         //   --pos;
115         // }
116         if (pos != rows.begin()) {
117           --pos;
118         }
119         retIdx = pos - rows.begin();
120       } else {
121         auto pos = upper_bound(rows.begin(), rows.end(), rowVal);
122         retIdx = std::min((frUInt4)(pos - rows.begin()), (frUInt4) rows.size());
123       }
124     }
125     // lower extrapolation
126     else if (rowVal < rows.front()) {
127       if (true) {
128         // if (extrapolateTypeRowLower == frExtrapolateType::frcSnapUp) {
129         retIdx = 0;
130       }
131     }
132     // upper extrapolation
133     else {
134       if (true) {
135         // if (extrapolateTypeRowUpper == frExtrapolateType::frcSnapDown) {
136         retIdx = rows.size() - 1;
137       }
138     }
139     return retIdx;
140   }
141 
142   frCollection<rowClass> rows;
143   frCollection<valClass> vals;
144 
145   frString rowName;
146 
147   frInterpolateType interpolateTypeRow;
148   frInterpolateType interpolateTypeCol;
149   frExtrapolateType extrapolateTypeRowLower;
150   frExtrapolateType extrapolateTypeRowUpper;
151   bool lowerBound;
152 };
153 
154 // fr2DLookupTbl
155 template <class rowClass, class colClass, class valClass>
156 class fr2DLookupTbl
157 {
158  public:
159   friend class frLef58SpacingTableConstraint;
160   // constructor
fr2DLookupTbl()161   fr2DLookupTbl()
162       : interpolateTypeRow(frInterpolateType::frcSnapDown),
163         interpolateTypeCol(frInterpolateType::frcSnapDown),
164         extrapolateTypeRowLower(frExtrapolateType::frcSnapDown),
165         extrapolateTypeRowUpper(frExtrapolateType::frcSnapDown),
166         extrapolateTypeColLower(frExtrapolateType::frcSnapDown),
167         extrapolateTypeColUpper(frExtrapolateType::frcSnapDown)
168   {
169   }
fr2DLookupTbl(const fr2DLookupTbl & in)170   fr2DLookupTbl(const fr2DLookupTbl& in)
171       : rows(in.rows),
172         cols(in.cols),
173         vals(in.vals),
174         rowName(in.rowName),
175         colName(in.colName),
176         interpolateTypeRow(in.interpolateTypeRow),
177         interpolateTypeCol(in.interpolateTypeCol),
178         extrapolateTypeRowLower(in.extrapolateTypeRowLower),
179         extrapolateTypeRowUpper(in.extrapolateTypeRowUpper),
180         extrapolateTypeColLower(in.extrapolateTypeColLower),
181         extrapolateTypeColUpper(in.extrapolateTypeColUpper)
182   {
183   }
fr2DLookupTbl(const frString & rowNameIn,const frCollection<rowClass> & rowsIn,const frString & colNameIn,const frCollection<colClass> & colsIn,const frCollection<frCollection<valClass>> & valsIn)184   fr2DLookupTbl(const frString& rowNameIn,
185                 const frCollection<rowClass>& rowsIn,
186                 const frString& colNameIn,
187                 const frCollection<colClass>& colsIn,
188                 const frCollection<frCollection<valClass>>& valsIn)
189   {
190     rowName = rowNameIn;
191     rows = rowsIn;
192     colName = colNameIn;
193     cols = colsIn;
194     vals = valsIn;
195     interpolateTypeRow = frInterpolateType::frcSnapDown;
196     interpolateTypeCol = frInterpolateType::frcSnapDown;
197     extrapolateTypeRowLower = frExtrapolateType::frcSnapUp;
198     extrapolateTypeRowUpper = frExtrapolateType::frcSnapUp;
199     extrapolateTypeColLower = frExtrapolateType::frcSnapDown;
200     extrapolateTypeColUpper = frExtrapolateType::frcSnapDown;
201   }
202 
203   // getters
getRowName()204   frString getRowName() const { return rowName; }
getColName()205   frString getColName() const { return colName; }
206 
getRows()207   frCollection<rowClass> getRows() { return rows; }
getCols()208   frCollection<colClass> getCols() { return cols; }
getValues()209   frCollection<frCollection<valClass>> getValues() { return vals; }
210 
211   // others
find(const rowClass & rowVal,const colClass & colVal)212   valClass find(const rowClass& rowVal, const colClass& colVal) const
213   {
214     valClass retVal;
215     frUInt4 rowIdx = getRowIdx(rowVal);
216     frUInt4 colIdx = getColIdx(colVal);
217     // std::cout << "rowIdx = " << rowIdx << ", colIdx = " << colIdx <<
218     // std::endl <<std::flush;
219     retVal = vals[rowIdx][colIdx];
220     return retVal;
221   }
findMin()222   valClass findMin() const { return vals.front().front(); }
findMax()223   valClass findMax() const { return vals.back().back(); }
224 
225   // debug
printTbl()226   void printTbl() const
227   {
228     std::cout << "rowName: " << rowName << std::endl;
229     for (auto& m : rows) {
230       std::cout << m << " ";
231     }
232     std::cout << "\n colName: " << colName << std::endl;
233     for (auto& m : cols) {
234       std::cout << m << " ";
235     }
236     std::cout << "\n vals: " << std::endl;
237     for (auto& m : vals) {
238       for (auto& n : m) {
239         std::cout << n << " ";
240       }
241       std::cout << std::endl;
242     }
243   }
244 
245  private:
getRowIdx(const rowClass & rowVal)246   frUInt4 getRowIdx(const rowClass& rowVal) const
247   {
248     // currently only implement spacingtable style
249     auto pos = --(std::lower_bound(rows.begin(), rows.end(), rowVal));
250     return std::max(0, (int) std::distance(rows.begin(), pos));
251   }
getColIdx(const colClass & colVal)252   frUInt4 getColIdx(const colClass& colVal) const
253   {
254     // currently only implement spacingtable style
255     auto pos = --(std::lower_bound(cols.begin(), cols.end(), colVal));
256     return std::max(0, (int) std::distance(cols.begin(), pos));
257   }
258 
259   frCollection<rowClass> rows;
260   frCollection<colClass> cols;
261   frCollection<frCollection<valClass>> vals;
262 
263   frString rowName;
264   frString colName;
265 
266   frInterpolateType interpolateTypeRow;
267   frInterpolateType interpolateTypeCol;
268   frExtrapolateType extrapolateTypeRowLower;
269   frExtrapolateType extrapolateTypeRowUpper;
270   frExtrapolateType extrapolateTypeColLower;
271   frExtrapolateType extrapolateTypeColUpper;
272 };
273 
274 }  // namespace fr
275 
276 #endif
277