aGrUM 3.1.1
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-2026 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-2026 *
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
41#pragma once
42
43
50
51#include <agrum/base/core/binTreeNode.h> // to ease IDE parser
52#ifndef DOXYGEN_SHOULD_SKIP_THIS
53
54namespace gum {
55
56 template < typename Val >
57 BinTreeNode< Val >::BinTreeNode(const Val& v) :
58 val_(v), parent_(nullptr), parent_dir_(BinTreeDir::NO_PARENT) {
59 GUM_CONSTRUCTOR(BinTreeNode);
60
61 // set the children
62 children_[0] = nullptr;
63 children_[1] = nullptr;
64 }
65
66 template < typename Val >
67 BinTreeNode< Val >::BinTreeNode(const BinTreeNode< Val >& from) :
68 val_(from.val_), parent_(nullptr), parent_dir_(BinTreeDir::NO_PARENT) {
69 GUM_CONS_CPY(BinTreeNode);
70
71 // set the children
72 children_[0] = nullptr;
73 children_[1] = nullptr;
74 }
75
76 template < typename Val >
77 BinTreeNode< Val >::~BinTreeNode() {
78 GUM_DESTRUCTOR(BinTreeNode);
79
80 // update the tree accordingly to the removal of this
81 if (parent_ != nullptr)
82 parent_->children_[static_cast< int >(parent_dir_)]
83 = nullptr; // parent_dir can not be NO_PARENT (... sure ?)
84
85 if (children_[0] != nullptr) {
86 children_[0]->parent_ = nullptr;
87 children_[0]->parent_dir_ = BinTreeDir::NO_PARENT;
88 }
89
90 if (children_[1] != nullptr) {
91 children_[1]->parent_ = nullptr;
92 children_[1]->parent_dir_ = BinTreeDir::NO_PARENT;
93 }
94 }
95
98
99 template < typename Val >
100 BinTreeNode< Val >& BinTreeNode< Val >::operator=(const BinTreeNode< Val >& from) {
101 // avoid self assignment
102 if (this != &from) {
103 GUM_OP_CPY(BinTreeNode);
104 val_ = from.val_;
105 }
106
107 return *this;
108 }
109
110 template < typename Val >
111 Val& BinTreeNode< Val >::value() {
112 return val_;
113 }
114
115 template < typename Val >
116 Val& BinTreeNode< Val >::operator*() {
117 return val_;
118 }
119
120 template < typename Val >
121 BinTreeNode< Val >* BinTreeNode< Val >::child(BinTreeDir dir) const {
122 return children_[static_cast< int >(dir)];
123 }
124
125 template < typename Val >
126 BinTreeNode< Val >* BinTreeNode< Val >::leftChild() const {
127 return children_[static_cast< int >(BinTreeDir::LEFT_CHILD)];
128 }
129
130 template < typename Val >
131 BinTreeNode< Val >* BinTreeNode< Val >::rightChild() const {
132 return children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)];
133 }
134
135 template < typename Val >
136 BinTreeNode< Val >* BinTreeNode< Val >::parent() const {
137 return parent_;
138 }
139
140 template < typename Val >
141 BinTreeDir BinTreeNode< Val >::parentDir() const {
142 return parent_dir_;
143 }
144
145 template < typename Val >
146 void BinTreeNode< Val >::insertLeftChild(BinTreeNode< Val >& new_child) {
147 if (new_child.parent_ != nullptr) {
148 GUM_ERROR(DuplicateElement, "this child already has a parent in the BST")
149 }
150
151 if (children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] != nullptr) {
152 GUM_ERROR(DuplicateElement, "this child already has a parent in the BST")
153 }
154
155 // proceed to the chaining
156 new_child.parent_ = this;
157 new_child.parent_dir_ = BinTreeDir::LEFT_CHILD;
158 children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] = &new_child;
159 }
160
161 template < typename Val >
162 BinTreeNode< Val >* BinTreeNode< Val >::insertLeftChild(const Val& val) {
163 if (children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] != nullptr) {
164 GUM_ERROR(DuplicateElement, "this child already has a parent in the BST")
165 }
166
167 BinTreeNode< Val >* new_child = new BinTreeNode< Val >(val);
168
169 // proceed to the chaining
170 new_child->parent_ = this;
171 new_child->parent_dir_ = BinTreeDir::LEFT_CHILD;
172 children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] = new_child;
173
174 return new_child;
175 }
176
177 template < typename Val >
178 void BinTreeNode< Val >::insertRightChild(BinTreeNode< Val >& new_child) {
179 if (new_child.parent_ != nullptr) {
180 GUM_ERROR(DuplicateElement, "this child already has a parent in the BST")
181 }
182
183 if (children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] != nullptr) {
184 GUM_ERROR(DuplicateElement, "this node already has a right child")
185 }
186
187 // proceed to the chaining
188 new_child.parent_ = this;
189 new_child.parent_dir_ = BinTreeDir::RIGHT_CHILD;
190 children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] = &new_child;
191 }
192
193 template < typename Val >
194 BinTreeNode< Val >* BinTreeNode< Val >::insertRightChild(const Val& val) {
195 if (children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] != nullptr) {
196 GUM_ERROR(DuplicateElement, "this node already has a right child")
197 }
198
199 BinTreeNode< Val >* new_child = new BinTreeNode< Val >(val);
200
201 // proceed to the chaining
202 new_child->parent_ = this;
203 new_child->parent_dir_ = BinTreeDir::RIGHT_CHILD;
204 children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] = new_child;
205
206 return new_child;
207 }
208
209 template < typename Val >
210 void BinTreeNode< Val >::insertChild(BinTreeNode< Val >& new_child, BinTreeDir child_dir) {
211 if (new_child.parent_ != nullptr) {
212 GUM_ERROR(DuplicateElement, "this child has already a parent")
213 }
214
215 if (children_[static_cast< int >(child_dir)] != nullptr) {
216 GUM_ERROR(DuplicateElement, "this node has already this child")
217 }
218
219 // proceed to the chaining
220 new_child.parent_ = this;
221 new_child.parent_dir_ = child_dir;
222 children_[static_cast< int >(child_dir)] = &new_child;
223 }
224
225 template < typename Val >
226 BinTreeNode< Val >* BinTreeNode< Val >::insertChild(const Val& val, BinTreeDir child_dir) {
227 if (children_[static_cast< int >(child_dir)] != nullptr) {
228 GUM_ERROR(DuplicateElement, "this node has already this child")
229 }
230
231 BinTreeNode< Val >* new_child = new BinTreeNode< Val >(val);
232
233 // proceed to the chaining
234 new_child->parent_ = this;
235 new_child->parent_dir_ = child_dir;
236 children_[static_cast< int >(child_dir)] = new_child;
237
238 return new_child;
239 }
240
241 template < typename Val >
242 void BinTreeNode< Val >::eraseLeftLink() {
243 if (children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] != nullptr) {
244 children_[static_cast< int >(BinTreeDir::LEFT_CHILD)]->parent_ = nullptr;
245 children_[static_cast< int >(BinTreeDir::LEFT_CHILD)]->parent_dir_ = BinTreeDir::NO_PARENT;
246 children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] = nullptr;
247 }
248 }
249
250 template < typename Val >
251 void BinTreeNode< Val >::eraseRightLink() {
252 if (children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] != nullptr) {
253 children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)]->parent_ = nullptr;
254 children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)]->parent_dir_ = BinTreeDir::NO_PARENT;
255 children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] = nullptr;
256 }
257 }
258
259 template < typename Val >
260 void BinTreeNode< Val >::eraseLink(BinTreeDir tree_dir) {
261 if (children_[static_cast< int >(tree_dir)] != nullptr) {
262 children_[static_cast< int >(tree_dir)]->parent_ = nullptr;
263 children_[static_cast< int >(tree_dir)]->parent_dir_ = BinTreeDir::NO_PARENT;
264 children_[static_cast< int >(tree_dir)] = nullptr;
265 }
266 }
267
268 template < typename Val >
269 BinTreeNode< Val >* BinTreeNode< Val >::leftmostNode() const {
270 BinTreeNode< Val >* node = const_cast< BinTreeNode< Val >* >(this);
271
272 while (node->children_[static_cast< int >(BinTreeDir::LEFT_CHILD)] != nullptr)
273 node = node->children_[static_cast< int >(BinTreeDir::LEFT_CHILD)];
274
275 return node;
276 }
277
278 template < typename Val >
279 BinTreeNode< Val >* BinTreeNode< Val >::rightmostNode() const {
280 BinTreeNode< Val >* node = const_cast< BinTreeNode< Val >* >(this);
281
282 while (node->children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)] != nullptr)
283 node = node->children_[static_cast< int >(BinTreeDir::RIGHT_CHILD)];
284
285 return node;
286 }
287
288 template < typename Val >
289 BinTreeNode< Val >* BinTreeNode< Val >::root() const {
290 BinTreeNode< Val >* node = const_cast< BinTreeNode< Val >* >(this);
291
292 while (node->parent_ != nullptr)
293 node = node->parent_;
294
295 return node;
296 }
297
298} // namespace gum
299
300#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:76
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 3.1.1

© PHW&CG&others - 2022
DoXyGeN 1.16.1