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-2013 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  {
299  FatalErrorIn("subset(const UList<T>&, const T&, const 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  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  {
335  FatalErrorIn("inplaceSubset(const UList<T>&, const T&, ListType&)")
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 // As clarification:
415 // coded as inversion from pointEdges to edges but completely general.
416 template<class InList, class OutList>
418 (
419  const label nEdges,
420  const UList<InList>& pointEdges,
421  List<OutList>& edges
422 )
423 {
424  // Number of points per edge
425  labelList nPointsPerEdge(nEdges, 0);
426 
427  forAll(pointEdges, pointI)
428  {
429  const InList& pEdges = pointEdges[pointI];
430 
431  forAll(pEdges, j)
432  {
433  nPointsPerEdge[pEdges[j]]++;
434  }
435  }
436 
437  // Size edges
438  edges.setSize(nEdges);
439 
440  forAll(nPointsPerEdge, edgeI)
441  {
442  edges[edgeI].setSize(nPointsPerEdge[edgeI]);
443  }
444  nPointsPerEdge = 0;
445 
446  // Fill edges
447  forAll(pointEdges, pointI)
448  {
449  const InList& pEdges = pointEdges[pointI];
450 
451  forAll(pEdges, j)
452  {
453  label edgeI = pEdges[j];
454 
455  edges[edgeI][nPointsPerEdge[edgeI]++] = pointI;
456  }
457  }
458 }
459 
460 
461 template<class ListType>
463 (
464  const ListType& l,
465  typename ListType::const_reference t,
466  const label start
467 )
468 {
469  label index = -1;
470 
471  for (label i = start; i < l.size(); i++)
472  {
473  if (l[i] == t)
474  {
475  index = i;
476  break;
477  }
478  }
479 
480  return index;
481 }
482 
483 
484 template<class ListType>
486 (
487  const ListType& l,
488  typename ListType::const_reference t,
489  const label start
490 )
491 {
492  // Count occurrences
493  label n = 0;
494 
495  for (label i = start; i < l.size(); i++)
496  {
497  if (l[i] == t)
498  {
499  n++;
500  }
501  }
502 
503  // Create and fill
504  labelList indices(n);
505  n = 0;
506 
507  for (label i = start; i < l.size(); i++)
508  {
509  if (l[i] == t)
510  {
511  indices[n++] = i;
512  }
513  }
514 
515  return indices;
516 }
517 
518 
519 template<class ListType>
520 void Foam::setValues
521 (
522  ListType& l,
523  const labelUList& indices,
524  typename ListType::const_reference t
525 )
526 {
527  forAll(indices, i)
528  {
529  l[indices[i]] = t;
530  }
531 }
532 
533 
534 template<class ListType>
535 ListType Foam::createWithValues
536 (
537  const label sz,
538  const typename ListType::const_reference initValue,
539  const labelUList& indices,
540  typename ListType::const_reference setValue
541 )
542 {
543  ListType l(sz, initValue);
544  setValues(l, indices, setValue);
545  return l;
546 }
547 
548 
549 template<class ListType>
550 Foam::label Foam::findMax(const ListType& l, const label start)
551 {
552  if (start >= l.size())
553  {
554  return -1;
555  }
556 
557  label index = start;
558 
559  for (label i = start+1; i < l.size(); i++)
560  {
561  if (l[i] > l[index])
562  {
563  index = i;
564  }
565  }
566 
567  return index;
568 }
569 
570 
571 template<class ListType>
572 Foam::label Foam::findMin(const ListType& l, const label start)
573 {
574  if (start >= l.size())
575  {
576  return -1;
577  }
578 
579  label index = start;
580 
581  for (label i = start+1; i < l.size(); i++)
582  {
583  if (l[i] < l[index])
584  {
585  index = i;
586  }
587  }
588 
589  return index;
590 }
591 
592 
593 template<class ListType>
595 (
596  const ListType& l,
597  typename ListType::const_reference t,
598  const label start
599 )
600 {
601  if (start >= l.size())
602  {
603  return -1;
604  }
605 
606  label low = start;
607  label high = l.size() - 1;
608 
609  while (low <= high)
610  {
611  label mid = (low + high)/2;
612 
613  if (t < l[mid])
614  {
615  high = mid - 1;
616  }
617  else if (t > l[mid])
618  {
619  low = mid + 1;
620  }
621  else
622  {
623  return mid;
624  }
625  }
626 
627  return -1;
628 }
629 
630 
631 template<class ListType, class BinaryOp>
633 (
634  const ListType& l,
635  typename ListType::const_reference t,
636  const label start,
637  const BinaryOp& bop
638 )
639 {
640  if (start >= l.size())
641  {
642  return -1;
643  }
644 
645  label low = start;
646  label high = l.size() - 1;
647 
648  while ((high - low) > 1)
649  {
650  label mid = (low + high)/2;
651 
652  if (bop(l[mid], t))
653  {
654  low = mid;
655  }
656  else
657  {
658  high = mid;
659  }
660  }
661 
662  if (bop(l[high], t))
663  {
664  return high;
665  }
666  else
667  {
668  if (bop(l[low], t))
669  {
670  return low;
671  }
672  else
673  {
674  return -1;
675  }
676  }
677 }
678 
679 
680 template<class ListType>
682 (
683  const ListType& l,
684  typename ListType::const_reference t,
685  const label start
686 )
687 {
688  return findLower(l, t, start, lessOp<typename ListType::value_type>());
689 }
690 
691 
692 template<class Container, class T, int nRows>
693 Foam::List<Container> Foam::initList(const T elems[nRows])
694 {
695  List<Container> lst(nRows);
696 
697  forAll(lst, rowI)
698  {
699  lst[rowI] = Container(elems[rowI]);
700  }
701  return lst;
702 }
703 
704 
705 template<class Container, class T, int nRows, int nColumns>
706 Foam::List<Container> Foam::initListList(const T elems[nRows][nColumns])
707 {
708  List<Container> lst(nRows);
709 
710  Container cols(nColumns);
711  forAll(lst, rowI)
712  {
713  forAll(cols, colI)
714  {
715  cols[colI] = elems[rowI][colI];
716  }
717  lst[rowI] = cols;
718  }
719  return lst;
720 }
721 
722 
723 template<class T>
725 {
726  if (y.size())
727  {
728  if (x.size())
729  {
730  label sz = x.size();
731  x.setSize(sz + y.size());
732  forAll(y, i)
733  {
734  x[sz++] = y[i];
735  }
736  }
737  else
738  {
739  x = y;
740  }
741  }
742 }
743 
744 
745 template<class ListType>
746 ListType Foam::reverseList(const ListType& list)
747 {
748  const label listSize = list.size();
749  const label lastIndex = listSize - 1;
750 
751  ListType tmpList(listSize);
752 
753  forAll(tmpList, elemI)
754  {
755  tmpList[elemI] = list[lastIndex - elemI];
756  }
757 
758  return tmpList;
759 }
760 
761 
762 template<class ListType>
763 void Foam::inplaceReverseList(ListType& list)
764 {
765  const label listSize = list.size();
766  const label lastIndex = listSize - 1;
767  const label nIterations = listSize >> 1;
768 
769  label elemI = 0;
770  while (elemI < nIterations)
771  {
772  Swap(list[elemI], list[lastIndex - elemI]);
773 
774  elemI++;
775  }
776 }
777 
778 
779 template<class ListType>
780 ListType Foam::rotateList(const ListType& list, const label n)
781 {
782  const label listSize = list.size();
783 
784  ListType tmpList(listSize);
785 
786  forAll(tmpList, elemI)
787  {
788  label index = (elemI - n) % listSize;
789 
790  if (index < 0)
791  {
792  index += listSize;
793  }
794 
795  tmpList[elemI] = list[index];
796  }
797 
798  return tmpList;
799 }
800 
801 
802 template<template<typename> class ListType, class DataType>
803 void Foam::inplaceRotateList(ListType<DataType>& list, label n)
804 {
805  const label listSize = list.size();
806 
807  n = (listSize - n) % listSize;
808 
809  if (n < 0)
810  {
811  n += listSize;
812  }
813 
814  SubList<DataType> firstHalf(list, n, 0);
815  SubList<DataType> secondHalf(list, listSize - n, n);
816 
817  inplaceReverseList(firstHalf);
818  inplaceReverseList(secondHalf);
819 
820  inplaceReverseList(list);
821 }
822 
823 
824 // ************************************************************************* //
void operator()(List< T > &x, const List< T > &y) const
ListType reverseList(const ListType &list)
Reverse a list. First element becomes last element etc.
void invertManyToMany(const label len, const UList< InList > &, List< OutList > &)
Invert many-to-many.
label findIndex(const ListType &, typename ListType::const_reference, const label start=0)
Find first occurence of given element and return index,.
void inplaceMapValue(const labelUList &oldToNew, Container &)
Map values. Do not map negative values.
label findMax(const ListType &, const label start=0)
Find index of max element (and larger than given element).
void inplaceReorder(const labelUList &oldToNew, ListType &)
Inplace reorder the elements of a list.
void sortedOrder(const UList< T > &, labelList &order)
Generate the (stable) sort order for the list.
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 inplaceRotateList(ListType< DataType > &list, label n)
Inplace reversal of a list using the Reversal Block Swapping algorithm.
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:76
Various functions to operate on Lists.
void inplaceMapKey(const labelUList &oldToNew, Container &)
Recreate with mapped keys. Do not map elements with negative key.
const volScalarField & T
Definition: createFields.H:25
label n
void clear()
Clear the list, i.e. set size to zero.
Definition: List.C:379
void setSize(const label)
Reset size of List.
Definition: List.C:318
#define forAll(list, i)
Definition: UList.H:421
void inplaceReverseList(ListType &list)
Inplace reversal of a list using Swap.
ListType renumber(const labelUList &oldToNew, const ListType &)
Renumber the values (not the indices) of a list.
label size() const
Return the number of elements in the UList.
Definition: UListI.H:299
void setValues(ListType &, const labelUList &indices, typename ListType::const_reference)
Opposite of findIndices: set values at indices to given 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,.
errorManip< error > abort(error &err)
Definition: errorManip.H:131
label findMin(const ListType &, const label start=0)
Find index of min element (and less than given element).
void Swap(T &a, T &b)
Definition: Swap.H:43
void duplicateOrder(const UList< T > &, labelList &order)
Generate (sorted) indices corresponding to duplicate list values.
#define FatalErrorIn(functionName)
Report an error message using Foam::FatalError.
Definition: error.H:314
void uniqueOrder(const UList< T > &, labelList &order)
Generate (sorted) indices corresponding to unique list values.
error FatalError
scalar y
List< Container > initListList(const T[nRows][nColumns])
To construct a (square) ListList from a C array. Has extra Container type.
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
label findSortedIndex(const ListType &, typename ListType::const_reference, const label start=0)
Find first occurence of given element in sorted list and return index,.
void stableSort(UList< T > &)
Definition: UList.C:121
void inplaceSubset(const UList< T > &select, const T &value, ListType &)
Inplace extract elements of List when select is a certain value.
A List obtained as a section of another List.
Definition: SubList.H:53
ListType subset(const UList< T > &select, const T &value, const ListType &)
Extract elements of List when select is a certain value.
ListType reorder(const labelUList &oldToNew, const ListType &)
Reorder the elements (indices, not values) of a list.
labelList findIndices(const ListType &, typename ListType::const_reference, const label start=0)
Find all occurences of given element. Linear search.
Less function class that can be used for sorting.
Definition: UList.H:99
void inplaceRenumber(const labelUList &oldToNew, ListType &)
Inplace renumber the values of a list.
List< Container > initList(const T[nRows])
To construct a List from a C array. Has extra Container type.
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.