341 lines
14 KiB
MQL5
341 lines
14 KiB
MQL5
//+------------------------------------------------------------------+
|
|
//| SortedMap.mqh |
|
|
//| Copyright 2000-2025, MetaQuotes Ltd. |
|
|
//| https://www.mql5.com |
|
|
//+------------------------------------------------------------------+
|
|
#include <Generic\Interfaces\IMap.mqh>
|
|
#include <Generic\Interfaces\IComparer.mqh>
|
|
#include <Generic\Internal\DefaultComparer.mqh>
|
|
#include <Generic\Internal\CompareFunction.mqh>
|
|
#include "HashMap.mqh"
|
|
#include "SortedSet.mqh"
|
|
//+------------------------------------------------------------------+
|
|
//| Class CSortedMap<TKey, TValue>. |
|
|
//| Usage: Represents a collection of key/value pairs that are sorted|
|
|
//| on the key. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
class CSortedMap: public IMap<TKey,TValue>
|
|
{
|
|
protected:
|
|
CRedBlackTree<CKeyValuePair<TKey,TValue>*>*m_tree;
|
|
IComparer<TKey>*m_comparer;
|
|
bool m_delete_comparer;
|
|
|
|
public:
|
|
CSortedMap(void);
|
|
CSortedMap(IComparer<TKey>*comparer);
|
|
CSortedMap(IMap<TKey,TValue>*map);
|
|
CSortedMap(IMap<TKey,TValue>*map,IComparer<TKey>*comparer);
|
|
~CSortedMap(void);
|
|
//--- methods of filling data
|
|
bool Add(CKeyValuePair<TKey,TValue>*value) { return m_tree.Add(value); }
|
|
bool Add(TKey key,TValue value);
|
|
//--- methods of access to protected data
|
|
int Count(void) { return m_tree.Count(); }
|
|
bool Contains(CKeyValuePair<TKey,TValue>*item) { return m_tree.Contains(item); }
|
|
bool Contains(TKey key,TValue value);
|
|
bool ContainsKey(TKey key);
|
|
bool ContainsValue(TValue value);
|
|
IComparer<TKey> *Comparer(void) const { return(m_comparer); }
|
|
//--- methods of copy data from collection
|
|
int CopyTo(CKeyValuePair<TKey,TValue>*&dst_array[],const int dst_start=0);
|
|
int CopyTo(TKey &dst_keys[],TValue &dst_values[],const int dst_start=0);
|
|
//--- methods of cleaning and deleting
|
|
void Clear(void);
|
|
bool Remove(CKeyValuePair<TKey,TValue>*item) { return m_tree.Remove(item); }
|
|
bool Remove(TKey key);
|
|
//--- method of access to the data
|
|
bool TryGetValue(TKey key,TValue &value);
|
|
bool TrySetValue(TKey key,TValue value);
|
|
|
|
private:
|
|
static void ClearNodes(CRedBlackTreeNode<CKeyValuePair<TKey,TValue>*>*node);
|
|
};
|
|
//+------------------------------------------------------------------+
|
|
//| Initializes a new instance of the CSortedMap<TKey,TValue> class |
|
|
//| that is empty, has the default initial capacity, and uses the |
|
|
//| default comparer for the key type. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
CSortedMap::CSortedMap(void)
|
|
{
|
|
//--- use default comaprer
|
|
m_comparer=new CDefaultComparer<TKey>();
|
|
m_delete_comparer=true;
|
|
m_tree=new CRedBlackTree<CKeyValuePair<TKey,TValue>*>(new CKeyValuePairComparer<TKey,TValue>(m_comparer));
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Initializes a new instance of the CSortedMap<TKey,TValue> class |
|
|
//| that is empty, has the default initial capacity, and uses the |
|
|
//| specified IComparer<TKey>. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
CSortedMap::CSortedMap(IComparer<TKey>*comparer)
|
|
{
|
|
//--- check comaprer
|
|
if(CheckPointer(comparer)==POINTER_INVALID)
|
|
{
|
|
//--- use default comaprer
|
|
m_comparer=new CDefaultComparer<TKey>();
|
|
m_delete_comparer=true;
|
|
}
|
|
else
|
|
{
|
|
//--- use specified comaprer
|
|
m_comparer=comparer;
|
|
m_delete_comparer=false;
|
|
}
|
|
m_tree=new CRedBlackTree<CKeyValuePair<TKey,TValue>*>(new CKeyValuePairComparer<TKey,TValue>(m_comparer));
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Initializes a new instance of the CSortedMap<TKey,TValue> class |
|
|
//| that contains elements copied from the specified |
|
|
//| IMap<TKey,TValue> and uses the default comparer for the key type.|
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
CSortedMap::CSortedMap(IMap<TKey,TValue>*map)
|
|
{
|
|
//--- use default comaprer
|
|
m_comparer=new CDefaultComparer<TKey>();
|
|
m_delete_comparer=true;
|
|
m_tree=new CRedBlackTree<CKeyValuePair<TKey,TValue>*>(map,new CKeyValuePairComparer<TKey,TValue>(m_comparer));
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Initializes a new instance of the CSortedMap<TKey,TValue> class |
|
|
//| that contains elements copied from the specified |
|
|
//| IMap<TKey,TValue> and uses the specified IComparer<TKey>. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
CSortedMap::CSortedMap(IMap<TKey,TValue>*map,IComparer<TKey>*comparer)
|
|
{
|
|
//--- check comaprer
|
|
if(CheckPointer(comparer)==POINTER_INVALID)
|
|
{
|
|
//--- use default comaprer
|
|
m_comparer=new CDefaultComparer<TKey>();
|
|
m_delete_comparer=true;
|
|
}
|
|
else
|
|
{
|
|
//--- use specified comaprer
|
|
m_comparer=comparer;
|
|
m_delete_comparer=false;
|
|
}
|
|
m_tree=new CRedBlackTree<CKeyValuePair<TKey,TValue>*>(map,new CKeyValuePairComparer<TKey,TValue>(m_comparer));
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Destructor. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
CSortedMap::~CSortedMap(void)
|
|
{
|
|
//--- delete comparer
|
|
if(m_delete_comparer)
|
|
delete m_comparer;
|
|
//--- delete tree comparer
|
|
delete m_tree.Comparer();
|
|
//--- delete nodes values
|
|
ClearNodes(m_tree.Root());
|
|
//--- delete tree and nodes
|
|
delete m_tree;
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Walk all nodes of tree and delete their value. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
static void CSortedMap::ClearNodes(CRedBlackTreeNode<CKeyValuePair<TKey,TValue>*>*node)
|
|
{
|
|
//--- check node
|
|
if(CheckPointer(node)==POINTER_INVALID)
|
|
return;
|
|
//--- walk of a right subtree
|
|
if(!node.Right().IsLeaf())
|
|
ClearNodes(node.Right());
|
|
//--- delete value
|
|
delete node.Value();
|
|
//--- walk of a left subtree
|
|
if(!node.Left().IsLeaf())
|
|
ClearNodes(node.Left());
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Adds the specified key and value to the map. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
bool CSortedMap::Add(TKey key,TValue value)
|
|
{
|
|
//--- create pair
|
|
CKeyValuePair<TKey,TValue>*pair=new CKeyValuePair<TKey,TValue>(key,value);
|
|
//--- add pair to tree
|
|
bool success=m_tree.Add(pair);
|
|
//--- if addition was not successful delte pair
|
|
if(!success)
|
|
delete pair;
|
|
return(success);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Determines whether the map contains the specified key with value.|
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
bool CSortedMap::Contains(TKey key,TValue value)
|
|
{
|
|
//--- find node with specified key
|
|
CKeyValuePair<TKey,TValue>pair(key,NULL);
|
|
CRedBlackTreeNode<CKeyValuePair<TKey,TValue>*>*node=m_tree.Find(GetPointer(pair));
|
|
//--- create value comparer
|
|
CDefaultEqualityComparer<TValue>comaprer;
|
|
//--- determine whether the finding node contains specified value
|
|
if(CheckPointer(node)!=POINTER_INVALID && comaprer.Equals(value,node.Value().Value()))
|
|
return(true);
|
|
return(false);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Determines whether the map contains the specified key. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
bool CSortedMap::ContainsKey(TKey key)
|
|
{
|
|
//--- crete pair
|
|
CKeyValuePair<TKey,TValue>pair(key,NULL);
|
|
//--- determines whether the tree contains the pair.
|
|
return m_tree.Contains(GetPointer(pair));
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Determines whether the map contains the specified value. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
bool CSortedMap::ContainsValue(TValue value)
|
|
{
|
|
//--- copy all pairs in array
|
|
CKeyValuePair<TKey,TValue>*array[];
|
|
int count=m_tree.CopyTo(array);
|
|
//--- create value comparer
|
|
CDefaultEqualityComparer<TValue>comaprer;
|
|
//--- determines whether the array contains the specified value
|
|
for(int i=0; i<count; i++)
|
|
if(comaprer.Equals(value,array[i].Value()))
|
|
return(true);
|
|
return(false);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Copies a range of elements from the map to a compatible |
|
|
//| one-dimensional array. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
int CSortedMap::CopyTo(CKeyValuePair<TKey,TValue>*&dst_array[],const int dst_start=0)
|
|
{
|
|
int result=m_tree.CopyTo(dst_array,dst_start);
|
|
if(result>0)
|
|
{
|
|
//--- create clones for each pair
|
|
for(int i=0; i<result; i++)
|
|
dst_array[dst_start+i]=dst_array[dst_start+i].Clone();
|
|
}
|
|
return(result);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Copies a range of elements from the map to a compatible |
|
|
//| one-dimensionals keys and values arrays. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
int CSortedMap::CopyTo(TKey &dst_keys[],TValue &dst_values[],const int dst_start=0)
|
|
{
|
|
//--- create array and copy all values from tree to there
|
|
CKeyValuePair<TKey,TValue>*array[];
|
|
int count=m_tree.CopyTo(array);
|
|
//--- check real cout
|
|
if(count>0)
|
|
{
|
|
//--- resize keys array
|
|
if(dst_start+count>ArraySize(dst_keys))
|
|
ArrayResize(dst_keys,dst_start+count);
|
|
//--- resize values array
|
|
if(dst_start+count>ArraySize(dst_values))
|
|
ArrayResize(dst_values,MathMin(ArraySize(dst_keys),dst_start+count));
|
|
//--- start copy
|
|
int index=0;
|
|
while(index<count && dst_start+index<ArraySize(dst_keys) && dst_start+index<ArraySize(dst_values))
|
|
{
|
|
dst_keys[dst_start+index]=array[index].Key();
|
|
dst_values[dst_start+index]=array[index].Value();
|
|
index++;
|
|
}
|
|
return(index);
|
|
}
|
|
return(0);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Clear and delete all values from map. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
void CSortedMap::Clear(void)
|
|
{
|
|
//--- check count
|
|
if(m_tree.Count()>0)
|
|
{
|
|
//--- delete nodes values
|
|
ClearNodes(m_tree.Root());
|
|
//--- claer th tree
|
|
m_tree.Clear();
|
|
}
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Removes the value with the specified key from the map. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
bool CSortedMap::Remove(TKey key)
|
|
{
|
|
//--- create pair with specified key
|
|
CKeyValuePair<TKey,TValue>pair(key,NULL);
|
|
//--- find node
|
|
CRedBlackTreeNode<CKeyValuePair<TKey,TValue>*>*node=m_tree.Find(GetPointer(pair));
|
|
//--- check node
|
|
if(CheckPointer(node)!=POINTER_INVALID)
|
|
{
|
|
CKeyValuePair<TKey,TValue>*real_pair=node.Value();
|
|
//--- remove node from tree
|
|
if(m_tree.Remove(node))
|
|
{
|
|
//--- check and delete node value
|
|
if(CheckPointer(real_pair)==POINTER_DYNAMIC)
|
|
delete real_pair;
|
|
return(true);
|
|
}
|
|
}
|
|
return(false);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Gets the value associated with the specified key. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
bool CSortedMap::TryGetValue(TKey key,TValue &value)
|
|
{
|
|
//--- create pair with specified key
|
|
CKeyValuePair<TKey,TValue>pair(key,NULL);
|
|
//--- find node with specified pair in the tree
|
|
CRedBlackTreeNode<CKeyValuePair<TKey,TValue>*>*node=m_tree.Find(GetPointer(pair));
|
|
//--- check node
|
|
if(CheckPointer(node)==POINTER_INVALID)
|
|
return(false);
|
|
//--- get value
|
|
value=node.Value().Value();
|
|
return(true);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Sets the value associated with the specified key. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TValue>
|
|
bool CSortedMap::TrySetValue(TKey key,TValue value)
|
|
{
|
|
//--- create pair with specified key
|
|
CKeyValuePair<TKey,TValue>pair(key,NULL);
|
|
//--- find node with specified pair in the tree
|
|
CRedBlackTreeNode<CKeyValuePair<TKey,TValue>*>*node=m_tree.Find(GetPointer(pair));
|
|
//--- check node
|
|
if(CheckPointer(node)==POINTER_INVALID)
|
|
return(false);
|
|
//--- set value
|
|
node.Value().Value(value);
|
|
return(true);
|
|
}
|
|
//+------------------------------------------------------------------+
|