//+------------------------------------------------------------------+
//|                                                    ArrayList.mqh |
//|                             Copyright 2000-2025, MetaQuotes Ltd. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic\Interfaces\IList.mqh>
#include <Generic\Interfaces\IComparer.mqh>
#include <Generic\Internal\EqualFunction.mqh>
#include <Generic\Internal\ArrayFunction.mqh>
#include <Generic\Internal\Introsort.mqh>
#include <Generic\Internal\DefaultComparer.mqh>
//+------------------------------------------------------------------+
//| Class CArrayList<T>.                                             |
//| Usage: Represents a strongly typed list of values that can be    |
//|        accessed by index. Provides methods to search, sort, and  |
//|        manipulate lists.                                         |
//+------------------------------------------------------------------+
template<typename T>
class CArrayList: public IList<T>
  {
protected:
   T                 m_items[];
   int               m_size;
   const int         m_default_capacity;

public:
                     CArrayList(void);
                     CArrayList(const int capacity);
                     CArrayList(ICollection<T>*collection);
                     CArrayList(T &array[]);
                    ~CArrayList(void);
   //--- methods of access to protected data
   int               Capacity(void);
   void              Capacity(const int capacity);
   int               Count(void);
   bool              Contains(T item);
   void              TrimExcess(void);
   //--- method of access to the data
   bool              TryGetValue(const int index,T &value);
   bool              TrySetValue(const int index,T value);
   //--- methods of filling the array
   bool              Add(T item);
   bool              AddRange(T &array[]);
   bool              AddRange(ICollection<T>*collection);
   bool              Insert(const int index,T item);
   bool              InsertRange(const int index,T &array[]);
   bool              InsertRange(const int index,ICollection<T>*collection);
   //--- methods of copy data from collection   
   int               CopyTo(T &dst_array[],const int dst_start=0);
   //--- methods for binary searching index   
   int               BinarySearch(T item);
   int               BinarySearch(T item,IComparer<T>*comparer);
   int               BinarySearch(const int index,const int count,T item,IComparer<T>*comparer);
   //--- methods for searching index   
   int               IndexOf(T item);
   int               IndexOf(T item,const int start_index);
   int               IndexOf(T item,const int start_index,const int count);
   int               LastIndexOf(T item);
   int               LastIndexOf(T item,const int start_index);
   int               LastIndexOf(T item,const int start_index,const int count);
   //--- methods of cleaning and deleting   
   void              Clear(void);
   bool              Remove(T item);
   bool              RemoveAt(const int index);
   bool              RemoveRange(const int start_index,const int count);
   //--- reversing method
   bool              Reverse(void);
   bool              Reverse(const int start_index,const int count);
   //--- sorting method   
   bool              Sort(void);
   bool              Sort(IComparer<T>*comparer);
   bool              Sort(const int start_index,const int count,IComparer<T>*comparer);

private:
   void              EnsureCapacity(const int min);
  };
//+------------------------------------------------------------------+
//| Initializes a new instance of the CArrayList<T> class that is    |
//| empty and has the default initial capacity.                      |
//+------------------------------------------------------------------+
template<typename T>
CArrayList::CArrayList(void): m_default_capacity(4),
                              m_size(0)
  {
   ArrayResize(m_items,m_default_capacity);
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CArrayList<T> class that is    |
//| empty and has the specified initial capacity.                    |
//+------------------------------------------------------------------+
template<typename T>
CArrayList::CArrayList(const int capacity): m_default_capacity(4),
                                            m_size(0)
  {
   ArrayResize(m_items,capacity);
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CArrayList<T> class that       |
//| contains elements copied from the specified array and has        |
//| sufficient capacity to accommodate the number of elements copied.|
//+------------------------------------------------------------------+
template<typename T>
CArrayList::CArrayList(T &array[]): m_default_capacity(4),
                                    m_size(0)
  {
   m_size=ArrayCopy(m_items,array);
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CArrayList<T> class that       |
//| contains elements copied from the specified collection and has   |
//| sufficient capacity to accommodate the number of elements copied.|
//+------------------------------------------------------------------+
template<typename T>
CArrayList::CArrayList(ICollection<T>*collection): m_default_capacity(4),
                                                   m_size(0)
  {
//--- check collection   
   if(CheckPointer(collection)!=POINTER_INVALID)
      m_size=collection.CopyTo(m_items,0);
  }
//+------------------------------------------------------------------+
//| Destructor.                                                      |
//+------------------------------------------------------------------+
template<typename T>
CArrayList::~CArrayList(void)
  {
  }
//+------------------------------------------------------------------+
//| Gets the total number of elements the internal data structure can|
//| hold without resizing.                                           |
//+------------------------------------------------------------------+
template<typename T>
int CArrayList::Capacity(void)
  {
   return ArraySize(m_items);
  }
//+------------------------------------------------------------------+
//| Sets the total number of elements the internal data structure can|
//| hold without resizing.                                           |
//+------------------------------------------------------------------+
template<typename T>
void CArrayList::Capacity(const int capacity)
  {
//--- check new capacity should be greater than current size
   if(capacity>=m_size && capacity!=ArraySize(m_items))
     {
      if(capacity>0)
         ArrayResize(m_items,capacity);
      else
         ArrayFree(m_items);
     }
  }
//+------------------------------------------------------------------+
//| Gets the number of elements.                                     |
//+------------------------------------------------------------------+
template<typename T>
int CArrayList::Count(void)
  {
   return(m_size);
  }
//+------------------------------------------------------------------+
//| Determines whether an element is in the list.                    |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::Contains(T item)
  {
//--- try to find item in array
   for(int i=0; i<m_size; i++)
     {
      //--- use default equality function
      if(::Equals(m_items[i],item))
         return(true);
     }
   return(false);
  }
//+------------------------------------------------------------------+
//| Gets the element at the specified index.                         |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::TryGetValue(const int index,T &value)
  {
//--- check index
   if((uint)index<(uint)m_size)
     {
      //--- get value by index
      value=m_items[index];
      return(true);
     }
   return(false);
  }
//+------------------------------------------------------------------+
//| Sets the element at the specified index.                         |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::TrySetValue(const int index,T value)
  {
//--- check index
   if((uint)index<(uint)m_size)
     {
      //--- set value by index
      m_items[index]=value;
      return(true);
     }
   return(false);
  }
//+------------------------------------------------------------------+
//| Sets the capacity to the actual number of elements in the list,  |
//| if that number is less than a threshold value.                   |
//+------------------------------------------------------------------+
template<typename T>
void CArrayList::TrimExcess(void)
  {
//--- calculate threshold value
   int threshold=(int)(((double)ArraySize(m_items))*0.9);
//--- set a сapacity equal to the size
   if(m_size<threshold)
      Capacity(m_size);
  }
//+------------------------------------------------------------------+
//| Adds an value to the end of the list.                            |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::Add(T item)
  {
//--- increse capacity if its necessary
   if(m_size==ArraySize(m_items))
      EnsureCapacity(m_size+1);
//--- add value to the end      
   m_items[m_size++]=item;
   return(true);
  }
//+------------------------------------------------------------------+
//| Adds the elements of the specified array to the end of the list. |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::AddRange(T &array[])
  {
//--- increse capacity if its necessary
   if(m_size==ArraySize(m_items))
      EnsureCapacity(m_size+ArraySize(array));
//--- add values to the end    
   m_size+=ArrayCopy(m_items,array,m_size);
   return(true);
  }
//+------------------------------------------------------------------+
//| Adds the elements of the specified collection to the end of the  |
//| list.                                                            |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::AddRange(ICollection<T>*collection)
  {
//--- check collection
   if(CheckPointer(collection)==POINTER_INVALID)
      return(false);
//--- increse capacity if its necessary
   if(m_size==ArraySize(m_items))
      EnsureCapacity(m_size+collection.Count());
//--- add value to the end    
   m_size+=collection.CopyTo(m_items,m_size);
   return(true);
  }
//+------------------------------------------------------------------+
//| Inserts an element into the list at the specified index.         |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::Insert(const int index,T item)
  {
//--- check index  
   if((uint)index>(uint)m_size)
      return(false);
//--- increse capacity if its necessary      
   if(m_size==ArraySize(m_items))
      EnsureCapacity(m_size+1);
//--- shift the values to the right
   if(index<m_size)
      ArrayCopy(m_items,m_items,index+1,index,m_size-index);
//--- insert value by index
   m_items[index]=item;
   m_size++;
   return(true);
  }
//+------------------------------------------------------------------+
//| Inserts the elements of a array into the list at the specified   |
//| index.                                                           |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::InsertRange(const int index,T &array[])
  {
//--- check index  
   if((uint)index>(uint)m_size)
      return(false);
   int size=ArraySize(array);
//--- check size of inserted array
   if(size>0)
     {
      //--- increse capacity if its necessary      
      EnsureCapacity(m_size+size);
      //--- shift the values to the right
      if(index<m_size)
         ArrayCopy(m_items,m_items,index+size,index,m_size-index);
      //--- insert values by index
      m_size+=ArrayCopy(m_items,array,index);
     }
   return(true);
  }
//+------------------------------------------------------------------+
//| Inserts the elements of a collection into the list at the        |
//| specified index.                                                 |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::InsertRange(const int index,ICollection<T>*collection)
  {
//--- check collection
   if(CheckPointer(collection)==POINTER_INVALID)
      return(false);
//--- check index  
   if((uint)index>(uint)m_size)
      return(false);
   int count=collection.Count();
//--- check count of inserted collection
   if(count>0)
     {
      //--- increse capacity if its necessary    
      EnsureCapacity(m_size+count);
      //--- shift the values to the right
      if(index<m_size)
         ArrayCopy(m_items,m_items,index+count,index,m_size-index);
      //--- insert values by index
      m_size+=collection.CopyTo(m_items,index);
     }
   return(true);
  }
//+------------------------------------------------------------------+
//| Copies a range of elements from the list to a compatible         |
//| one-dimensional array.                                           |
//+------------------------------------------------------------------+
template<typename T>
int CArrayList::CopyTo(T &dst_array[],const int dst_start=0)
  {
   return ArrayCopy(dst_array,m_items,dst_start,0,m_size);
  }
//+------------------------------------------------------------------+
//| Searches a range of elements in the sorted list for an element   |
//| using the specified comparer and returns the zero-based index of |
//| the element.                                                     |
//+------------------------------------------------------------------+
template<typename T>
int CArrayList::BinarySearch(const int start_index,const int count,T item,IComparer<T>*comparer)
  {
//--- check index
   if(start_index<0 || count<0 || m_size-start_index<count)
      return(-1);
//--- check comparer
   if(CheckPointer(comparer)!=POINTER_INVALID)
     {
      //--- use specified comparer     
      return ArrayBinarySearch(m_items, start_index, count, item, comparer);
     }
   else
     {
      CDefaultComparer<T>def_comparer;
      //--- use default comparer
      return ArrayBinarySearch(m_items, start_index, count, item, GetPointer(def_comparer));
     }
  }
//+------------------------------------------------------------------+
//| Searches the entire sorted list for an element using the         |
//| specified comparer and returns the zero-based index of the       |
//| element.                                                         |
//+------------------------------------------------------------------+
template<typename T>
int CArrayList::BinarySearch(T item,IComparer<T>*comparer)
  {
   return BinarySearch(0, m_size, item, comparer);
  }
//+------------------------------------------------------------------+
//| Searches the entire sorted list for an element using the default |
//| comparer and returns the zero-based index of the element.        |
//+------------------------------------------------------------------+
template<typename T>
int CArrayList::BinarySearch(T item)
  {
   return BinarySearch(item, NULL);
  }
//+------------------------------------------------------------------+
//| Searches for the specified value and returns the zero-based index|
//| of the first occurrence within the entire list.                  |
//+------------------------------------------------------------------+
template<typename T>
int CArrayList::IndexOf(T item)
  {
   return ArrayIndexOf(m_items, item, 0, m_size);
  }
//+------------------------------------------------------------------+
//| Searches for the specified value and returns the zero-based index|
//| of the first occurrence within the range of elements in the list |
//| that extends from the specified index to the last element.       |
//+------------------------------------------------------------------+
template<typename T>
int CArrayList::IndexOf(T item,const int start_index)
  {
//--- check start index
   if(start_index>=m_size)
      return(-1);

   return ArrayIndexOf(m_items, item, start_index, m_size-start_index);
  }
//+------------------------------------------------------------------+
//| Searches for the specified value and returns the zero-based index|
//| of the first occurrence within the range of elements in the list |
//| that starts at the specified index and contains the specified    |
//| number of elements.                                              |
//+------------------------------------------------------------------+
template<typename T>
int CArrayList::IndexOf(T item,const int start_index,const int count)
  {
//--- check start index and count
   if(start_index<0 || count<0 || start_index>=m_size)
      return(-1);

   return ArrayIndexOf(m_items, item, start_index, MathMin(m_size-start_index,count));
  }
//+------------------------------------------------------------------+
//| Searches for the specified value and returns the zero-based index|
//| of the last occurrence within the entire list.                   |
//+------------------------------------------------------------------+
template<typename T>
int CArrayList::LastIndexOf(T item)
  {
   return LastIndexOf(item, m_size - 1, m_size);
  }
//+------------------------------------------------------------------+
//| Searches for the specified value and returns the zero-based index|
//| of the last occurrence within the range of elements in the list  |
//| that extends from the first element to the specified index.      |
//+------------------------------------------------------------------+
template<typename T>
int CArrayList::LastIndexOf(T item,const int start_index)
  {
//--- check start index
   if(start_index>=m_size)
      return(-1);

   return ArrayLastIndexOf(m_items, item, start_index, start_index+1);
  }
//+------------------------------------------------------------------+
//| Searches for the specified value and returns the zero-based      |
//| index of the last occurrence within the range of elements in the |
//| list that contains the specified number of elements and ends at  |
//| the specified index.                                             |
//+------------------------------------------------------------------+
template<typename T>
int CArrayList::LastIndexOf(T item,const int start_index,const int count)
  {
//--- check start index and count
   if(start_index<0 || count<0 || start_index>=m_size)
      return(-1);

   return ArrayLastIndexOf(m_items, item, start_index, MathMin(start_index+1,count));
  }
//+------------------------------------------------------------------+
//| Removes all elements from the list.                              |
//+------------------------------------------------------------------+
template<typename T>
void CArrayList::Clear(void)
  {
//--- check current size
   if(m_size>0)
     {
      ZeroMemory(m_items);
      m_size=0;
     }
  }
//+------------------------------------------------------------------+
//| Removes the element at the specified index of the list.          |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::RemoveAt(const int index)
  {
//--- check index  
   if((uint)index>=(uint)m_size)
      return(false);
//--- decrement size
   m_size--;
//--- shift the values to the left
   if(index<m_size)
      ArrayCopy(m_items,m_items,index,index+1,m_size-index);
   return(true);
  }
//+------------------------------------------------------------------+
//| Removes the first occurrence of a specific object from the list. |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::Remove(T item)
  {
//--- find index of value
   int index=IndexOf(item);
//--- delete element by index   
   if(index>=0)
      return RemoveAt(index);
   else
      return(false);
  }
//+------------------------------------------------------------------+
//| Removes a range of elements from the list.                       |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::RemoveRange(const int start_index,const int count)
  {
//--- check start index and count  
   if(start_index<0 || count<0 || m_size-start_index<count)
      return(false);
   if(count>0)
     {
      //--- decrement size
      m_size-=count;
      //--- shift the values to the left      
      if(start_index<m_size)
         ArrayCopy(m_items,m_items,start_index,start_index+count,m_size-start_index);
     }
   return(true);
  }
//+------------------------------------------------------------------+
//| Reverses the order of the elements in the entire list.           |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::Reverse(void)
  {
   return Reverse(0, m_size);
  }
//+------------------------------------------------------------------+
//| Reverses the order of the elements in the specified range.       |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::Reverse(const int start_index,const int count)
  {
//--- check start index and count  
   if(start_index<0 || count<0 || m_size-start_index<count)
      return(false);
   return ArrayReverse(m_items, start_index, count);
  }
//+------------------------------------------------------------------+
//| Sorts the elements in the entire list using the default comparer.|
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::Sort(void)
  {
   return Sort(0,m_size,NULL);
  }
//+------------------------------------------------------------------+
//| Sorts the elements in the entire list using the specified        |
//| comparer.                                                        |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::Sort(IComparer<T>*comparer)
  {
   return Sort(0,m_size,comparer);
  }
//+------------------------------------------------------------------+
//| Sorts the elements in a range of elements in list using the      |
//| specified comparer.                                              |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::Sort(const int start_index,const int count,IComparer<T>*comparer)
  {
//--- check start index and count  
   if(start_index<0 || count<0 || m_size-start_index<count)
      return(false);
//--- create instances of sorter
   Introsort<T,T>sorter();
//--- set array to sorter
   ArrayCopy(sorter.keys,m_items);
//--- check comparer
   if(CheckPointer(comparer)!=POINTER_INVALID)
     {
      //--- use specified comparer     
      sorter.comparer=comparer;
      //--- sort array
      sorter.Sort(start_index,count);
     }
   else
     {
      //--- use default comparer
      CDefaultComparer<T>def_comparer;
      sorter.comparer=GetPointer(def_comparer);
      //--- sort array
      sorter.Sort(start_index,count);
     }
//--- store the sorted array
   ArrayCopy(m_items,sorter.keys);
   return(true);
  }
//+------------------------------------------------------------------+
//| Ensures that the capacity of this list is at least the given     |
//| minimum value. If the currect capacity of the list is less than  |
//| min, the capacity is increased to twice the current capacity or  |
//| to min, whichever is larger.                                     |
//+------------------------------------------------------------------+
template<typename T>
void CArrayList::EnsureCapacity(const int min)
  {
   int size=ArraySize(m_items);
//--- check current size
   if(size<min)
     {
      int new_capacity=(size==0) ? m_default_capacity : size*2;
      //--- allow the list to grow to maximum possible capacity before encountering overflow
      if((uint)new_capacity>INT_MAX)
         new_capacity=INT_MAX;
      if(new_capacity<min)
         new_capacity=min;
      //--- set new capacity         
      Capacity(new_capacity);
     }
  }
//+------------------------------------------------------------------+