/*! \file BisectionInterConnetction.cpp \brief Inter connection between off-diag strips \author Xavier Juvigny, ONERA \date Jul. 2nd 2012 \date Nov. 30th 2016 */ // This file is part of Dissection // // Dissection is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // Linking Dissection statically or dynamically with other modules is making // a combined work based on Disssection. Thus, the terms and conditions of // the GNU General Public License cover the whole combination. // // As a special exception, the copyright holders of Dissection give you // permission to combine Dissection program with free software programs or // libraries that are released under the GNU LGPL and with independent modules // that communicate with Dissection solely through the Dissection-fortran // interface. You may copy and distribute such a system following the terms of // the GNU GPL for Dissection and the licenses of the other code concerned, // provided that you include the source code of that other code when and as // the GNU GPL requires distribution of source code and provided that you do // not modify the Dissection-fortran interface. // // Note that people who make modified versions of Dissection are not obligated // to grant this special exception for their modified versions; it is their // choice whether to do so. The GNU General Public License gives permission to // release a modified version without this exception; this exception also makes // it possible to release a modified version which carries forward this // exception. If you modify the Dissection-fortran interface, this exception // does not apply to your modified version of Dissection, and you must remove // this exception when you distribute your modified version. // // This exception is an additional permission under section 7 of the GNU // General Public License, version 3 ("GPLv3") // // Dissection is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with Dissection. If not, see . // // ============================================================== // == Implementation of the Interconnection methods == // ============================================================== # include # include # include # include # include "Splitters/BitManipulations.hpp" # include "Compiler/DebugUtils.hpp" # include "Splitters/BisectionInterConnection.hpp" using namespace Dissection; // ============================================================== // == Strip methods == // ============================================================== Strip::Strip(std::list& indices) { assert(!indices.empty()); /* Next contiguous index. */ unsigned nextContInd; /* First local index is the first element of the list */ begin_dst = indices.front(); /* Which one remove from the list */ indices.pop_front(); nextContInd = begin_dst + 1; while ((!indices.empty()) && (nextContInd == indices.front())) { nextContInd += 1; indices.pop_front(); } width = nextContInd - begin_dst; } // .............................................................. bool Strip::inside(const Strip& T, unsigned& decal) const { bool flg = (begin_dst>=T.begin_dst) && (nextIndice()<=T.nextIndice()); decal = unsigned(T.begin_dst - begin_dst); return flg; } // -------------------------------------------------------------- // ============================================================== // == SetOfStrips methods == // ============================================================== SetOfStrips::SetOfStrips(std::list& indices) : _lst_strips() { unsigned start = 0; while (!indices.empty()) { _lst_strips.push_back(Strip(indices)); Strip& strp = _lst_strips.back(); strp.begin_src = start; start += strp.width; } assert(indices.empty()); } // .............................................................. void SetOfStrips::push_back(const SetOfStrips& strps) { for (const_iterator it = strps.begin(); it != strps.end(); ++it) { _lst_strips.push_back(*it); } } // .............................................................. SetOfStrips& SetOfStrips::operator += (const SetOfStrips& strips) { std::list unionOfStrips; const std::list& lstS2= strips._lst_strips; std::list::iterator itS1 = _lst_strips.begin(); std::list::const_iterator itS2 = lstS2.begin(); // Easy cases when current or parameter set of strips // is empty // -------------------------------------------------- if (itS2 == lstS2.end()) return *this; if (itS1 == _lst_strips.end()) { _lst_strips = lstS2; return *this; } // General case, when neither set is empty : // ---------------------------------------- Strip curStrip; unsigned nextCurStripInd; if ((*itS1).begin_dst < (*itS2).begin_dst) { curStrip = *itS1; itS1++; } else { curStrip = *itS2; itS2++; } nextCurStripInd = curStrip.nextIndice(); while ((itS1 != _lst_strips.end()) && (itS2 != lstS2.end() )) { // Cases where we bind strips : Update current strip if ((*itS1).begin_dst<=nextCurStripInd) { unsigned nextS1StripInd = (*itS1).nextIndice(); if (nextS1StripInd>nextCurStripInd) { curStrip.width = nextS1StripInd-curStrip.begin_dst; nextCurStripInd = nextS1StripInd; } itS1++; } else if ((*itS2).begin_dst<=nextCurStripInd) { unsigned nextS2StripInd = (*itS2).nextIndice(); if (nextS2StripInd>nextCurStripInd) { curStrip.width = nextS2StripInd-curStrip.begin_dst; nextCurStripInd = nextS2StripInd; } itS2++; } else { // Case where we can't bind strips. // -------------------------------- // 1. Register current strip : unionOfStrips.push_back(curStrip); // Create new strip : if ((*itS1).begin_dst < (*itS2).begin_dst) { curStrip = *itS1; itS1++; } else { curStrip = *itS2; itS2++; } nextCurStripInd = curStrip.nextIndice(); } }// While (((itS1 != _lst_strips.end())&&(itS2 != lstS2.end())) // One of set of strips is cared in the union. // Finish the union computation with the remained strips in // one of set of strips : if (itS1 != _lst_strips.end()) { while ((itS1 != _lst_strips.end()) && ((*itS1).begin_dst<=nextCurStripInd)) { unsigned nextS1StripInd = (*itS1).nextIndice(); if (nextS1StripInd>nextCurStripInd) { curStrip.width = nextS1StripInd-curStrip.begin_dst; nextCurStripInd = nextS1StripInd; } itS1++; } unionOfStrips.push_back(curStrip); while (itS1 != _lst_strips.end()){ unionOfStrips.push_back(*itS1); itS1++; } } if (itS2 != lstS2.end()) { while ((itS2 != lstS2.end()) && ((*itS2).begin_dst<=nextCurStripInd)) { unsigned nextS2StripInd = (*itS2).begin_dst+(*itS2).width; if (nextS2StripInd>nextCurStripInd) { curStrip.width = nextS2StripInd-curStrip.begin_dst; nextCurStripInd = nextS2StripInd; } itS2++; } unionOfStrips.push_back(curStrip); while (itS2 != lstS2.end()){ unionOfStrips.push_back(*itS2); itS2++; } } // Update src indices in union of strips : unsigned start = 0; for (itS1 = unionOfStrips.begin(); itS1 != unionOfStrips.end(); itS1++) { (*itS1).begin_src = start; start += (*itS1).width; } // Copy new list of strips in current strip : _lst_strips = unionOfStrips; return *this; } // ............................................................ unsigned SetOfStrips::numberOfIndices() const { unsigned width = 0U; for (const_iterator it = begin(); it != end(); it++) { width += (*it).width; } return width; } // ............................................................ SetOfStrips::operator std::list() { std::list lst; for (SetOfStrips::iterator itS = begin(); itS != end(); itS++) { for (unsigned l = (*itS).begin_dst; l < (*itS).nextIndice();l++) lst.push_back(l); } return lst; } // ............................................................ void SetOfStrips::para_union(const SetOfStrips& strips, SetOfStrips& paraStrips1, SetOfStrips& paraStrips2, SetOfStrips& seqStrips) const { const std::list& lstS1= _lst_strips; const std::list& lstS2= strips._lst_strips; std::list::const_iterator itS1 = lstS1.begin(); std::list::const_iterator itS2 = lstS2.begin(); std::list& lstP1= paraStrips1._lst_strips; std::list& lstP2= paraStrips2._lst_strips; std::list& lstS = seqStrips._lst_strips; // Easy cases when current or parameter set of strips // is empty // -------------------------------------------------- if (itS2 == lstS2.end()) { paraStrips1 = *this; return; } if (itS1 == lstS1.end()) { paraStrips2 = strips; return; } // General case : neither set is empty // ----------------------------------- bool curStripSeq;// Parallel(false) or sequential(true) strip ? unsigned parFromStrip; // Number from which is build the strip unsigned begCurStrip, szCurStrip, endCurStrip; begCurStrip=std::min((*itS1).begin_dst,(*itS2).begin_dst); if ((*itS1).begin_dst == (*itS2).begin_dst) {// First strip is sequential in this case : curStripSeq = true; if ((*itS1).width < (*itS2).width) { szCurStrip = (*itS1).width; itS1++; } else if ((*itS2).width < (*itS1).width) { szCurStrip = (*itS2).width; itS2++; } else { szCurStrip = (*itS1).width; itS1++; itS2++; } lstS.push_back(Strip(begCurStrip,szCurStrip)); } else {// First strip is parallel curStripSeq = false; if ((*itS1).begin_dst < (*itS2).begin_dst) { unsigned endS1 = (*itS1).nextIndice()-1; parFromStrip = 1; if (endS1 < (*itS2).begin_dst) { szCurStrip = (*itS1).width; itS1++; } else szCurStrip = (*itS2).begin_dst - begCurStrip; } else { unsigned endS2 = (*itS2).nextIndice()-1; parFromStrip = 2; if (endS2 < (*itS1).begin_dst) { szCurStrip = (*itS2).width; itS2++; } else szCurStrip = (*itS1).begin_dst - begCurStrip; } if (1 == parFromStrip) lstP1.push_back(Strip(begCurStrip,szCurStrip)); else { assert(2 == parFromStrip); lstP2.push_back(Strip(begCurStrip,szCurStrip)); } } endCurStrip = begCurStrip + szCurStrip - 1; while ((itS1 != lstS1.end()) && (itS2 != lstS2.end())) { // Search first indice for the next strip and if it's // sequential or not if ( ((*itS1).begin_dst <= endCurStrip) || ((*itS2).begin_dst <= endCurStrip) ) { // We are in this case : // |---------| <---- itS1 or itS2 // |-----------| <---- itS2 or itS1 // |----| <---- The current union strip // or this case : // |---------| <---- itS1 or itS2 // |----| <---- itS2 or itS1 // |----| <---- The current union strip begCurStrip = endCurStrip+1; // In this case, we switch between parallel and sequential // strips curStripSeq = !curStripSeq; } else { // We are in this case : // |-----| <---- itS1 or itS2 // |---------| <---- itS2 or itS1 // |--| <---- The current union strip begCurStrip= std::min((*itS1).begin_dst,(*itS2).begin_dst); // In this case, the next strip is sequential only // if both strips to union begin with same indices curStripSeq=((*itS1).begin_dst==(*itS2).begin_dst); } // Search size of the next strip : if (curStripSeq) {// Strips S1 and S2 have common indices unsigned endS1 = (*itS1).nextIndice()-1; unsigned endS2 = (*itS2).nextIndice()-1; if (endS1 < endS2) { szCurStrip = endS1-begCurStrip+1; itS1++; } else if (endS2 < endS1) { szCurStrip = endS2-begCurStrip+1; itS2++; } else { szCurStrip = endS1-begCurStrip+1; itS1++; itS2++; } lstS.push_back(Strip(begCurStrip,szCurStrip)); } else {// We care about some part of S1 or S2 // having exclusive indices if ((*itS1).begin_dst <= begCurStrip) {// S1 has some exclusive indices unsigned endS1 = (*itS1).nextIndice()-1; parFromStrip = 1; if (endS1 < (*itS2).begin_dst) { szCurStrip = endS1 - begCurStrip + 1; itS1++; } else szCurStrip = (*itS2).begin_dst - begCurStrip; } else { // S2 has some exclusive indices unsigned endS2 = (*itS2).nextIndice()-1; parFromStrip = 2; if (endS2 < (*itS1).begin_dst) { szCurStrip = endS2 - begCurStrip + 1; itS2++; } else szCurStrip = (*itS1).begin_dst - begCurStrip; } if (1 == parFromStrip) lstP1.push_back(Strip(begCurStrip,szCurStrip)); else { assert(2 == parFromStrip); lstP2.push_back(Strip(begCurStrip,szCurStrip)); } } endCurStrip = begCurStrip + szCurStrip - 1; }// end while // Now, one of S1 or (and) S2 has all indices in union if (itS1==lstS1.end()) { if (itS2!=lstS2.end()) { if ((*itS2).begin_dst0) { _outOfDiags = new SetOfStrips[lvl]; _row_strips = new SetOfStrips[((lvl+1)*lvl)/2]; _col_strips = new SetOfStrips[((lvl+1)*lvl)/2]; assert(_row_strips!=NULL); assert(_col_strips!=NULL); } } // ------------------------------------------------------------ FathersStrips::FathersStrips(FathersStrips& inter) : _level(inter._level), _outOfDiags(inter._outOfDiags), _seq_strips(inter._seq_strips), _par_strips(inter._par_strips), _row_strips(inter._row_strips), _col_strips(inter._col_strips) { inter._level = 0; inter._outOfDiags = NULL; inter._seq_strips = NULL; inter._par_strips = NULL; inter._row_strips = NULL; inter._col_strips = NULL; } // ------------------------------------------------------------ FathersStrips::~FathersStrips() { if (_outOfDiags) delete [] _outOfDiags; if (_seq_strips) delete [] _seq_strips; if (_par_strips) delete [] _par_strips; if (_row_strips) delete [] _row_strips; if (_col_strips) delete [] _col_strips; } // ------------------------------------------------------------ void FathersStrips::alloc(unsigned lvl) { if (_outOfDiags) delete [] _outOfDiags; if (_seq_strips) delete [] _seq_strips; if (_par_strips) delete [] _par_strips; if (_row_strips) delete [] _row_strips; if (_col_strips) delete [] _col_strips; _level = lvl; if (lvl>0) { _outOfDiags = new SetOfStrips[lvl]; _row_strips = new SetOfStrips[((lvl+1)*lvl)/2]; _col_strips = new SetOfStrips[((lvl+1)*lvl)/2]; assert(_row_strips!=NULL); assert(_col_strips!=NULL); } } // ------------------------------------------------------------ SetOfStrips& FathersStrips::operator [] (unsigned lvl) { assert(lvl<_level); assert(_outOfDiags!=NULL); return _outOfDiags[lvl]; } // ------------------------------------------------------------ const SetOfStrips& FathersStrips::operator [] (unsigned lvl) const { assert(lvl<_level); assert(_outOfDiags!=NULL); return _outOfDiags[lvl]; } // ____________________________________________________________ SetOfStrips& FathersStrips::getRowSetOfStrips(unsigned l1, unsigned l2) { unsigned ind; assert(l1<_level); assert(l2<_level); if (l1 > l2) { ind = l2+((l1+1)*l1)/2; return _col_strips[ind]; } ind = l1+((l2+1)*l2)/2; return _row_strips[ind]; } // ------------------------------------------------------------ const SetOfStrips& FathersStrips::getRowSetOfStrips(unsigned l1, unsigned l2) const { unsigned ind; assert(l1<_level); assert(l2<_level); if (l1 > l2) { ind = l2+((l1+1)*l1)/2; return _col_strips[ind]; } ind = l1+((l2+1)*l2)/2; return _row_strips[ind]; } // ------------------------------------------------------------ SetOfStrips& FathersStrips::getColSetOfStrips(unsigned l1, unsigned l2) { unsigned ind; assert(l1<_level); assert(l2<_level); if (l1 > l2) { ind = l2+((l1+1)*l1)/2; return _row_strips[ind]; } ind = l1+((l2+1)*l2)/2; return _col_strips[ind]; } // ------------------------------------------------------------ const SetOfStrips& FathersStrips::getColSetOfStrips(unsigned l1, unsigned l2) const { unsigned ind; assert(l1<_level); assert(l2<_level); if (l1 > l2) { ind = l2+((l1+1)*l1)/2; return _row_strips[ind]; } ind = l1+((l2+1)*l2)/2; return _col_strips[ind]; } // --------------------------------------------------------------