Princeec13/mql5
Watch
0
0
Fork
You've already forked mql5
 1
Code Issues Pull requests 1 Projects Releases Packages Wiki Activity Actions
mql5/Include/Generic/RedBlackTree.mqh

935 lines
73 KiB
MQL5
RawPermalinkNormal ViewHistory

new files added
2025-08-05 01:57:33 -04:00
<EFBFBD><EFBFBD>//+------------------------------------------------------------------+
//| RedBlackTree.mqh |
//| Copyright 2000-2025, MetaQuotes Ltd. |
//| https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic\Interfaces\ICollection.mqh>
#include <Generic\Internal\DefaultComparer.mqh>
#include <Generic\Internal\ArrayFunction.mqh>
#include <Generic\Interfaces\IComparer.mqh>
#include "Stack.mqh"
//+------------------------------------------------------------------+
//| Enum ENUM_RED_BLACK_TREE_NODE_TYPE. |
//| Usage: Defines possible node colors for red black tree. |
//+------------------------------------------------------------------+
enum ENUM_RED_BLACK_TREE_NODE_TYPE
{
RED_BLACK_TREE_NODE_RED=0,
RED_BLACK_TREE_NODE_BLACK=1
};
//+------------------------------------------------------------------+
//| Class CRedBlackTreeNode<T>. |
//| Usage: Represents a node of red black tree. |
//+------------------------------------------------------------------+
template<typename T>
class CRedBlackTreeNode
{
private:
T m_value;
CRedBlackTreeNode<T>*m_left;
CRedBlackTreeNode<T>*m_right;
CRedBlackTreeNode<T>*m_parent;
ENUM_RED_BLACK_TREE_NODE_TYPE m_clr;
public:
CRedBlackTreeNode(void);
CRedBlackTreeNode(T value);
~CRedBlackTreeNode(void);
//--- methods of access to protected data
T Value(void) { return(m_value); }
void Value(T value) { m_value=value; }
CRedBlackTreeNode<T> *Parent(void) { return(m_parent); }
void Parent(CRedBlackTreeNode<T>*node) { m_parent=node; }
CRedBlackTreeNode<T> *Left(void) { return(m_left); }
void Left(CRedBlackTreeNode<T>*node) { m_left=node; }
CRedBlackTreeNode<T> *Right(void) { return(m_right); }
void Right(CRedBlackTreeNode<T>*node) { m_right=node; }
ENUM_RED_BLACK_TREE_NODE_TYPE Color(void) { return(m_clr); }
void Color(ENUM_RED_BLACK_TREE_NODE_TYPE clr) { m_clr=clr; }
//--- check node is empty
bool IsLeaf(void);
//--- create new empty node
static CRedBlackTreeNode<T>*CreateEmptyNode(void);
};
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTreeNode<T> class that|
//| is empty. |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTreeNode::CRedBlackTreeNode(void) : m_clr(RED_BLACK_TREE_NODE_RED)
{
}
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTreeNode<T> class with|
//| specified value. |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTreeNode::CRedBlackTreeNode(T value)
{
m_value=value;
m_clr=RED_BLACK_TREE_NODE_RED;
m_left=CreateEmptyNode();
m_right=CreateEmptyNode();
}
//+------------------------------------------------------------------+
//| Destructor. |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTreeNode::~CRedBlackTreeNode(void)
{
if(CheckPointer(m_left)==POINTER_DYNAMIC)
delete m_left;
if(CheckPointer(m_right)==POINTER_DYNAMIC)
delete m_right;
}
//+------------------------------------------------------------------+
//| Check node is empty. |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTreeNode::IsLeaf(void)
{
return(m_clr==RED_BLACK_TREE_NODE_BLACK &&
CheckPointer(m_left)==POINTER_INVALID &&
CheckPointer(m_right)==POINTER_INVALID);
}
//+------------------------------------------------------------------+
//| Create new empty black node. |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTreeNode<T>*CRedBlackTreeNode::CreateEmptyNode(void)
{
CRedBlackTreeNode<T>*new_node=new CRedBlackTreeNode<T>();
new_node.m_clr=RED_BLACK_TREE_NODE_BLACK;
new_node.m_parent=NULL;
new_node.m_left=NULL;
new_node.m_right=NULL;
//--- return new empty node
return(new_node);
}
//+------------------------------------------------------------------+
//| Class CRedBlackTree<T>. |
//| Usage: A red black tree is a data structure which is a type of |
//| self-balancing binary search tree. |
//+------------------------------------------------------------------+
template<typename T>
class CRedBlackTree: public ICollection<T>
{
protected:
CRedBlackTreeNode<T>*m_root_node;
CRedBlackTreeNode<T>*m_last_node;
IComparer<T>*m_comparer;
int m_count;
bool m_delete_comparer;
public:
CRedBlackTree(void);
CRedBlackTree(IComparer<T>*comparer);
CRedBlackTree(ICollection<T>*collection);
CRedBlackTree(ICollection<T>*collection,IComparer<T>*comparer);
CRedBlackTree(T &array[]);
CRedBlackTree(T &array[],IComparer<T>*comparer);
~CRedBlackTree(void);
//--- methods of filling data
bool Add(T value);
//--- methods of access to protected data
CRedBlackTreeNode<T>*Root(void) { return(m_root_node); }
int Count(void) { return(m_count); }
bool Contains(T item);
IComparer<T> *Comparer(void) const { return(m_comparer); }
bool TryGetMin(T &min);
bool TryGetMax(T &max);
//--- methods of copy data from collection
int CopyTo(T &dst_array[],const int dst_start=0);
//--- methods of cleaning and removing
void Clear(void);
bool Remove(T value);
bool Remove(CRedBlackTreeNode<T>*node);
bool RemoveMin(void);
bool RemoveMax(void);
//--- method for searching
CRedBlackTreeNode<T>*Find(T value);
CRedBlackTreeNode<T>*FindMax(void);
CRedBlackTreeNode<T>*FindMin(void);
private:
void RotateRight(CRedBlackTreeNode<T>*rotate_node);
void RotateLeft(CRedBlackTreeNode<T>*rotate_node);
void BalanceTreeAfterInsert(CRedBlackTreeNode<T>*insert_node);
void BalanceTreeAfterDelete(CRedBlackTreeNode<T>*linked_node);
static void WalkNextLevel(CRedBlackTreeNode<T>*node,T &array[],int &index);
};
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTree<T> class that is |
//| empty and uses the specified comparer. |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::CRedBlackTree(void): m_count(0)
{
//--- use default comaprer
m_comparer=new CDefaultComparer<T>();
m_delete_comparer=true;
}
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTree<T> class that is |
//| empty and uses the specified comparer. |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::CRedBlackTree(IComparer<T>*comparer): m_count(0)
{
//--- check comaprer
if(CheckPointer(comparer)==POINTER_INVALID)
{
//--- use default comaprer
m_comparer=new CDefaultComparer<T>();
m_delete_comparer=true;
}
else
{
//--- use specified equality comaprer
m_comparer=comparer;
m_delete_comparer=false;
}
}
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTree<T> class that |
//| uses the default equality comparer, contains elements copied from|
//| the specified collection. |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::CRedBlackTree(ICollection<T>*collection): m_count(0)
{
//--- use default comaprer
m_comparer=new CDefaultComparer<T>();
m_delete_comparer=true;
//--- check collection
if(CheckPointer(collection)==POINTER_INVALID)
return;
//--- copy all elements from specified collection to array
T array[];
int size=collection.CopyTo(array);
//--- fill red black tree by elements from the array
for(int i=0; i<size; i++)
Add(array[i]);
}
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTree<T> class that |
//| uses the specified comparer and contains elements copied from |
//| the specified collection. |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::CRedBlackTree(ICollection<T>*collection,IComparer<T>*comparer): m_count(0)
{
//--- check comaprer
if(CheckPointer(comparer)==POINTER_INVALID)
{
//--- use default comaprer
m_comparer=new CDefaultComparer<T>();
m_delete_comparer=true;
}
else
{
//--- use specified equality comaprer
m_comparer=comparer;
m_delete_comparer=false;
}
//--- check collection
if(CheckPointer(collection)==POINTER_INVALID)
return;
//--- copy all elements from specified collection to array
T array[];
int size=collection.CopyTo(array);
//--- fill red black tree by elements from the array
for(int i=0; i<size; i++)
Add(array[i]);
}
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTree<T> class that |
//| uses the default equality comparer and contains elements copied |
//| from the specified array. |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::CRedBlackTree(T &array[]): m_count(0)
{
//--- use default comaprer
m_comparer=new CDefaultComparer<T>();
m_delete_comparer=true;
//--- fill red black tree by elements from the specified array
for(int i=0; i<ArraySize(array); i++)
Add(array[i]);
}
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTree<T> class that |
//| uses the specified comparer and contains elements copied from |
//| the specified array. |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::CRedBlackTree(T &array[],IComparer<T>*comparer): m_count(0)
{
//--- check comaprer
if(CheckPointer(comparer)==POINTER_INVALID)
{
//--- use default comaprer
m_comparer=new CDefaultComparer<T>();
m_delete_comparer=true;
}
else
{
//--- use specified equality comaprer
m_comparer=comparer;
m_delete_comparer=false;
}
//--- fill red black tree by elements from the specified array
for(int i=0; i<ArraySize(array); i++)
Add(array[i]);
}
//+------------------------------------------------------------------+
//| Destructor. |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::~CRedBlackTree(void)
{
//--- delete comparer
if(m_delete_comparer)
delete m_comparer;
//--- clear tree
Clear();
}
//+------------------------------------------------------------------+
//| Adds a new item to the tree. If the element already belongs to |
//| this tree, no new element will be added. |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::Add(T value)
{
//--- traverse tree - find node below
if(CheckPointer(Find(value))!=POINTER_INVALID)
return(false);
//--- create new node
CRedBlackTreeNode<T>*new_node=new CRedBlackTreeNode<T>(value);
CRedBlackTreeNode<T>*work_node=m_root_node;
while(CheckPointer(work_node)!=POINTER_INVALID && !work_node.IsLeaf())
{
//--- find parent
new_node.Parent(work_node);
int result= m_comparer.Compare(value, work_node.Value());
if(result == 0)
{
//--- node with same value already exists
return(false);
}
work_node=(result>0 ? work_node.Right() : work_node.Left());
}
//--- insert node into tree starting at parent's location
if(CheckPointer(new_node.Parent())!=POINTER_INVALID)
{
if(m_comparer.Compare(new_node.Value(),new_node.Parent().Value())>0)
{
if(CheckPointer(new_node.Parent().Right())==POINTER_DYNAMIC && new_node.Parent().Right().IsLeaf())
delete new_node.Parent().Right();
new_node.Parent().Right(new_node);
}
else
{
if(CheckPointer(new_node.Parent().Left())==POINTER_DYNAMIC && new_node.Parent().Left().IsLeaf())
delete new_node.Parent().Left();
new_node.Parent().Left(new_node);
}
}
else
{
//--- first node added
m_root_node=new_node;
}
//--- restore red-black properties
BalanceTreeAfterInsert(new_node);
m_last_node=new_node;
//--- increment count
m_count++;
return(true);
}
//+------------------------------------------------------------------+
//| Determines whether this tree contains the specified item. |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::Contains(T item)
{
CRedBlackTreeNode<T>*tree_node=Find(item);
return(CheckPointer(tree_node)!=POINTER_INVALID);
}
//+------------------------------------------------------------------+
//| Finds the minimum element stored in the tree. |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::TryGetMin(T &min)
{
CRedBlackTreeNode<T>*work_node=m_root_node;
//--- check tree is empty
if(CheckPointer(work_node)==POINTER_INVALID || work_node.IsLeaf())
return(false);
//--- traverse to the extreme left to find the smallest key
while(!work_node.Left().IsLeaf())
work_node=work_node.Left();
//--- store min value
m_last_node=work_node;
min=work_node.Value();
return(true);
}
//+------------------------------------------------------------------+
//| Finds the maximum element stored in the tree. |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::TryGetMax(T &max)
{
CRedBlackTreeNode<T>*work_node=m_root_node;
//--- check tree is empty
if(CheckPointer(work_node)==POINTER_INVALID || work_node.IsLeaf())
return(false);
//--- traverse to the extreme right to find the largest key
while(!work_node.Right().IsLeaf())
work_node=work_node.Right();
//--- store max value
m_last_node=work_node;
max=work_node.Value();
return(true);
}
//+------------------------------------------------------------------+
//| Copies a range of elements from the tree to a compatible |
//| one-dimensional array. |
//+------------------------------------------------------------------+
template<typename T>
int CRedBlackTree::CopyTo(T &dst_array[],const int dst_start=0)
{
//--- check root node
if(CheckPointer(m_root_node)==POINTER_INVALID)
return(0);
//--- resize array
if(dst_start+m_count>ArraySize(dst_array))
ArrayResize(dst_array,dst_start+m_count);
//--- start copy
int index=dst_start;
if(!m_root_node.IsLeaf())
{
//--- store all values in the stack
WalkNextLevel(m_root_node,dst_array,index);
//--- copy values from stack to array
return(index-dst_start);
}
else
{
//--- tree is empty
return(0);
}
}
//+------------------------------------------------------------------+
//| Removes all nodes from the tree. |
//+------------------------------------------------------------------+
template<typename T>
void CRedBlackTree::Clear(void)
{
//--- check count
if(m_count>0)
{
//--- delete root node
if(CheckPointer(m_root_node)==POINTER_DYNAMIC)
delete m_root_node;
//--- delete last node
if(CheckPointer(m_last_node)==POINTER_DYNAMIC)
delete m_last_node;
m_count=0;
}
}
//+------------------------------------------------------------------+
//| Removes a node with specified value from the tree. |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::Remove(T value)
{
//--- try to find node with specified value
CRedBlackTreeNode<T>*delete_node=Find(value);
if(CheckPointer(delete_node)!=POINTER_INVALID)
return Remove(delete_node);
return(false);
}
//+------------------------------------------------------------------+
//| Removes a node from the tree. |
//| A node to be deleted will be: |
//| 1. a leaf with no children |
//| 2. have one child |
//| 3. have two children |
//| If the deleted node is red, the red black properties still hold. |
//| If the deleted node is black, the tree needs rebalancing. |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::Remove(CRedBlackTreeNode<T>*delete_node)
{
//--- check node
if(CheckPointer(delete_node)==POINTER_INVALID)
return(false);
Reference in a new issueCopy permalink