#ifndef LIB_MQLPLUS_BASE_OBJECT_TREE_NODE_MQH_INCLUDED
#define LIB_MQLPLUS_BASE_OBJECT_TREE_NODE_MQH_INCLUDED
#property version "1.0";
/**********************************************************************************
 * Copyright (C) 2010-2022 Dominik Egert <info@freie-netze.de>
 *
 * This file is the objects include file.
 *
 * MQLplus, including this file may not be copied and/or distributed
 * without explecit permit by the author.
 * Author Dominik Egert / Freie Netze UG.
 **********************************************************************************
 *
 *  Version: 1.0
 *  State: production
 *
 *  File information
 *  ================
 *
 *
 *
*/
#ifdef DBG_MSG_TRACE_FILE_LOADER
    DBG_MSG_TRACE_FILE_LOADER;

#endif



// Incluse base node object
#include "lib_base_obj_node.mqh"





/*********************************************************************************************************************************************************/
/*                                                                                                                                                       */
/* MQLplus data structures                                                                                                                               */
/*                                                                                                                                                       */
/*********************************************************************************************************************************************************/


    ///////////////////////////////////////
    //
    //  Object Tree Node
    //

    // Base Tree object

        #define NODE_SUBTYPE    _object_node<USER_DATA, NODE_TYPE>
        #define THIS_TYPE       _object_t_node<USER_DATA, NODE_TYPE>

        template <typename USER_DATA, typename NODE_TYPE>
        class _object_t_node : public NODE_SUBTYPE
        {
            public:
            // Constructors / Destructor

                // Default constructor
                _object_t_node() :
                    NODE_SUBTYPE    ()
                { };

                // Copy constructor
                _object_t_node(const THIS_TYPE& p_in)
                {
                    _left       = p_in._left;
                    _right      = p_in._right;
                };

                // Destructor
                ~_object_t_node()
                { };


            // Element selector functions

                // Lowest key element
                NODE_TYPE* left()
                { return(bottom()); }

                // Highest key element
                NODE_TYPE* right()
                {
                    THIS_TYPE* ptr_obj = ::GetPointer(this);
                    while( (ptr_obj._left != NULL)
                        && (!_StopFlag) )
                    { ptr_obj = ptr_obj._right; }

                    // Return
                    return(ptr_obj);
                }

                THIS_TYPE* insert(THIS_TYPE* _root, THIS_TYPE*& _this_parent, const bool unique = false)
                { 
                    // Check root node
                    if(_root == NULL)
                    { return(::GetPointer(this)); }

                    // Local init
                    THIS_TYPE* ptr                      = _root;
                    _this_parent                  		= NULL;

                    // Find tree position
                    if(unique)
                    {
                        while( (ptr != NULL)
                            && (ptr.this_obj != this_obj)
                            && (!_StopFlag) )
                        {
                            _this_parent	            = ptr;
                            ptr         	            = (ptr.this_obj > this_obj) ? ptr._left : ptr._right;
                        }
                        
                        if( ((ptr != NULL) && (ptr.this_obj == this_obj))
                         || ((_this_parent != NULL) && (_this_parent.this_obj == this_obj)) )
                        { 
                            _this_parent                = NULL;
                            return(NULL); 
                        }
                    }
                    else
                    {
                        while( (ptr != NULL)
                            && (!_StopFlag) )
                        {
                            _this_parent	            = ptr;
                            ptr         	            = (ptr.this_obj > this_obj) ? ptr._left : ptr._right;
                        }
                    }

                    // Insert node
                    if(_this_parent.this_obj > this_obj)
                    { _this_parent._left                = ::GetPointer(this); }
                    else
                    { _this_parent._right               = ::GetPointer(this); }

                    // Return
                    return(_root);
                };

                // Remove object from tree
                THIS_TYPE* remove()
                { 
                    THIS_TYPE* tmp_ptr = NULL;
                    return(remove(tmp_ptr)); 
                };
                
                THIS_TYPE* remove(THIS_TYPE*& _this_parent)
                {
                    // Precheck
                    if( (_this_parent == NULL)
                     && (_left == NULL)
                     && (_right == NULL) )
                     { return(NULL); }

                    // Local init
                    THIS_TYPE* _this_node             	= ::GetPointer(this);
                    THIS_TYPE* _root                  	= (_this_parent == _this_node) ? _this_node : NULL;
                    THIS_TYPE* _sub_parent            	= NULL;
                    THIS_TYPE* _sub_node              	= NULL;

                    switch( ((_left != NULL) + (_right != NULL)) << ((_this_node == _root) ? 3 : NULL) )
                    {
                        // No children (Leaf)
                        case 0:
							// Update parent
							if(_this_parent == NULL)
							{ _root                     = NULL; }

							// Update parents right
							else if(_this_parent._right == _this_node)
							{ _this_parent._right		= NULL; }

                            // Update parents left
							else if(_this_parent._left == _this_node)
							{ _this_parent._left		= NULL; }

                            // Preserve node details for parent update
                            // (_left receives successor node)
                            // (_right receives successors right child node)
                            // (_this_parent receives successors right child's new parent)
							_left                       = NULL;
							_right                      = NULL;
							//_this_parent                = NULL;
							break;

                        // One child
                        case 1:
							// Return new root node
							if(_this_parent == NULL)
							{ 
							    _root                   = (_left != NULL) ? _left : _right; 
							    _left                   = _root;
							}
							
							// Update parents right
							else if(_this_parent._right == _this_node)
							{ 
							    _this_parent._right 	= (_left != NULL) ? _left : _right; 
							    _left                   = _this_parent._right;
							}

                            // Update parents left
							else if(_this_parent._left == _this_node)
							{ 
							    _this_parent._left      = (_left != NULL) ? _left : _right; 
							    _left                   = _this_parent._left;
							}

                            // Preserve node details for parent update
                            // (_left receives successor node)
                            // (_right receives successors right child node)
                            // (_this_parent receives successors right child's new parent)
                            _right                      = _left._right;
						    _this_parent                = _left;
							break;

                        // Two children
                        case 2:
                            _sub_parent                 = _this_node;
							_sub_node 					= _subtree_smallest_key(_right, _sub_parent);

                            // Remove subnode from tree, reattach right branch
                            if(_sub_parent != _this_node)
                            { 
                                _sub_parent._left       = _sub_node._right;
                                _sub_node._right        = _right;
                            }

                            // Update root node
							if(_this_parent == NULL)
							{ _root 					= _sub_node; }

							// Update _this_parent
							else if(_this_parent._right == _this_node)
							{ _this_parent._right	    = _sub_node; }
                            else
							{ _this_parent._left 	    = _sub_node; }

							// Reconnect left node
                            _sub_node._left             = _left;
                            
                            // Preserve node details for parent update
                            // (_left receives successor node)
                            // (_right receives successors right child node)
                            // (_this_parent receives successors right child's new parent)
                            _left                       = _sub_node;
                            _right                      = (_sub_parent != _this_node) ? _sub_parent._left : _sub_node._right;
                            _this_parent                = _sub_parent;
							break;

                        // Root node destruction
                        default:
                            _delete_subnodes(_root);
                            _root._left                 = NULL;
                            _root._right                = NULL;
					}

					// Return
					return(_root);
				};


            // Operators

                // Assignment operator
                void operator=(NODE_TYPE& p_in)
                { NODE_SUBTYPE::operator=(p_in); };

                NODE_TYPE* operator[](USER_DATA& value)
                {
                    // Local init
                    THIS_TYPE* x = ::GetPointer(this);

                    // Loop tree
                    while( (x != NULL)
                        && (x.this_obj != value) )
                    { x = (x.this_obj > value) ? x._left : x._right; }

                    // Return
                    return(x);
                    //return((x.this_obj == value) ? x : NULL);
                };


            protected:
            // Tree algorithm functions

                // Get smallest key
                NODE_TYPE* _subtree_smallest_key(THIS_TYPE* ptr)
                {
					THIS_TYPE* _this_parent = NULL;
					return(_subtree_smallest_key(ptr, _this_parent));
				};

                NODE_TYPE* _subtree_smallest_key(THIS_TYPE* ptr, THIS_TYPE*& _this_parent)
                {
                    while( (ptr != NULL)
                        && (ptr._left != NULL) )
                    { 
						_this_parent	= ptr;
						ptr 			= ptr._left; 
					}
                    return(ptr);
                };

                // Get greatest key
                NODE_TYPE* _subtree_greatest_key(THIS_TYPE* ptr)
                {
					THIS_TYPE* _this_parent = NULL;
					return(_subtree_greatest_key(ptr, _this_parent));
				};

                NODE_TYPE* _subtree_greatest_key(THIS_TYPE* ptr, THIS_TYPE*& _this_parent)
                {
                    while( (ptr != NULL)
                        && (ptr._right != NULL) )
                    { 
						_this_parent	= ptr;
						ptr 			= ptr._right; 
					}
                    return(ptr);
                };

                // Recursive tree deletion
                const bool _delete_subnodes(THIS_TYPE* p_in)
                {
                    // Discard empty node
                    if(p_in == NULL)
                    { return(false); }

                    // Check left node
                    if(_delete_subnodes(p_in._left))
                    { delete(p_in._left); }
                    
                    // Check right node
                    if(_delete_subnodes(p_in._right))
                    { delete(p_in._right); }

                    // Return
                    return(true);
                };


            public:
            // Debugging helper
            
                const string _node_to_string()                      { return(__obj_to_string(this_obj)); };
                const string __obj_to_string(uchar p_in)            { return(StringFormat("%u", p_in)); };
                const string __obj_to_string(ushort p_in)           { return(StringFormat("%u", p_in)); };
                const string __obj_to_string(uint p_in)             { return(StringFormat("%u", p_in)); };
                const string __obj_to_string(ulong p_in)            { return(StringFormat("%llu", p_in)); };
                const string __obj_to_string(char p_in)             { return(StringFormat("%i", p_in)); };
                const string __obj_to_string(short p_in)            { return(StringFormat("%i", p_in)); };
                const string __obj_to_string(int p_in)              { return(StringFormat("%i", p_in)); };
                const string __obj_to_string(long p_in)             { return(StringFormat("%lli", p_in)); };
                const string __obj_to_string(datetime p_in)         { return(TimeToString(p_in)); };
                const string __obj_to_string(color p_in)            { return(ColorToString(p_in)); };
                const string __obj_to_string(float p_in)            { return(StringFormat("%f", p_in)); };
                const string __obj_to_string(double p_in)           { return(StringFormat("%f", p_in)); };
                template <typename T>
                const string __obj_to_string(T& p_in)               { return(typename(p_in)); };
        };

        #undef THIS_TYPE
        #undef NODE_SUBTYPE



//
// END MQL data structures                                                                                                                                */
//*********************************************************************************************************************************************************/
#endif // LIB_MQLPLUS_BASE_OBJECT_TREE_NODE_MQH_INCLUDED