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-2019 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 CompType, class ThermoType>
55 class TDACChemistryModel;
56 
57 template<class CompType, class ThermoType>
58 class binaryTree
59 {
60 
61 public:
62 
65 
66 
67 private:
68 
69  //- Reference to the chemistryModel
71 
72  //- Root node of the binary tree
73  bn *root_;
74 
75  //- Maximum number of elements in the binary tree
76  label maxNLeafs_;
77 
78  //- Size of the BST (= number of chemPoint stored)
79  label size_;
80 
81  //- Secondary retrieve search variables
82  label n2ndSearch_;
83  label max2ndSearch_;
84 
85  //- Insert new node at the position of phi0
86  // phi0 should be already attached to another node or the pointer to it
87  // will be lost
88  void insertNode
89  (
90  chP*& phi0,
91  bn*& newNode
92  );
93 
94  //- Perform a search in the subtree starting from the subtree node y
95  // This search continues to use the hyperplane to walk the tree
96  // If covering EOA is found return true and x points to the chemPoint
97  bool inSubTree
98  (
99  const scalarField& phiq,
100  bn* y,
101  chP* x
102  );
103 
104  void deleteSubTree(binaryNode<CompType, ThermoType>* subTreeRoot);
105 
106  inline void deleteSubTree()
107  {
108  deleteSubTree(root_);
109  }
110 
111  //- Replace the binaryNode u with v
112  void transplant(bn* u, bn* v);
113 
114  chP* chemPSibling(bn* y);
115  chP* chemPSibling(chP* x);
116 
117  bn* nodeSibling(bn* y);
118  bn* nodeSibling(chP* x);
119 
120  void deleteAllNode(bn* subTreeRoot);
121 
122  dictionary coeffsDict_;
123 
124 public:
125  //- Constructors
126 
127  //- Construct from dictionary and chemistryOnLineLibrary
128  binaryTree
129  (
131  dictionary coeffsDict
132  );
133 
134  //- Member functions
135  inline label size()
136  {
137  return size_;
138  }
139 
140  //- Computes iteratively the depth of the subTree
141  label depth(bn* subTreeRoot);
143  inline label depth()
144  {
145  return depth(root_);
146  }
148  inline bn* root()
149  {
150  return root_;
151  }
153  inline label maxNLeafs()
154  {
155  return maxNLeafs_;
156  }
157 
158  // Insert a new leaf starting from the parent node of phi0
159  // Parameters: phi0 the leaf to replace by a node
160  // phiq the new composition to store
161  // Rphiq the mapping of the new composition point
162  // A the mapping gradient matrix
163  // B the matrix used to initialize the EOA
164  // nCols the size of the matrix
165  // Returns: void
166  // Description :
167  //1) Create a new leaf with the data to initialize the EOA and to
168  // retrieve the mapping by linear interpolation (the EOA is
169  // initialize in the chemPoint constructor)
170  //2) Get the parent node of phi0 and connect a new node in place of the
171  // leaf of phi0. This new node is constructed with phi0 on the left
172  // and phiq on the right (the hyperplane is computed inside the
173  // binaryNode constructor)
174  void insertNewLeaf
175  (
176  const scalarField& phiq,
177  const scalarField& Rphiq,
178  const scalarSquareMatrix& A,
179  const scalarField& scaleFactor,
180  const scalar& epsTol,
181  const label nCols,
182  chP*& phi0
183  );
184 
185 
186 
187  // Search the binaryTree until the nearest leaf of a specified
188  // leaf is found.
189  void binaryTreeSearch
190  (
191  const scalarField& phiq,
192  bn* node,
193  chP*& nearest
194  );
195 
196  // Perform a secondary binary tree search starting from a failed
197  // chemPoint x, with a depth-first search algorithm
198  // If another candidate is found return true and x points to the chemP
199  bool secondaryBTSearch(const scalarField& phiq, chP*& x);
200 
201  //- Delete a leaf from the binary tree and reshape the binary tree for
202  // the following binary tree search
203  // Return the index in the nodeList of the removed node
204  // (-1 when no node)
205  void deleteLeaf(chP*& phi0);
206 
207  //- Cheap balance function
208  // This function just roughly separate the space in two parts
209  // with a hyperplane which separate the two extreme chemPoint in the
210  // direction of the maximum the variance
211  // Then, it repopulate the tree with this hyperplane stored at the root
212  // and by inserting the chemPoint in increasing order of value in that
213  // direction
214  void balance();
216  inline void deleteAllNode()
217  {
218  deleteAllNode(root_);
219  }
220 
221  chP* treeMin(bn* subTreeRoot);
223  inline chP* treeMin()
224  {
225  return treeMin(root_);
226  }
227 
228  chP* treeSuccessor(chP* x);
229 
230  //- Removes every entries of the tree and delete the associated objects
231  void clear();
232 
233  //- ListFull
234  bool isFull();
235 
236  void resetNumRetrieve();
237 };
238 
239 
240 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
241 
242 } // End namespace Foam
243 
244 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
245 
246 #ifdef NoRepository
247  #include "binaryTree.C"
248 #endif
249 
250 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
251 
252 #endif
253 
254 // ************************************************************************* //
void resetNumRetrieve()
Definition: binaryTree.C:824
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:158
chP * treeSuccessor(chP *x)
Definition: binaryTree.C:751
void balance()
Cheap balance function.
Definition: binaryTree.C:641
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:384
Leaf of the binary tree. The chemPoint stores the composition &#39;phi&#39;, the mapping of this composition ...
chemPointISAT< CompType, ThermoType > chP
Definition: binaryTree.H:63
bool secondaryBTSearch(const scalarField &phiq, chP *&x)
Definition: binaryTree.C:521
BasicChemistryModel< rhoReactionThermo > & chemistry
void binaryTreeSearch(const scalarField &phiq, bn *node, chP *&nearest)
Definition: binaryTree.C:467
scalar y
binaryNode< CompType, ThermoType > bn
Definition: binaryTree.H:62
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:803
Node of the binary tree.
Definition: binaryNode.H:49
const dimensionedScalar & phi0
Magnetic flux quantum: default SI units: [Wb].
binaryTree(TDACChemistryModel< CompType, ThermoType > &chemistry, dictionary coeffsDict)
Constructors.
Definition: binaryTree.C:345
label size()
Member functions.
Definition: binaryTree.H:134
label maxNLeafs()
Definition: binaryTree.H:152
void deleteLeaf(chP *&phi0)
Delete a leaf from the binary tree and reshape the binary tree for.
Definition: binaryTree.C:578
bool isFull()
ListFull.
Definition: binaryTree.C:817
void deleteAllNode()
Definition: binaryTree.H:215
Namespace for OpenFOAM.