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