563 lines
20 KiB
MQL5
563 lines
20 KiB
MQL5
//+------------------------------------------------------------------+
|
|
//| 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;
|
|
}
|
|
//+------------------------------------------------------------------+
|