src/OpenFOAM/containers/Lists/ListOps/ListOpsTemplates.C

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   4    \\    /   O peration     |
   5     \\  /    A nd           | Copyright (C) 2011 OpenFOAM Foundation
   6      \\/     M anipulation  |
   7 -------------------------------------------------------------------------------
   8 License
   9     This file is part of OpenFOAM.
  10
  11     OpenFOAM is free software: you can redistribute it and/or modify it
  12     under the terms of the GNU General Public License as published by
  13     the Free Software Foundation, either version 3 of the License, or
  14     (at your option) any later version.
  15
  16     OpenFOAM 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 OpenFOAM.  If not, see <http://www.gnu.org/licenses/>.
  23
  24 \*---------------------------------------------------------------------------*/
  25
  26 #include "ListOps.H"
  27
  28 // * * * * * * * * * * * * * * * Global Functions  * * * * * * * * * * * * * //
  29
  30 template<class ListType>
  31 ListType Foam::renumber
  32 (
  33     const labelUList& oldToNew,
  34     const ListType& lst
  35 )
  36 {
  37     // Create copy
  38     ListType newLst(lst.size());
  39
  40     // ensure consistent addressable size (eg, DynamicList)
  41     newLst.setSize(lst.size());
  42
  43     forAll(lst, elemI)
  44     {
  45         if (lst[elemI] >= 0)
  46         {
  47             newLst[elemI] = oldToNew[lst[elemI]];
  48         }
  49     }
  50
  51     return newLst;
  52 }
  53
  54
  55 template<class ListType>
  56 void Foam::inplaceRenumber
  57 (
  58     const labelUList& oldToNew,
  59     ListType& lst
  60 )
  61 {
  62     forAll(lst, elemI)
  63     {
  64         if (lst[elemI] >= 0)
  65         {
  66             lst[elemI] = oldToNew[lst[elemI]];
  67         }
  68     }
  69 }
  70
  71
  72 template<class ListType>
  73 ListType Foam::reorder
  74 (
  75     const labelUList& oldToNew,
  76     const ListType& lst
  77 )
  78 {
  79     // Create copy
  80     ListType newLst(lst.size());
  81
  82     // ensure consistent addressable size (eg, DynamicList)
  83     newLst.setSize(lst.size());
  84
  85     forAll(lst, elemI)
  86     {
  87         if (oldToNew[elemI] >= 0)
  88         {
  89             newLst[oldToNew[elemI]] = lst[elemI];
  90         }
  91         else
  92         {
  93             newLst[elemI] = lst[elemI];
  94         }
  95     }
  96     return newLst;
  97 }
  98
  99
 100 template<class ListType>
 101 void Foam::inplaceReorder
 102 (
 103     const labelUList& oldToNew,
 104     ListType& lst
 105 )
 106 {
 107     // Create copy
 108     ListType newLst(lst.size());
 109
 110     // ensure consistent addressable size (eg, DynamicList)
 111     newLst.setSize(lst.size());
 112
 113     forAll(lst, elemI)
 114     {
 115         if (oldToNew[elemI] >= 0)
 116         {
 117             newLst[oldToNew[elemI]] = lst[elemI];
 118         }
 119         else
 120         {
 121             newLst[elemI] = lst[elemI];
 122         }
 123     }
 124
 125     lst.transfer(newLst);
 126 }
 127
 128
 129 template<class Container>
 130 void Foam::inplaceMapValue
 131 (
 132     const labelUList& oldToNew,
 133     Container& lst
 134 )
 135 {
 136     for
 137     (
 138         typename Container::iterator iter = lst.begin();
 139         iter != lst.end();
 140         ++iter
 141     )
 142     {
 143         if (iter() >= 0)
 144         {
 145             iter() = oldToNew[iter()];
 146         }
 147     }
 148 }
 149
 150
 151 template<class Container>
 152 void Foam::inplaceMapKey
 153 (
 154     const labelUList& oldToNew,
 155     Container& lst
 156 )
 157 {
 158     Container newLst(lst.size());
 159
 160     for
 161     (
 162         typename Container::iterator iter = lst.begin();
 163         iter != lst.end();
 164         ++iter
 165     )
 166     {
 167         if (iter.key() >= 0)
 168         {
 169             newLst.insert(oldToNew[iter.key()], iter());
 170         }
 171     }
 172
 173     lst.transfer(newLst);
 174 }
 175
 176
 177 template<class T>
 178 void Foam::sortedOrder
 179 (
 180     const UList<T>& lst,
 181     labelList& order
 182 )
 183 {
 184     // list lengths must be identical
 185     if (order.size() != lst.size())
 186     {
 187         // avoid copying any elements, they are overwritten anyhow
 188         order.clear();
 189         order.setSize(lst.size());
 190     }
 191
 192     forAll(order, elemI)
 193     {
 194         order[elemI] = elemI;
 195     }
 196     Foam::stableSort(order, typename UList<T>::less(lst));
 197 }
 198
 199
 200 template<class T>
 201 void Foam::duplicateOrder
 202 (
 203     const UList<T>& lst,
 204     labelList& order
 205 )
 206 {
 207     if (lst.size() < 2)
 208     {
 209         order.clear();
 210         return;
 211     }
 212
 213     sortedOrder(lst, order);
 214
 215     label n = 0;
 216     for (label i = 0; i < order.size() - 1; ++i)
 217     {
 218         if (lst[order[i]] == lst[order[i+1]])
 219         {
 220             order[n++] = order[i];
 221         }
 222     }
 223     order.setSize(n);
 224 }
 225
 226
 227 template<class T>
 228 void Foam::uniqueOrder
 229 (
 230     const UList<T>& lst,
 231     labelList& order
 232 )
 233 {
 234     sortedOrder(lst, order);
 235
 236     if (order.size() > 1)
 237     {
 238         label n = 0;
 239         for (label i = 0; i < order.size() - 1; ++i)
 240         {
 241             if (lst[order[i]] != lst[order[i+1]])
 242             {
 243                 order[n++] = order[i];
 244             }
 245         }
 246         order[n++] = order[order.size()-1];
 247         order.setSize(n);
 248     }
 249 }
 250
 251
 252 template<class T, class ListType>
 253 ListType Foam::subset
 254 (
 255     const UList<T>& select,
 256     const T& value,
 257     const ListType& lst
 258 )
 259 {
 260     // select must at least cover the list range
 261     if (select.size() < lst.size())
 262     {
 263         FatalErrorIn("subset(const UList<T>&, const T&, const ListType&)")
 264             << "select is of size " << select.size()
 265             << "; but it must index a list of size " << lst.size()
 266             << abort(FatalError);
 267     }
 268
 269     ListType newLst(lst.size());
 270
 271     // ensure consistent addressable size (eg, DynamicList)
 272     newLst.setSize(lst.size());
 273
 274     label nElem = 0;
 275     forAll(lst, elemI)
 276     {
 277         if (select[elemI] == value)
 278         {
 279             newLst[nElem++] = lst[elemI];
 280         }
 281     }
 282     newLst.setSize(nElem);
 283
 284     return newLst;
 285 }
 286
 287
 288 template<class T, class ListType>
 289 void Foam::inplaceSubset
 290 (
 291     const UList<T>& select,
 292     const T& value,
 293     ListType& lst
 294 )
 295 {
 296     // select must at least cover the list range
 297     if (select.size() < lst.size())
 298     {
 299         FatalErrorIn("inplaceSubset(const UList<T>&, const T&, ListType&)")
 300             << "select is of size " << select.size()
 301             << "; but it must index a list of size " << lst.size()
 302             << abort(FatalError);
 303     }
 304
 305     label nElem = 0;
 306     forAll(lst, elemI)
 307     {
 308         if (select[elemI] == value)
 309         {
 310             if (nElem != elemI)
 311             {
 312                 lst[nElem] = lst[elemI];
 313             }
 314             ++nElem;
 315         }
 316     }
 317
 318     lst.setSize(nElem);
 319 }
 320
 321
 322 template<class BoolListType, class ListType>
 323 ListType Foam::subset
 324 (
 325     const BoolListType& select,
 326     const ListType& lst
 327 )
 328 {
 329     // select can have a different size
 330     // eg, when it is a PackedBoolList or a labelHashSet
 331
 332     ListType newLst(lst.size());
 333
 334     // ensure consistent addressable size (eg, DynamicList)
 335     newLst.setSize(lst.size());
 336
 337     label nElem = 0;
 338     forAll(lst, elemI)
 339     {
 340         if (select[elemI])
 341         {
 342             newLst[nElem++] = lst[elemI];
 343         }
 344     }
 345     newLst.setSize(nElem);
 346
 347     return newLst;
 348 }
 349
 350
 351 template<class BoolListType, class ListType>
 352 void Foam::inplaceSubset
 353 (
 354     const BoolListType& select,
 355     ListType& lst
 356 )
 357 {
 358     // select can have a different size
 359     // eg, when it is a PackedBoolList or a labelHashSet
 360
 361     label nElem = 0;
 362     forAll(lst, elemI)
 363     {
 364         if (select[elemI])
 365         {
 366             if (nElem != elemI)
 367             {
 368                 lst[nElem] = lst[elemI];
 369             }
 370             ++nElem;
 371         }
 372     }
 373
 374     lst.setSize(nElem);
 375 }
 376
 377
 378 // As clarification:
 379 // coded as inversion from pointEdges to edges but completely general.
 380 template<class InList, class OutList>
 381 void Foam::invertManyToMany
 382 (
 383     const label nEdges,
 384     const UList<InList>& pointEdges,
 385     List<OutList>& edges
 386 )
 387 {
 388     // Number of points per edge
 389     labelList nPointsPerEdge(nEdges, 0);
 390
 391     forAll(pointEdges, pointI)
 392     {
 393         const InList& pEdges = pointEdges[pointI];
 394
 395         forAll(pEdges, j)
 396         {
 397             nPointsPerEdge[pEdges[j]]++;
 398         }
 399     }
 400
 401     // Size edges
 402     edges.setSize(nEdges);
 403
 404     forAll(nPointsPerEdge, edgeI)
 405     {
 406         edges[edgeI].setSize(nPointsPerEdge[edgeI]);
 407     }
 408     nPointsPerEdge = 0;
 409
 410     // Fill edges
 411     forAll(pointEdges, pointI)
 412     {
 413         const InList& pEdges = pointEdges[pointI];
 414
 415         forAll(pEdges, j)
 416         {
 417             label edgeI = pEdges[j];
 418
 419             edges[edgeI][nPointsPerEdge[edgeI]++] = pointI;
 420         }
 421     }
 422 }
 423
 424
 425 template<class ListType>
 426 Foam::label Foam::findIndex
 427 (
 428     const ListType& l,
 429     typename ListType::const_reference t,
 430     const label start
 431 )
 432 {
 433     label index = -1;
 434
 435     for (label i = start; i < l.size(); i++)
 436     {
 437         if (l[i] == t)
 438         {
 439             index = i;
 440             break;
 441         }
 442     }
 443
 444     return index;
 445 }
 446
 447
 448 template<class ListType>
 449 Foam::labelList Foam::findIndices
 450 (
 451     const ListType& l,
 452     typename ListType::const_reference t,
 453     const label start
 454 )
 455 {
 456     // Count occurrences
 457     label n = 0;
 458
 459     for (label i = start; i < l.size(); i++)
 460     {
 461         if (l[i] == t)
 462         {
 463             n++;
 464         }
 465     }
 466
 467     // Create and fill
 468     labelList indices(n);
 469     n = 0;
 470
 471     for (label i = start; i < l.size(); i++)
 472     {
 473         if (l[i] == t)
 474         {
 475             indices[n++] = i;
 476         }
 477     }
 478
 479     return indices;
 480 }
 481
 482
 483 template<class ListType>
 484 void Foam::setValues
 485 (
 486     ListType& l,
 487     const labelUList& indices,
 488     typename ListType::const_reference t
 489 )
 490 {
 491     forAll(indices, i)
 492     {
 493         l[indices[i]] = t;
 494     }
 495 }
 496
 497
 498 template<class ListType>
 499 ListType Foam::createWithValues
 500 (
 501     const label sz,
 502     const typename ListType::const_reference initValue,
 503     const labelUList& indices,
 504     typename ListType::const_reference setValue
 505 )
 506 {
 507     ListType l(sz, initValue);
 508     setValues(l, indices, setValue);
 509     return l;
 510 }
 511
 512
 513 template<class ListType>
 514 Foam::label Foam::findMax(const ListType& l, const label start)
 515 {
 516     if (start >= l.size())
 517     {
 518         return -1;
 519     }
 520
 521     label index = start;
 522
 523     for (label i = start+1; i < l.size(); i++)
 524     {
 525         if (l[i] > l[index])
 526         {
 527             index = i;
 528         }
 529     }
 530
 531     return index;
 532 }
 533
 534
 535 template<class ListType>
 536 Foam::label Foam::findMin(const ListType& l, const label start)
 537 {
 538     if (start >= l.size())
 539     {
 540         return -1;
 541     }
 542
 543     label index = start;
 544
 545     for (label i = start+1; i < l.size(); i++)
 546     {
 547         if (l[i] < l[index])
 548         {
 549             index = i;
 550         }
 551     }
 552
 553     return index;
 554 }
 555
 556
 557 template<class ListType>
 558 Foam::label Foam::findSortedIndex
 559 (
 560     const ListType& l,
 561     typename ListType::const_reference t,
 562     const label start
 563 )
 564 {
 565     if (start >= l.size())
 566     {
 567         return -1;
 568     }
 569
 570     label low = start;
 571     label high = l.size() - 1;
 572
 573     while (low <= high)
 574     {
 575         label mid = (low + high)/2;
 576
 577         if (t < l[mid])
 578         {
 579             high = mid - 1;
 580         }
 581         else if (t > l[mid])
 582         {
 583             low = mid + 1;
 584         }
 585         else
 586         {
 587             return mid;
 588         }
 589     }
 590
 591     return -1;
 592 }
 593
 594
 595 template<class ListType>
 596 Foam::label Foam::findLower
 597 (
 598     const ListType& l,
 599     typename ListType::const_reference t,
 600     const label start
 601 )
 602 {
 603     if (start >= l.size())
 604     {
 605         return -1;
 606     }
 607
 608     label low = start;
 609     label high = l.size() - 1;
 610
 611     while ((high - low) > 1)
 612     {
 613         label mid = (low + high)/2;
 614
 615         if (l[mid] < t)
 616         {
 617             low = mid;
 618         }
 619         else
 620         {
 621             high = mid;
 622         }
 623     }
 624
 625     if (l[high] < t)
 626     {
 627         return high;
 628     }
 629     else
 630     {
 631         if (l[low] < t)
 632         {
 633             return low;
 634         }
 635         else
 636         {
 637             return -1;
 638         }
 639     }
 640 }
 641
 642
 643 template<class Container, class T, int nRows>
 644 Foam::List<Container> Foam::initList(const T elems[nRows])
 645 {
 646     List<Container> lst(nRows);
 647
 648     forAll(lst, rowI)
 649     {
 650         lst[rowI] = Container(elems[rowI]);
 651     }
 652     return lst;
 653 }
 654
 655
 656 template<class Container, class T, int nRows, int nColumns>
 657 Foam::List<Container> Foam::initListList(const T elems[nRows][nColumns])
 658 {
 659     List<Container> lst(nRows);
 660
 661     Container cols(nColumns);
 662     forAll(lst, rowI)
 663     {
 664         forAll(cols, colI)
 665         {
 666             cols[colI] = elems[rowI][colI];
 667         }
 668         lst[rowI] = cols;
 669     }
 670     return lst;
 671 }
 672
 673
 674 // ************************************************************************* //