| //+------------------------------------------------------------------+
|
| //| 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;
|
| }
|
| //+------------------------------------------------------------------+
|
