src/foam/containers/Lists/PriorityList/PriorityList.C

   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
  30 Author
  31     Hrvoje Jasak, Wikki Ltd.  All rights reserved
  32
  33 \*---------------------------------------------------------------------------*/
  34
  35 #include "PriorityList.H"
  36
  37 // * * * * * * * * * * * * * Private Member Functions  * * * * * * * * * * * //
  38
  39 template<class Type>
  40 void Foam::PriorityList<Type>::sortList()
  41 {
  42     // Reset indices and sorted indices
  43     for (label i = 0; i < size_; i++)
  44     {
  45         indices_[i] = i;
  46         sortedIndices_[i] = i;
  47     }
  48
  49     for (label i = size_/2 - 1; i >= 0; i--)
  50     {
  51         this->bisectionSort(i);
  52     }
  53
  54     listSorted_ = true;
  55 }
  56
  57
  58 template<class Type>
  59 void Foam::PriorityList<Type>::bisectionSort(const label startIndex)
  60 {
  61     label i = startIndex;
  62
  63     for (;;)
  64     {
  65         // Find largest node and left and right children
  66         label n = i;
  67         label il = 2*i + 1;
  68         label ir = il + 1;
  69
  70         if
  71         (
  72             il < size_
  73          && greater(weights_[indices_[il]], weights_[indices_[n]])
  74         )
  75         {
  76             n = il;
  77         }
  78
  79         if
  80         (
  81             ir < size_
  82          && greater(weights_[indices_[ir]], weights_[indices_[n]])
  83         )
  84         {
  85             n = ir;
  86         }
  87
  88         // End of bisection
  89         if (n == i) break;
  90
  91         // Swap i with largest n
  92         Foam::Swap(indices_[i], indices_[n]);
  93
  94         // Swap positions in sorted index list
  95         sortedIndices_[indices_[i]] = i;
  96         sortedIndices_[indices_[n]] = n;
  97
  98         // Update for next position
  99         i = n;
 100     }
 101 }
 102
 103
 104 template<class Type>
 105 void Foam::PriorityList<Type>::sortUpwards(const label startIndex)
 106 {
 107     // Set root
 108     label i = startIndex;
 109
 110     label n = (i - 1)/2;
 111
 112     while (i > 0 && greater(weights_[indices_[i]], weights_[indices_[n]]))
 113     {
 114         // Swap node i and n if not in proper order
 115         Foam::Swap(indices_[i], indices_[n]);
 116
 117         // Swap positions in sorted index list
 118         sortedIndices_[indices_[i]] = i;
 119         sortedIndices_[indices_[n]] = n;
 120
 121         // Update for next position
 122         i = n;
 123         n = (i - 1)/2;
 124     }
 125 }
 126
 127
 128 // * * * * * * * * * * * * * * * * Constructors  * * * * * * * * * * * * * * //
 129
 130 // Construct given capacity
 131 template<class Type>
 132 Foam::PriorityList<Type>::PriorityList(const label capacity)
 133 :
 134     indices_(capacity),
 135     weights_(capacity),
 136     sortedIndices_(capacity),
 137     size_(capacity),
 138     listSorted_(false)
 139 {}
 140
 141
 142 // * * * * * * * * * * * * * * * Member Functions  * * * * * * * * * * * * * //
 143
 144 template<class Type>
 145 Foam::label Foam::PriorityList<Type>::removeHead()
 146 {
 147     if (!listSorted_)
 148     {
 149         this->sortList();
 150     }
 151
 152     label maxIndex = indices_[0];
 153
 154     if (--size_ > 0)
 155     {
 156         Foam::Swap(indices_[0], indices_[size_]);
 157         sortedIndices_[indices_[0]] = 0;
 158         this->bisectionSort(0);
 159     }
 160
 161     return maxIndex;
 162 }
 163
 164
 165 template<class Type>
 166 void Foam::PriorityList<Type>::set
 167 (
 168     const label i,
 169     const Type& value
 170 )
 171 {
 172     weights_[i] = value;
 173
 174     // List is no longer sorted
 175     listSorted_ = false;
 176 }
 177
 178
 179 template<class Type>
 180 void Foam::PriorityList<Type>::updateWeight
 181 (
 182     const label i,
 183     const Type& newWeight
 184 )
 185 {
 186     if (!listSorted_)
 187     {
 188         this->sortList();
 189     }
 190
 191     Type delta = newWeight - weights_[i];
 192
 193     weights_[i] = newWeight;
 194
 195     if (greater(delta, pTraits<Type>::zero))
 196     {
 197         this->sortUpwards(sortedIndices_[i]);
 198     }
 199     else
 200     {
 201         this->bisectionSort(sortedIndices_[i]);
 202     }
 203 }
 204
 205
 206 // ************************************************************************* //