aGrUM 2.3.2
a C++ library for (probabilistic) graphical models
binTreeNode_tpl.h
Go to the documentation of this file.
1/****************************************************************************
2 * This file is part of the aGrUM/pyAgrum library. *
3 * *
4 * Copyright (c) 2005-2025 by *
5 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
6 * - Christophe GONZALES(_at_AMU) *
7 * *
8 * The aGrUM/pyAgrum library is free software; you can redistribute it *
9 * and/or modify it under the terms of either : *
10 * *
11 * - the GNU Lesser General Public License as published by *
12 * the Free Software Foundation, either version 3 of the License, *
13 * or (at your option) any later version, *
14 * - the MIT license (MIT), *
15 * - or both in dual license, as here. *
16 * *
17 * (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html) *
18 * *
19 * This aGrUM/pyAgrum library is distributed in the hope that it will be *
20 * useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, *
21 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
22 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE *
23 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, *
25 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR *
26 * OTHER DEALINGS IN THE SOFTWARE. *
27 * *
28 * See LICENCES for more details. *
29 * *
30 * SPDX-FileCopyrightText: Copyright 2005-2025 *
31 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
32 * - Christophe GONZALES(_at_AMU) *
33 * SPDX-License-Identifier: LGPL-3.0-or-later OR MIT *
34 * *
35 * Contact : info_at_agrum_dot_org *
36 * homepage : http://agrum.gitlab.io *
37 * gitlab : https://gitlab.com/agrumery/agrum *
38 * *
39 ****************************************************************************/
40#pragma once
41
42
49
50#ifndef DOXYGEN_SHOULD_SKIP_THIS
51
52namespace gum {
53
54 template < typename Val >
55 INLINE BinTreeNode< Val >::BinTreeNode(const Val& v) :
56 val_(v), parent_(nullptr), parent_dir_(BinTreeDir::NO_PARENT) {
57 GUM_CONSTRUCTOR(BinTreeNode);
58
59 // set the children
60 children_[0] = nullptr;
61 children_[1] = nullptr;
62 }
63
64 template < typename Val >
65 INLINE BinTreeNode< Val >::BinTreeNode(const BinTreeNode< Val >& from) :
66 val_(from.val_), parent_(nullptr), parent_dir_(BinTreeDir::NO_PARENT) {
67 GUM_CONS_CPY(BinTreeNode);
68
69 // set the children
70 children_[0] = nullptr;
71 children_[1] = nullptr;
72 }
73
74 template < typename Val >
75 INLINE BinTreeNode< Val >::~BinTreeNode() {
76 GUM_DESTRUCTOR(BinTreeNode);
77
78 // update the tree accordingly to the removal of this
79 if (parent_ != nullptr)
80 parent_->children_[static_cast< int >(parent_dir_)]
81 = nullptr; // parent_dir can not be NO_PARENT (... sure ?)
82
83 if (children_[0] != nullptr) {
84 children_[0]->parent_ = nullptr;
85 children_[0]->parent_dir_ = BinTreeDir::NO_PARENT;
86 }
87
88 if (children_[1] != nullptr) {
89 children_[1]->parent_ = nullptr;
90 children_[1]->parent_dir_ = BinTreeDir::NO_PARENT;
91 }
92 }
93
96
97 template < typename Val >
98 INLINE BinTreeNode< Val >& BinTreeNode< Val >::operator=(const BinTreeNode< Val >& from) {
99 // avoid self assignment
100 if (this != &from) {
101 GUM_OP_CPY(BinTreeNode);
102 val_ = from.val_;
103 }
104
105 return *this;
106 }
107
108 template < typename Val >
109 INLINE Val& BinTreeNode< Val >::value() {
110 return val_;
111 }
112
113 template < typename Val >
114 INLINE Val& BinTreeNode< Val >::operator*() {
115 return val_;
116 }
117
118 template < typename Val >
119 INLINE BinTreeNode< Val >* BinTreeNode< Val >::child(BinTreeDir dir) const {
120 return children_[static_cast< int >(dir)];
121 }
122
123 template < typename Val >
124 INLINE BinTreeNode< Val >* BinTreeNode< Val >::leftChild() const {
125 return children_[static_cast< int >(BinTreeDir::LEFT_CHILD)];
126 }
127
128 template < typename Val >
129 INLINE BinTreeNode< Val >* BinTreeNode< Val >::rightChild() const {
130 return children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)];
131 }
132
133 template < typename Val >
134 INLINE BinTreeNode< Val >* BinTreeNode< Val >::parent() const {
135 return parent_;
136 }
137
138 template < typename Val >
139 INLINE BinTreeDir BinTreeNode< Val >::parentDir() const {
140 return parent_dir_;
141 }
142
143 template < typename Val >
144 INLINE void BinTreeNode< Val >::insertLeftChild(BinTreeNode< Val >& new_child) {
145 if (new_child.parent_ != nullptr) {
146 GUM_ERROR(DuplicateElement, "this child already has a parent in the BST")
147 }
148
149 if (children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] != nullptr) {
150 GUM_ERROR(DuplicateElement, "this child already has a parent in the BST")
151 }
152
153 // proceed to the chaining
154 new_child.parent_ = this;
155 new_child.parent_dir_ = BinTreeDir::LEFT_CHILD;
156 children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] = &new_child;
157 }
158
159 template < typename Val >
160 INLINE BinTreeNode< Val >* BinTreeNode< Val >::insertLeftChild(const Val& val) {
161 if (children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] != nullptr) {
162 GUM_ERROR(DuplicateElement, "this child already has a parent in the BST")
163 }
164
165 BinTreeNode< Val >* new_child = new BinTreeNode< Val >(val);
166
167 // proceed to the chaining
168 new_child->parent_ = this;
169 new_child->parent_dir_ = BinTreeDir::LEFT_CHILD;
170 children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] = new_child;
171
172 return new_child;
173 }
174
175 template < typename Val >
176 INLINE void BinTreeNode< Val >::insertRightChild(BinTreeNode< Val >& new_child) {
177 if (new_child.parent_ != nullptr) {
178 GUM_ERROR(DuplicateElement, "this child already has a parent in the BST")
179 }
180
181 if (children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] != nullptr) {
182 GUM_ERROR(DuplicateElement, "this node already has a right child")
183 }
184
185 // proceed to the chaining
186 new_child.parent_ = this;
187 new_child.parent_dir_ = BinTreeDir::RIGHT_CHILD;
188 children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] = &new_child;
189 }
190
191 template < typename Val >
192 INLINE BinTreeNode< Val >* BinTreeNode< Val >::insertRightChild(const Val& val) {
193 if (children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] != nullptr) {
194 GUM_ERROR(DuplicateElement, "this node already has a right child")
195 }
196
197 BinTreeNode< Val >* new_child = new BinTreeNode< Val >(val);
198
199 // proceed to the chaining
200 new_child->parent_ = this;
201 new_child->parent_dir_ = BinTreeDir::RIGHT_CHILD;
202 children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] = new_child;
203
204 return new_child;
205 }
206
207 template < typename Val >
208 INLINE void BinTreeNode< Val >::insertChild(BinTreeNode< Val >& new_child, BinTreeDir child_dir) {
209 if (new_child.parent_ != nullptr) {
210 GUM_ERROR(DuplicateElement, "this child has already a parent")
211 }
212
213 if (children_[static_cast< int >(child_dir)] != nullptr) {
214 GUM_ERROR(DuplicateElement, "this node has already this child")
215 }
216
217 // proceed to the chaining
218 new_child.parent_ = this;
219 new_child.parent_dir_ = child_dir;
220 children_[static_cast< int >(child_dir)] = &new_child;
221 }
222
223 template < typename Val >
224 INLINE BinTreeNode< Val >* BinTreeNode< Val >::insertChild(const Val& val, BinTreeDir child_dir) {
225 if (children_[static_cast< int >(child_dir)] != nullptr) {
226 GUM_ERROR(DuplicateElement, "this node has already this child")
227 }
228
229 BinTreeNode< Val >* new_child = new BinTreeNode< Val >(val);
230
231 // proceed to the chaining
232 new_child->parent_ = this;
233 new_child->parent_dir_ = child_dir;
234 children_[static_cast< int >(child_dir)] = new_child;
235
236 return new_child;
237 }
238
239 template < typename Val >
240 INLINE void BinTreeNode< Val >::eraseLeftLink() {
241 if (children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] != nullptr) {
242 children_[static_cast< int >(BinTreeDir::LEFT_CHILD)]->parent_ = nullptr;
243 children_[static_cast< int >(BinTreeDir::LEFT_CHILD)]->parent_dir_ = BinTreeDir::NO_PARENT;
244 children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] = nullptr;
245 }
246 }
247
248 template < typename Val >
249 INLINE void BinTreeNode< Val >::eraseRightLink() {
250 if (children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] != nullptr) {
251 children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)]->parent_ = nullptr;
252 children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)]->parent_dir_ = BinTreeDir::NO_PARENT;
253 children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] = nullptr;
254 }
255 }
256
257 template < typename Val >
258 INLINE void BinTreeNode< Val >::eraseLink(BinTreeDir tree_dir) {
259 if (children_[static_cast< int >(tree_dir)] != nullptr) {
260 children_[static_cast< int >(tree_dir)]->parent_ = nullptr;
261 children_[static_cast< int >(tree_dir)]->parent_dir_ = BinTreeDir::NO_PARENT;
262 children_[static_cast< int >(tree_dir)] = nullptr;
263 }
264 }
265
266 template < typename Val >
267 INLINE BinTreeNode< Val >* BinTreeNode< Val >::leftmostNode() const {
268 BinTreeNode< Val >* node = const_cast< BinTreeNode< Val >* >(this);
269
270 while (node->children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] != nullptr)
271 node = node->children_[static_cast< int >(BinTreeDir::LEFT_CHILD)];
272
273 return node;
274 }
275
276 template < typename Val >
277 INLINE BinTreeNode< Val >* BinTreeNode< Val >::rightmostNode() const {
278 BinTreeNode< Val >* node = const_cast< BinTreeNode< Val >* >(this);
279
280 while (node->children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] != nullptr)
281 node = node->children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)];
282
283 return node;
284 }
285
286 template < typename Val >
287 INLINE BinTreeNode< Val >* BinTreeNode< Val >::root() const {
288 BinTreeNode< Val >* node = const_cast< BinTreeNode< Val >* >(this);
289
290 while (node->parent_ != nullptr)
291 node = node->parent_;
292
293 return node;
294 }
295
296} // namespace gum
297
298#endif // DOXYGEN_SHOULD_SKIP_THIS
gum::BinTreeNode::BinTreeNode
BinTreeNode(const Val &v)
Basic constructor: a node without parent nor children.
DuplicateElement
Exception : a similar element already exists.
GUM_ERROR
#define GUM_ERROR(type, msg)
Definition exceptions.h:72
gum
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
gum::BinTreeDir
BinTreeDir
The direction of a given edge in a binary tree.
Definition binTreeNode.h:56
aGrUM 2.3.2

© PHW&CG&others - 2022
DoXyGeN 1.16.1