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