mobinzkr/mql-for-begginers
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
mql-for-begginers/Include/Generic/LinkedList.mqh
Mobin Zarekar 3a4dea3f15 init
2025-07-22 18:30:17 +03:00

563 lines
20 KiB
MQL5
Raw Permalink Blame History

//+------------------------------------------------------------------+
//| LinkedList.mqh |
//| Copyright 2000-2025, MetaQuotes Ltd. |
//| https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic\Interfaces\ICollection.mqh>
#include <Generic\Internal\EqualFunction.mqh>
//+------------------------------------------------------------------+
//| Class CLinkedListNode<T>. |
//| Usage: Represents a node of linked list. |
//+------------------------------------------------------------------+
template<typename T>
class CLinkedListNode
{
protected:
CLinkedList<T>*m_list;
CLinkedListNode<T>*m_next;
CLinkedListNode<T>*m_prev;
T m_item;
public:
CLinkedListNode(T value): m_item(value) { }
CLinkedListNode(CLinkedList<T>*list,T value): m_list(list),m_item(value) { }
~CLinkedListNode(void) { }
//--- methods of access to protected data
CLinkedList<T>* List(void) { return(m_list); }
void List(CLinkedList<T>*value) { m_list=value; }
CLinkedListNode<T>*Next(void) { return(m_next); }
void Next(CLinkedListNode<T>*value) { m_next=value; }
CLinkedListNode<T>*Previous(void) { return(m_prev); }
void Previous(CLinkedListNode<T>*value) { m_prev=value; }
T Value(void) { return(m_item); }
void Value(T value) { m_item=value; }
};
//+------------------------------------------------------------------+
//| Class CLinkedList<T>. |
//| Usage: Represents a doubly linked list. |
//+------------------------------------------------------------------+
template<typename T>
class CLinkedList: public ICollection<T>
{
protected:
CLinkedListNode<T>*m_head;
int m_count;
public:
CLinkedList(void);
CLinkedList(ICollection<T>*collection);
CLinkedList(T &array[]);
~CLinkedList(void);
//--- methods of filling data
bool Add(T value);
CLinkedListNode<T>*AddAfter(CLinkedListNode<T>*node,T value);
bool AddAfter(CLinkedListNode<T>*node,CLinkedListNode<T>*new_node);
CLinkedListNode<T>*AddBefore(CLinkedListNode<T>*node,T value);
bool AddBefore(CLinkedListNode<T>*node,CLinkedListNode<T>*new_node);
CLinkedListNode<T>*AddFirst(T value);
bool AddFirst(CLinkedListNode<T>*node);
CLinkedListNode<T>*AddLast(T value);
bool AddLast(CLinkedListNode<T>*node);
//--- methods of access to protected data
int Count(void);
CLinkedListNode<T>*Head(void) {return(m_head);}
CLinkedListNode<T>*First(void);
CLinkedListNode<T>*Last(void);
bool Contains(T item);
//--- methods of copy data from collection
int CopyTo(T &dst_array[],const int dst_start=0);
//--- methods of cleaning and deleting
void Clear(void);
bool Remove(T item);
bool Remove(CLinkedListNode<T>*node);
bool RemoveFirst(void);
bool RemoveLast(void);
//--- method for searching
CLinkedListNode<T>*Find(T value);
CLinkedListNode<T>*FindLast(T value);
private:
bool ValidateNode(CLinkedListNode<T>*node);
bool ValidateNewNode(CLinkedListNode<T>*node);
void InternalInsertNodeBefore(CLinkedListNode<T>*node,CLinkedListNode<T>*new_node);
void InternalInsertNodeToEmptyList(CLinkedListNode<T>*new_node);
void InternalRemoveNode(CLinkedListNode<T>*node);
};
//+------------------------------------------------------------------+
//| Initializes a new instance of the CLinkedList<T> class that is |
//| empty. |
//+------------------------------------------------------------------+
template<typename T>
CLinkedList::CLinkedList(void): m_count(0)
{
}
//+------------------------------------------------------------------+
//| Initializes a new instance of the CLinkedList<T> class that |
//| contains elements copied from the specified array and has |
//| sufficient capacity to accommodate the number of elements copied.|
//+------------------------------------------------------------------+
template<typename T>
CLinkedList::CLinkedList(T &array[]): m_count(0)
{
for(int i=0; i<ArraySize(array); i++)
AddLast(array[i]);
}
//+------------------------------------------------------------------+
//| Initializes a new instance of the CLinkedList<T> class that |
//| contains elements copied from the specified collection and has |
//| sufficient capacity to accommodate the number of elements copied.|
//+------------------------------------------------------------------+
template<typename T>
CLinkedList::CLinkedList(ICollection<T>*collection): m_count(0)
{
//--- check collection
if(CheckPointer(collection)!=POINTER_INVALID)
{
T array[];
int size=collection.CopyTo(array,0);
for(int i=0; i<size; i++)
AddLast(array[i]);
}
}
//+------------------------------------------------------------------+
//| Destructor. |
//+------------------------------------------------------------------+
template<typename T>
CLinkedList::~CLinkedList(void)
{
Clear();
}
//+------------------------------------------------------------------+
//| Adds an value to the end of the list. |
//+------------------------------------------------------------------+
template<typename T>
bool CLinkedList::Add(T value)
{
return(CheckPointer(AddLast(value))!=POINTER_INVALID);
}
//+------------------------------------------------------------------+
//| Adds a new node containing the specified value after the |
//| specified existing node in the CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
CLinkedListNode<T>*CLinkedList::AddAfter(CLinkedListNode<T>*node,T value)
{
//--- check node
if(!ValidateNode(node))
return(NULL);
//--- create new node
CLinkedListNode<T>*result=new CLinkedListNode<T>(node.List(),value);
//--- insert node to the list
InternalInsertNodeBefore(node.Next(),result);
return(result);
}
//+------------------------------------------------------------------+
//| Adds the specified new node after the specified existing node in |
//| the LinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
bool CLinkedList::AddAfter(CLinkedListNode<T>*node,CLinkedListNode<T>*new_node)
{
//--- check node
if(!ValidateNode(node))
return(false);
//--- check new node
if(!ValidateNewNode(new_node))
return(false);
//--- insert node to the list
InternalInsertNodeBefore(node.Next(),new_node);
//--- set the current list as list for new node
new_node.List(GetPointer(this));
return(true);
}
//+------------------------------------------------------------------+
//| Adds a new node containing the specified value before the |
//| specified existing node in the CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
CLinkedListNode<T>*CLinkedList::AddBefore(CLinkedListNode<T>*node,T value)
{
//--- check node
if(!ValidateNode(node))
return(NULL);
//--- create new node
CLinkedListNode<T>*result=new CLinkedListNode<T>(node.List(),value);
//--- insert node to the list
InternalInsertNodeBefore(node,result);
if(node==m_head)
m_head=result;
return(result);
}
//+------------------------------------------------------------------+
//| Adds the specified new node before the specified existing node in|
//| the LinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
bool CLinkedList::AddBefore(CLinkedListNode<T>*node,CLinkedListNode<T>*new_node)
{
//--- check node
if(!ValidateNode(node))
return(false);
//--- check new node
if(!ValidateNewNode(new_node))
return(false);
//--- insert node to the list
InternalInsertNodeBefore(node,new_node);
//--- set the current list as list for new node
new_node.List(GetPointer(this));
if(node==m_head)
m_head=new_node;
return(true);
}
//+------------------------------------------------------------------+
//| Adds a new node containing the specified value at the start of |
//| the CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
CLinkedListNode<T>*CLinkedList::AddFirst(T value)
{
//--- create new node
CLinkedListNode<T>*node=new CLinkedListNode<T>(GetPointer(this),value);
//--- check head node
if(CheckPointer(m_head)==POINTER_INVALID)
{
//--- insert node to the empty list
InternalInsertNodeToEmptyList(node);
}
else
{
//--- insert node to the list
InternalInsertNodeBefore(m_head,node);
m_head=node;
}
return(node);
}
//+------------------------------------------------------------------+
//| Adds the specified new node at the start of the CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
bool CLinkedList::AddFirst(CLinkedListNode<T>*node)
{
//--- check node
if(!ValidateNewNode(node))
return(false);
//--- check head node
if(CheckPointer(m_head)==POINTER_INVALID)
{
//--- insert node to the empty list
InternalInsertNodeToEmptyList(node);
}
else
{
//--- insert node to the list
InternalInsertNodeBefore(m_head,node);
m_head=node;
}
//--- set the current list as list for node
node.List(GetPointer(this));
return(true);
}
//+------------------------------------------------------------------+
//| Adds a new node containing the specified value at the end of the |
//| CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
CLinkedListNode<T>*CLinkedList::AddLast(T value)
{
//--- create new node
CLinkedListNode<T>*node=new CLinkedListNode<T>(GetPointer(this),value);
//--- check head node
if(CheckPointer(m_head)==POINTER_INVALID)
{
//--- insert node to the empty list
InternalInsertNodeToEmptyList(node);
}
else
{
//--- insert node to the list
InternalInsertNodeBefore(m_head,node);
}
return(node);
}
//+------------------------------------------------------------------+
//| Adds the specified new node at the end of the CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
bool CLinkedList::AddLast(CLinkedListNode<T>*node)
{
//--- check node
if(!ValidateNewNode(node))
return(false);
//--- check head node
if(CheckPointer(m_head)==POINTER_INVALID)
{
//--- insert node to the empty list
InternalInsertNodeToEmptyList(node);
}
else
{
//--- insert node to the list
InternalInsertNodeBefore(m_head,node);
}
//--- set the current list as list for node
node.List(GetPointer(this));
return(true);
}
//+------------------------------------------------------------------+
//| Determines whether an element is in the linked list. |
//+------------------------------------------------------------------+
template<typename T>
int CLinkedList::Count(void)
{
return(m_count);
}
//+------------------------------------------------------------------+
//| Gets the first node of the CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
CLinkedListNode<T>*CLinkedList::First(void)
{
return(m_head);
}
//+------------------------------------------------------------------+
//| Gets the last node of the CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
CLinkedListNode<T>*CLinkedList::Last(void)
{
return(CheckPointer(m_head)!=POINTER_INVALID ? m_head.Previous() : NULL);
}
//+------------------------------------------------------------------+
//| Determines whether a value is in the CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
bool CLinkedList::Contains(T item)
{
return(CheckPointer(Find(item))!=POINTER_INVALID);
}
//+------------------------------------------------------------------+
//| Copies a range of elements from the linkedlist to a compatible |
//| one-dimensional array. |
//+------------------------------------------------------------------+
template<typename T>
int CLinkedList::CopyTo(T &dst_array[],const int dst_start=0)
{
//--- resize array
if(dst_start+m_count>ArraySize(dst_array))
ArrayResize(dst_array,dst_start+m_count);
//--- check start index
if(dst_start>ArraySize(dst_array))
return(0);
//--- start copy
CLinkedListNode<T>*node=m_head;
if(CheckPointer(node)!=POINTER_INVALID)
{
int dst_index=dst_start;
do
{
dst_array[dst_index++]=node.Value();
node=node.Next();
}
while(dst_index<ArraySize(dst_array) && node!=m_head);
return(dst_index-dst_start);
}
//--- list is empty
return(0);
}
//+------------------------------------------------------------------+
//| Removes all nodes from the CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
void CLinkedList::Clear(void)
{
//--- check count
if(m_count>0)
{
//--- check head node
if(CheckPointer(m_head)!=POINTER_INVALID)
{
while(m_head.Next()!=m_head)
{
CLinkedListNode<T>*node=m_head.Next();
m_head.Next(node.Next());
delete node;
}
delete m_head;
}
//--- reset count
m_count=0;
}
}
//+------------------------------------------------------------------+
//| Removes the first occurrence of the specified value from the |
//| CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
bool CLinkedList::Remove(T item)
{
//--- find node with specified value
CLinkedListNode<T>*node=Find(item);
if(CheckPointer(node)!=POINTER_INVALID)
{
//--- remove node
InternalRemoveNode(node);
return(true);
}
return(false);
}
//+------------------------------------------------------------------+
//| Removes the specified node from the LinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
bool CLinkedList::Remove(CLinkedListNode<T>*node)
{
//--- check node
if(ValidateNode(node))
{
//--- remove node
InternalRemoveNode(node);
return(true);
}
return(false);
}
//+------------------------------------------------------------------+
//| Removes the node at the start of the CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
bool CLinkedList::RemoveFirst(void)
{
//--- check head node
if(CheckPointer(m_head)==POINTER_INVALID)
return(false);
//--- remove head node
InternalRemoveNode(m_head);
return(true);
}
//+------------------------------------------------------------------+
//| Removes the node at the end of the CLinkedList<T>. |
//+------------------------------------------------------------------+
template<typename T>
bool CLinkedList::RemoveLast(void)
{
//--- check head node
if(CheckPointer(m_head)==POINTER_INVALID)
return(false);
//--- remove last node
InternalRemoveNode(m_head.Previous());
return(true);
}
//+------------------------------------------------------------------+
//| Finds the first node that contains the specified value. |
//+------------------------------------------------------------------+
template<typename T>
CLinkedListNode<T>*CLinkedList::Find(T value)
{
CLinkedListNode<T>*node=m_head;
//--- start search specified value in the list
if(CheckPointer(node)!=POINTER_INVALID)
{
do
{
//--- use default equals function
if(::Equals(node.Value(),value))
return(node);
node=node.Next();
}
while(node!=m_head);
}
return(NULL);
}
//+------------------------------------------------------------------+
//| Finds the last node that contains the specified value. |
//+------------------------------------------------------------------+
template<typename T>
CLinkedListNode<T>*CLinkedList::FindLast(T value)
{
//--- check head node
if(CheckPointer(m_head)==POINTER_INVALID)
return(NULL);
//--- get last node
CLinkedListNode<T> *last = m_head.Previous();
CLinkedListNode<T> *node = last;
//--- start search from the end of the list
if(node!=NULL)
{
do
{
//--- use default equals function
if(::Equals(node.Value(),value))
return(node);
node=node.Previous();
}
while(node!=last);
}
return(NULL);
}
//+------------------------------------------------------------------+
//| Validation of node on not null and belongs in the current list. |
//+------------------------------------------------------------------+
template<typename T>
bool CLinkedList::ValidateNode(CLinkedListNode<T>*node)
{
return(CheckPointer(node)!=POINTER_INVALID && node.List()==GetPointer(this));
}
//+------------------------------------------------------------------+
//| Validation of new node on not null. |
//+------------------------------------------------------------------+
template<typename T>
bool CLinkedList::ValidateNewNode(CLinkedListNode<T>*node)
{
return(CheckPointer(node)!=POINTER_INVALID && node.List()==NULL);
}
//+------------------------------------------------------------------+
//| Insert node before the specified node. |
//+------------------------------------------------------------------+
template<typename T>
void CLinkedList::InternalInsertNodeBefore(CLinkedListNode<T>*node,CLinkedListNode<T>*new_node)
{
//--- set node befor the specified node
new_node.Next(node);
new_node.Previous(node.Previous());
node.Previous().Next(new_node);
node.Previous(new_node);
//--- increment count
m_count++;
}
//+------------------------------------------------------------------+
//| Add first node to the list. |
//+------------------------------------------------------------------+
template<typename T>
void CLinkedList::InternalInsertNodeToEmptyList(CLinkedListNode<T>*new_node)
{
//--- set node as head of the list
new_node.Next(new_node);
new_node.Previous(new_node);
m_head=new_node;
//--- increment count
m_count++;
}
//+------------------------------------------------------------------+
//| Remove specified node from the list. |
//+------------------------------------------------------------------+
template<typename T>
void CLinkedList::InternalRemoveNode(CLinkedListNode<T>*node)
{
//--- check node
if(node.Next()==node)
{
//--- resets the head of the list
m_head=NULL;
}
else
{
//--- detach node from the list
node.Next().Previous(node.Previous());
node.Previous().Next(node.Next());
if(m_head==node)
m_head=node.Next();
}
//--- decrement count and delete node
m_count--;
delete node;
}
//+------------------------------------------------------------------+
Reference in a new issue View git blame Copy permalink