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