ListOpsTemplates.C
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration | Website: https://openfoam.org
5  \\ / A nd | Copyright (C) 2011-2021 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(const labelUList& oldToNew, const ListType& lst)
32 {
33  ListType newLst;
34 
35  renumber(oldToNew, lst, newLst);
36 
37  return newLst;
38 }
39 
40 
41 template<class ListType>
42 void Foam::renumber
43 (
44  const labelUList& oldToNew,
45  const ListType& lst,
46  ListType& newLst
47 )
48 {
49  newLst.setSize(lst.size());
50 
51  forAll(lst, elemI)
52  {
53  renumber(oldToNew, lst[elemI], newLst[elemI]);
54  }
55 }
56 
57 
58 inline void Foam::renumber
59 (
60  const labelUList& oldToNew,
61  const label lst,
62  label& newLst
63 )
64 {
65  if (lst >= 0)
66  {
67  newLst = oldToNew[lst];
68  }
69 }
70 
71 
72 template<class ListType>
73 void Foam::inplaceRenumber(const labelUList& oldToNew, ListType& lst)
74 {
75  forAll(lst, elemI)
76  {
77  inplaceRenumber(oldToNew, lst[elemI]);
78  }
79 }
80 
81 
82 inline void Foam::inplaceRenumber(const labelUList& oldToNew, label& lst)
83 {
84  if (lst >= 0)
85  {
86  lst = oldToNew[lst];
87  }
88 }
89 
90 
91 template<class ListType>
92 ListType Foam::reorder
93 (
94  const labelUList& oldToNew,
95  const ListType& lst
96 )
97 {
98  // Create copy
99  ListType newLst(lst.size());
100 
101  // ensure consistent addressable size (eg, DynamicList)
102  newLst.setSize(lst.size());
103 
104  forAll(lst, elemI)
105  {
106  if (oldToNew[elemI] >= 0)
107  {
108  newLst[oldToNew[elemI]] = lst[elemI];
109  }
110  else
111  {
112  newLst[elemI] = lst[elemI];
113  }
114  }
115  return newLst;
116 }
117 
118 
119 template<class ListType>
121 (
122  const labelUList& oldToNew,
123  ListType& lst
124 )
125 {
126  // Create copy
127  ListType newLst(lst.size());
128 
129  // ensure consistent addressable size (eg, DynamicList)
130  newLst.setSize(lst.size());
131 
132  forAll(lst, elemI)
133  {
134  if (oldToNew[elemI] >= 0)
135  {
136  newLst[oldToNew[elemI]] = lst[elemI];
137  }
138  else
139  {
140  newLst[elemI] = lst[elemI];
141  }
142  }
143 
144  lst.transfer(newLst);
145 }
146 
147 
148 template<class Container>
150 (
151  const labelUList& oldToNew,
152  Container& lst
153 )
154 {
155  for
156  (
157  typename Container::iterator iter = lst.begin();
158  iter != lst.end();
159  ++iter
160  )
161  {
162  if (*iter >= 0)
163  {
164  *iter = oldToNew[*iter];
165  }
166  }
167 }
168 
169 
170 template<class Container>
172 (
173  const labelUList& oldToNew,
174  Container& lst
175 )
176 {
177  Container newLst(lst.size());
178 
179  for
180  (
181  typename Container::iterator iter = lst.begin();
182  iter != lst.end();
183  ++iter
184  )
185  {
186  if (iter.key() >= 0)
187  {
188  newLst.insert(oldToNew[iter.key()], iter());
189  }
190  }
191 
192  lst.transfer(newLst);
193 }
194 
195 
196 template<class T>
198 (
199  const UList<T>& lst,
200  labelList& order
201 )
202 {
203  sortedOrder(lst, order, typename UList<T>::less(lst));
204 }
205 
206 
207 template<class T, class Cmp>
209 (
210  const UList<T>& lst,
211  labelList& order,
212  const Cmp& cmp
213 )
214 {
215  // list lengths must be identical
216  if (order.size() != lst.size())
217  {
218  // avoid copying any elements, they are overwritten anyhow
219  order.clear();
220  order.setSize(lst.size());
221  }
222 
223  forAll(order, elemI)
224  {
225  order[elemI] = elemI;
226  }
227  Foam::stableSort(order, cmp);
228 }
229 
230 
231 template<class T>
233 (
234  const UList<T>& lst,
235  labelList& order
236 )
237 {
238  duplicateOrder(lst, order, typename UList<T>::less(lst));
239 }
240 
241 
242 template<class T, class Cmp>
244 (
245  const UList<T>& lst,
246  labelList& order,
247  const Cmp& cmp
248 )
249 {
250  if (lst.size() < 2)
251  {
252  order.clear();
253  return;
254  }
255 
256  sortedOrder(lst, order, cmp);
257 
258  label n = 0;
259  for (label i = 0; i < order.size() - 1; ++i)
260  {
261  if (lst[order[i]] == lst[order[i+1]])
262  {
263  order[n++] = order[i];
264  }
265  }
266  order.setSize(n);
267 }
268 
269 
270 template<class T>
272 (
273  const UList<T>& lst,
274  labelList& order
275 )
276 {
277  uniqueOrder(lst, order, typename UList<T>::less(lst));
278 }
279 
280 
281 template<class T, class Cmp>
283 (
284  const UList<T>& lst,
285  labelList& order,
286  const Cmp& cmp
287 )
288 {
289  sortedOrder(lst, order, cmp);
290 
291  if (order.size() > 1)
292  {
293  label n = 0;
294  for (label i = 0; i < order.size() - 1; ++i)
295  {
296  if (lst[order[i]] != lst[order[i+1]])
297  {
298  order[n++] = order[i];
299  }
300  }
301  order[n++] = order[order.size()-1];
302  order.setSize(n);
303  }
304 }
305 
306 
307 template<class T, class ListType>
308 ListType Foam::subset
309 (
310  const UList<T>& select,
311  const T& value,
312  const ListType& lst
313 )
314 {
315  // select must at least cover the list range
316  if (select.size() < lst.size())
317  {
319  << "select is of size " << select.size()
320  << "; but it must index a list of size " << lst.size()
321  << abort(FatalError);
322  }
323 
324  ListType newLst(lst.size());
325 
326  // ensure consistent addressable size (eg, DynamicList)
327  newLst.setSize(lst.size());
328 
329  label nElem = 0;
330  forAll(lst, elemI)
331  {
332  if (select[elemI] == value)
333  {
334  newLst[nElem++] = lst[elemI];
335  }
336  }
337  newLst.setSize(nElem);
338 
339  return newLst;
340 }
341 
342 
343 template<class T, class ListType>
345 (
346  const UList<T>& select,
347  const T& value,
348  ListType& lst
349 )
350 {
351  // select must at least cover the list range
352  if (select.size() < lst.size())
353  {
355  << "select is of size " << select.size()
356  << "; but it must index a list of size " << lst.size()
357  << abort(FatalError);
358  }
359 
360  label nElem = 0;
361  forAll(lst, elemI)
362  {
363  if (select[elemI] == value)
364  {
365  if (nElem != elemI)
366  {
367  lst[nElem] = lst[elemI];
368  }
369  ++nElem;
370  }
371  }
372 
373  lst.setSize(nElem);
374 }
375 
376 
377 template<class BoolListType, class ListType>
378 ListType Foam::subset
379 (
380  const BoolListType& select,
381  const ListType& lst
382 )
383 {
384  // select can have a different size
385  // eg, when it is a PackedBoolList or a labelHashSet
386 
387  ListType newLst(lst.size());
388 
389  // ensure consistent addressable size (eg, DynamicList)
390  newLst.setSize(lst.size());
391 
392  label nElem = 0;
393  forAll(lst, elemI)
394  {
395  if (select[elemI])
396  {
397  newLst[nElem++] = lst[elemI];
398  }
399  }
400  newLst.setSize(nElem);
401 
402  return newLst;
403 }
404 
405 
406 template<class BoolListType, class ListType>
408 (
409  const BoolListType& select,
410  ListType& lst
411 )
412 {
413  // select can have a different size
414  // eg, when it is a PackedBoolList or a labelHashSet
415 
416  label nElem = 0;
417  forAll(lst, elemI)
418  {
419  if (select[elemI])
420  {
421  if (nElem != elemI)
422  {
423  lst[nElem] = lst[elemI];
424  }
425  ++nElem;
426  }
427  }
428 
429  lst.setSize(nElem);
430 }
431 
432 
433 template<class InList, class OutList>
435 (
436  const label nEdges,
437  const UList<InList>& pointEdges,
438  List<OutList>& edges
439 )
440 {
441  // Number of points per edge
442  labelList nPointsPerEdge(nEdges, 0);
443 
444  forAll(pointEdges, pointi)
445  {
446  const InList& pEdges = pointEdges[pointi];
447 
448  forAll(pEdges, j)
449  {
450  nPointsPerEdge[pEdges[j]]++;
451  }
452  }
453 
454  // Size edges
455  edges.setSize(nEdges);
456 
457  forAll(nPointsPerEdge, edgeI)
458  {
459  edges[edgeI].setSize(nPointsPerEdge[edgeI]);
460  }
461  nPointsPerEdge = 0;
462 
463  // Fill edges
464  forAll(pointEdges, pointi)
465  {
466  const InList& pEdges = pointEdges[pointi];
467 
468  forAll(pEdges, j)
469  {
470  label edgeI = pEdges[j];
471 
472  edges[edgeI][nPointsPerEdge[edgeI]++] = pointi;
473  }
474  }
475 }
476 
477 
478 template<class ListType>
480 (
481  const ListType& l,
482  typename ListType::const_reference x
483 )
484 {
485  label result = 0;
486  forAll(l, i)
487  {
488  if (l[i] == x)
489  {
490  ++ result;
491  }
492  }
493  return result;
494 }
495 
496 
497 template<class ListType>
499 (
500  const ListType& l,
501  typename ListType::const_reference t,
502  const label start
503 )
504 {
505  label index = -1;
506 
507  for (label i = start; i < l.size(); i++)
508  {
509  if (l[i] == t)
510  {
511  index = i;
512  break;
513  }
514  }
515 
516  return index;
517 }
518 
519 
520 template<class ListType>
522 (
523  const ListType& l,
524  typename ListType::const_reference t,
525  const label start
526 )
527 {
528  // Count occurrences
529  label n = 0;
530 
531  for (label i = start; i < l.size(); i++)
532  {
533  if (l[i] == t)
534  {
535  n++;
536  }
537  }
538 
539  // Create and fill
540  labelList indices(n);
541  n = 0;
542 
543  for (label i = start; i < l.size(); i++)
544  {
545  if (l[i] == t)
546  {
547  indices[n++] = i;
548  }
549  }
550 
551  return indices;
552 }
553 
554 
555 template<class ListType>
556 void Foam::setValues
557 (
558  ListType& l,
559  const labelUList& indices,
560  typename ListType::const_reference t
561 )
562 {
563  forAll(indices, i)
564  {
565  l[indices[i]] = t;
566  }
567 }
568 
569 
570 template<class ListType>
571 ListType Foam::createWithValues
572 (
573  const label sz,
574  const typename ListType::const_reference initValue,
575  const labelUList& indices,
576  typename ListType::const_reference setValue
577 )
578 {
579  ListType l(sz, initValue);
580  setValues(l, indices, setValue);
581  return l;
582 }
583 
584 
585 template<class ListType>
586 Foam::label Foam::findMax(const ListType& l, const label start)
587 {
588  if (start >= l.size())
589  {
590  return -1;
591  }
592 
593  label index = start;
594 
595  for (label i = start+1; i < l.size(); i++)
596  {
597  if (l[i] > l[index])
598  {
599  index = i;
600  }
601  }
602 
603  return index;
604 }
605 
606 
607 template<class ListType>
608 Foam::label Foam::findMin(const ListType& l, const label start)
609 {
610  if (start >= l.size())
611  {
612  return -1;
613  }
614 
615  label index = start;
616 
617  for (label i = start+1; i < l.size(); i++)
618  {
619  if (l[i] < l[index])
620  {
621  index = i;
622  }
623  }
624 
625  return index;
626 }
627 
628 
629 template<class ListType>
631 (
632  const ListType& l,
633  typename ListType::const_reference t,
634  const label start
635 )
636 {
637  if (start >= l.size())
638  {
639  return -1;
640  }
641 
642  label low = start;
643  label high = l.size() - 1;
644 
645  while (low <= high)
646  {
647  label mid = (low + high)/2;
648 
649  if (t < l[mid])
650  {
651  high = mid - 1;
652  }
653  else if (t > l[mid])
654  {
655  low = mid + 1;
656  }
657  else
658  {
659  return mid;
660  }
661  }
662 
663  return -1;
664 }
665 
666 
667 template<class ListType, class BinaryOp>
669 (
670  const ListType& l,
671  typename ListType::const_reference t,
672  const label start,
673  const BinaryOp& bop
674 )
675 {
676  if (start >= l.size())
677  {
678  return -1;
679  }
680 
681  label low = start;
682  label high = l.size() - 1;
683 
684  while ((high - low) > 1)
685  {
686  label mid = (low + high)/2;
687 
688  if (bop(l[mid], t))
689  {
690  low = mid;
691  }
692  else
693  {
694  high = mid;
695  }
696  }
697 
698  if (bop(l[high], t))
699  {
700  return high;
701  }
702  else
703  {
704  if (bop(l[low], t))
705  {
706  return low;
707  }
708  else
709  {
710  return -1;
711  }
712  }
713 }
714 
715 
716 template<class ListType>
718 (
719  const ListType& l,
720  typename ListType::const_reference t,
721  const label start
722 )
723 {
724  return findLower(l, t, start, lessOp<typename ListType::value_type>());
725 }
726 
727 
728 template<class Container, class T, int mRows>
729 Foam::List<Container> Foam::initList(const T elems[mRows])
730 {
731  List<Container> lst(mRows);
732 
733  forAll(lst, rowI)
734  {
735  lst[rowI] = Container(elems[rowI]);
736  }
737  return lst;
738 }
739 
740 
741 template<class Container, class T, int mRows, int nColumns>
742 Foam::List<Container> Foam::initListList(const T elems[mRows][nColumns])
743 {
744  List<Container> lst(mRows);
745 
746  Container cols(nColumns);
747  forAll(lst, rowI)
748  {
749  forAll(cols, colI)
750  {
751  cols[colI] = elems[rowI][colI];
752  }
753  lst[rowI] = cols;
754  }
755  return lst;
756 }
757 
758 
759 template<class T>
761 {
762  if (y.size())
763  {
764  if (x.size())
765  {
766  label sz = x.size();
767  x.setSize(sz + y.size());
768  forAll(y, i)
769  {
770  x[sz++] = y[i];
771  }
772  }
773  else
774  {
775  x = y;
776  }
777  }
778 }
779 
780 
781 template<class ListType>
782 ListType Foam::reverseList(const ListType& list)
783 {
784  const label listSize = list.size();
785  const label lastIndex = listSize - 1;
786 
787  ListType tmpList(listSize);
788 
789  forAll(tmpList, elemI)
790  {
791  tmpList[elemI] = list[lastIndex - elemI];
792  }
793 
794  return tmpList;
795 }
796 
797 
798 template<class ListType>
799 void Foam::inplaceReverseList(ListType& list)
800 {
801  const label listSize = list.size();
802  const label lastIndex = listSize - 1;
803  const label nIterations = listSize >> 1;
804 
805  label elemI = 0;
806  while (elemI < nIterations)
807  {
808  Swap(list[elemI], list[lastIndex - elemI]);
809 
810  elemI++;
811  }
812 }
813 
814 
815 template<class ListType>
816 ListType Foam::rotateList(const ListType& list, const label n)
817 {
818  const label listSize = list.size();
819 
820  ListType tmpList(listSize);
821 
822  forAll(tmpList, elemI)
823  {
824  label index = (elemI - n) % listSize;
825 
826  if (index < 0)
827  {
828  index += listSize;
829  }
830 
831  tmpList[elemI] = list[index];
832  }
833 
834  return tmpList;
835 }
836 
837 
838 template<template<typename> class ListType, class DataType>
839 void Foam::inplaceRotateList(ListType<DataType>& list, label n)
840 {
841  const label listSize = list.size();
842 
843  n = (listSize - n) % listSize;
844 
845  if (n < 0)
846  {
847  n += listSize;
848  }
849 
850  SubList<DataType> firstHalf(list, n, 0);
851  SubList<DataType> secondHalf(list, listSize - n, n);
852 
853  inplaceReverseList(firstHalf);
854  inplaceReverseList(secondHalf);
855 
856  inplaceReverseList(list);
857 }
858 
859 
860 // ************************************************************************* //
void inplaceSubset(const UList< T > &select, const T &value, ListType &)
Inplace extract elements of List when select is a certain value.
void inplaceMapKey(const labelUList &oldToNew, Container &)
Recreate with mapped keys. Do not map elements with negative key.
ListType renumber(const labelUList &oldToNew, const ListType &)
Renumber the values (not the indices) of a list.
void duplicateOrder(const UList< T > &, labelList &order)
Generate (sorted) indices corresponding to duplicate list values.
void inplaceReorder(const labelUList &oldToNew, ListType &)
Inplace reorder the elements of a list.
label findSortedIndex(const ListType &, typename ListType::const_reference, const label start=0)
Find first occurrence of given element in sorted list and return index,.
#define forAll(list, i)
Loop across all elements in list.
Definition: UList.H:434
intWM_LABEL_SIZE_t label
A label is an int32_t or int64_t as specified by the pre-processor macro WM_LABEL_SIZE.
Definition: label.H:59
void sortedOrder(const UList< T > &, labelList &order)
Generate the (stable) sort order for the list.
void inplaceRenumber(const labelUList &oldToNew, ListType &)
Inplace renumber the values of a list.
error FatalError
#define FatalErrorInFunction
Report an error message using Foam::FatalError.
Definition: error.H:323
ListType rotateList(const ListType &list, const label n)
Rotate a list by n places. If n is positive rotate clockwise/right/down.
void size(const label)
Override size to be inconsistent with allocated storage.
Definition: ListI.H:164
void uniqueOrder(const UList< T > &, labelList &order)
Generate (sorted) indices corresponding to unique list values.
List< Container > initList(const T[mRows])
To construct a List from a C array. Has extra Container type.
label count(const ListType &l, typename ListType::const_reference x)
Count the number of occurrences of a value in a list.
void setValues(ListType &, const labelUList &indices, typename ListType::const_reference)
Opposite of findIndices: set values at indices to given value.
label findMin(const ListType &, const label start=0)
Find index of min element (and less than given element).
labelList findIndices(const ListType &, typename ListType::const_reference, const label start=0)
Find all occurrences of given element. Linear search.
ListType createWithValues(const label sz, typename ListType::const_reference initValue, const labelUList &indices, typename ListType::const_reference setValue)
Opposite of findIndices: set values at indices to given value.
Various functions to operate on Lists.
void inplaceReverseList(ListType &list)
Inplace reversal of a list using Swap.
scalar y
A List obtained as a section of another List.
Definition: SubList.H:53
Less function class that can be used for sorting.
Definition: UList.H:117
void operator()(List< T > &x, const List< T > &y) const
void Swap(T &a, T &b)
Definition: Swap.H:43
void clear()
Clear the list, i.e. set size to zero.
Definition: ListI.H:125
errorManip< error > abort(error &err)
Definition: errorManip.H:131
A 1D vector of objects of type <T>, where the size of the vector is known and can be used for subscri...
Definition: HashTable.H:60
ListType reverseList(const ListType &list)
Reverse a list. First element becomes last element etc.
label findMax(const ListType &, const label start=0)
Find index of max element (and larger than given element).
ListType reorder(const labelUList &oldToNew, const ListType &)
Reorder the elements (indices, not values) of a list.
List< Container > initListList(const T[mRows][nColumns])
To construct a (square) ListList from a C array. Has extra Container type.
void inplaceMapValue(const labelUList &oldToNew, Container &)
Map values. Do not map negative values.
label findIndex(const ListType &, typename ListType::const_reference, const label start=0)
Find first occurrence of given element and return index,.
const volScalarField & T
void setSize(const label)
Reset size of List.
Definition: List.C:281
void inplaceRotateList(ListType< DataType > &list, label n)
Inplace reversal of a list using the Reversal Block Swapping algorithm.
void invertManyToMany(const label len, const UList< InList > &, List< OutList > &)
Invert many-to-many.
ListType subset(const UList< T > &select, const T &value, const ListType &)
Extract elements of List when select is a certain value.
label findLower(const ListType &, typename ListType::const_reference, const label stary, const BinaryOp &bop)
Find last element < given value in sorted list and return index,.
label n
label size() const
Return the number of elements in the UList.
Definition: UListI.H:311
void stableSort(UList< T > &)
Definition: UList.C:129