ListOps.H
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 InNamspace
25  Foam
26 
27 Description
28  Various functions to operate on Lists.
29 
30 SourceFiles
31  ListOps.C
32  ListOpsTemplates.C
33 
34 \*---------------------------------------------------------------------------*/
35 
36 #ifndef ListOps_H
37 #define ListOps_H
38 
39 #include "labelList.H"
40 #include "ops.H"
41 
42 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
43 
44 namespace Foam
45 {
46 
47 extern const labelList emptyLabelList;
48 
49 //- Return reference to zero-sized list. Compare to List::null() which returns
50 // null pointer cast as list reference.
51 template<class Type>
52 static const List<Type>& emptyList()
53 {
54  return *reinterpret_cast<const List<Type>* >(&emptyLabelList);
55 }
56 
57 //- Renumber the values (not the indices) of a list.
58 // Negative ListType elements are left as is.
59 template<class ListType>
60 ListType renumber(const labelUList& oldToNew, const ListType&);
61 
62 //- Inplace renumber the values of a list.
63 // Negative ListType elements are left as is.
64 template<class ListType>
65 void inplaceRenumber(const labelUList& oldToNew, ListType&);
66 
67 
68 //- Reorder the elements (indices, not values) of a list.
69 // Negative ListType elements are left as is.
70 template<class ListType>
71 ListType reorder(const labelUList& oldToNew, const ListType&);
72 
73 //- Inplace reorder the elements of a list.
74 // Negative ListType elements are left as is.
75 template<class ListType>
76 void inplaceReorder(const labelUList& oldToNew, ListType&);
77 
78 
79 // Variants to work with iterators and sparse tables.
80 // Need to have iterators and insert()
81 
82 //- Map values. Do not map negative values.
83 template<class Container>
84 void inplaceMapValue(const labelUList& oldToNew, Container&);
85 
86 //- Recreate with mapped keys. Do not map elements with negative key.
87 template<class Container>
88 void inplaceMapKey(const labelUList& oldToNew, Container&);
89 
90 
91 //- Generate the (stable) sort order for the list
92 template<class T>
93 void sortedOrder(const UList<T>&, labelList& order);
94 
95 template<class T, class Cmp>
96 void sortedOrder(const UList<T>&, labelList& order, const Cmp& cmp);
97 
98 //- Generate (sorted) indices corresponding to duplicate list values
99 template<class T>
100 void duplicateOrder(const UList<T>&, labelList& order);
101 
102 template<class T, class Cmp>
103 void duplicateOrder(const UList<T>&, labelList& order, const Cmp& cmp);
104 
105 //- Generate (sorted) indices corresponding to unique list values
106 template<class T>
107 void uniqueOrder(const UList<T>&, labelList& order);
108 
109 template<class T, class Cmp>
110 void uniqueOrder(const UList<T>&, labelList& order, const Cmp& cmp);
111 
112 //- Extract elements of List when select is a certain value.
113 // eg, to extract all selected elements:
114 // subset<bool, labelList>(selectedElems, true, lst);
115 template<class T, class ListType>
116 ListType subset(const UList<T>& select, const T& value, const ListType&);
117 
118 //- Inplace extract elements of List when select is a certain value.
119 // eg, to extract all selected elements:
120 // inplaceSubset<bool, labelList>(selectedElems, true, lst);
121 template<class T, class ListType>
122 void inplaceSubset(const UList<T>& select, const T& value, ListType&);
123 
124 //- Extract elements of List when select is true
125 // eg, to extract all selected elements:
126 // subset<boolList, labelList>(selectedElems, lst);
127 // Note a labelHashSet could also be used for the bool-list
128 template<class BoolListType, class ListType>
129 ListType subset(const BoolListType& select, const ListType&);
130 
131 //- Inplace extract elements of List when select is true
132 // eg, to extract all selected elements:
133 // inplaceSubset<boolList, labelList>(selectedElems, lst);
134 // Note a labelHashSet could also be used for the bool-list
135 template<class BoolListType, class ListType>
136 void inplaceSubset(const BoolListType& select, ListType&);
137 
138 //- Invert one-to-one map. Unmapped elements will be -1.
139 labelList invert(const label len, const labelUList&);
140 
141 //- Invert one-to-many map. Unmapped elements will be size 0.
142 labelListList invertOneToMany(const label len, const labelUList&);
143 
144 //- Invert many-to-many.
145 // Input and output types need to be inherited from List.
146 // eg, faces to pointFaces.
147 template<class InList, class OutList>
148 void invertManyToMany(const label len, const UList<InList>&, List<OutList>&);
149 
150 template<class InList, class OutList>
152 {
153  List<OutList> out;
154  invertManyToMany<InList,OutList>(len, in, out);
155  return out;
156 }
157 
158 //- Create identity map (map[i] == i) of given length
159 labelList identity(const label len);
160 
161 //- Find first occurence of given element and return index,
162 // return -1 if not found. Linear search.
163 template<class ListType>
165 (
166  const ListType&,
167  typename ListType::const_reference,
168  const label start=0
169 );
170 
171 //- Find all occurences of given element. Linear search.
172 template<class ListType>
174 (
175  const ListType&,
176  typename ListType::const_reference,
177  const label start=0
178 );
179 
180 //- Opposite of findIndices: set values at indices to given value
181 template<class ListType>
182 void setValues
183 (
184  ListType&,
185  const labelUList& indices,
186  typename ListType::const_reference
187 );
188 
189 //- Opposite of findIndices: set values at indices to given value
190 template<class ListType>
191 ListType createWithValues
192 (
193  const label sz,
194  typename ListType::const_reference initValue,
195  const labelUList& indices,
196  typename ListType::const_reference setValue
197 );
198 
199 //- Find index of max element (and larger than given element).
200 // return -1 if not found. Linear search.
201 template<class ListType>
202 label findMax(const ListType&, const label start=0);
203 
204 
205 //- Find index of min element (and less than given element).
206 // return -1 if not found. Linear search.
207 template<class ListType>
208 label findMin(const ListType&, const label start=0);
209 
210 
211 //- Find first occurence of given element in sorted list and return index,
212 // return -1 if not found. Binary search.
213 template<class ListType>
215 (
216  const ListType&,
217  typename ListType::const_reference,
218  const label start=0
219 );
220 
221 
222 //- Find last element < given value in sorted list and return index,
223 // return -1 if not found. Binary search.
224 template<class ListType, class BinaryOp>
226 (
227  const ListType&,
228  typename ListType::const_reference,
229  const label stary,
230  const BinaryOp& bop
231 );
232 
233 
234 //- Find last element < given value in sorted list and return index,
235 // return -1 if not found. Binary search.
236 template<class ListType>
238 (
239  const ListType&,
240  typename ListType::const_reference,
241  const label start=0
242 );
243 
244 
245 //- To construct a List from a C array. Has extra Container type
246 // to initialise e.g. wordList from arrays of char*.
247 template<class Container, class T, int nRows>
248 List<Container> initList(const T[nRows]);
249 
250 
251 //- To construct a (square) ListList from a C array. Has extra Container type
252 // to initialise e.g. faceList from arrays of labels.
253 template<class Container, class T, int nRows, int nColumns>
254 List<Container> initListList(const T[nRows][nColumns]);
255 
256 
257 //- Helper class for list to append y onto the end of x
258 template<class T>
260 {
261 public:
262  void operator()(List<T>& x, const List<T>& y) const;
263 };
264 
265 
266 //- Reverse a list. First element becomes last element etc.
267 template<class ListType>
268 ListType reverseList(const ListType& list);
269 
270 
271 //- Inplace reversal of a list using Swap.
272 template<class ListType>
273 void inplaceReverseList(ListType& list);
274 
275 
276 //- Rotate a list by n places. If n is positive rotate clockwise/right/down.
277 // If n is negative rotate anti-clockwise/left/up.
278 template<class ListType>
279 ListType rotateList(const ListType& list, const label n);
280 
281 
282 //- Inplace reversal of a list using the Reversal Block Swapping algorithm.
283 template<template<typename> class ListType, class DataType>
284 void inplaceRotateList(ListType<DataType>& list, label n);
285 
286 
287 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
288 
289 } // End namespace Foam
290 
291 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
292 
293 #ifdef NoRepository
294 # include "ListOpsTemplates.C"
295 #endif
296 
297 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
298 
299 #endif
300 
301 // ************************************************************************* //
302 
const labelList emptyLabelList
Definition: ListOps.C:31
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 T(FieldField< Field, Type > &f1, const FieldField< Field, Type > &f2)
labelListList invertOneToMany(const label len, const labelUList &)
Invert one-to-many map. Unmapped elements will be size 0.
Definition: ListOps.C:67
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.
Helper class for list to append y onto the end of x.
Definition: ListOps.H:259
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 inplaceMapKey(const labelUList &oldToNew, Container &)
Recreate with mapped keys. Do not map elements with negative key.
Namespace for OpenFOAM.
label n
static const List< Type > & emptyList()
Return reference to zero-sized list. Compare to List::null() which returns.
Definition: ListOps.H:52
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.
void setValues(ListType &, const labelUList &indices, typename ListType::const_reference)
Opposite of findIndices: set values at indices to given value.
labelList identity(const label len)
Create identity map (map[i] == i) of given length.
Definition: ListOps.C:104
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 findMin(const ListType &, const label start=0)
Find index of min element (and less than given element).
void duplicateOrder(const UList< T > &, labelList &order)
Generate (sorted) indices corresponding to duplicate list values.
labelList invert(const label len, const labelUList &)
Invert one-to-one map. Unmapped elements will be -1.
Definition: ListOps.C:37
void uniqueOrder(const UList< T > &, labelList &order)
Generate (sorted) indices corresponding to unique list values.
scalar y
List< Container > initListList(const T[nRows][nColumns])
To construct a (square) ListList from a C array. Has extra Container type.
List< label > labelList
A List of labels.
Definition: labelList.H:56
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 inplaceSubset(const UList< T > &select, const T &value, ListType &)
Inplace extract elements of List when select is a certain value.
ListType subset(const UList< T > &select, const T &value, const ListType &)
Extract elements of List when select is a certain value.
Combination-Reduction operation for a parallel run.
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.
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.