Debian Codegraph @

3rdparty/dissection/src/Splitters/BisectionInterConnection.cpp

raw
1 /*! \file BisectionInterConnetction.cpp
2 \brief Inter connection between off-diag strips
3 \author Xavier Juvigny, ONERA
4 \date Jul. 2nd 2012
5 \date Nov. 30th 2016
6 */
7
8 // This file is part of Dissection
9 //
10 // Dissection is free software: you can redistribute it and/or modify
11 // it under the terms of the GNU General Public License as published by
12 // the Free Software Foundation, either version 3 of the License, or
13 // (at your option) any later version.
14 //
15 // Linking Dissection statically or dynamically with other modules is making
16 // a combined work based on Disssection. Thus, the terms and conditions of
17 // the GNU General Public License cover the whole combination.
18 //
19 // As a special exception, the copyright holders of Dissection give you
20 // permission to combine Dissection program with free software programs or
21 // libraries that are released under the GNU LGPL and with independent modules
22 // that communicate with Dissection solely through the Dissection-fortran
23 // interface. You may copy and distribute such a system following the terms of
24 // the GNU GPL for Dissection and the licenses of the other code concerned,
25 // provided that you include the source code of that other code when and as
26 // the GNU GPL requires distribution of source code and provided that you do
27 // not modify the Dissection-fortran interface.
28 //
29 // Note that people who make modified versions of Dissection are not obligated
30 // to grant this special exception for their modified versions; it is their
31 // choice whether to do so. The GNU General Public License gives permission to
32 // release a modified version without this exception; this exception also makes
33 // it possible to release a modified version which carries forward this
34 // exception. If you modify the Dissection-fortran interface, this exception
35 // does not apply to your modified version of Dissection, and you must remove
36 // this exception when you distribute your modified version.
37 //
38 // This exception is an additional permission under section 7 of the GNU
39 // General Public License, version 3 ("GPLv3")
40 //
41 // Dissection is distributed in the hope that it will be useful,
42 // but WITHOUT ANY WARRANTY; without even the implied warranty of
43 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
44 // GNU General Public License for more details.
45 //
46 // You should have received a copy of the GNU General Public License
47 // along with Dissection. If not, see <http://www.gnu.org/licenses/>.
48 //
49
50 // ==============================================================
51 // == Implementation of the Interconnection methods ==
52 // ==============================================================
53 # include <cstdlib>
54 # include <list>
55 # include <algorithm>
56 # include <cassert>
57 # include "Splitters/BitManipulations.hpp"
58 # include "Compiler/DebugUtils.hpp"
59 # include "Splitters/BisectionInterConnection.hpp"
60 using namespace Dissection;
61
62 // ==============================================================
63 // == Strip methods ==
64 // ==============================================================
65 Strip::Strip(std::list<unsigned>& indices)
66 {
67 assert(!indices.empty());
68 /* Next contiguous index. */
69 unsigned nextContInd;
70 /* First local index is the first element of the list */
71 begin_dst = indices.front();
72 /* Which one remove from the list */
73 indices.pop_front();
74 nextContInd = begin_dst + 1;
75 while ((!indices.empty()) && (nextContInd == indices.front()))
76 {
77 nextContInd += 1;
78 indices.pop_front();
79 }
80 width = nextContInd - begin_dst;
81 }
82 // ..............................................................
83 bool
84 Strip::inside(const Strip& T, unsigned& decal) const
85 {
86 bool flg = (begin_dst>=T.begin_dst) &&
87 (nextIndice()<=T.nextIndice());
88 decal = unsigned(T.begin_dst - begin_dst);
89 return flg;
90 }
91 // --------------------------------------------------------------
92 // ==============================================================
93 // == SetOfStrips methods ==
94 // ==============================================================
95 SetOfStrips::SetOfStrips(std::list<unsigned>& indices) :
96 _lst_strips()
97 {
98 unsigned start = 0;
99 while (!indices.empty()) {
100 _lst_strips.push_back(Strip(indices));
101 Strip& strp = _lst_strips.back();
102 strp.begin_src = start;
103 start += strp.width;
104 }
105 assert(indices.empty());
106 }
107 // ..............................................................
108 void
109 SetOfStrips::push_back(const SetOfStrips& strps)
110 {
111 for (const_iterator it = strps.begin();
112 it != strps.end(); ++it) {
113 _lst_strips.push_back(*it);
114 }
115 }
116 // ..............................................................
117 SetOfStrips&
118 SetOfStrips::operator += (const SetOfStrips& strips)
119 {
120 std::list<Strip> unionOfStrips;
121 const std::list<Strip>& lstS2= strips._lst_strips;
122 std::list<Strip>::iterator itS1 = _lst_strips.begin();
123 std::list<Strip>::const_iterator itS2 = lstS2.begin();
124 // Easy cases when current or parameter set of strips
125 // is empty
126 // --------------------------------------------------
127 if (itS2 == lstS2.end()) return *this;
128 if (itS1 == _lst_strips.end())
129 {
130 _lst_strips = lstS2;
131 return *this;
132 }
133 // General case, when neither set is empty :
134 // ----------------------------------------
135 Strip curStrip;
136 unsigned nextCurStripInd;
137 if ((*itS1).begin_dst < (*itS2).begin_dst)
138 {
139 curStrip = *itS1;
140 itS1++;
141 }
142 else
143 {
144 curStrip = *itS2;
145 itS2++;
146 }
147 nextCurStripInd = curStrip.nextIndice();
148 while ((itS1 != _lst_strips.end()) &&
149 (itS2 != lstS2.end() ))
150 {
151 // Cases where we bind strips : Update current strip
152 if ((*itS1).begin_dst<=nextCurStripInd)
153 {
154 unsigned nextS1StripInd = (*itS1).nextIndice();
155 if (nextS1StripInd>nextCurStripInd) {
156 curStrip.width = nextS1StripInd-curStrip.begin_dst;
157 nextCurStripInd = nextS1StripInd;
158 }
159 itS1++;
160 }
161 else if ((*itS2).begin_dst<=nextCurStripInd)
162 {
163 unsigned nextS2StripInd = (*itS2).nextIndice();
164 if (nextS2StripInd>nextCurStripInd) {
165 curStrip.width = nextS2StripInd-curStrip.begin_dst;
166 nextCurStripInd = nextS2StripInd;
167 }
168 itS2++;
169 }
170 else
171 { // Case where we can't bind strips.
172 // --------------------------------
173 // 1. Register current strip :
174 unionOfStrips.push_back(curStrip);
175 // Create new strip :
176 if ((*itS1).begin_dst < (*itS2).begin_dst)
177 {
178 curStrip = *itS1;
179 itS1++;
180 }
181 else
182 {
183 curStrip = *itS2;
184 itS2++;
185 }
186 nextCurStripInd = curStrip.nextIndice();
187 }
188 }// While (((itS1 != _lst_strips.end())&&(itS2 != lstS2.end()))
189
190 // One of set of strips is cared in the union.
191 // Finish the union computation with the remained strips in
192 // one of set of strips :
193 if (itS1 != _lst_strips.end())
194 {
195 while ((itS1 != _lst_strips.end()) && ((*itS1).begin_dst<=nextCurStripInd))
196 {
197 unsigned nextS1StripInd = (*itS1).nextIndice();
198 if (nextS1StripInd>nextCurStripInd) {
199 curStrip.width = nextS1StripInd-curStrip.begin_dst;
200 nextCurStripInd = nextS1StripInd;
201 }
202 itS1++;
203 }
204 unionOfStrips.push_back(curStrip);
205 while (itS1 != _lst_strips.end()){
206 unionOfStrips.push_back(*itS1);
207 itS1++;
208 }
209 }
210 if (itS2 != lstS2.end())
211 {
212 while ((itS2 != lstS2.end()) &&
213 ((*itS2).begin_dst<=nextCurStripInd))
214
215 {
216 unsigned nextS2StripInd = (*itS2).begin_dst+(*itS2).width;
217 if (nextS2StripInd>nextCurStripInd) {
218 curStrip.width = nextS2StripInd-curStrip.begin_dst;
219 nextCurStripInd = nextS2StripInd;
220 }
221 itS2++;
222 }
223 unionOfStrips.push_back(curStrip);
224 while (itS2 != lstS2.end()){
225 unionOfStrips.push_back(*itS2);
226 itS2++;
227 }
228 }
229 // Update src indices in union of strips :
230 unsigned start = 0;
231 for (itS1 = unionOfStrips.begin(); itS1 != unionOfStrips.end();
232 itS1++) {
233 (*itS1).begin_src = start;
234 start += (*itS1).width;
235 }
236 // Copy new list of strips in current strip :
237 _lst_strips = unionOfStrips;
238 return *this;
239 }
240 // ............................................................
241 unsigned
242 SetOfStrips::numberOfIndices() const
243 {
244 unsigned width = 0U;
245 for (const_iterator it = begin(); it != end(); it++)
246 {
247 width += (*it).width;
248 }
249 return width;
250 }
251 // ............................................................
252 SetOfStrips::operator std::list<unsigned>()
253 {
254 std::list<unsigned> lst;
255 for (SetOfStrips::iterator itS = begin(); itS != end(); itS++)
256 {
257 for (unsigned l = (*itS).begin_dst; l < (*itS).nextIndice();l++)
258 lst.push_back(l);
259 }
260 return lst;
261 }
262 // ............................................................
263 void
264 SetOfStrips::para_union(const SetOfStrips& strips,
265 SetOfStrips& paraStrips1,
266 SetOfStrips& paraStrips2,
267 SetOfStrips& seqStrips) const
268 {
269 const std::list<Strip>& lstS1= _lst_strips;
270 const std::list<Strip>& lstS2= strips._lst_strips;
271 std::list<Strip>::const_iterator itS1 = lstS1.begin();
272 std::list<Strip>::const_iterator itS2 = lstS2.begin();
273 std::list<Strip>& lstP1= paraStrips1._lst_strips;
274 std::list<Strip>& lstP2= paraStrips2._lst_strips;
275 std::list<Strip>& lstS = seqStrips._lst_strips;
276 // Easy cases when current or parameter set of strips
277 // is empty
278 // --------------------------------------------------
279 if (itS2 == lstS2.end()) {
280 paraStrips1 = *this;
281 return;
282 }
283 if (itS1 == lstS1.end())
284 {
285 paraStrips2 = strips;
286 return;
287 }
288 // General case : neither set is empty
289 // -----------------------------------
290 bool curStripSeq;// Parallel(false) or sequential(true) strip ?
291 unsigned parFromStrip; // Number from which is build the strip
292 unsigned begCurStrip, szCurStrip, endCurStrip;
293
294 begCurStrip=std::min<unsigned>((*itS1).begin_dst,(*itS2).begin_dst);
295 if ((*itS1).begin_dst == (*itS2).begin_dst)
296 {// First strip is sequential in this case :
297 curStripSeq = true;
298 if ((*itS1).width < (*itS2).width) {
299 szCurStrip = (*itS1).width;
300 itS1++;
301 }
302 else if ((*itS2).width < (*itS1).width) {
303 szCurStrip = (*itS2).width;
304 itS2++;
305 }
306 else {
307 szCurStrip = (*itS1).width;
308 itS1++;
309 itS2++;
310 }
311 lstS.push_back(Strip(begCurStrip,szCurStrip));
312 }
313 else {// First strip is parallel
314 curStripSeq = false;
315 if ((*itS1).begin_dst < (*itS2).begin_dst)
316 {
317 unsigned endS1 = (*itS1).nextIndice()-1;
318 parFromStrip = 1;
319 if (endS1 < (*itS2).begin_dst) {
320 szCurStrip = (*itS1).width;
321 itS1++;
322 }
323 else
324 szCurStrip = (*itS2).begin_dst - begCurStrip;
325 }
326 else
327 {
328 unsigned endS2 = (*itS2).nextIndice()-1;
329 parFromStrip = 2;
330 if (endS2 < (*itS1).begin_dst) {
331 szCurStrip = (*itS2).width;
332 itS2++;
333 }
334 else
335 szCurStrip = (*itS1).begin_dst - begCurStrip;
336 }
337 if (1 == parFromStrip)
338 lstP1.push_back(Strip(begCurStrip,szCurStrip));
339 else {
340 assert(2 == parFromStrip);
341 lstP2.push_back(Strip(begCurStrip,szCurStrip));
342 }
343 }
344 endCurStrip = begCurStrip + szCurStrip - 1;
345 while ((itS1 != lstS1.end()) && (itS2 != lstS2.end()))
346 {
347 // Search first indice for the next strip and if it's
348 // sequential or not
349 if ( ((*itS1).begin_dst <= endCurStrip) ||
350 ((*itS2).begin_dst <= endCurStrip) ) {
351 // We are in this case :
352 // |---------| <---- itS1 or itS2
353 // |-----------| <---- itS2 or itS1
354 // |----| <---- The current union strip
355 // or this case :
356 // |---------| <---- itS1 or itS2
357 // |----| <---- itS2 or itS1
358 // |----| <---- The current union strip
359 begCurStrip = endCurStrip+1;
360 // In this case, we switch between parallel and sequential
361 // strips
362 curStripSeq = !curStripSeq;
363 }
364 else
365 {
366 // We are in this case :
367 // |-----| <---- itS1 or itS2
368 // |---------| <---- itS2 or itS1
369 // |--| <---- The current union strip
370
371 begCurStrip=
372 std::min<unsigned>((*itS1).begin_dst,(*itS2).begin_dst);
373 // In this case, the next strip is sequential only
374 // if both strips to union begin with same indices
375 curStripSeq=((*itS1).begin_dst==(*itS2).begin_dst);
376 }
377 // Search size of the next strip :
378 if (curStripSeq)
379 {// Strips S1 and S2 have common indices
380 unsigned endS1 = (*itS1).nextIndice()-1;
381 unsigned endS2 = (*itS2).nextIndice()-1;
382 if (endS1 < endS2) {
383 szCurStrip = endS1-begCurStrip+1;
384 itS1++;
385 }
386 else if (endS2 < endS1) {
387 szCurStrip = endS2-begCurStrip+1;
388 itS2++;
389 }
390 else {
391 szCurStrip = endS1-begCurStrip+1;
392 itS1++;
393 itS2++;
394 }
395 lstS.push_back(Strip(begCurStrip,szCurStrip));
396 }
397 else {// We care about some part of S1 or S2
398 // having exclusive indices
399 if ((*itS1).begin_dst <= begCurStrip)
400 {// S1 has some exclusive indices
401 unsigned endS1 = (*itS1).nextIndice()-1;
402 parFromStrip = 1;
403 if (endS1 < (*itS2).begin_dst) {
404 szCurStrip = endS1 - begCurStrip + 1;
405 itS1++;
406 }
407 else
408 szCurStrip = (*itS2).begin_dst - begCurStrip;
409 }
410 else {
411 // S2 has some exclusive indices
412 unsigned endS2 = (*itS2).nextIndice()-1;
413 parFromStrip = 2;
414 if (endS2 < (*itS1).begin_dst) {
415 szCurStrip = endS2 - begCurStrip + 1;
416 itS2++;
417 }
418 else
419 szCurStrip = (*itS1).begin_dst - begCurStrip;
420 }
421 if (1 == parFromStrip)
422 lstP1.push_back(Strip(begCurStrip,szCurStrip));
423 else {
424 assert(2 == parFromStrip);
425 lstP2.push_back(Strip(begCurStrip,szCurStrip));
426 }
427 }
428 endCurStrip = begCurStrip + szCurStrip - 1;
429 }// end while
430 // Now, one of S1 or (and) S2 has all indices in union
431 if (itS1==lstS1.end())
432 {
433 if (itS2!=lstS2.end())
434 {
435 if ((*itS2).begin_dst<endCurStrip) {
436 unsigned endS2 = (*itS2).nextIndice()-1;
437 lstP2.push_back(Strip(endCurStrip+1,endS2-endCurStrip));
438 itS2++;
439 }
440 while (itS2!=lstS2.end())
441 lstP2.push_back(*itS2++);
442 }
443 }
444 else {
445 if ((*itS1).begin_dst<endCurStrip) {
446 unsigned endS1 = (*itS1).nextIndice()-1;
447 lstP1.push_back(Strip(endCurStrip+1,endS1-endCurStrip));
448 itS1++;
449 }
450 while (itS1!=lstS1.end())
451 lstP1.push_back(*itS1++);
452 }
453 // End of the algorithm....
454 }
455 // ............................................................
456 // ==============================================================
457 // == FathersStrips methods implementation ==
458 // ==============================================================
459 FathersStrips::FathersStrips() :
460 _level(0),
461 _outOfDiags(NULL),
462 _seq_strips(NULL),
463 _par_strips(NULL),
464 _row_strips(NULL),
465 _col_strips(NULL)
466 {}
467 // ------------------------------------------------------------
468 FathersStrips::FathersStrips(unsigned lvl) :
469 _level(lvl),
470 _outOfDiags(NULL),
471 _seq_strips(NULL),
472 _par_strips(NULL),
473 _row_strips(NULL),
474 _col_strips(NULL)
475 {
476 if (lvl>0)
477 {
478 _outOfDiags = new SetOfStrips[lvl];
479 _row_strips = new SetOfStrips[((lvl+1)*lvl)/2];
480 _col_strips = new SetOfStrips[((lvl+1)*lvl)/2];
481 assert(_row_strips!=NULL);
482 assert(_col_strips!=NULL);
483 }
484 }
485 // ------------------------------------------------------------
486 FathersStrips::FathersStrips(FathersStrips& inter) :
487 _level(inter._level),
488 _outOfDiags(inter._outOfDiags),
489 _seq_strips(inter._seq_strips),
490 _par_strips(inter._par_strips),
491 _row_strips(inter._row_strips),
492 _col_strips(inter._col_strips)
493 {
494 inter._level = 0;
495 inter._outOfDiags = NULL;
496 inter._seq_strips = NULL;
497 inter._par_strips = NULL;
498 inter._row_strips = NULL;
499 inter._col_strips = NULL;
500 }
501 // ------------------------------------------------------------
502 FathersStrips::~FathersStrips()
503 {
504 if (_outOfDiags) delete [] _outOfDiags;
505 if (_seq_strips) delete [] _seq_strips;
506 if (_par_strips) delete [] _par_strips;
507 if (_row_strips) delete [] _row_strips;
508 if (_col_strips) delete [] _col_strips;
509 }
510 // ------------------------------------------------------------
511 void
512 FathersStrips::alloc(unsigned lvl)
513 {
514 if (_outOfDiags) delete [] _outOfDiags;
515 if (_seq_strips) delete [] _seq_strips;
516 if (_par_strips) delete [] _par_strips;
517 if (_row_strips) delete [] _row_strips;
518 if (_col_strips) delete [] _col_strips;
519 _level = lvl;
520 if (lvl>0)
521 {
522 _outOfDiags = new SetOfStrips[lvl];
523 _row_strips = new SetOfStrips[((lvl+1)*lvl)/2];
524 _col_strips = new SetOfStrips[((lvl+1)*lvl)/2];
525 assert(_row_strips!=NULL);
526 assert(_col_strips!=NULL);
527 }
528 }
529 // ------------------------------------------------------------
530 SetOfStrips&
531 FathersStrips::operator [] (unsigned lvl)
532 {
533 assert(lvl<_level);
534 assert(_outOfDiags!=NULL);
535 return _outOfDiags[lvl];
536 }
537 // ------------------------------------------------------------
538 const SetOfStrips&
539 FathersStrips::operator [] (unsigned lvl) const
540 {
541 assert(lvl<_level);
542 assert(_outOfDiags!=NULL);
543 return _outOfDiags[lvl];
544 }
545 // ____________________________________________________________
546 SetOfStrips&
547 FathersStrips::getRowSetOfStrips(unsigned l1, unsigned l2)
548 {
549 unsigned ind;
550
551 assert(l1<_level);
552 assert(l2<_level);
553
554 if (l1 > l2)
555 {
556 ind = l2+((l1+1)*l1)/2;
557 return _col_strips[ind];
558 }
559 ind = l1+((l2+1)*l2)/2;
560 return _row_strips[ind];
561 }
562 // ------------------------------------------------------------
563 const SetOfStrips&
564 FathersStrips::getRowSetOfStrips(unsigned l1, unsigned l2) const
565 {
566 unsigned ind;
567
568 assert(l1<_level);
569 assert(l2<_level);
570
571 if (l1 > l2)
572 {
573 ind = l2+((l1+1)*l1)/2;
574 return _col_strips[ind];
575 }
576 ind = l1+((l2+1)*l2)/2;
577 return _row_strips[ind];
578 }
579 // ------------------------------------------------------------
580 SetOfStrips&
581 FathersStrips::getColSetOfStrips(unsigned l1, unsigned l2)
582 {
583 unsigned ind;
584
585 assert(l1<_level);
586 assert(l2<_level);
587
588 if (l1 > l2)
589 {
590 ind = l2+((l1+1)*l1)/2;
591 return _row_strips[ind];
592 }
593 ind = l1+((l2+1)*l2)/2;
594 return _col_strips[ind];
595 }
596 // ------------------------------------------------------------
597 const SetOfStrips&
598 FathersStrips::getColSetOfStrips(unsigned l1, unsigned l2) const
599 {
600 unsigned ind;
601
602 assert(l1<_level);
603 assert(l2<_level);
604
605 if (l1 > l2)
606 {
607 ind = l2+((l1+1)*l1)/2;
608 return _row_strips[ind];
609 }
610 ind = l1+((l2+1)*l2)/2;
611 return _col_strips[ind];
612 }
613 // --------------------------------------------------------------