amirghadiri1987
617 lines
49 KiB
Plaintext
617 lines
49 KiB
Plaintext
//+------------------------------------------------------------------+
|
||
//| ArrayList.mqh |
|
||
//| Copyright 2000-2024, 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);
|
||
}
|
||
}
|
||
//+------------------------------------------------------------------+
|