src/foam/containers/Lists/PriorityList/PriorityList.H

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | foam-extend: Open Source CFD
   4    \\    /   O peration     | Version:     3.2
   5     \\  /    A nd           | Web:         http://www.foam-extend.org
   6      \\/     M anipulation  | For copyright notice see file Copyright
   7 -------------------------------------------------------------------------------
   8 License
   9     This file is part of foam-extend.
  10
  11     foam-extend 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 3 of the License, or (at your
  14     option) any later version.
  15
  16     foam-extend is distributed in the hope that it will be useful, but
  17     WITHOUT ANY WARRANTY; without even the implied warranty of
  18     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19     General Public License for more details.
  20
  21     You should have received a copy of the GNU General Public License
  22     along with foam-extend.  If not, see <http://www.gnu.org/licenses/>.
  23
  24 Class
  25     PriorityList
  26
  27 Description
  28     Priority list with changing priorities for inserted elements.
  29     List is sorted on access to produce element index with highest weight
  30
  31 Author
  32     Hrvoje Jasak, Wikki Ltd.  All rights reserved
  33
  34 References:
  35     R. Sedgewick, "Algorithms", Addison-Wesley, Reading, MA, 2nd edition, 1988.
  36
  37 SourceFiles
  38     PriorityList.C
  39
  40 \*---------------------------------------------------------------------------*/
  41
  42 #ifndef PriorityList_H
  43 #define PriorityList_H
  44
  45 #include "label.H"
  46
  47 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
  48
  49 namespace Foam
  50 {
  51
  52 /*---------------------------------------------------------------------------*\
  53                       Class PriorityList Declaration
  54 \*---------------------------------------------------------------------------*/
  55
  56 template<class Type>
  57 class PriorityList
  58 {
  59     // Private data
  60
  61         //- Indices into weights
  62         labelList indices_;
  63
  64         //- Weights
  65         List<Type> weights_;
  66
  67         //- Sorted indices
  68         labelList sortedIndices_;
  69
  70         //- Active size
  71         label size_;
  72
  73         //- Is the list sorted?
  74         mutable bool listSorted_;
  75
  76
  77     // Private static functions
  78
  79         //- Greater element comparison
  80         inline static bool greater(const Type& a, const Type& b)
  81         {
  82             return a > b;
  83         }
  84
  85
  86     // Private Member Functions
  87
  88         //- Disallow default bitwise copy construct
  89         PriorityList(const PriorityList<Type>&);
  90
  91         //- Disallow default bitwise assignment
  92         void operator=(const PriorityList<Type>&);
  93
  94
  95         //- Sort list
  96         void sortList();
  97
  98         //- Bisection sort
  99         void bisectionSort(const label startIndex);
 100
 101         //- Sort upwards using bisection with root i
 102         void sortUpwards(const label startIndex);
 103
 104
 105 public:
 106
 107     // Constructors
 108
 109         //- Construct given capacity
 110         PriorityList(const label capacity);
 111
 112
 113     // Destructor - default
 114
 115
 116     // Member Functions
 117
 118         //- Return size
 119         label size() const
 120         {
 121             return size_;
 122         }
 123
 124         //- Is the list empty?
 125         bool empty() const
 126         {
 127             return size_ <= 0;
 128         }
 129
 130         //- Return indices
 131         const labelList& indices() const
 132         {
 133             return indices_;
 134         }
 135
 136         //- Return weights
 137         const List<Type>& weights() const
 138         {
 139             return weights_;
 140         }
 141
 142
 143         //- Return index with highest weight and remove
 144         label removeHead();
 145
 146         //- Set element with weight
 147         void set(const label i, const Type& value);
 148
 149         //- Update weight
 150         void updateWeight(const label i, const Type& newWeight);
 151 };
 152
 153
 154 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 155
 156 } // End namespace Foam
 157
 158 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 159
 160 #ifdef NoRepository
 161 #   include "PriorityList.C"
 162 #endif
 163
 164 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 165
 166 #endif
 167
 168 // ************************************************************************* //