474 lines
19 KiB
MQL5
474 lines
19 KiB
MQL5
|
#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
|