16 #ifndef _LIMBO_ALGORITHMS_PLACEMENT_GREEDYSEARCH_H
17 #define _LIMBO_ALGORITHMS_PLACEMENT_GREEDYSEARCH_H
43 typedef Component node_type;
44 typedef Segment row_type;
45 typedef int site_coordinate_type;
46 typedef list<node_type*> node_vector_type;
47 typedef list<node_type*> node_fail_vector_type;
48 typedef vector<row_type*> row_vector_type;
55 vector<list<node_type*>::iterator> vItNode;
64 cost_type(cost_type
const& rhs)
68 site_id = rhs.site_id;
69 color_id = rhs.color_id;
70 vItNode = rhs.vItNode;
74 friend bool operator<(cost_type
const& c1, cost_type
const& c2) {
return c1.cost < c2.cost;}
77 SegLegalizerCF* pslmr;
79 GSCallback(SegLegalizerCF* psl) : pslmr(psl) {}
80 GSCallback(GSCallback
const& rhs) : pslmr(rhs.pslmr) {}
85 site_coordinate_type site_xl(
const node_type* pn)
const {}
86 site_coordinate_type site_xh(
const node_type* pn)
const {}
89 pair<size_t, size_t> row_range(
const node_type* pn)
const {}
92 node_vector_type& nodes_in_row(
size_t row_idx)
const {}
95 bool check_displace(
const node_type* pn, site_coordinate_type x, site_coordinate_type y)
const {}
104 cost_type calc_cost(
const node_type* pcomp2, site_coordinate_type seg_id2,
105 site_coordinate_type site_id2, vector<list<node_type*>::iterator>
const& vItNode,
unsigned int swap_cnt)
const{}
108 bool check_valid(cost_type
const& c)
const {}
110 void apply(node_type* pcomp, cost_type
const& c, node_fail_vector_type& vFailNode,
int swap_cnt)
const {}
113 row_type* row(
size_t row_idx)
const {}
114 site_coordinate_type site_xl(
const row_type* pr)
const {}
115 site_coordinate_type site_xh(
const row_type* pr)
const {}
121 template <
typename T>
129 template <
typename T>
138 template <
typename CallbackType>
143 typedef CallbackType callback_type;
144 typedef typename callback_type::node_type node_type;
145 typedef typename callback_type::cost_type cost_type;
146 typedef typename callback_type::row_type row_type;
147 typedef typename callback_type::site_coordinate_type site_coordinate_type;
149 typedef typename callback_type::node_fail_vector_type node_fail_vector_type;
150 typedef typename callback_type::row_vector_type row_vector_type;
167 void operator()(node_fail_vector_type& vFailNode,
int max_swap_cnt) {this->
run(vFailNode, max_swap_cnt);}
171 void run(node_fail_vector_type& vFailNode,
int max_swap_cnt)
173 for (
typename node_fail_vector_type::iterator it = vFailNode.begin();
174 it != vFailNode.end(); )
176 node_value_type n = *it;
177 bool success_flag =
false;
178 for (
int i = 0; i <= max_swap_cnt; ++i)
188 typename node_fail_vector_type::iterator itPrev = it;
190 vFailNode.erase(itPrev);
200 bool search_swap(node_value_type n, node_fail_vector_type& vFailNode,
int swap_cnt)
202 typedef typename node_vector_type::iterator node_iterator_type;
203 pair<size_t, size_t> row_range =
m_cbk.row_range(n);
205 size_t row_idx1 = row_range.first;
206 size_t row_idx2 = row_range.second;
207 assert(row_idx1 < row_idx2);
211 assert(!
m_cbk.check_valid(best_cost));
212 for (
size_t row_idx = row_idx1; row_idx != row_idx2; ++row_idx)
214 node_vector_type& vNode =
m_cbk.nodes_in_row(row_idx);
216 row_const_value_type row =
m_cbk.row(row_idx);
218 vector<node_iterator_type> vIt2 (swap_cnt+1, vNode.begin());
219 bool next_flag1 =
false;
220 for (
int i = 0; i < swap_cnt; ++i)
222 if (vIt2.back() == vNode.end())
229 if (next_flag1)
continue;
230 for (; vIt2.back() != vNode.end(); ++vIt2.back())
233 for (
int i = vIt2.size()-1; i > 0; --i)
240 bool next_flag2 =
false;
242 for (
int i = 0; i < vIt2.size()-1; ++i)
245 assert(n != *vIt2[i]);
252 if (next_flag2)
continue;
255 site_coordinate_type ws_site_xl;
256 site_coordinate_type ws_site_xh =
m_cbk.site_xl(*vIt2.back());
257 if (vIt2.front() != vNode.begin())
259 node_iterator_type it2_0 = vIt2.front();
261 ws_site_xl = this->
site_xh(*it2_0);
263 else ws_site_xl =
m_cbk.site_xl(row);
265 if (ws_site_xh-ws_site_xl < site_size_x)
continue;
268 for (site_coordinate_type tgt_site = ws_site_xl;
269 tgt_site <= ws_site_xh-site_size_x; ++tgt_site)
272 if (!
m_cbk.check_displace(n, tgt_site, row_idx))
continue;
273 cost_type cur_cost =
m_cbk.calc_cost(n, row_idx, tgt_site, vIt2, swap_cnt);
274 if (!
m_cbk.check_valid(best_cost) || cur_cost < best_cost)
276 best_cost = cur_cost;
281 if (
m_cbk.check_valid(best_cost))
284 m_cbk.apply(n, best_cost, vFailNode, swap_cnt);
299 site_coordinate_type
node_site_gap_x(node_const_value_type n1, node_const_value_type n2)
const
305 site_coordinate_type
site_xl(node_const_value_type n)
const
307 return m_cbk.site_xl(n);
311 site_coordinate_type
site_xh(node_const_value_type n)
const
313 return m_cbk.site_xh(n);
callback_type m_cbk
a copiable callback_type is required
void apply(GdsCellReference const &cellRef, ObjectType *object)
apply cell reference
site_coordinate_type node_site_gap_x(node_const_value_type n1, node_const_value_type n2) const
const T * const_value_type
constant value type
site_coordinate_type site_xh(node_const_value_type n) const
T const & const_value_type
constant value type
void operator()(node_fail_vector_type &vFailNode, int max_swap_cnt)
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
site_coordinate_type node_site_size_x(node_const_value_type n) const
void run(node_fail_vector_type &vFailNode, int max_swap_cnt)
bool search_swap(node_value_type n, node_fail_vector_type &vFailNode, int swap_cnt)
site_coordinate_type site_xl(node_const_value_type n) const
callback_type::node_vector_type node_vector_type
node container for a single row
GreedySearch(callback_type cbk=callback_type())