PackedBoolList.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 "PackedBoolList.H"
27 #include "IOstreams.H"
28 
29 // * * * * * * * * * * * * * Private Member Functions * * * * * * * * * * * //
30 
31 bool Foam::PackedBoolList::bitorPrepare
32 (
33  const PackedList<1>& lst,
34  label& maxPackLen
35 )
36 {
37  const StorageList& lhs = this->storage();
38  const StorageList& rhs = lst.storage();
39 
40  const label packLen1 = this->packedLength();
41  const label packLen2 = lst.packedLength();
42 
43 
44  // check how the lists interact and if bit trimming is needed
45  bool needTrim = false;
46  maxPackLen = packLen1;
47 
48  if (packLen1 == packLen2)
49  {
50  // identical packed lengths - only resize if absolutely necessary
51  if
52  (
53  this->size() != lst.size()
54  && maxPackLen
55  && rhs[maxPackLen-1] > lhs[maxPackLen-1]
56  )
57  {
58  // second list has a higher bit set
59  // extend addressable area and use trim
60  resize(lst.size());
61  needTrim = true;
62  }
63  }
64  else if (packLen2 < packLen1)
65  {
66  // second list is shorter, this limits the or
67  maxPackLen = packLen2;
68  }
69  else
70  {
71  // second list is longer, find the highest bit set
72  for (label storeI = packLen1; storeI < packLen2; ++storeI)
73  {
74  if (rhs[storeI])
75  {
76  maxPackLen = storeI+1;
77  }
78  }
79 
80  // the upper limit moved - resize for full coverage and trim later
81  if (maxPackLen > packLen1)
82  {
83  resize(maxPackLen * packing());
84  needTrim = true;
85  }
86  }
87 
88  return needTrim;
89 }
90 
91 
92 template<class LabelListType>
93 Foam::label Foam::PackedBoolList::setIndices(const LabelListType& indices)
94 {
95  // no better information, just guess something about the size
96  reserve(indices.size());
97 
98  label cnt = 0;
99  forAll(indices, elemI)
100  {
101  if (set(indices[elemI]))
102  {
103  ++cnt;
104  }
105  }
106 
107  return cnt;
108 }
109 
110 
111 template<class LabelListType>
112 Foam::label Foam::PackedBoolList::unsetIndices(const LabelListType& indices)
113 {
114  label cnt = 0;
115  forAll(indices, elemI)
116  {
117  if (unset(indices[elemI]))
118  {
119  ++cnt;
120  }
121  }
122 
123  return cnt;
124 }
125 
126 
127 template<class LabelListType>
128 Foam::label Foam::PackedBoolList::subsetIndices(const LabelListType& indices)
129 {
130  // handle trivial case
131  if (empty() || indices.empty())
132  {
133  clear();
134  return 0;
135  }
136 
137  // normal case
138  PackedBoolList anded;
139  anded.reserve(size());
140 
141  label cnt = 0;
142  forAll(indices, elemI)
143  {
144  const label& index = indices[elemI];
145  if (operator[](index))
146  {
147  anded.set(index);
148  ++cnt;
149  }
150  }
151 
152  transfer(anded);
153  return cnt;
154 }
155 
156 
157 // * * * * * * * * * * * * * * * * Constructors * * * * * * * * * * * * * * //
158 
160 :
161  PackedList<1>()
162 {
163  is >> *this;
164 }
165 
166 
167 // * * * * * * * * * * * * * * Member Functions * * * * * * * * * * * * * * //
168 
170 {
171  // extend addressable area if needed, return maximum size possible
172  label len = 0;
173  const bool needTrim = bitorPrepare(lst, len);
174 
175  // operate directly with the underlying storage
176  StorageList& lhs = this->storage();
177  const StorageList& rhs = lst.storage();
178 
179  for (label i=0; i < len; ++i)
180  {
181  lhs[i] |= rhs[i];
182  }
183 
184  if (needTrim)
185  {
186  trim();
187  }
188 }
189 
190 
192 {
193  return setIndices(indices);
194 }
195 
196 
198 {
199  return setIndices(indices);
200 }
201 
202 
204 {
205  // operate directly with the underlying storage
206  StorageList& lhs = this->storage();
207  const StorageList& rhs = lst.storage();
208 
209  // overlapping storage size
210  const label len = min(this->packedLength(), lst.packedLength());
211 
212  for (label i=0; i < len; ++i)
213  {
214  lhs[i] &= ~rhs[i];
215  }
216 }
217 
218 
220 {
221  return unsetIndices(indices);
222 }
223 
224 
226 {
227  return unsetIndices(indices);
228 }
229 
230 
232 {
233  // shrink addressable area if needed
234  if (this->size() > lst.size())
235  {
236  this->resize(lst.size());
237  }
238 
239  // operate directly with the underlying storage
240  StorageList& lhs = this->storage();
241  const StorageList& rhs = lst.storage();
242 
243  const label len = this->packedLength();
244 
245  for (label i=0; i < len; ++i)
246  {
247  lhs[i] &= rhs[i];
248  }
249 }
250 
251 
253 {
254  return subsetIndices(indices);
255 }
256 
257 
259 {
260  return subsetIndices(indices);
261 }
262 
263 
265 {
266  labelList lst(this->count());
267 
268  if (lst.size())
269  {
270  label nElem = 0;
271 
272  forAll(*this, elemI)
273  {
274  if (get(elemI))
275  {
276  lst[nElem++] = elemI;
277  }
278  }
279 
280  lst.setSize(nElem);
281  }
282 
283  return lst.xfer();
284 }
285 
286 
287 // * * * * * * * * * * * * * * Member Operators * * * * * * * * * * * * * * //
288 
290 {
291  this->setSize(lst.size());
292 
293  // overwrite with new true/false values
294  forAll(*this, elemI)
295  {
296  set(elemI, lst[elemI]);
297  }
298 }
299 
300 
303 {
304  // extend addressable area if needed, return maximum size possible
305  label len = 0;
306  const bool needTrim = bitorPrepare(lst, len);
307 
308  // operate directly with the underlying storage
309  StorageList& lhs = this->storage();
310  const StorageList& rhs = lst.storage();
311 
312  for (label i=0; i < len; ++i)
313  {
314  lhs[i] ^= rhs[i];
315  }
316 
317  if (needTrim)
318  {
319  trim();
320  }
321 
322  return *this;
323 }
324 
325 
326 // * * * * * * * * * * * * * * Global Operators * * * * * * * * * * * * * * //
327 
328 Foam::PackedBoolList Foam::operator&
329 (
330  const PackedBoolList& lst1,
331  const PackedBoolList& lst2
332 )
333 {
334  PackedBoolList result(lst1);
335  result &= lst2;
336 
337  // trim to bits actually used
338  result.trim();
339 
340  return result;
341 }
342 
343 
344 Foam::PackedBoolList Foam::operator^
345 (
346  const PackedBoolList& lst1,
347  const PackedBoolList& lst2
348 )
349 {
350  PackedBoolList result(lst1);
351  result ^= lst2;
352 
353  // trim to bits actually used
354  result.trim();
355 
356  return result;
357 }
358 
359 
360 Foam::PackedBoolList Foam::operator|
361 (
362  const PackedBoolList& lst1,
363  const PackedBoolList& lst2
364 )
365 {
366  PackedBoolList result(lst1);
367  result |= lst2;
368  return result;
369 }
370 
371 
372 // ************************************************************************* //
void subset(const PackedList< 1 > &)
Subset with the specified list.
A simple container for copying or transferring objects of type <T>.
Definition: Xfer.H:85
#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
static label packedLength(const label)
Calculate the list length when packed.
Definition: PackedListI.H:62
Xfer< List< T > > xfer()
Transfer contents to the Xfer container.
Definition: ListI.H:177
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
Definition: HashTable.H:60
An Istream is an abstract base class for all input systems (streams, files, token lists etc)...
Definition: Istream.H:57
void size(const label)
Override size to be inconsistent with allocated storage.
Definition: ListI.H:163
void reserve(const label)
Reserve allocation space for at least this size.
Definition: PackedListI.H:862
Useful combination of include files which define Sin, Sout and Serr and the use of IO streams general...
label packedLength() const
The list length when packed.
Definition: PackedListI.H:932
void set(const PackedList< 1 > &)
Set specified bits.
A dynamically allocatable list of packed unsigned integers.
Definition: PackedList.H:117
void operator=(const bool val)
Assignment of all entries to the given value.
static unsigned int packing()
The number of entries per packed storage element.
Definition: PackedListI.H:45
void setSize(const label, const unsigned int &val=0u)
Alias for resize()
Definition: PackedListI.H:822
void clear()
Clear the list, i.e. set addressable size to zero.
Definition: PackedListI.H:891
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
void resize(const label, const unsigned int &val=0u)
Reset addressable list size, does not shrink the allocated size.
Definition: PackedListI.H:728
PackedBoolList & operator^=(const PackedList< 1 > &)
Xor operator (lists may be dissimilar sizes)
dimensioned< Type > min(const dimensioned< Type > &, const dimensioned< Type > &)
PackedBoolList()
Construct null.
unsigned int count() const
Count number of bits set, O(log(n))
Definition: PackedList.C:55
void setSize(const label)
Reset size of List.
Definition: List.C:281
bool trim()
Trim any trailing zero elements.
Definition: PackedList.C:74
A bit-packed bool list.
List< unsigned int > & storage()
Return the underlying packed storage.
Definition: PackedListI.H:918
void transfer(PackedBoolList &)
Transfer the contents of the argument list into this list.
A List with indirect addressing.
Definition: fvMatrix.H:106
void unset(const PackedList< 1 > &)
Unset specified bits.
bool empty() const
Return true if the list is empty (ie, size() is zero).
Definition: PackedListI.H:720
label size() const
Number of entries.
Definition: PackedListI.H:713
List< StorageType > StorageList
Definition: PackedList.H:154
label size() const
Return the number of elements in the UList.
Definition: UListI.H:299
Xfer< labelList > used() const
Return indices of the used (true) elements as a list of labels.