src/mesh/cfMesh/utilities/containers/VRWGraph/VRWGraphI.H

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | cfMesh: A library for mesh generation
   4    \\    /   O peration     |
   5     \\  /    A nd           | Author: Franjo Juretic (franjo.juretic@c-fields.com)
   6      \\/     M anipulation  | Copyright (C) Creative Fields, Ltd.
   7 -------------------------------------------------------------------------------
   8 License
   9     This file is part of cfMesh.
  10
  11     cfMesh is free software; you can redistribute it and/or modify it
  12     under the terms of the GNU General Public License as published by the
  13     Free Software Foundation; either version 3 of the License, or (at your
  14     option) any later version.
  15
  16     cfMesh is distributed in the hope that it will be useful, but WITHOUT
  17     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19     for more details.
  20
  21     You should have received a copy of the GNU General Public License
  22     along with cfMesh.  If not, see <http://www.gnu.org/licenses/>.
  23
  24 \*---------------------------------------------------------------------------*/
  25
  26 inline void Foam::VRWGraph::checkIndex(const label i, const label j) const
  27 {
  28     if( (i < 0) || (i >= rows_.size()) )
  29     {
  30         FatalErrorIn
  31         (
  32             "void Foam::VRWGraph<T,width>::"
  33             "checkIndex(const label i, const label j) const"
  34         ) << "Row index " << i
  35             << " is not in range " << 0
  36             << " and " << rows_.size() << abort(FatalError);
  37     }
  38
  39     if( (j < 0) || (j >= rows_[i].size()) )
  40         FatalErrorIn
  41         (
  42             "void Foam::VRWGraph<T,width>::"
  43             "checkIndex(label const, const label) const"
  44         ) << "Column index " << j
  45             << " is not in range " << 0
  46             << " and " << rows_[i].size() << abort(FatalError);
  47 }
  48
  49 // * * * * * * * * * * * * * * * * Constructors  * * * * * * * * * * * * * * //
  50
  51 //- Construct null
  52 inline Foam::VRWGraph::VRWGraph()
  53 :
  54     data_(),
  55     rows_()
  56 {}
  57
  58 //- Construct given size
  59 inline Foam::VRWGraph::VRWGraph
  60 (
  61     const label size
  62 )
  63 :
  64     data_(),
  65     rows_(size)
  66 {
  67     for(label rowI=0;rowI<size;++rowI)
  68     {
  69         rows_[rowI].start() = INVALIDROW;
  70         rows_[rowI].size() = NONE;
  71     }
  72 }
  73
  74 inline Foam::VRWGraph::VRWGraph
  75 (
  76     const label nRows,
  77     const label nColumnsInRow
  78 )
  79 :
  80     data_(nRows * nColumnsInRow),
  81     rows_(nRows)
  82 {
  83     for(label rowI=0;rowI<nRows;++rowI)
  84     {
  85         rows_[rowI].start() = rowI * nColumnsInRow;
  86         rows_[rowI].size() = nColumnsInRow;
  87     }
  88 }
  89
  90 inline Foam::VRWGraph::VRWGraph
  91 (
  92     const label nRows,
  93     const label nColumnsInRow,
  94     const label t
  95 )
  96 :
  97     data_(nRows * nColumnsInRow, t),
  98     rows_(nRows)
  99 {
 100     for(label rowI=0;rowI<nRows;++rowI)
 101     {
 102         rows_[rowI].start() = rowI * nColumnsInRow;
 103         rows_[rowI].size() = nColumnsInRow;
 104     }
 105 }
 106
 107 inline Foam::VRWGraph::VRWGraph
 108 (
 109     const VRWGraph& ol
 110 )
 111 :
 112     data_(ol.data_),
 113     rows_(ol.rows_)
 114 {}
 115
 116 inline Foam::VRWGraph::~VRWGraph()
 117 {}
 118
 119
 120 // * * * * * * * * * * * * * * * Member Functions  * * * * * * * * * * * * * //
 121
 122 inline Foam::label Foam::VRWGraph::size() const
 123 {
 124     return rows_.size();
 125 }
 126
 127 inline Foam::label Foam::VRWGraph::sizeOfRow(const label rowI) const
 128 {
 129     return rows_[rowI].size();
 130 }
 131
 132 inline void Foam::VRWGraph::setSize(const label size)
 133 {
 134     if( size > rows_.size() )
 135     {
 136         rowElement rowInfo(INVALIDROW, NONE);
 137
 138         for(label i=rows_.size();i<size;++i)
 139             rows_.append(rowInfo);
 140     }
 141     else
 142     {
 143         rows_.setSize(size);
 144     }
 145 }
 146
 147 void Foam::VRWGraph::setSizeAndColumnWidth
 148 (
 149     const label newNumRows,
 150     const label rcWidth
 151 )
 152 {
 153     if( rows_.size() != 0 )
 154         FatalErrorIn
 155         (
 156             "void Foam::VRWGraph::setSizeAndColumnWidth"
 157             "(const label size, const label rcWidth)"
 158         ) << "This function should be used for empty graphs, only!"
 159             << exit(FatalError);
 160
 161     data_.setSize(newNumRows * rcWidth);
 162     data_ = FREEENTRY;
 163
 164     rows_.setSize(newNumRows);
 165     label start(0);
 166
 167     for(label i=0;i<newNumRows;++i)
 168     {
 169         rows_[i].start() = start;
 170         rows_[i].size() = 0;
 171         data_[start] = FREESTART;
 172
 173         start += rcWidth;
 174     }
 175 }
 176
 177 template<class ListType>
 178 inline void Foam::VRWGraph::setSizeAndRowSize(const ListType& l)
 179 {
 180     //- set the size of graph rows
 181     const label nRows = l.size();
 182     rows_.setSize(nRows);
 183
 184     label start(0);
 185     for(label rowI=0;rowI<nRows;++rowI)
 186     {
 187         rows_[rowI].size() = l[rowI];
 188
 189         if( rows_[rowI].size() != NONE )
 190         {
 191             rows_[rowI].start() = start;
 192         }
 193         else
 194         {
 195             rows_[rowI].start() = INVALIDROW;
 196         }
 197
 198         start += rows_[rowI].size();
 199     }
 200
 201     data_.setSize(start);
 202 }
 203
 204 inline void Foam::VRWGraph::setRowSize(const label rowI, const label newSize)
 205 {
 206     # ifdef FULLDEBUG
 207     if( (rowI < 0) || (rowI >= rows_.size()) )
 208         FatalErrorIn
 209         (
 210             "void Foam::VRWGraph<T,width>::"
 211             "checkIndex(const label rowI, const label size) const"
 212         ) << "Row index " << Foam::label(rowI)
 213             << " is not in range " << Foam::label(0)
 214             << " and " << rows_.size() << abort(FatalError);
 215     # endif
 216
 217     const label start = rows_[rowI].start();
 218     if( start == INVALIDROW )
 219     {
 220         if( newSize > 0 )
 221         {
 222             rows_[rowI].start() = data_.size();
 223             for(label i=0;i<newSize;++i)
 224                 data_.append(NONE);
 225             rows_[rowI].size() = newSize;
 226         }
 227     }
 228     else if( newSize > rows_[rowI].size() )
 229     {
 230         //- check if there is some unused space after the last element
 231         bool foundUnused(true);
 232
 233         for(label i=rows_[rowI].size();i<newSize;++i)
 234         {
 235             const label j = start + i;
 236             if(
 237                 (j >= data_.size()) ||
 238                 (data_[j] != FREEENTRY) ||
 239                 (data_[j] == FREESTART)
 240             )
 241             {
 242                 foundUnused = false;
 243                 break;
 244             }
 245         }
 246
 247         if( foundUnused )
 248         {
 249             //- row can be extended without copying
 250             for(label i=rows_[rowI].size();i<newSize;++i)
 251                 data_[start+i] = NONE;
 252         }
 253         else
 254         {
 255             //- row is copied at the end of the data list
 256             rows_[rowI].start() = data_.size();
 257             for(label i=0;i<rows_[rowI].size();++i)
 258             {
 259                 data_.append(data_[start+i]);
 260                 data_[start+i] = FREEENTRY;
 261             }
 262             for(label i=rows_[rowI].size();i<newSize;++i)
 263                 data_.append(NONE);
 264         }
 265
 266         rows_[rowI].size() = newSize;
 267     }
 268     else if( newSize < rows_[rowI].size() )
 269     {
 270         for(label i=newSize;i<rows_[rowI].size();++i)
 271             data_[start+i] = FREEENTRY;
 272         rows_[rowI].size() = newSize;
 273         if( newSize == 0 )
 274             rows_[rowI].start() = INVALIDROW;
 275     }
 276 }
 277
 278 inline void Foam::VRWGraph::clear()
 279 {
 280     data_.setSize(0);
 281     rows_.setSize(0);
 282 }
 283
 284 template<class ListType>
 285 inline void Foam::VRWGraph::appendList
 286 (
 287     const ListType& l
 288 )
 289 {
 290     if( l.size() == 0 )
 291     {
 292         rows_.append(rowElement(INVALIDROW, 0));
 293         return;
 294     }
 295
 296     rowElement rowInfo(data_.size(), l.size());
 297     const label size = l.size();
 298     for(label elI=0;elI<size;++elI)
 299         data_.append(l[elI]);
 300     rows_.append(rowInfo);
 301 }
 302
 303 inline void Foam::VRWGraph::append(const label rowI, const label el)
 304 {
 305     rowElement& re = rows_[rowI];
 306
 307     if( re.start() == INVALIDROW )
 308     {
 309         re.start() = data_.size();
 310         re.size() = 1;
 311         data_.append(el);
 312     }
 313     else
 314     {
 315         const label oldStart = re.start();
 316         const label oldSize = re.size();
 317          ++re.size();
 318
 319         if( oldStart + oldSize < data_.size() )
 320         {
 321             if(
 322                 (data_[oldStart+oldSize] == FREEENTRY) ||
 323                 (data_[oldStart+oldSize] == FREESTART)
 324             )
 325             {
 326                 data_[oldStart + oldSize] = el;
 327             }
 328             else
 329             {
 330                 re.start() = data_.size();
 331                 for(label i=0;i<oldSize;++i)
 332                 {
 333                     data_.append(data_[oldStart+i]);
 334                     data_[oldStart+i] = FREEENTRY;
 335                 }
 336                 data_.append(el);
 337             }
 338         }
 339         else
 340         {
 341             data_.append(el);
 342         }
 343     }
 344 }
 345
 346 inline void Foam::VRWGraph::appendIfNotIn(const label rowI, const label el)
 347 {
 348     if( !contains(rowI, el) )
 349         append(rowI, el);
 350 }
 351
 352 template<class ListType>
 353 inline void Foam::VRWGraph::setRow
 354 (
 355     const label rowI,
 356     const ListType& l
 357 )
 358 {
 359     this->setRowSize(rowI, l.size());
 360     const label start = rows_[rowI].start();
 361     const label size = l.size();
 362     for(label elI=0;elI<size;++elI)
 363         data_[start+elI] = l[elI];
 364 }
 365
 366 inline void Foam::VRWGraph::mergeGraphs(const List<VRWGraph>& graphParts)
 367 {
 368     const label nGraphs = graphParts.size();
 369     const label nRows = graphParts[0].size();
 370     forAll(graphParts, i)
 371     {
 372         if( nRows != graphParts[i].size() )
 373             FatalErrorIn
 374             (
 375                 "inline void Foam::VRWGraph::mergeGraphs(const List<VRWGraph>&)"
 376             ) << "Cannot merge graphs" << abort(FatalError);
 377     }
 378
 379     //- find the number of elements in each row
 380     labelLongList nElmtsInRow(nRows);
 381     for(label rowI=0;rowI<nRows;++rowI)
 382     {
 383         label sum(0);
 384         for(label i=0;i<nGraphs;++i)
 385             sum += graphParts[i].sizeOfRow(rowI);
 386
 387         nElmtsInRow[rowI] = sum;
 388     }
 389
 390     setSizeAndRowSize(nElmtsInRow);
 391
 392     //- Finally, assemble the merged graph
 393     for(label rowI=0;rowI<nRows;++rowI)
 394     {
 395         forAll(graphParts, i)
 396         {
 397             const VRWGraph& gp = graphParts[i];
 398             for(label j=0;j<gp.sizeOfRow(rowI);++j)
 399                 this->operator()(rowI, --nElmtsInRow[rowI]) = gp(rowI, j);
 400         }
 401     }
 402 }
 403
 404 template<class GraphType>
 405 inline void Foam::VRWGraph::reverseAddressing
 406 (
 407     const label nRows,
 408     const GraphType& origGraph
 409 )
 410 {
 411     const label origSize = origGraph.size();
 412     labelLongList nElmtsInRow(nRows);
 413
 414     for(label rowI=0;rowI<nRows;++rowI)
 415         nElmtsInRow[rowI] = 0;
 416
 417     for(label rowI=0;rowI<origSize;++rowI)
 418     {
 419         const label rowSize = origGraph[rowI].size();
 420
 421         for(label i=0;i<rowSize;++i)
 422             ++nElmtsInRow[origGraph[rowI][i]];
 423     }
 424
 425     setSizeAndRowSize(nElmtsInRow);
 426     nElmtsInRow = 0;
 427
 428     //- finally fill in the data
 429     for(label rowI=0;rowI<origSize;++rowI)
 430     {
 431         const label rowSize = origGraph[rowI].size();
 432
 433         for(label i=0;i<rowSize;++i)
 434         {
 435             const label el = origGraph[rowI][i];
 436             this->operator()(el, nElmtsInRow[el]++) = rowI;
 437         }
 438     }
 439 }
 440
 441 template<class GraphType>
 442 inline void Foam::VRWGraph::reverseAddressing(const GraphType& origGraph)
 443 {
 444     const label size = origGraph.size();
 445     label maxValue(-1);
 446
 447     for(label rowI=0;rowI<size;++rowI)
 448     {
 449         const label rowSize = origGraph[rowI].size();
 450         for(label i=0;i<rowSize;++i)
 451             maxValue = Foam::max(maxValue, origGraph[rowI][i]);
 452     }
 453
 454     ++maxValue;
 455     reverseAddressing(maxValue, origGraph);
 456 }
 457
 458 inline void Foam::VRWGraph::reverseAddressing
 459 (
 460     const label nRows,
 461     const VRWGraph& origGraph
 462 )
 463 {
 464     const label origSize = origGraph.size();
 465     labelLongList nElmtsInRow(nRows);
 466
 467     for(label rowI=0;rowI<nRows;++rowI)
 468         nElmtsInRow[rowI] = 0;
 469
 470     for(label rowI=0;rowI<origSize;++rowI)
 471     {
 472         const label rowSize = origGraph.sizeOfRow(rowI);
 473
 474         for(label i=0;i<rowSize;++i)
 475             ++nElmtsInRow[origGraph(rowI, i)];
 476     }
 477
 478     setSizeAndRowSize(nElmtsInRow);
 479     nElmtsInRow = 0;
 480
 481     //- finally fill in the data
 482     for(label rowI=0;rowI<origSize;++rowI)
 483     {
 484         const label rowSize = origGraph.sizeOfRow(rowI);
 485
 486         for(label i=0;i<rowSize;++i)
 487         {
 488             const label el = origGraph(rowI, i);
 489             this->operator()(el, nElmtsInRow[el]++) = rowI;
 490         }
 491     }
 492 }
 493
 494 inline void Foam::VRWGraph::reverseAddressing(const VRWGraph& origGraph)
 495 {
 496     const label size = origGraph.size();
 497     label maxValue(-1);
 498
 499     for(label rowI=0;rowI<size;++rowI)
 500     {
 501         const label rowSize = origGraph.sizeOfRow(rowI);
 502         for(label i=0;i<rowSize;++i)
 503             maxValue = Foam::max(maxValue, origGraph(rowI, i));
 504     }
 505
 506     ++maxValue;
 507     reverseAddressing(maxValue, origGraph);
 508 }
 509
 510 inline bool Foam::VRWGraph::contains
 511 (
 512     const label rowI,
 513     const label e
 514 ) const
 515 {
 516     const label start = rows_[rowI].start();
 517     if( start == INVALIDROW )
 518         return false;
 519     const label size = rows_[rowI].size();
 520
 521     for(register label i=0;i<size;++i)
 522         if( data_[start+i] == e )
 523             return true;
 524
 525     return false;
 526 }
 527
 528 inline Foam::label Foam::VRWGraph::containsAtPosition
 529 (
 530     const label rowI,
 531     const label e
 532 ) const
 533 {
 534     const label start = rows_[rowI].start();
 535     if( start == INVALIDROW )
 536         return -1;
 537
 538     const label size = rows_[rowI].size();
 539     for(register label i=0;i<size;++i)
 540         if( data_[start+i] == e )
 541             return i;
 542
 543     return -1;
 544 }
 545
 546 // * * * * * * * * * * * * * * * Member Operators  * * * * * * * * * * * * * //
 547
 548 inline Foam::label Foam::VRWGraph::operator()
 549 (
 550     const label i,
 551     const label j
 552 ) const
 553 {
 554     #ifdef FULLDEBUG
 555     checkIndex(i, j);
 556     #endif
 557
 558     return data_[rows_[i].start() + j];
 559 }
 560
 561
 562 inline Foam::label& Foam::VRWGraph::operator()
 563 (
 564     const label i, const label j
 565 )
 566 {
 567     #ifdef FULLDEBUG
 568     checkIndex(i, j);
 569     #endif
 570
 571     return data_[rows_[i].start() + j];
 572 }
 573
 574 inline Foam::constRow Foam::VRWGraph::operator[](const label i) const
 575 {
 576     return constRow(*this, i);
 577 }
 578
 579 inline Foam::row Foam::VRWGraph::operator[](const label i)
 580 {
 581     return row(*this, i);
 582 }
 583
 584 inline void Foam::VRWGraph::operator=
 585 (
 586     const VRWGraph& l
 587 )
 588 {
 589     data_ = l.data_;
 590     rows_ = l.rows_;
 591 }
 592
 593
 594 // ************************************************************************* //