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 // ************************************************************************* //
unsigned int count() const
Count number of bits set, O(log(n))
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
Xfer< labelList > used() const
Return indices of the used (true) elements as a list of labels.
#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:90
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
Definition: HashTable.H:59
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:76
void reserve(const label)
Reserve allocation space for at least this size.
Useful combination of include files which define Sin, Sout and Serr and the use of IO streams general...
bool empty() const
Return true if the list is empty (ie, size() is zero).
label packedLength() const
The list length when packed.
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.
void setSize(const label, const unsigned int &val=0u)
Alias for resize()
void clear()
Clear the list, i.e. set addressable size to zero.
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
void resize(const label, const unsigned int &val=0u)
Reset addressable list size, does not shrink the allocated size.
PackedBoolList & operator^=(const PackedList< 1 > &)
Xor operator (lists may be dissimilar sizes)
dimensioned< Type > min(const dimensioned< Type > &, const dimensioned< Type > &)
PackedBoolList()
Construct null.
label size() const
Return the number of elements in the UList.
Definition: UListI.H:299
void setSize(const label)
Reset size of List.
Definition: List.C:295
bool trim()
Trim any trailing zero elements.
A bit-packed bool list.
List< unsigned int > & storage()
Return the underlying packed storage.
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.
List< StorageType > StorageList
Definition: PackedList.H:154
label size() const
Number of entries.