Home
Downloads
Documentation
Installation
User Guide
man-pages
API Documentation
README
Release Notes
Changes
License
Support
SourceForge Project
Main Page
Related Pages
Namespaces
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Pages
src
OpenFOAM
containers
Lists
PackedList
PackedList.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) 1991-2010 OpenCFD Ltd.
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
Class
25
Foam::PackedList
26
27
Description
28
A dynamically allocatable list of packed unsigned integers.
29
30
The list resizing is similar to DynamicList, thus the methods clear()
31
and setSize() behave like their DynamicList counterparts and the methods
32
reserve() and setCapacity() can be used to influence the allocation.
33
34
The number of bits per item is specified by the template parameter nBits.
35
36
Note
37
In a const context, the '[]' operator simply returns the stored value,
38
with out-of-range elements returned as zero.
39
In a non-const context, the '[]' operator returns an iteratorBase, which
40
might not have a valid reference for out-of-range elements.
41
The iteratorBase class handles the assignment of new values.
42
43
Using the iteratorBase as a proxy allows assignment of values
44
between list elements. Thus the following bit of code works as expected:
45
@code
46
list[1] = list[5]; // value assignment, not iterator position
47
list[2] = list[5] = 4; // propagates value
48
list[1] = list[5] = list[6]; // propagates value
49
@endcode
50
51
Using get() or the '[]' operator are similarly fast. Looping and reading
52
via an iterator is approx. 15% slower, but can be more flexible.
53
54
Using the set() operator (and the '[]' operator) are marginally slower
55
(approx. 5%) than using an iterator, but the set() method has the
56
advantage of also returning a bool if the value changed. This can be
57
useful for branching on changed values.
58
59
@code
60
list[5] = 4;
61
changed = list.set(5, 8);
62
if (changed) ...
63
@endcode
64
65
The lazy evaluation used means that reading an out-of-range element
66
returns zero, but does not affect the list size. Even in a non-const
67
context, only the assigment itself causes the element to be created.
68
For example,
69
@code
70
list.resize(4);
71
Info<< list[10] << "\n"; // print zero, but doesn't adjust list
72
list[8] = 1;
73
@endcode
74
75
SeeAlso
76
Foam::DynamicList
77
78
SourceFiles
79
PackedListI.H
80
PackedList.C
81
82
\*---------------------------------------------------------------------------*/
83
84
#ifndef PackedList_H
85
#define PackedList_H
86
87
#include <
OpenFOAM/labelList.H
>
88
#include <
OpenFOAM/StaticAssert.H
>
89
90
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
91
92
namespace
Foam
93
{
94
95
// Forward declaration of friend functions and operators
96
template
<
unsigned
nBits>
class
PackedList;
97
98
// template<unsigned nBits>
99
// Ostream& operator<<(Ostream&, const PackedList<nBits>&);
100
101
102
/*---------------------------------------------------------------------------*\
103
Class PackedListName Declaration
104
\*---------------------------------------------------------------------------*/
105
106
TemplateName
(PackedList);
107
108
/*---------------------------------------------------------------------------*\
109
Class PackedList Declaration
110
\*---------------------------------------------------------------------------*/
111
112
template
<
unsigned
nBits=1>
113
class
PackedList
114
:
115
private
List
<unsigned int>
116
{
117
typedef
unsigned
int
StorageType;
118
typedef
List<StorageType>
StorageList
;
119
120
//- nBits must be positive (non-zero) and fit within the storage
121
// For simplicity, assume 8-bit bytes
122
StaticAssert(nBits && nBits < (
sizeof
(StorageType) << 3));
123
124
// Private data
125
126
//- Number of nBits entries
127
label size_;
128
129
// Private Member Functions
130
131
//- Calculate the list length when packed
132
inline
static
label packedLength(
const
label);
133
134
public
:
135
136
// Public data
137
138
//- The max. number of bits that can be templated.
139
// Might someday be useful for a template assert.
140
inline
static
unsigned
int
max_bits
();
141
142
//- The max. value for an entry, which simultaneously the bit-mask
143
// eg, ((1 << 2) - 1) yields 0b0011
144
inline
static
unsigned
int
max_value
();
145
146
//- The number of entries per packed storage element
147
inline
static
unsigned
int
packing
();
148
149
//- Masking for all bits below the offset
150
inline
static
unsigned
int
maskLower
(
unsigned
offset);
151
152
// Forward declaration of iterators
153
154
class
iteratorBase
;
155
class
iterator
;
156
class
const_iterator
;
157
158
// Constructors
159
160
//- Null constructor
161
inline
PackedList
();
162
163
//- Construct with given size, initializes list to 0.
164
explicit
inline
PackedList
(
const
label
size
);
165
166
//- Construct with given size and value for all elements.
167
PackedList
(
const
label size,
const
unsigned
val);
168
169
//- Copy constructor.
170
inline
PackedList
(
const
PackedList<nBits>
&);
171
172
//- Construct by transferring the parameter contents
173
inline
PackedList
(
const
Xfer
<
PackedList<nBits>
>&);
174
175
//- Construct from a list of labels
176
explicit
PackedList
(
const
UList<label>
&);
177
178
//- Clone
179
inline
autoPtr< PackedList<nBits>
>
clone
()
const
;
180
181
// Member Functions
182
183
// Access
184
185
//- The number of elements that can be stored before reallocating
186
inline
label
capacity
()
const
;
187
188
//- Number of entries.
189
inline
label
size
()
const
;
190
191
//- Return true if the list is empty (ie, size() is zero).
192
inline
bool
empty
()
const
;
193
194
//- Get value at index I.
195
// Never auto-vivify entries.
196
inline
unsigned
int
get
(
const
label)
const
;
197
198
//- Set value at index I. Return true if value changed.
199
// Does auto-vivify for non-existent entries.
200
// Default value set is the max_value.
201
inline
bool
set
(
const
label,
const
unsigned
int
val = ~0u);
202
203
//- Unset the entry at index I. Return true if value changed.
204
// Never auto-vivify entries.
205
inline
bool
unset
(
const
label);
206
207
//- Return the underlying packed storage
208
inline
List<unsigned int>
&
storage
();
209
210
//- Return the underlying packed storage
211
inline
const
List<unsigned int>
&
storage
()
const
;
212
213
//- Count number of bits set, O(log(n))
214
// Uses the Hamming weight (population count) method
215
// http://en.wikipedia.org/wiki/Hamming_weight
216
unsigned
int
count
()
const
;
217
218
//- Return the values as a labelList
219
labelList
values
()
const
;
220
221
//- Print values and information
222
Ostream
&
print
(
Ostream
&)
const
;
223
224
// Edit
225
226
//- Trim any trailing zero elements
227
bool
trim
();
228
229
//- Invert the bits in the addressable region.
230
void
flip
();
231
232
//- Alter the size of the underlying storage.
233
// The addressed size will be truncated if needed to fit, but will
234
// remain otherwise untouched.
235
inline
void
setCapacity
(
const
label);
236
237
//- Reset addressable list size, does not shrink the allocated size.
238
// Optionally specify a value for new elements.
239
inline
void
resize
(
const
label,
const
unsigned
int
& val = 0);
240
241
//- Alias for resize()
242
inline
void
setSize
(
const
label,
const
unsigned
int
& val = 0);
243
244
//- Reserve allocation space for at least this size.
245
// Never shrinks the allocated size.
246
// The list size is adjusted as per DynamicList with
247
// SizeInc=0, SizeMult=2, SizeDiv=1
248
inline
void
reserve
(
const
label);
249
250
//- Clear the list, i.e. set addressable size to zero.
251
// Does not adjust the underlying storage
252
inline
void
clear
();
253
254
//- Clear the list and delete storage.
255
inline
void
clearStorage
();
256
257
//- Shrink the allocated space to what is actually used.
258
inline
void
shrink
();
259
260
//- Transfer the contents of the argument list into this list
261
// and annul the argument list.
262
inline
void
transfer
(
PackedList<nBits>
&);
263
264
//- Transfer contents to the Xfer container
265
inline
Xfer< PackedList<nBits>
>
xfer
();
266
267
268
// Member operators
269
270
//- Append a value at the end of the list
271
inline
void
append
(
const
unsigned
int
val);
272
273
//- Remove and return the last element
274
inline
unsigned
int
remove
();
275
276
//- Get value at index I
277
// Never auto-vivify entries.
278
inline
unsigned
int
operator[]
(
const
label)
const
;
279
280
//- Set value at index I.
281
// Returns iterator to perform the actual operation.
282
// Does not auto-vivify entries, but will when assigned to.
283
inline
iteratorBase
operator[]
(
const
label);
284
285
//- Assignment of all entries to the given value. Takes linear time.
286
inline
void
operator=
(
const
unsigned
int
val);
287
288
//- Assignment operator. Takes linear time.
289
void
operator=
(
const
PackedList<nBits>
&);
290
291
//- Assignment operator. Takes linear time.
292
void
operator=
(
const
UList<label>
&);
293
294
// Ostream operator
295
296
// // Write PackedList to Ostream.
297
// friend Ostream& operator<< <nBits> (Ostream&, const PackedList<nBits>&);
298
299
// Iterators and helpers
300
301
//- The iterator base for PackedList
302
// Note: data and functions are protected, to allow reuse by iterator
303
// and prevent most external usage.
304
class
iteratorBase
305
{
306
friend
class
PackedList
;
307
308
protected
:
309
310
// Protected Data
311
312
//- Pointer to original list
313
// This also lets us use the default bitwise copy/assignment
314
PackedList
*
list_
;
315
316
//- Element index
317
label
index_
;
318
319
// Protected Member Functions
320
321
//- Get value as unsigned, no range-checking
322
inline
unsigned
int
get
()
const
;
323
324
//- Set value, returning true if changed, no range-checking
325
inline
bool
set
(
unsigned
int);
326
327
// Constructors
328
329
//- Construct null
330
inline
iteratorBase
();
331
332
//- Construct from base list and position index
333
inline
iteratorBase
(
const
PackedList
*,
const
label);
334
335
public
:
336
337
// Member Operators
338
339
//- Compare values (not positions)
340
inline
bool
operator==
(
const
iteratorBase
&)
const
;
341
inline
bool
operator!=
(
const
iteratorBase
&)
const
;
342
343
//- Assign value, not position.
344
// This allows packed[0] = packed[3] for assigning values
345
inline
unsigned
int
operator=
(
const
iteratorBase
&);
346
347
//- Assign value.
348
// A non-existent entry will be auto-vivified.
349
inline
unsigned
int
operator=
(
const
unsigned
int
val);
350
351
//- Conversion operator
352
// Never auto-vivify entries.
353
inline
operator
unsigned
int ()
const
;
354
355
//- Print value and information
356
Ostream
&
print
(
Ostream
&)
const
;
357
};
358
359
360
//- The iterator class used for PackedList
361
class
iterator
362
:
363
public
iteratorBase
364
{
365
366
//- Disallow copy constructor from const_iterator - violates const-ness!
367
iterator
(
const
const_iterator
&);
368
369
//- Disallow assignment from const_iterator - violates const-ness!
370
void
operator=(
const
const_iterator
&);
371
372
public
:
373
374
// Constructors
375
376
//- Construct null
377
inline
iterator
();
378
379
//- Construct from iterator base, eg iter(packedlist[i])
380
// but also "iterator iter = packedlist[i];"
381
// An out-of-range iterator is assigned end()
382
inline
iterator
(
const
iteratorBase
&);
383
384
//- Construct from base list and position index
385
inline
iterator
(
const
PackedList
*,
const
label);
386
387
// Member Operators
388
389
//- Compare positions (not values)
390
inline
bool
operator==
(
const
iteratorBase
&)
const
;
391
inline
bool
operator!=
(
const
iteratorBase
&)
const
;
392
393
//- Assign from iteratorBase, eg iter = packedlist[i]
394
// An out-of-range iterator is assigned end()
395
inline
iterator
& operator=(
const
iteratorBase
&);
396
397
//- Return value
398
inline
unsigned
int
operator*
()
const
;
399
400
//- Return value
401
inline
unsigned
int
operator()
()
const
;
402
403
//- Return iteratorBase for assigning values
404
inline
iteratorBase
&
operator*
();
405
406
//- Return iteratorBase for assigning values
407
inline
iteratorBase
&
operator()
();
408
409
inline
iterator
&
operator++
();
410
inline
iterator
operator++
(
int
);
411
412
inline
iterator
&
operator--
();
413
inline
iterator
operator--
(
int
);
414
415
};
416
417
//- iterator set to the beginning of the PackedList
418
inline
iterator
begin
();
419
420
//- iterator set to beyond the end of the PackedList
421
inline
iterator
end
();
422
423
424
//- The const_iterator for PackedList
425
class
const_iterator
426
:
427
public
iteratorBase
428
{
429
public
:
430
431
// Constructors
432
433
//- Construct null
434
inline
const_iterator
();
435
436
//- Construct from iterator base, eg iter(packedlist[i])
437
// but also "const_iterator iter = packedlist[i];"
438
// An out-of-range iterator is assigned cend()
439
inline
const_iterator
(
const
iteratorBase
&);
440
441
//- Construct from base list and position index
442
inline
const_iterator
(
const
PackedList
*,
const
label);
443
444
//- Construct from iterator
445
inline
const_iterator
(
const
iterator
&);
446
447
// Member operators
448
449
//- Compare positions (not values)
450
inline
bool
operator==
(
const
iteratorBase
&)
const
;
451
inline
bool
operator!=
(
const
iteratorBase
&)
const
;
452
453
//- Assign from iteratorBase or derived
454
// eg, iter = packedlist[i] or even iter = list.begin()
455
inline
const_iterator
&
operator=
(
const
iteratorBase
&);
456
457
//- Return referenced value directly
458
inline
unsigned
int
operator*
()
const
;
459
460
//- Return referenced value directly
461
inline
unsigned
int
operator()
()
const
;
462
463
inline
const_iterator
&
operator++
();
464
inline
const_iterator
operator++
(
int
);
465
466
inline
const_iterator
&
operator--
();
467
inline
const_iterator
operator--
(
int
);
468
469
};
470
471
472
//- const_iterator set to the beginning of the PackedList
473
inline
const_iterator
cbegin
()
const
;
474
475
//- const_iterator set to beyond the end of the PackedList
476
inline
const_iterator
cend
()
const
;
477
478
//- const_iterator set to the beginning of the PackedList
479
inline
const_iterator
begin
()
const
;
480
481
//- const_iterator set to beyond the end of the PackedList
482
inline
const_iterator
end
()
const
;
483
484
};
485
486
487
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
488
489
}
// End namespace Foam
490
491
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
492
493
#include "
PackedListI.H
"
494
495
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
496
497
#ifdef NoRepository
498
# include "
PackedList.C
"
499
#endif
500
501
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
502
503
#endif
504
505
// ************************ vim: set sw=4 sts=4 et: ************************ //