#ifndef LIB_MQLPLUS_BASE_OBJ_TREE_TEMPLATES_MQH_INCLUDED
#define LIB_MQLPLUS_BASE_OBJ_TREE_TEMPLATES_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 element handler
#include "lib_base_node_element.mqh"



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


    ///////////////////////////////////////
    //
    //  Tree object
    //

        // Base object
        template <typename USER_DATA, typename NODE_TYPE>
        struct _tree : public _element_collection<USER_DATA, NODE_TYPE>
        {
            public:
            // Element access structure

                class tree_element : public _element<_param_details<NODE_TYPE>, NODE_TYPE, USER_DATA>
                {
                    public:
                    // Constructors
                    tree_element() : _element()                                                                 { };
                    tree_element(NODE_TYPE* p_obj, _param_details<NODE_TYPE>* p_in) : _element(p_obj, p_in)     { };
                    tree_element(const tree_element& p_in) : _element(p_in)                                     { };

                    // Functions
                    void remove(const bool _do_not_destroy = false)
                    {
                        p_params.p_last_added   = (p_params.p_last_added == p_element_obj) ? NULL : p_params.p_last_added;
                        NODE_TYPE* _root        = p_element_obj.remove(p_params.p_root, p_params.do_not_destroy || _do_not_destroy);
                        p_params.p_root         = (_root != NULL) ? _root : p_params.p_root;
                        p_params._size--;
                        delete(p_element_obj);
                    };
                };


            protected:
            // Constructors / Destructor

                // Default constructor
                _tree() :
                    _element_collection<USER_DATA, NODE_TYPE>()
                { };

                // Copy constructor
                _tree(const _tree<USER_DATA, NODE_TYPE>& p_in) :
                    _element_collection<USER_DATA, NODE_TYPE>(p_in.p_params)
                { };

                // Destructor
                ~_tree()
                { reset(); };


            // Assignment operator

                void operator=(_tree<USER_DATA, NODE_TYPE>& p_in)
                {
                    // Detach current tree
                    reset();

                    // Assign new tree
                    _element_collection<USER_DATA, NODE_TYPE>::operator=(p_in);
                };


            // Comparison operator
            
                const bool operator!=(const _tree<USER_DATA, NODE_TYPE>& p_in)
                { return(!operator==(p_in)); };

                const bool operator==(const _tree<USER_DATA, NODE_TYPE>& p_in)
                { 
                    // Return
                    return(false);
                };

            
            public:
            // Access operator

                tree_element operator[](USER_DATA& p_in)
                { return(tree_element(p_params.p_root.operator[](p_in), p_params)); };


            // Array functions

                template <typename ARRAY_TYPE>
                const int get_array(ARRAY_TYPE& p_arr[], const bool reverse = false)                                            { USER_DATA tmp; return(_get_array(p_arr, tmp, WHOLE_ARRAY, reverse, true)); };
                template <typename ARRAY_TYPE>
                const int get_array(ARRAY_TYPE& p_arr[], const USER_DATA& start, const bool reverse = false)                    { return(_get_array(p_arr, start, WHOLE_ARRAY, reverse, false)); };
                template <typename ARRAY_TYPE>
                const int get_array(ARRAY_TYPE& p_arr[], const USER_DATA& start, const int count, const bool reverse = false)   { return(_get_array(p_arr, start, count, reverse, false)); };


            private:
            // General object functions

                // Reset tree
                void reset()
                {
                    if(::CheckPointer(p_params) == POINTER_INVALID)
                    { return; }

                    if(p_params.instance_cnt == 1)
                    {
                        // Detach object
                        if(p_params.do_not_destroy)
                        { p_params.p_root.detach_obj(); }

                        // Delete subtrees
                        delete_subtree(p_params.p_root);
                        
                        // Delete tree root
                        if(p_params.p_root != NULL)
                        { delete(p_params.p_root); }
                    }
                    p_params.clear();
                    p_params.instance_cnt += (p_params.instance_cnt == NULL);
                };


            // Tree functions

                // Objects to array
                template <typename ARRAY_TYPE>
                const int _get_array(ARRAY_TYPE& p_arr[], USER_DATA& _first_obj, const int count, const bool reverse, const bool whole_tree)
                {
                    // Precheck
                    if(p_params.p_root == NULL)
                    {
                        ArrayFree(p_arr);
                        return(NULL);
                    }

                    // Local init
                    NODE_TYPE*  p_this      = (whole_tree) || (p_params.p_left.get_obj() == _first_obj) ? p_params.p_left : p_params.p_root.operator[](_first_obj);
                    const int   _size       = (count != WHOLE_ARRAY) ? MathMin(count, p_params._size) : p_params._size;
                    const int   _end        = _size - 1;
                    int         cnt         = NULL;
                    int         arr_ptr     = (reverse) ? _end : NULL;

                    // Adjust output array
                    ArrayResize(p_arr, _size);

                    // Ascend main tree
                    while( (p_this != NULL)
                        && (cnt <= _end)
                        && (!_StopFlag) )
                    {
                        // Handle this node
                        cast_obj(p_arr, p_this, arr_ptr);
                        cnt++;
                        arr_ptr += (reverse) ? -1 : 1;

                        // Handle all sub-nodes
                        if(p_this.right_element() != NULL)
                        { traverse_sub_tree(p_arr, p_this.right_element(), cnt, arr_ptr, _end, reverse); }

                        // Loop control
                        p_this = p_this.parent_element();
                    }

                    // Return
                    return((_StopFlag) ? NULL : ArraySize(p_arr));
                };


			protected:
            // Generic cast object function

                void cast_obj(USER_DATA& p_arr[], NODE_TYPE* p_this, const int arr_ptr)                                         { p_arr[arr_ptr] = p_this.get_obj(); }
                void cast_obj(tree_element& p_arr[], NODE_TYPE* p_this, const int arr_ptr)                                      { p_arr[arr_ptr].set(p_this, p_params); }
                void cast_obj(tree_element*& p_arr[], NODE_TYPE* p_this, const int arr_ptr)
                {
                    // Value assignment
                    if(CheckPointer(p_arr[arr_ptr]) == POINTER_INVALID)
                    { p_arr[arr_ptr] = new tree_element(p_this, p_params); }
                    else
                    { p_arr[arr_ptr].set(p_this, p_params); }
                };


            // Element functions

                // Insert element
                const bool insert(USER_DATA& p_in)
                {
                    // Create new tree node
                    NODE_TYPE* p_new = new NODE_TYPE(p_in);

					// Insert and return
					if(insert(p_new))
					{ return(true); }
					
					// Insert failed
					delete(p_new);
					
					return(false);
				};

                const bool insert(NODE_TYPE* p_new)
                {
                    // Insert node
                    if(p_params.p_root == NULL)
                    {
                        p_params.p_root             = p_new;
                        p_params.p_left             = p_new;
                        p_params.p_right            = p_new;
                        p_params.p_last_added       = p_new;
                        p_params._size++;
                    }
                    else
                    {
                        NODE_TYPE* _root            = p_new.insert(p_params.p_root);
                        if(_root == NULL)
                        { return(false); }
                        p_params.p_root             = _root;
                        p_params.p_left             = (p_params.p_left.get_key() > p_new.get_key())		? p_new : p_params.p_left;
                        p_params.p_right            = (p_params.p_right.get_key() < p_new.get_key())	? p_new : p_params.p_right;
                        p_params.p_last_added       = p_new;
                        p_params._size++;
                    }

                    // Return
                    return(true);
                };

                // Remove element
                const bool remove(USER_DATA& p_in, const bool _do_not_destroy = false)
                {
                    // Precheck list
                    if( (p_params.p_root == NULL)
                     || (p_in < p_params.p_left.get_key())
                     || (p_in > p_params.p_right.get_key()) )
                    { return(false); }

                    // Get access object and return
                    return(remove(p_params.p_root.operator[](p_in), _do_not_destroy));
				};

                const bool remove(NODE_TYPE* p_remove, const bool _do_not_destroy = false)
                {
					// Precheck input
                    if(p_remove == NULL)
					{ return(false); }

                    // Remove node from tree
                    NODE_TYPE* p_node               = p_remove.parent_element();
                    NODE_TYPE* _root                = p_remove.remove(p_params.p_root, p_params.do_not_destroy);
                    p_node                          = (p_node == NULL) ? _root : p_node;

                    // Update control structure
                    p_params._size--;
                    if(p_params._size == NULL)
                    {
                        p_params.p_root             = NULL;
                        p_params.p_left             = NULL;
                        p_params.p_right            = NULL;
                        p_params.p_last_added       = NULL;
                    }
                    else
                    {
                        p_params.p_root             = (_root != NULL)                           ? _root             : p_params.p_root;
                        p_params.p_left             = (p_params.p_left != p_remove)             ? p_params.p_left   : p_node.smallest_node();
                        p_params.p_right            = (p_params.p_right != p_remove)            ? p_params.p_right  : p_node.greatest_node();
                        p_params.p_last_added       = (p_params.p_last_added == p_remove)       ? NULL              : p_params.p_last_added;
                    }

                    // Disconnect and remove element
                    if(p_params.do_not_destroy || _do_not_destroy)
                    { p_remove.detach_obj(); }
                    delete(p_remove);

                    // Return
                    return(true);
                };


            private:
            // Tree algorithm functions

                // Traverse subtree value gathering
                template <typename ARRAY_TYPE>
                void traverse_sub_tree(ARRAY_TYPE& p_arr[], NODE_TYPE* ptr, int& cnt, int& arr_ptr, const int _end, const bool reverse)
                {
                    // End of tree
                    if( (ptr == NULL)
                     || (cnt > _end) )
                    { return; }

                    // Visit child
                    if( (ptr.left_element() != NULL)
                     && (cnt <= _end) )
                    { traverse_sub_tree(p_arr, ptr.left_element(), cnt, arr_ptr, _end, reverse); }

                    // Local node
                    if(cnt <= _end)
                    {
                        cnt++;
                        cast_obj(p_arr, ptr, arr_ptr);
                        arr_ptr += (reverse) ? -1 : 1;
                    }

                    // Visit sibling
                    if( (ptr.right_element() != NULL)
                     && (cnt <= _end) )
                    { traverse_sub_tree(p_arr, ptr.right_element(), cnt, arr_ptr, _end, reverse); }
                };

                // Recursive tree deletion
                void delete_subtree(NODE_TYPE* p_in)
                {
                    // Discard empty node
                    if(p_in == NULL)
                    { return; }

                    // Check left tree
                    if(p_in.left_element() != NULL)
                    {
                        if(p_params.do_not_destroy)
                        { p_in.left_element().detach_obj(); }

                        delete_subtree(p_in.left_element());

                        if(CheckPointer(p_in.left_element()) != POINTER_INVALID)
                        { delete(p_in.left_element()); }
                    }

                    // Check right tree
                    if(p_in.right_element() != NULL)
                    {
                        if(p_params.do_not_destroy)
                        { p_in.right_element().detach_obj(); }

                        delete_subtree(p_in.right_element());

                        if(CheckPointer(p_in.right_element()) != POINTER_INVALID)
                        { delete(p_in.right_element()); }
                    }
                };


            public:
            // Debugging helper

                // Validator helper
                NODE_TYPE* get_tree_root()
                { return(p_params.p_root); }

                // Print tree helper
                void print_tree_size(const string comment = "")
                { print_tree(comment, true); };

                void print_tree(const string comment = "", const bool size_only = false)
                {
                    int count = NULL;
                    string out = "";
                    string out_buffer[];
                    _print_tree(p_params.p_root, 0, out, count, out_buffer);

                    if(size_only)
                    { 
                        printf("Elements counted: %i", count); 
                        return;
                    }
                    
                    printf("********* TREE BEGIN (%s) *************", comment);                    
                    for(int cnt = NULL; cnt < ArraySize(out_buffer); cnt++)
                    { printf("%s", out_buffer[cnt]); }
                    printf("%s\nElements: %i\n********* TREE END *************", out, count);

                    // Return
                    return;
                }

                void _print_tree(NODE_TYPE* _root, const int lvl, string& out, int& count, string& out_buffer[])
                {
                    if(_root == NULL)
                    { 
                        StringSetLength(out, StringLen(out) - 1);
                        out += "---<empty>---\n";
                        return; 
                    }

                    // This node
                    _print_tabs(out, lvl, out_buffer);
                    string node_out = _root._node_to_string(count);
                    
                    // Check for errors
                    if(node_out == NULL)
                    { 
                        out += "\n !!! ERROR IN NODE HIRARCHY !!! \n\n";
                        return; 
                    }

                    // Add output
                    out += StringFormat("%s\n", node_out);

                    // Left node
                    _print_tabs(out, lvl, out_buffer);
                    out += " -> left: \n";
                    _print_tree(_root.left_element(), lvl + 1, out, count, out_buffer);
                    
                    // Right node
                    _print_tabs(out, lvl, out_buffer);
                    out += " -> right: \n";
                    _print_tree(_root.right_element(), lvl + 1, out, count, out_buffer);

                    _print_tabs(out, lvl, out_buffer);
                    out += "Done\n";
                }

                void _print_tabs(string& out, const int lvl, string& out_buffer[])
                { 
                    _print_max_len(out, out_buffer);
                    out += StringFormat("%i:  ", lvl); for(int cnt = NULL; (cnt < lvl); cnt++) { out += "   "; } 
                };

                void _print_max_len(string& out, string& out_buffer[])
                {
                    if(StringLen(out) > 4096)
                    {
                        const int ptr = ArrayResize(out_buffer, ArraySize(out_buffer) + 1) - 1;
                        out_buffer[ptr] = out;
                        out = "";
                    }
                };
        };



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