376 lines
14 KiB
MQL5
376 lines
14 KiB
MQL5
|
#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
|