ListOpsTemplates.C
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration |
5  \\ / A nd | Copyright (C) 2011-2016 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>
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>
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>
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>
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>
179 (
180  const UList<T>& lst,
181  labelList& order
182 )
183 {
184  sortedOrder(lst, order, typename UList<T>::less(lst));
185 }
186 
187 
188 template<class T, class Cmp>
190 (
191  const UList<T>& lst,
192  labelList& order,
193  const Cmp& cmp
194 )
195 {
196  // list lengths must be identical
197  if (order.size() != lst.size())
198  {
199  // avoid copying any elements, they are overwritten anyhow
200  order.clear();
201  order.setSize(lst.size());
202  }
203 
204  forAll(order, elemI)
205  {
206  order[elemI] = elemI;
207  }
208  Foam::stableSort(order, cmp);
209 }
210 
211 
212 template<class T>
214 (
215  const UList<T>& lst,
216  labelList& order
217 )
218 {
219  duplicateOrder(lst, order, typename UList<T>::less(lst));
220 }
221 
222 
223 template<class T, class Cmp>
225 (
226  const UList<T>& lst,
227  labelList& order,
228  const Cmp& cmp
229 )
230 {
231  if (lst.size() < 2)
232  {
233  order.clear();
234  return;
235  }
236 
237  sortedOrder(lst, order, cmp);
238 
239  label n = 0;
240  for (label i = 0; i < order.size() - 1; ++i)
241  {
242  if (lst[order[i]] == lst[order[i+1]])
243  {
244  order[n++] = order[i];
245  }
246  }
247  order.setSize(n);
248 }
249 
250 
251 template<class T>
253 (
254  const UList<T>& lst,
255  labelList& order
256 )
257 {
258  uniqueOrder(lst, order, typename UList<T>::less(lst));
259 }
260 
261 
262 template<class T, class Cmp>
264 (
265  const UList<T>& lst,
266  labelList& order,
267  const Cmp& cmp
268 )
269 {
270  sortedOrder(lst, order, cmp);
271 
272  if (order.size() > 1)
273  {
274  label n = 0;
275  for (label i = 0; i < order.size() - 1; ++i)
276  {
277  if (lst[order[i]] != lst[order[i+1]])
278  {
279  order[n++] = order[i];
280  }
281  }
282  order[n++] = order[order.size()-1];
283  order.setSize(n);
284  }
285 }
286 
287 
288 template<class T, class ListType>
289 ListType Foam::subset
290 (
291  const UList<T>& select,
292  const T& value,
293  const ListType& lst
294 )
295 {
296  // select must at least cover the list range
297  if (select.size() < lst.size())
298  {
300  << "select is of size " << select.size()
301  << "; but it must index a list of size " << lst.size()
302  << abort(FatalError);
303  }
304 
305  ListType newLst(lst.size());
306 
307  // ensure consistent addressable size (eg, DynamicList)
308  newLst.setSize(lst.size());
309 
310  label nElem = 0;
311  forAll(lst, elemI)
312  {
313  if (select[elemI] == value)
314  {
315  newLst[nElem++] = lst[elemI];
316  }
317  }
318  newLst.setSize(nElem);
319 
320  return newLst;
321 }
322 
323 
324 template<class T, class ListType>
326 (
327  const UList<T>& select,
328  const T& value,
329  ListType& lst
330 )
331 {
332  // select must at least cover the list range
333  if (select.size() < lst.size())
334  {
336  << "select is of size " << select.size()
337  << "; but it must index a list of size " << lst.size()
338  << abort(FatalError);
339  }
340 
341  label nElem = 0;
342  forAll(lst, elemI)
343  {
344  if (select[elemI] == value)
345  {
346  if (nElem != elemI)
347  {
348  lst[nElem] = lst[elemI];
349  }
350  ++nElem;
351  }
352  }
353 
354  lst.setSize(nElem);
355 }
356 
357 
358 template<class BoolListType, class ListType>
359 ListType Foam::subset
360 (
361  const BoolListType& select,
362  const ListType& lst
363 )
364 {
365  // select can have a different size
366  // eg, when it is a PackedBoolList or a labelHashSet
367 
368  ListType newLst(lst.size());
369 
370  // ensure consistent addressable size (eg, DynamicList)
371  newLst.setSize(lst.size());
372 
373  label nElem = 0;
374  forAll(lst, elemI)
375  {
376  if (select[elemI])
377  {
378  newLst[nElem++] = lst[elemI];
379  }
380  }
381  newLst.setSize(nElem);
382 
383  return newLst;
384 }
385 
386 
387 template<class BoolListType, class ListType>
389 (
390  const BoolListType& select,
391  ListType& lst
392 )
393 {
394  // select can have a different size
395  // eg, when it is a PackedBoolList or a labelHashSet
396 
397  label nElem = 0;
398  forAll(lst, elemI)
399  {
400  if (select[elemI])
401  {
402  if (nElem != elemI)
403  {
404  lst[nElem] = lst[elemI];
405  }
406  ++nElem;
407  }
408  }
409 
410  lst.setSize(nElem);
411 }
412 
413 
414 template<class InList, class OutList>
416 (
417  const label nEdges,
418  const UList<InList>& pointEdges,
419  List<OutList>& edges
420 )
421 {
422  // Number of points per edge
423  labelList nPointsPerEdge(nEdges, 0);
424 
425  forAll(pointEdges, pointi)
426  {
427  const InList& pEdges = pointEdges[pointi];
428 
429  forAll(pEdges, j)
430  {
431  nPointsPerEdge[pEdges[j]]++;
432  }
433  }
434 
435  // Size edges
436  edges.setSize(nEdges);
437 
438  forAll(nPointsPerEdge, edgeI)
439  {
440  edges[edgeI].setSize(nPointsPerEdge[edgeI]);
441  }
442  nPointsPerEdge = 0;
443 
444  // Fill edges
445  forAll(pointEdges, pointi)
446  {
447  const InList& pEdges = pointEdges[pointi];
448 
449  forAll(pEdges, j)
450  {
451  label edgeI = pEdges[j];
452 
453  edges[edgeI][nPointsPerEdge[edgeI]++] = pointi;
454  }
455  }
456 }
457 
458 
459 template<class ListType>
461 (
462  const ListType& l,
463  typename ListType::const_reference t,
464  const label start
465 )
466 {
467  label index = -1;
468 
469  for (label i = start; i < l.size(); i++)
470  {
471  if (l[i] == t)
472  {
473  index = i;
474  break;
475  }
476  }
477 
478  return index;
479 }
480 
481 
482 template<class ListType>
484 (
485  const ListType& l,
486  typename ListType::const_reference t,
487  const label start
488 )
489 {
490  // Count occurrences
491  label n = 0;
492 
493  for (label i = start; i < l.size(); i++)
494  {
495  if (l[i] == t)
496  {
497  n++;
498  }
499  }
500 
501  // Create and fill
502  labelList indices(n);
503  n = 0;
504 
505  for (label i = start; i < l.size(); i++)
506  {
507  if (l[i] == t)
508  {
509  indices[n++] = i;
510  }
511  }
512 
513  return indices;
514 }
515 
516 
517 template<class ListType>
518 void Foam::setValues
519 (
520  ListType& l,
521  const labelUList& indices,
522  typename ListType::const_reference t
523 )
524 {
525  forAll(indices, i)
526  {
527  l[indices[i]] = t;
528  }
529 }
530 
531 
532 template<class ListType>
533 ListType Foam::createWithValues
534 (
535  const label sz,
536  const typename ListType::const_reference initValue,
537  const labelUList& indices,
538  typename ListType::const_reference setValue
539 )
540 {
541  ListType l(sz, initValue);
542  setValues(l, indices, setValue);
543  return l;
544 }
545 
546 
547 template<class ListType>
548 Foam::label Foam::findMax(const ListType& l, const label start)
549 {
550  if (start >= l.size())
551  {
552  return -1;
553  }
554 
555  label index = start;
556 
557  for (label i = start+1; i < l.size(); i++)
558  {
559  if (l[i] > l[index])
560  {
561  index = i;
562  }
563  }
564 
565  return index;
566 }
567 
568 
569 template<class ListType>
570 Foam::label Foam::findMin(const ListType& l, const label start)
571 {
572  if (start >= l.size())
573  {
574  return -1;
575  }
576 
577  label index = start;
578 
579  for (label i = start+1; i < l.size(); i++)
580  {
581  if (l[i] < l[index])
582  {
583  index = i;
584  }
585  }
586 
587  return index;
588 }
589 
590 
591 template<class ListType>
593 (
594  const ListType& l,
595  typename ListType::const_reference t,
596  const label start
597 )
598 {
599  if (start >= l.size())
600  {
601  return -1;
602  }
603 
604  label low = start;
605  label high = l.size() - 1;
606 
607  while (low <= high)
608  {
609  label mid = (low + high)/2;
610 
611  if (t < l[mid])
612  {
613  high = mid - 1;
614  }
615  else if (t > l[mid])
616  {
617  low = mid + 1;
618  }
619  else
620  {
621  return mid;
622  }
623  }
624 
625  return -1;
626 }
627 
628 
629 template<class ListType, class BinaryOp>
631 (
632  const ListType& l,
633  typename ListType::const_reference t,
634  const label start,
635  const BinaryOp& bop
636 )
637 {
638  if (start >= l.size())
639  {
640  return -1;
641  }
642 
643  label low = start;
644  label high = l.size() - 1;
645 
646  while ((high - low) > 1)
647  {
648  label mid = (low + high)/2;
649 
650  if (bop(l[mid], t))
651  {
652  low = mid;
653  }
654  else
655  {
656  high = mid;
657  }
658  }
659 
660  if (bop(l[high], t))
661  {
662  return high;
663  }
664  else
665  {
666  if (bop(l[low], t))
667  {
668  return low;
669  }
670  else
671  {
672  return -1;
673  }
674  }
675 }
676 
677 
678 template<class ListType>
680 (
681  const ListType& l,
682  typename ListType::const_reference t,
683  const label start
684 )
685 {
686  return findLower(l, t, start, lessOp<typename ListType::value_type>());
687 }
688 
689 
690 template<class Container, class T, int mRows>
691 Foam::List<Container> Foam::initList(const T elems[mRows])
692 {
693  List<Container> lst(mRows);
694 
695  forAll(lst, rowI)
696  {
697  lst[rowI] = Container(elems[rowI]);
698  }
699  return lst;
700 }
701 
702 
703 template<class Container, class T, int mRows, int nColumns>
704 Foam::List<Container> Foam::initListList(const T elems[mRows][nColumns])
705 {
706  List<Container> lst(mRows);
707 
708  Container cols(nColumns);
709  forAll(lst, rowI)
710  {
711  forAll(cols, colI)
712  {
713  cols[colI] = elems[rowI][colI];
714  }
715  lst[rowI] = cols;
716  }
717  return lst;
718 }
719 
720 
721 template<class T>
723 {
724  if (y.size())
725  {
726  if (x.size())
727  {
728  label sz = x.size();
729  x.setSize(sz + y.size());
730  forAll(y, i)
731  {
732  x[sz++] = y[i];
733  }
734  }
735  else
736  {
737  x = y;
738  }
739  }
740 }
741 
742 
743 template<class ListType>
744 ListType Foam::reverseList(const ListType& list)
745 {
746  const label listSize = list.size();
747  const label lastIndex = listSize - 1;
748 
749  ListType tmpList(listSize);
750 
751  forAll(tmpList, elemI)
752  {
753  tmpList[elemI] = list[lastIndex - elemI];
754  }
755 
756  return tmpList;
757 }
758 
759 
760 template<class ListType>
761 void Foam::inplaceReverseList(ListType& list)
762 {
763  const label listSize = list.size();
764  const label lastIndex = listSize - 1;
765  const label nIterations = listSize >> 1;
766 
767  label elemI = 0;
768  while (elemI < nIterations)
769  {
770  Swap(list[elemI], list[lastIndex - elemI]);
771 
772  elemI++;
773  }
774 }
775 
776 
777 template<class ListType>
778 ListType Foam::rotateList(const ListType& list, const label n)
779 {
780  const label listSize = list.size();
781 
782  ListType tmpList(listSize);
783 
784  forAll(tmpList, elemI)
785  {
786  label index = (elemI - n) % listSize;
787 
788  if (index < 0)
789  {
790  index += listSize;
791  }
792 
793  tmpList[elemI] = list[index];
794  }
795 
796  return tmpList;
797 }
798 
799 
800 template<template<typename> class ListType, class DataType>
801 void Foam::inplaceRotateList(ListType<DataType>& list, label n)
802 {
803  const label listSize = list.size();
804 
805  n = (listSize - n) % listSize;
806 
807  if (n < 0)
808  {
809  n += listSize;
810  }
811 
812  SubList<DataType> firstHalf(list, n, 0);
813  SubList<DataType> secondHalf(list, listSize - n, n);
814 
815  inplaceReverseList(firstHalf);
816  inplaceReverseList(secondHalf);
817 
818  inplaceReverseList(list);
819 }
820 
821 
822 // ************************************************************************* //
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 occurence of given element in sorted list and return index,.
#define forAll(list, i)
Loop across all elements in list.
Definition: UList.H:428
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:319
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:163
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.
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 occurences 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:115
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:124
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:61
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 occurence 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:299
void stableSort(UList< T > &)
Definition: UList.C:129