28 #ifndef DOXYGEN_SHOULD_SKIP_THIS 32 template <
typename Val >
43 template <
typename Val >
54 template <
typename Val >
78 template <
typename Val >
80 operator=(
const BinTreeNode< Val >& from) {
90 template <
typename Val >
95 template <
typename Val >
100 template <
typename Val >
102 return _children[
static_cast< int >(dir)];
105 template <
typename Val >
110 template <
typename Val >
115 template <
typename Val >
120 template <
typename Val >
125 template <
typename Val >
127 if (new_child._parent) {
128 GUM_ERROR(DuplicateElement,
"this child already has a parent in the BST");
132 GUM_ERROR(DuplicateElement,
"this child already has a parent in the BST");
136 new_child._parent =
this;
141 template <
typename Val >
144 GUM_ERROR(DuplicateElement,
"this child already has a parent in the BST");
147 BinTreeNode< Val >* new_child =
new BinTreeNode< Val >(val);
150 new_child->_parent =
this;
157 template <
typename Val >
159 if (new_child._parent) {
160 GUM_ERROR(DuplicateElement,
"this child already has a parent in the BST");
164 GUM_ERROR(DuplicateElement,
"this node already has a right child");
168 new_child._parent =
this;
173 template <
typename Val >
176 GUM_ERROR(DuplicateElement,
"this node already has a right child");
179 BinTreeNode< Val >* new_child =
new BinTreeNode< Val >(val);
182 new_child->_parent =
this;
189 template <
typename Val >
192 if (new_child._parent) {
193 GUM_ERROR(DuplicateElement,
"this child has already a parent");
196 if (
_children[static_cast< int >(child_dir)]) {
197 GUM_ERROR(DuplicateElement,
"this node has already this child");
201 new_child._parent =
this;
202 new_child._parent_dir = child_dir;
203 _children[
static_cast< int >(child_dir)] = &new_child;
206 template <
typename Val >
207 INLINE BinTreeNode< Val >*
209 if (
_children[static_cast< int >(child_dir)]) {
210 GUM_ERROR(DuplicateElement,
"this node has already this child");
213 BinTreeNode< Val >* new_child =
new BinTreeNode< Val >(val);
216 new_child->_parent =
this;
217 new_child->_parent_dir = child_dir;
218 _children[
static_cast< int >(child_dir)] = new_child;
223 template <
typename Val >
233 template <
typename Val >
243 template <
typename Val >
245 if (
_children[static_cast< int >(tree_dir)]) {
248 _children[
static_cast< int >(tree_dir)] =
nullptr;
252 template <
typename Val >
254 BinTreeNode< Val >* node =
const_cast< BinTreeNode< Val >*
>(
this);
262 template <
typename Val >
264 BinTreeNode< Val >* node =
const_cast< BinTreeNode< Val >*
>(
this);
272 template <
typename Val >
274 BinTreeNode< Val >* node =
const_cast< BinTreeNode< Val >*
>(
this);
276 while (node->_parent)
277 node = node->_parent;
284 #endif // DOXYGEN_SHOULD_SKIP_THIS BinTreeNode< Val > * child(BinTreeDir dir) const
Returns the given child of a node.
Val & value()
Returns the value stored in a node of the binary search tree.
BinTreeNode< Val > * leftmostNode() const
Returns the leftmost node of the current tree.
Val _val
The value stored in a node of the tree.
BinTreeNode< Val > * insertLeftChild(const Val &val)
Adds a new left child to the current node.
void eraseLeftLink()
Remove the link between the current node and its left child.
BinTreeNode< Val > * leftChild() const
Returns the given child of a node.
BinTreeNode< Val > * _children[2]
The children of the current node.
gum is the global namespace for all aGrUM entities
BinTreeNode(const Val &v)
Basic constructor: a node without parent nor children.
void eraseLink(BinTreeDir tree_dir)
Remove the link between the current node and one of its children.
BinTreeDir
The direction of a given edge in a binary tree.
BinTreeNode< Val > & operator=(const BinTreeNode< Val > &from)
Copy operator: copy the value of from into this.
BinTreeNode< Val > * rightmostNode() const
Returns the rightmost node of the current tree.
BinTreeDir _parent_dir
the direction to follow from the parent to reach the current node.
void eraseRightLink()
Remove the link between the current node and its right child.
BinTreeDir parentDir() const
Returns the direction of the edge parent->current node, if any.
BinTreeNode< Val > * root() const
Returns the top ancestor of the current tree.
BinTreeNode< Val > * rightChild() const
Returns the given child of a node.
BinTreeNode< Val > * parent() const
Returns the parent of a node.
Val & operator*()
Alias for method value.
BinTreeNode< Val > * _parent
The parent of the node.
BinTreeNode< Val > * insertRightChild(const Val &val)
Adds a new left child to the current node.
~BinTreeNode()
Class destructor.
#define GUM_ERROR(type, msg)
BinTreeNode< Val > * insertChild(const Val &val, BinTreeDir child_dir)
Adds a new child to the current node.