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