All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
binaryTree.H
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration | Website: https://openfoam.org
5  \\ / A nd | Copyright (C) 2016-2021 OpenFOAM Foundation
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::binaryTree
26 
27 Description
28 
29  Data storage of the chemistryOnLineLibrary according to a binary
30  tree structure.
31 
32  0 (root node)
33  / \
34  0 0
35  / \ / \
36  L R L 0
37  / \
38  L R
39 
40  L: leafLeft_
41  R: leafRight_
42 
43 \*---------------------------------------------------------------------------*/
44 
45 #ifndef binaryTree_H
46 #define binaryTree_H
47 
48 #include "binaryNode.H"
49 #include "chemPointISAT.H"
50 
51 namespace Foam
52 {
53 
54 template<class ThermoType>
55 class TDACChemistryModel;
56 
57 template<class ThermoType>
58 class binaryTree
59 {
60 public:
61 
62  // Public Typedefs
63 
66 
67 
68 private:
69 
70  // Private Data
71 
72  //- Reference to the chemistryModel
74 
75  //- Root node of the binary tree
76  bn *root_;
77 
78  //- Maximum number of elements in the binary tree
79  label maxNLeafs_;
80 
81  //- Size of the BST (= number of chemPoint stored)
82  label size_;
83 
84  //- Secondary retrieve search variables
85  label n2ndSearch_;
86 
87  //- Secondary retrieve search variables
88  label max2ndSearch_;
89 
90 
91  // Private Member Functions
92 
93  //- Insert new node at the position of phi0. phi0 should be already
94  // attached to another node or the pointer to it will be lost.
95  void insertNode(chP*& phi0, bn*& newNode);
96 
97  //- Perform a search in the subtree starting from the subtree node y.
98  // This search continues to use the hyperplane to walk the tree.
99  // If covering EOA is found return true and x points to the chemPoint.
100  bool inSubTree
101  (
102  const scalarField& phiq,
103  bn* y,
104  chP* x
105  );
106 
107  void deleteSubTree(binaryNode<ThermoType>* subTreeRoot);
108 
109  inline void deleteSubTree()
110  {
111  deleteSubTree(root_);
112  }
113 
114  //- Replace the binaryNode u with v
115  void transplant(bn* u, bn* v);
116 
117  chP* chemPSibling(bn* y);
118 
119  chP* chemPSibling(chP* x);
120 
121  bn* nodeSibling(bn* y);
122 
123  bn* nodeSibling(chP* x);
124 
125  void deleteAllNode(bn* subTreeRoot);
126 
127  dictionary coeffsDict_;
128 
129 
130 public:
131 
132  //- Constructors
133 
134  //- Construct from dictionary and chemistryOnLineLibrary
135  binaryTree
136  (
138  dictionary coeffsDict
139  );
140 
141  //- Member functions
143  inline label size()
144  {
145  return size_;
146  }
147 
148  //- Computes iteratively the depth of the subTree
149  label depth(bn* subTreeRoot);
151  inline label depth()
152  {
153  return depth(root_);
154  }
156  inline bn* root()
157  {
158  return root_;
159  }
161  inline label maxNLeafs()
162  {
163  return maxNLeafs_;
164  }
165 
166  // Insert a new leaf starting from the parent node of phi0
167  // Parameters: phi0 the leaf to replace by a node
168  // phiq the new composition to store
169  // Rphiq the mapping of the new composition point
170  // A the mapping gradient matrix
171  // B the matrix used to initialise the EOA
172  // nCols the size of the matrix
173  // Returns: void
174  // Description :
175  //1) Create a new leaf with the data to initialise the EOA and to
176  // retrieve the mapping by linear interpolation (the EOA is
177  // initialise in the chemPoint constructor)
178  //2) Get the parent node of phi0 and connect a new node in place of the
179  // leaf of phi0. This new node is constructed with phi0 on the left
180  // and phiq on the right (the hyperplane is computed inside the
181  // binaryNode constructor)
182  void insertNewLeaf
183  (
184  const scalarField& phiq,
185  const scalarField& Rphiq,
186  const scalarSquareMatrix& A,
187  const scalarField& scaleFactor,
188  const scalar& epsTol,
189  const label nCols,
190  chP*& phi0
191  );
192 
193  // Search the binaryTree until the nearest leaf of a specified
194  // leaf is found.
195  void binaryTreeSearch
196  (
197  const scalarField& phiq,
198  bn* node,
199  chP*& nearest
200  );
201 
202  // Perform a secondary binary tree search starting from a failed
203  // chemPoint x, with a depth-first search algorithm
204  // If another candidate is found return true and x points to the chemP
205  bool secondaryBTSearch(const scalarField& phiq, chP*& x);
206 
207  //- Delete a leaf from the binary tree and reshape the binary tree for
208  // the following binary tree search
209  // Return the index in the nodeList of the removed node
210  // (-1 when no node)
211  void deleteLeaf(chP*& phi0);
212 
213  //- Cheap balance function
214  // This function just roughly separate the space in two parts
215  // with a hyperplane which separate the two extreme chemPoint in the
216  // direction of the maximum the variance
217  // Then, it repopulate the tree with this hyperplane stored at the root
218  // and by inserting the chemPoint in increasing order of value in that
219  // direction
220  void balance();
222  inline void deleteAllNode()
223  {
224  deleteAllNode(root_);
225  }
226 
227  chP* treeMin(bn* subTreeRoot);
229  inline chP* treeMin()
230  {
231  return treeMin(root_);
232  }
233 
234  chP* treeSuccessor(chP* x);
235 
236  //- Removes every entries of the tree and delete the associated objects
237  void clear();
238 
239  //- ListFull
240  bool isFull();
241 
242  void resetNumRetrieve();
243 };
244 
245 
246 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
247 
248 } // End namespace Foam
249 
250 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
251 
252 #ifdef NoRepository
253  #include "binaryTree.C"
254 #endif
255 
256 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
257 
258 #endif
259 
260 // ************************************************************************* //
Extends standardChemistryModel by adding the TDAC method.
void resetNumRetrieve()
Definition: binaryTree.C:818
intWM_LABEL_SIZE_t label
A label is an int32_t or int64_t as specified by the pre-processor macro WM_LABEL_SIZE.
Definition: label.H:59
A list of keyword definitions, which are a keyword followed by any number of values (e...
Definition: dictionary.H:156
void balance()
Cheap balance function.
Definition: binaryTree.C:635
void insertNewLeaf(const scalarField &phiq, const scalarField &Rphiq, const scalarSquareMatrix &A, const scalarField &scaleFactor, const scalar &epsTol, const label nCols, chP *&phi0)
Definition: binaryTree.C:378
Leaf of the binary tree. The chemPoint stores the composition &#39;phi&#39;, the mapping of this composition ...
bool secondaryBTSearch(const scalarField &phiq, chP *&x)
Definition: binaryTree.C:515
void binaryTreeSearch(const scalarField &phiq, bn *node, chP *&nearest)
Definition: binaryTree.C:461
scalar y
Data storage of the chemistryOnLineLibrary according to a binary tree structure.
Definition: binaryTree.H:57
void clear()
Removes every entries of the tree and delete the associated objects.
Definition: binaryTree.C:797
Node of the binary tree.
Definition: binaryNode.H:49
basicChemistryModel & chemistry
binaryNode< ThermoType > bn
Definition: binaryTree.H:63
chemPointISAT< ThermoType > chP
Definition: binaryTree.H:64
label size()
Member functions.
Definition: binaryTree.H:142
label maxNLeafs()
Definition: binaryTree.H:160
void deleteLeaf(chP *&phi0)
Delete a leaf from the binary tree and reshape the binary tree for.
Definition: binaryTree.C:572
bool isFull()
ListFull.
Definition: binaryTree.C:811
chP * treeSuccessor(chP *x)
Definition: binaryTree.C:745
const dimensionedScalar phi0
Magnetic flux quantum: default SI units: [Wb].
binaryTree(TDACChemistryModel< ThermoType > &chemistry, dictionary coeffsDict)
Constructors.
Definition: binaryTree.C:339
void deleteAllNode()
Definition: binaryTree.H:221
Namespace for OpenFOAM.