//+------------------------------------------------------------------+
//|                                                      HashMap.mqh |
//|                             Copyright 2000-2025, MetaQuotes Ltd. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic\Interfaces\IMap.mqh>
#include <Generic\Interfaces\IEqualityComparer.mqh>
#include <Generic\Internal\DefaultEqualityComparer.mqh>
#include <Generic\Interfaces\IComparable.mqh>
#include <Generic\Internal\CompareFunction.mqh>
#include "HashSet.mqh"
//+------------------------------------------------------------------+
//| Struct Entry<TKey, TValue>.                                      |
//| Usage: Internal structure for organization CHashMap<T>.          |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
struct Entry: public Slot<TValue>
  {
public:
   TKey              key;
                     Entry(void): key((TKey)NULL) {}
  };
//+------------------------------------------------------------------+
//| Class CKeyValuePair<TKey, TValue>.                               |
//| Usage: Defines a key/value pair that can be set or retrieved.    |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
class CKeyValuePair: public IComparable<CKeyValuePair<TKey,TValue>*>
  {
protected:
   TKey              m_key;
   TValue            m_value;

public:
                     CKeyValuePair(void)                                              {   }
                     CKeyValuePair(TKey key,TValue value): m_key(key), m_value(value) {   }
                    ~CKeyValuePair(void)                                              {   }
   //--- methods to access protected data
   TKey              Key(void)           { return(m_key);   }
   void              Key(TKey key)       { m_key=key;       }
   TValue            Value(void)         { return(m_value); }
   void              Value(TValue value) { m_value=value;   }
   //--- method to create clone of current instance
   CKeyValuePair<TKey,TValue>*Clone(void) { return new CKeyValuePair<TKey,TValue>(m_key,m_value); }
   //--- method to compare keys
   int               Compare(CKeyValuePair<TKey,TValue>*pair) { return ::Compare(m_key,pair.m_key); }
   //--- method for determining equality
   bool              Equals(CKeyValuePair<TKey,TValue>*pair) { return ::Equals(m_key,pair.m_key); }
   //--- method to calculate hash code   
   int               HashCode(void) { return ::GetHashCode(m_key); }
  };
//+------------------------------------------------------------------+
//| Class CKeyValuePairComparer<TKey, TValue>.                       |
//| Usage: Provides a comparer class for convertation IComparer<TKey>|
//|        to the IComparer<CKeyValuePair<TKey, TValue>*> interface. |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
class CKeyValuePairComparer: public IComparer<CKeyValuePair<TKey,TValue>*>
  {
private:
   IComparer<TKey>*m_comparer;

public:
                     CKeyValuePairComparer(IComparer<TKey>*comaprer)                      { m_comparer=comaprer;                          }
   int               Compare(CKeyValuePair<TKey,TValue>* x,CKeyValuePair<TKey,TValue>* y) { return(m_comparer.Compare(x.Key(), y.Key())); }
  };
//+------------------------------------------------------------------+
//| Class CHashMap<TKey, TValue>.                                    |
//| Usage: Represents a collection of keys and values.               |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
class CHashMap: public IMap<TKey,TValue>
  {
protected:
   int               m_buckets[];
   Entry<TKey,TValue>m_entries[];
   int               m_count;
   int               m_capacity;
   int               m_free_list;
   int               m_free_count;
   IEqualityComparer<TKey>*m_comparer;
   bool              m_delete_comparer;

public:
                     CHashMap(void);
                     CHashMap(const int capacity);
                     CHashMap(IEqualityComparer<TKey>*comparer);
                     CHashMap(const int capacity,IEqualityComparer<TKey>*comparer);
                     CHashMap(IMap<TKey,TValue>*map);
                     CHashMap(IMap<TKey,TValue>*map,IEqualityComparer<TKey>*comparer);
                    ~CHashMap(void);
   //--- methods of filling data 
   bool              Add(CKeyValuePair<TKey,TValue>*pair);
   bool              Add(TKey key,TValue value);
   //--- methods of access to protected data
   int               Count(void)                                       { return(m_count-m_free_count); }
   IEqualityComparer<TKey>*Comparer(void)                        const { return(m_comparer);           }
   bool              Contains(CKeyValuePair<TKey,TValue>*item);
   bool              Contains(TKey key,TValue value);
   bool              ContainsKey(TKey key);
   bool              ContainsValue(TValue value);
   //--- 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);
   bool              Remove(TKey key);
   //--- method of access to the data
   bool              TryGetValue(TKey key,TValue &value);
   bool              TrySetValue(TKey key,TValue value);

private:
   void              Initialize(const int capacity);
   bool              Resize(int new_size);
   int               FindEntry(TKey key);
   bool              Insert(TKey key,TValue value,const bool add);
   static int        m_collision_threshold;
  };
//+------------------------------------------------------------------+
//| Initializes a new instance of the CHashMap<TKey,TValue> class    |
//| that is empty, has the default initial capacity, and uses the    |
//| default equality comparer for the key type.                      |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
CHashMap::CHashMap(void): m_count(0),
                          m_free_list(0),
                          m_free_count(0),
                          m_capacity(0)
  {
//--- use default equality comaprer   
   m_comparer=new CDefaultEqualityComparer<TKey>();
   m_delete_comparer=true;
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CHashMap<TKey,TValue> class    |
//| that is empty, has the specified initial capacity, and uses the  |
//| default equality comparer for the key type.                      |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
CHashMap::CHashMap(const int capacity): m_count(0),
                                        m_free_list(0),
                                        m_free_count(0),
                                        m_capacity(0)
  {
//--- set capacity 
   if(capacity>0)
      Initialize(capacity);
//--- use default equality comaprer    
   m_comparer=new CDefaultEqualityComparer<TKey>();
   m_delete_comparer=true;
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CHashMap<TKey,TValue> class    |
//| that is empty, has the default initial capacity, and uses the    |
//| specified IEqualityComparer<TKey>.                               |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
CHashMap::CHashMap(IEqualityComparer<TKey>*comparer): m_count(0),
                                                      m_free_list(0),
                                                      m_free_count(0),
                                                      m_capacity(0)
  {
//--- check equality comaprer
   if(CheckPointer(comparer)==POINTER_INVALID)
     {
      //--- use default equality comaprer    
      m_comparer=new CDefaultEqualityComparer<TKey>();
      m_delete_comparer=true;
     }
   else
     {
      //--- use specified equality comaprer
      m_comparer=comparer;
      m_delete_comparer=false;
     }
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CHashMap<TKey,TValue> class    |
//| that is empty, has the specified initial capacity, and uses the  |
//| specified IEqualityComparer<TKey>.                               |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
CHashMap::CHashMap(const int capacity,IEqualityComparer<TKey>*comparer): m_count(0),
                                                                         m_free_list(0),
                                                                         m_free_count(0),
                                                                         m_capacity(0)
  {
   if(capacity>0)
      Initialize(capacity);
//--- check equality comaprer
   if(CheckPointer(comparer)==POINTER_INVALID)
     {
      //--- use default equality comaprer    
      m_comparer=new CDefaultEqualityComparer<TKey>();
      m_delete_comparer=true;
     }
   else
     {
      //--- use specified equality comaprer
      m_comparer=comparer;
      m_delete_comparer=false;
     }
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CHashMap<TKey,TValue> class    |
//| that contains elements copied from the specified                 |
//| IMap<TKey,TValue> and uses the default equality comparer for the |
//| key type.                                                        |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
CHashMap::CHashMap(IMap<TKey,TValue>*map): m_count(0),
                                           m_free_list(0),
                                           m_free_count(0),
                                           m_capacity(0)
  {
//--- use default equality comaprer    
   m_comparer=new CDefaultEqualityComparer<TKey>();
   m_delete_comparer=true;
//--- check map
   if(CheckPointer(map)!=POINTER_INVALID && map.Count()>0)
     {
      //--- set capacity 
      Initialize(map.Count());
      TKey keys[];
      TValue values[];
      map.CopyTo(keys,values);
      //--- copy all keys and values from specified map to current map      
      for(int i=0; i<map.Count(); i++)
         Add(keys[i],values[i]);
     }
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CHashMap<TKey,TValue> class    |
//| that contains elements copied from the specified                 |
//| IMap<TKey,TValue> and uses the specified IEqualityComparer<TKey>.|
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
CHashMap::CHashMap(IMap<TKey,TValue>*map,IEqualityComparer<TKey>*comparer): m_count(0),
                                                                            m_free_list(0),
                                                                            m_free_count(0),
                                                                            m_capacity(0)
  {
//--- check equality comaprer
   if(CheckPointer(comparer)==POINTER_INVALID)
     {
      //--- use default equality comaprer    
      m_comparer=new CDefaultEqualityComparer<TKey>();
      m_delete_comparer=true;
     }
   else
     {
      //--- use specified equality comaprer
      m_comparer=comparer;
      m_delete_comparer=false;
     }
//--- check map
   if(CheckPointer(map)!=POINTER_INVALID && map.Count()>0)
     {
      //--- set capacity 
      Initialize(map.Count());
      TKey keys[];
      TValue values[];
      map.CopyTo(keys,values);
      //--- copy all keys and values from specified map to current map      
      for(int i=0; i<map.Count(); i++)
         Add(keys[i],values[i]);
     }
  }
//+------------------------------------------------------------------+
//| Destructor.                                                      |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
CHashMap::~CHashMap(void)
  {
   if(m_delete_comparer)
      delete m_comparer;
  }
//+------------------------------------------------------------------+
//| Adds the specified key-value pair to the map.                    |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Add(CKeyValuePair<TKey,TValue>*pair)
  {
//--- check pair
   if(CheckPointer(pair)==POINTER_INVALID)
      return(false);
   return(Add(pair.Key(),pair.Value()));
  }
//+------------------------------------------------------------------+
//| Adds the specified key and value to the map.                     |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Add(TKey key,TValue value)
  {
   return(Insert(key,value,true));
  }
//+------------------------------------------------------------------+
//| Determines whether the map contains the specified key-value pair.|
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Contains(CKeyValuePair<TKey,TValue>*item)
  {
//--- check pair
   if(CheckPointer(item)==POINTER_INVALID)
      return(false);
//--- find pair with specified key
   int i=FindEntry(item.Key());
//--- create default equality value comparer
   CDefaultEqualityComparer<TValue>comparer;
//--- check value is equal value from the found pair      
   if(i>=0 && comparer.Equals(m_entries[i].value,item.Value()))
      return(true);
   else
      return(false);
  }
//+------------------------------------------------------------------+
//| Determines whether the map contains the specified key with value.|
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Contains(TKey key,TValue value)
  {
//--- find pair with specified key
   int i=FindEntry(key);
//--- create default equality value comparer
   CDefaultEqualityComparer<TValue>comparer;
//--- check value is equal value from the found pair      
   if(i>=0 && comparer.Equals(m_entries[i].value,value))
      return(true);
   else
      return(false);
  }
//+------------------------------------------------------------------+
//| Determines whether the map contains the specified key.           |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::ContainsKey(TKey key)
  {
   return(FindEntry(key)>=0);
  }
//+------------------------------------------------------------------+
//| Determines whether the map contains the specified value.         |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::ContainsValue(TValue value)
  {
//--- create default equality value comparer
   CDefaultEqualityComparer<TValue>comparer_value();
//--- try to find pair contains specified value
   for(int i=0; i<m_count; i++)
      if(m_entries[i].hash_code>=0 && comparer_value.Equals(m_entries[i].value,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 CHashMap::CopyTo(CKeyValuePair<TKey,TValue>*&dst_array[],const int dst_start=0)
  {
//--- resize array
   if(dst_start+m_count>ArraySize(dst_array))
      ArrayResize(dst_array,dst_start+m_count);
//--- start copy
   int index=0;
   for(int i=0; i<ArraySize(m_entries); i++)
      if(m_entries[i].hash_code>=0)
        {
         //--- check indexes
         if(dst_start+index>=ArraySize(dst_array) || index>=m_count)
            return(index);
         dst_array[dst_start+index++]=new CKeyValuePair<TKey,TValue>(m_entries[i].key,m_entries[i].value);
        }
   return(index);
  }
//+------------------------------------------------------------------+
//| Copies a range of elements from the map to a compatible          |
//| one-dimensionals keys and values arrays.                         |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
int CHashMap::CopyTo(TKey &dst_keys[],TValue &dst_values[],const int dst_start=0)
  {
   int count=m_count-m_free_count;
//--- 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;
   for(int i=0; i<ArraySize(m_entries); i++)
      if(m_entries[i].hash_code>=0)
        {
         //--- check indexes
         if(dst_start+index>=ArraySize(dst_keys) || dst_start+index>=ArraySize(dst_values) || index>=count)
            return(index);
         dst_keys[dst_start+index]=m_entries[i].key;
         dst_values[dst_start+index]=m_entries[i].value;
         index++;
        }
   return(index);
  }
//+------------------------------------------------------------------+
//| Removes all keys and values from the map.                        |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
void CHashMap::Clear(void)
  {
//--- check count
   if(m_count>0)
     {
      ArrayFill(m_buckets,0,m_capacity,-1);
      ArrayFree(m_entries);
      m_count=0;
      m_free_list=-1;
      m_free_count=0;
     }
  }
//+------------------------------------------------------------------+
//| Removes the specified key-value pair from map.                   |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Remove(CKeyValuePair<TKey,TValue>*item)
  {
//--- check pair
   if(CheckPointer(item)==POINTER_INVALID)
      return(false);
//--- find pair with specified key
   int i=FindEntry(item.Key());
//--- create default equality value comparer
   CDefaultEqualityComparer<TValue>comparer_value();
//--- remove pair   
   if(i>=0 && comparer_value.Equals(m_entries[i].value,item.Value()))
      return Remove(item.Key());
   return(false);
  }
//+------------------------------------------------------------------+
//| Removes the value with the specified key from the map.           |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Remove(TKey key)
  {
   if(m_capacity!=0)
     {
      int hash_code=m_comparer.HashCode(key)&0x7FFFFFFF;
      int bucket=hash_code%m_capacity;
      int last=-1;
      //--- search pair with specified key
      for(int i=m_buckets[bucket]; i>=0; last=i,i=m_entries[i].next)
        {
         if(m_entries[i].hash_code==hash_code && m_comparer.Equals(m_entries[i].key,key))
           {
            if(last<0)
               m_buckets[bucket]=m_entries[i].next;
            else
               m_entries[last].next=m_entries[i].next;
            //--- remove pair
            m_entries[i].hash_code=-1;
            m_entries[i].next=m_free_list;
            m_entries[i].key=(TKey)NULL;
            m_entries[i].value=(TValue)NULL;
            //--- incremet free count
            m_free_list=i;
            m_free_count++;
            return(true);
           }
        }
     }
   return(false);
  }
//+------------------------------------------------------------------+
//| Gets the value associated with the specified key.                |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::TryGetValue(TKey key,TValue &value)
  {
//--- find pair with specified key
   int i=FindEntry(key);
//--- check index
   if(i>=0)
     {
      //--- get value     
      value=m_entries[i].value;
      return(true);
     }
   return(false);
  }
//+------------------------------------------------------------------+
//| Sets the value associated with the specified key.                |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::TrySetValue(TKey key,TValue value)
  {
   return(Insert(key, value, false));
  }
//+------------------------------------------------------------------+
//| Initialize map with specified capacity.                          |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
void CHashMap::Initialize(const int capacity)
  {
   m_capacity=CPrimeGenerator::GetPrime(capacity);
   ArrayResize(m_buckets,m_capacity);
   ArrayFill(m_buckets,0,m_capacity,-1);
   ArrayResize(m_entries,m_capacity);
   m_free_list=-1;
  }
//+------------------------------------------------------------------+
//| Resize map.                                                      |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Resize(const int new_size)
  {
//--- resize buckets
   if(ArrayResize(m_buckets,new_size)!=new_size)
      return(false);
   ArrayFill(m_buckets,0,new_size,-1);
//--- resize entries
   if(ArrayResize(m_entries,new_size)!=new_size)
      return(false);
//--- restore buckets
   for(int i=0; i<m_count; i++)
      if(m_entries[i].hash_code>=0)
        {
         int bucket=m_entries[i].hash_code%new_size;
         m_entries[i].next = m_buckets[bucket];
         m_buckets[bucket] = i;
        }
//--- restore capacity
   m_capacity=new_size;
   return(true);
  }
//+------------------------------------------------------------------+
//| Find index of entry with specified key.                          |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
int CHashMap::FindEntry(TKey key)
  {
   if(m_capacity!=NULL)
     {
      //--- get hash code from key
      int hash_code=m_comparer.HashCode(key)&0x7FFFFFFF;
      //--- search pair with specified key
      for(int i=m_buckets[hash_code%m_capacity]; i>=0; i=m_entries[i].next)
         if(m_entries[i].hash_code==hash_code && m_comparer.Equals(m_entries[i].key,key))
            return(i);
     }
   return(-1);
  }
//+------------------------------------------------------------------+
//| Insert the value with the specified key from the map.            |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Insert(TKey key,TValue value,const bool add)
  {
   if(m_capacity==0)
      Initialize(0);
//--- get hash code from key
   int hash_code=m_comparer.HashCode(key)&0x7FFFFFFF;
   int target_bucket=hash_code%m_capacity;
//--- collisions count in one bucket with different hashes
   int collision_count=0;
//--- search pair with specified key
   for(int i=m_buckets[target_bucket]; i>=0; i=m_entries[i].next)
     {
      //--- hash compare
      if(m_entries[i].hash_code!=hash_code)
        {
         collision_count++;
         continue;
        }
      //--- value compare
      if(m_comparer.Equals(m_entries[i].key,key))
        {
         //--- adding duplicate
         if(add)
            return(false);
         m_entries[i].value=value;
         return(true);
        }
     }
//--- check collision
   if(collision_count>=m_collision_threshold)
     {
      int new_size=CPrimeGenerator::ExpandPrime(m_count);
      if(!Resize(new_size))
         return(false);
      target_bucket=hash_code%new_size;
     }
//--- calculate index
   int index;
   if(m_free_count>0)
     {
      index=m_free_list;
      m_free_list=m_entries[index].next;
      m_free_count--;
     }
   else
     {
      if(m_count==ArraySize(m_entries))
        {
         int new_size=CPrimeGenerator::ExpandPrime(m_count);
         if(!Resize(new_size))
            return(false);
         target_bucket=hash_code%new_size;
        }
      index=m_count;
      m_count++;
     }
//--- set pair
   m_entries[index].hash_code=hash_code;
   m_entries[index].next=m_buckets[target_bucket];
   m_entries[index].key=key;
   m_entries[index].value=value;
   m_buckets[target_bucket]=index;
   return(true);
  }
template<typename TKey,typename TValue>
static int CHashMap::m_collision_threshold=8;
//+------------------------------------------------------------------+