FreeFOAM The Cross-Platform CFD Toolkit
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>
114 :
115  private List<unsigned int>
116 {
117  typedef unsigned int StorageType;
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.
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
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
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: ************************ //