src/OpenFOAM/containers/Lists/PackedList/PackedList.H

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