All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
PackedList.H
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration | Website: https://openfoam.org
5  \\ / A nd | Copyright (C) 2011-2021 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 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 assignment 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  Also note that all unused internal storage elements are guaranteed to
76  always be bit-wise zero. This property must not be violated by any
77  inheriting classes.
78 
79  In addition to the normal output format, PackedList also supports a
80  compact ASCII format that may be convenient for user input in some
81  situations. The general format is a group of index/value pairs:
82  \verbatim
83  { (index1 value1) (index2 value2) (index3 value3) }
84  \endverbatim
85  The bool specialisation just uses the indices corresponding to
86  non-zero entries instead of a index/value pair:
87  \verbatim
88  { index1 index2 index3 }
89  \endverbatim
90  In both cases, the supplied indices can be randomly ordered.
91 
92 See also
93  Foam::DynamicList
94 
95 SourceFiles
96  PackedListI.H
97  PackedList.C
98 
99 \*---------------------------------------------------------------------------*/
100 
101 #ifndef PackedList_H
102 #define PackedList_H
103 
104 #include "labelList.H"
105 #include "UIndirectList.H"
106 #include <type_traits>
107 
108 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
109 
110 namespace Foam
111 {
112 
113 // Forward declaration of classes
114 class Istream;
115 class Ostream;
116 
117 // Forward declaration of friend functions and operators
118 template<unsigned nBits> class PackedList;
119 
120 template<unsigned nBits>
121 void writeEntry(Ostream& os, const PackedList<nBits>&);
122 
123 template<unsigned nBits>
125 
126 template<unsigned nBits>
127 Ostream& operator<<(Ostream&, const PackedList<nBits>&);
128 
129 
130 /*---------------------------------------------------------------------------*\
131  Class PackedListCore Declaration
132 \*---------------------------------------------------------------------------*/
133 
134 //- Template-invariant bits for PackedList
135 struct PackedListCore
136 {
137  //- Construct null
139  {}
140 
141  //- Define template name and debug
142  ClassName("PackedList");
143 };
144 
145 
146 /*---------------------------------------------------------------------------*\
147  Class PackedList Declaration
148 \*---------------------------------------------------------------------------*/
149 
150 template<unsigned nBits=1>
151 class PackedList
152 :
153  public PackedListCore,
154  private List<unsigned int>
155 {
156 protected:
158  typedef unsigned int StorageType;
159  typedef List<StorageType> StorageList;
160 
161  // Protected Member Functions
162 
163  //- Calculate the list length when packed
164  inline static label packedLength(const label);
165 
166  //- Read a list entry (allows for specialisation)
167  inline static unsigned int readValue(Istream&);
168 
169  //- Read an index/value pair and set accordingly.
170  // For bool specialisation, read a single index value
171  inline void setPair(Istream&);
172 
173 
174 private:
175 
176  //- nBits must be positive (non-zero) and fit within the storage.
177  // For efficiency, however, require packing at least 2 items otherwise
178  // it is more efficient to use a normal list.
179  // Thus max nBits is 1/2 of the base storage size.
180  // For simplicity, assume 8-bit bytes in the assert.
181  static_assert
182  (
183  nBits && nBits <= (sizeof(StorageType) << 2),
184  "nBits must be positive (non-zero) and fit within the storage"
185  );
186 
187  // Private Data
188 
189  //- Number of nBits entries
190  label size_;
191 
192 
193 public:
194 
195  // Public data
196 
197  //- The max. number of bits that can be templated.
198  // Might someday be useful for a template assert.
199  inline static unsigned int max_bits();
200 
201  //- The max. value for an entry, which simultaneously the bit-mask
202  // eg, ((1 << 2) - 1) yields 0b0011
203  inline static unsigned int max_value();
204 
205  //- The number of entries per packed storage element
206  inline static unsigned int packing();
207 
208  //- Masking for all bits below the offset
209  inline static unsigned int maskLower(unsigned offset);
210 
211 
212  // Forward declaration of iterators
213 
214  class iteratorBase;
215  class iterator;
216  class const_iterator;
217 
218 
219  // Constructors
220 
221  //- Null constructor
222  inline PackedList();
223 
224  //- Construct with given size, initialises list to 0
225  explicit inline PackedList(const label size);
226 
227  //- Construct with given size and value for all elements
228  inline PackedList(const label size, const unsigned val);
229 
230  //- Construct from Istream
231  inline PackedList(Istream&);
232 
233  //- Copy constructor
234  inline PackedList(const PackedList<nBits>&);
235 
236  //- Move constructor
237  inline PackedList(PackedList<nBits>&&);
238 
239  //- Construct from a list of labels
240  explicit inline PackedList(const labelUList&);
241 
242  //- Construct from an indirect list of labels
243  explicit inline PackedList(const UIndirectList<label>&);
244 
245  //- Clone
246  inline autoPtr<PackedList<nBits>> clone() const;
247 
248 
249  // Member Functions
250 
251  // Access
252 
253  //- The number of elements that can be stored before reallocating
254  inline label capacity() const;
255 
256  //- Number of entries.
257  inline label size() const;
258 
259  //- Return true if the list is empty (ie, size() is zero).
260  inline bool empty() const;
261 
262  //- Get value at index I.
263  // Never auto-vivify entries.
264  inline unsigned int get(const label) const;
265 
266  //- Set value at index I. Return true if value changed.
267  // Does auto-vivify for non-existent entries.
268  // Default value set is the max_value.
269  inline bool set(const label, const unsigned int val = ~0u);
270 
271  //- Unset the entry at index I. Return true if value changed.
272  // Never auto-vivify entries.
273  inline bool unset(const label);
274 
275  //- Return the underlying packed storage
276  // Manipulate with utmost caution
277  inline List<unsigned int>& storage();
278 
279  //- Return the underlying packed storage
280  inline const List<unsigned int>& storage() const;
281 
282  //- The list length when packed
283  inline label packedLength() const;
284 
285  //- Return the binary size in number of characters
286  // used in the underlying storage
287  inline std::streamsize byteSize() const;
288 
289  //- Count number of bits set, O(log(n))
290  // Uses the Hamming weight (population count) method
291  // http://en.wikipedia.org/wiki/Hamming_weight
292  unsigned int count() const;
293 
294  //- Return the values as a list of labels
295  labelList values() const;
296 
297  //- Print bit patterns, optionally output unused elements
298  //
299  // addressable bits:
300  // on: '1', off: '-'
301  //
302  // non-addressable bits:
303  // on: '!', off: '.'
304  //
305  Ostream& printBits(Ostream&, const bool fullOutput=false) const;
306 
307  //- Print information and bit patterns (with printBits)
308  Ostream& printInfo(Ostream&, const bool fullOutput=false) const;
309 
310 
311  // Edit
312 
313  //- Trim any trailing zero elements
314  bool trim();
315 
316  //- Invert the bits in the addressable region
317  void flip();
318 
319  //- Clear all bits
320  inline void reset();
321 
322  //- Alter the size of the underlying storage.
323  // The addressed size will be truncated if needed to fit, but will
324  // remain otherwise untouched.
325  inline void setCapacity(const label);
326 
327  //- Reset addressable list size, does not shrink the allocated size.
328  // Optionally specify a value for new elements.
329  inline void resize(const label, const unsigned int& val = 0u);
330 
331  //- Alias for resize()
332  inline void setSize(const label, const unsigned int& val = 0u);
333 
334  //- Reserve allocation space for at least this size.
335  // Never shrinks the allocated size.
336  // The list size is adjusted as per DynamicList with
337  // SizeInc=0, SizeMult=2, SizeDiv=1
338  inline void reserve(const label);
339 
340  //- Clear the list, i.e. set addressable size to zero.
341  // Does not adjust the underlying storage
342  inline void clear();
343 
344  //- Clear the list and delete storage.
345  inline void clearStorage();
346 
347  //- Shrink the allocated space to what is actually used.
348  inline void shrink();
349 
350  //- Transfer the contents of the argument list into this list
351  // and annul the argument list.
352  inline void transfer(PackedList<nBits>&);
353 
354 
355  // IO
356 
357  //- Clear list and read from stream
358  Istream& read(Istream&);
359 
360  //- Write, optionally with indexedOutput
361  //
362  // The indexed output may be convenient in some situations.
363  // The general format is a group of index/value pairs:
364  // \verbatim
365  // { (index1 value1) (index2 value2) (index3 value3) }
366  // \endverbatim
367  // The bool specialisation just uses the indices corresponding to
368  // non-zero entries instead of a index/value pair:
369  // \verbatim
370  // { index1 index2 index3 }
371  // \endverbatim
372  //
373  // Note the indexed output is only supported for ASCII streams.
374  Ostream& write
375  (
376  Ostream&,
377  const bool indexedOutput=false
378  ) const;
379 
380 
381  // Member Operators
382 
383  //- Append a value at the end of the list
384  inline PackedList<nBits>& append(const unsigned int val);
385 
386  //- Remove and return the last element
387  inline unsigned int remove();
388 
389  //- Get value at index I
390  // Never auto-vivify entries.
391  inline unsigned int operator[](const label) const;
392 
393  //- Set value at index I.
394  // Returns iterator to perform the actual operation.
395  // Does not auto-vivify entries, but will when assigned to.
396  inline iteratorBase operator[](const label);
397 
398  //- Assignment of all entries to the given value. Takes linear time.
399  inline void operator=(const unsigned int val);
400 
401  //- Assignment operator
402  void operator=(const PackedList<nBits>&);
403 
404  //- Move assignment operator
405  void operator=(PackedList<nBits>&&);
406 
407  //- Assignment operator
408  void operator=(const labelUList&);
409 
410  //- Assignment operator
411  void operator=(const UIndirectList<label>&);
412 
413 
414  // Iterators and helpers
415 
416  //- The iterator base for PackedList
417  // Note: data and functions are protected, to allow reuse by iterator
418  // and prevent most external usage.
419  class iteratorBase
420  {
421  friend class PackedList;
422 
423  protected:
424 
425  // Protected Data
426 
427  //- Pointer to original list
428  // This also lets us use the default bitwise copy/assignment
429  PackedList* list_;
430 
431  //- Element index
432  label index_;
433 
434 
435  // Protected Member Functions
436 
437  //- Get value as unsigned, no range-checking
438  inline unsigned int get() const;
439 
440  //- Set value, returning true if changed, no range-checking
441  inline bool set(unsigned int);
442 
443 
444  // Constructors
445 
446  //- Construct null
447  inline iteratorBase();
448 
449  //- Construct from base list and position index
450  inline iteratorBase(const PackedList*, const label);
451 
452  //- Default copy constructor
453  iteratorBase(const iteratorBase&) = default;
454 
455 
456  public:
457 
458  // Member Functions
459 
460  //- Return the element index corresponding to the iterator
461  inline label key() const;
462 
463  //- Write index/value for a non-zero entry
464  // The bool specialisation writes the index only
465  inline bool writeIfSet(Ostream&) const;
466 
467  // Member Operators
468 
469  //- Compare values (not positions)
470  inline bool operator==(const iteratorBase&) const;
471  inline bool operator!=(const iteratorBase&) const;
472 
473  //- Assign value, not position.
474  // This allows packed[0] = packed[3] for assigning values
475  inline void operator=(const iteratorBase&);
476 
477  //- Assign value.
478  // A non-existent entry will be auto-vivified.
479  inline void operator=(const unsigned int val);
480 
481  //- Conversion operator
482  // Never auto-vivify entries.
483  inline operator unsigned int () const;
484 
485  //- Print information and values
486  Ostream& printInfo(Ostream&) const;
487  };
488 
489 
490  //- The iterator class used for PackedList
491  class iterator
492  :
493  public iteratorBase
494  {
495 
496  //- Disallow default bitwise copy construction
497  // This would violate const-ness!
498  iterator(const const_iterator&);
499 
500  //- Disallow assignment from const_iterator
501  // This would violate const-ness!
502  void operator=(const const_iterator&);
503 
504 
505  public:
506 
507  // Constructors
508 
509  //- Construct null
510  inline iterator();
511 
512  //- Construct from iterator base, eg iter(packedlist[i])
513  // but also "iterator iter = packedlist[i];"
514  // An out-of-range iterator is assigned end()
515  inline iterator(const iteratorBase&);
516 
517  //- Construct from base list and position index
518  inline iterator(const PackedList*, const label);
519 
520 
521  // Member Operators
522 
523  //- Compare positions (not values)
524  inline bool operator==(const iteratorBase&) const;
525  inline bool operator!=(const iteratorBase&) const;
526 
527  //- Assign from iteratorBase, eg iter = packedlist[i]
528  // An out-of-range iterator is assigned end()
529  inline void operator=(const iteratorBase&);
530 
531  //- Return value
532  inline unsigned int operator*() const;
533 
534  //- Return value
535  inline unsigned int operator()() const;
536 
537  //- Return iteratorBase for assigning values
538  inline iteratorBase& operator*();
539 
540  //- Return iteratorBase for assigning values
541  inline iteratorBase& operator()();
542 
543  inline iterator& operator++();
544  inline iterator operator++(int);
545 
546  inline iterator& operator--();
547  inline iterator operator--(int);
548 
549  };
550 
551  //- Iterator set to the beginning of the PackedList
552  inline iterator begin();
553 
554  //- Iterator set to beyond the end of the PackedList
555  inline iterator end();
556 
557 
558  //- The const_iterator for PackedList
559  class const_iterator
560  :
561  public iteratorBase
562  {
563  public:
564 
565  // Constructors
566 
567  //- Construct null
568  inline const_iterator();
569 
570  //- Construct from iterator base, eg iter(packedlist[i])
571  // but also "const_iterator iter = packedlist[i];"
572  // An out-of-range iterator is assigned cend()
573  inline const_iterator(const iteratorBase&);
574 
575  //- Construct from base list and position index
576  inline const_iterator(const PackedList*, const label);
577 
578  //- Construct from iterator
579  inline const_iterator(const iterator&);
580 
581 
582  // Member Operators
583 
584  //- Compare positions (not values)
585  inline bool operator==(const iteratorBase&) const;
586  inline bool operator!=(const iteratorBase&) const;
587 
588  //- Assign from iteratorBase or derived
589  // eg, iter = packedlist[i] or even iter = list.begin()
590  inline void operator=(const iteratorBase&);
591 
592  //- Return referenced value directly
593  inline unsigned int operator*() const;
594 
595  //- Return referenced value directly
596  inline unsigned int operator()() const;
597 
598  inline const_iterator& operator++();
599  inline const_iterator operator++(int);
600 
601  inline const_iterator& operator--();
602  inline const_iterator operator--(int);
603  };
604 
605 
606  //- const_iterator set to the beginning of the PackedList
607  inline const_iterator cbegin() const;
608 
609  //- const_iterator set to beyond the end of the PackedList
610  inline const_iterator cend() const;
611 
612  //- const_iterator set to the beginning of the PackedList
613  inline const_iterator begin() const;
614 
615  //- const_iterator set to beyond the end of the PackedList
616  inline const_iterator end() const;
617 
618 
619  // IOstream Operators
620 
621  friend Istream& operator>> <nBits>
622  (
623  Istream&,
625  );
626 
627  friend Ostream& operator<< <nBits>
628  (
629  Ostream&,
630  const PackedList<nBits>&
631  );
632 };
633 
634 
635 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
636 
637 } // End namespace Foam
638 
639 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
640 
641 #include "PackedListI.H"
642 
643 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
644 
645 #ifdef NoRepository
646  #include "PackedList.C"
647 #endif
648 
649 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
650 
651 #endif
652 
653 // ************************************************************************* //
The iterator class used for PackedList.
Definition: PackedList.H:490
tmp< fvMatrix< Type > > operator*(const volScalarField::Internal &, const fvMatrix< Type > &)
tUEqn clear()
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
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
label count(const ListType &l, typename ListType::const_reference x)
Count the number of occurrences of a value in a list.
T * iterator
Random access iterator for traversing UList.
Definition: UList.H:269
ClassName("PackedList")
Define template name and debug.
string trim(const string &)
Return string trimmed of leading and trailing whitespace.
Definition: stringOps.C:934
points setSize(newPointi)
bool read(const char *, int32_t &)
Definition: int32IO.C:85
T clone(const T &t)
Definition: List.H:54
A dynamically allocatable list of packed unsigned integers.
Definition: PackedList.H:117
tmp< fvMatrix< Type > > operator==(const fvMatrix< Type > &, const fvMatrix< Type > &)
Istream & operator>>(Istream &, directionInfo &)
triSurfaceToAgglom resize(surfacesMesh.size())
void write(std::ostream &os, const bool binary, List< floatScalar > &fField)
Write floats ascii or binary.
PackedListCore()
Construct null.
Definition: PackedList.H:137
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
Template-invariant bits for PackedList.
Definition: PackedList.H:134
An Ostream is an abstract base class for all output systems (streams, files, token lists...
Definition: Ostream.H:54
void writeEntry(Ostream &os, const HashTable< T, Key, Hash > &ht)
Definition: HashTableIO.C:96
The const_iterator for PackedList.
Definition: PackedList.H:558
The iterator base for PackedList.
Definition: PackedList.H:418
const T * const_iterator
Random access iterator for traversing UList.
Definition: UList.H:281
A List with indirect addressing.
Definition: fvMatrix.H:106
An auto-pointer similar to the STL auto_ptr but with automatic casting to a reference to the type and...
Definition: PtrList.H:52
bool operator!=(const particle &, const particle &)
Definition: particle.C:1205
Namespace for OpenFOAM.