//+------------------------------------------------------------------+
//|                                            AssociativeArrays.mqh |
//|                                   Copyright 2016, Alain Verleyen |
//|                     https://login.mql5.com/en/users/angevoyageur |
//+------------------------------------------------------------------+
#property copyright "Copyright 2016, Alain Verleyen"
#property link      "http://www.phpinternalsbook.com/hashtables.html"

#include <Object.mqh>
//#include <Hash.mqh>
//+------------------------------------------------------------------+
//| Enumeration of possible actions (hashtable)                      |
//+------------------------------------------------------------------+
enum ENUM_HASH_ACTION
  {
   HASH_UPDATE=(1<<0),
   HASH_ADD=(1<<1),
   HASH_NEXT_INSERT=(1<<2),
   HASH_DEL_KEY=(1<<3),
   HASH_DEL_INDEX=(1<<4)
  };
//+------------------------------------------------------------------+
//| Class to manage Hashtable data                                   |
//+------------------------------------------------------------------+
template<typename T>
class CBucket
  {
private:
   ulong             hash;                                           /* Used for numeric indexing */
   uint              nKeyLength;
   T                *pData;
   CBucket          *pListNext;
   CBucket          *pListLast;
   CBucket          *pNext;
   CBucket          *pLast;
   string            arKey;

   //--- public interface
public:
                     CBucket(ulong h,uint kl,string key);
                    ~CBucket(void);
   //--- methods
   void              Link(CBucket *current);
   //--- Getters
   uint              KeyLength(void);
   ulong             Hash(void);
   T                *DataPtr(void);
   CBucket          *ListNext(void);
   CBucket          *ListLast(void);
   CBucket          *Next(void);
   CBucket          *Last(void);
   string            Key(void);
   //--- Setters
   void              SetNewNumericKey(ulong ikey);
   void              DataPtr(T *data);
   void              ListNext(CBucket *ptr);
   void              ListLast(CBucket *ptr);
   void              Next(CBucket *ptr);
   void              Last(CBucket *ptr);
  };
//+------------------------------------------------------------------+
//| Constructor                                                      |
//+------------------------------------------------------------------+
template<typename T>
void CBucket::CBucket(ulong h,uint kl,string key) : hash(h),nKeyLength(kl),arKey(key)
  {
  }
//+------------------------------------------------------------------+
//| Destructor                                                       |
//+------------------------------------------------------------------+
template<typename T>
void CBucket::~CBucket(void)
  {
   if(CheckPointer(pData)==POINTER_DYNAMIC)
     {
      delete pData;
     }
  }
//+------------------------------------------------------------------+
//| Link method used to insert a new Bucket                          |
//+------------------------------------------------------------------+
template<typename T>
void CBucket::Link(CBucket *current)
  {
   pNext=current;
   pLast=NULL;
   if(pNext!=NULL) pNext.pLast=GetPointer(this);
  }
//+------------------------------------------------------------------+
//| Set a new numeric key                                            |
//+------------------------------------------------------------------+
template<typename T>
void CBucket::SetNewNumericKey(ulong ikey)
  {
   hash=ikey;
   nKeyLength=0;
  }
//+------------------------------------------------------------------+
//| Getter KeyLength                                                 |
//+------------------------------------------------------------------+
template<typename T>
uint CBucket::KeyLength(void)
  {
   return(nKeyLength);
  }
//+------------------------------------------------------------------+
//| Getter Hash                                                      |
//+------------------------------------------------------------------+
template<typename T>
ulong CBucket::Hash(void)
  {
   return(hash);
  }
//+------------------------------------------------------------------+
//| Get pointer to data                                              |
//+------------------------------------------------------------------+
template<typename T>
T *CBucket::DataPtr(void)
  {
   return(pData);
  }
//+------------------------------------------------------------------+
//| Getter ListNext                                                  |
//+------------------------------------------------------------------+
template<typename T>
CBucket *CBucket::ListNext(void)
  {
   return(pListNext);
  }
//+------------------------------------------------------------------+
//| Getter ListLast                                                  |
//+------------------------------------------------------------------+
template<typename T>
CBucket *CBucket::ListLast(void)
  {
   return(pListLast);
  }
//+------------------------------------------------------------------+
//| Getter Next                                                      |
//+------------------------------------------------------------------+
template<typename T>
CBucket *CBucket::Next(void)
  {
   return(pNext);
  }
//+------------------------------------------------------------------+
//| Getter Last                                                      |
//+------------------------------------------------------------------+
template<typename T>
CBucket *CBucket::Last(void)
  {
   return(pLast);
  }
//+------------------------------------------------------------------+
//| Getter string Key                                                |
//+------------------------------------------------------------------+
template<typename T>
string CBucket::Key(void)
  {
   return(arKey);
  }
//+------------------------------------------------------------------+
//| Setter Data                                                      |
//+------------------------------------------------------------------+
template<typename T>
void CBucket::DataPtr(T *data)
  {
   pData=data;
  }
//+------------------------------------------------------------------+
//| Setter ListNext                                                  |
//+------------------------------------------------------------------+
template<typename T>
void CBucket::ListNext(CBucket *ptr)
  {
   pListNext=ptr;
  }
//+------------------------------------------------------------------+
//| Setter Last                                                      |
//+------------------------------------------------------------------+
template<typename T>
void CBucket::ListLast(CBucket *ptr)
  {
   pListLast=ptr;
  }
//+------------------------------------------------------------------+
//| Setter Next                                                      |
//+------------------------------------------------------------------+
template<typename T>
void CBucket::Next(CBucket *ptr)
  {
   pNext=ptr;
  }
//+------------------------------------------------------------------+
//| Setter Last                                                      |
//+------------------------------------------------------------------+
template<typename T>
void CBucket::Last(CBucket *ptr)
  {
   pLast=ptr;
  }
//+------------------------------------------------------------------+
//| Class implementing associative arrays ala PHP                    |
//+------------------------------------------------------------------+
template<typename T>
class CHashTable
  {
private:
   uint              _tableSize;
   uint              _tableMask;
   uint              _countItems;
   ulong             _nextFreeElement;
   CBucket<T>*_internalPointer;    /* Used for item traversal */
   CBucket<T>*_listHead;
   CBucket<T>*_listTail;
   CBucket<T>*_buckets[];
   uchar             nApplyCount;
   //--- methods
   void              _check_init();
   void              _reset_buckets(void);
   bool              _index_update_or_next_insert(ulong hash,T *data,int flag);
   bool              _add_or_update(string pKey,T *pData,int flag);
   bool              _del_key_or_index(string arKey,ulong h,int flag);
   void              _bucket_delete(CBucket<T>*p);
   void              _link_new(CBucket<T>*newBucket,CBucket<T>*last,CBucket<T>*next);
   void              _resize(void);
   bool              _rehash(void);
   void              _reindex(bool only_integer_keys);

   //--- public interface
public:
                     CHashTable(uint);
                    ~CHashTable(void);
   //--- methods
   uint              ItemsCount()                                       { return(_countItems); };
   bool              Update(string pKey,T *pData)                       { return(_add_or_update(pKey,pData,HASH_UPDATE)); };
   bool              Add(string pKey,T *pData)                          { return(_add_or_update(pKey,pData,HASH_ADD)); };
   bool              Add(ulong h,T *pData)                              { return(_index_update_or_next_insert(h, pData, HASH_UPDATE)); };
   bool              InsertNextIndex(T *pData)                          { return(_index_update_or_next_insert(0,pData,HASH_NEXT_INSERT)); };
   bool              Delete(string pKey)                                { return(_del_key_or_index(pKey,0,HASH_DEL_KEY)); };
   bool              Delete(ulong h)                                    { return(_del_key_or_index("",h,HASH_DEL_INDEX)); };
   bool              ExistsIntegerKey(ulong iKey);
   bool              Find(ulong pHash,T *&pData);
   bool              Find(string pKey,T *&pData);
   void              Clear(void);
   //---
   T                *First(void);
   T                *Next(void);
   bool              IsEnding(void);
   string            GetCurrentKey(bool &isNumeric);
  };
//+------------------------------------------------------------------+
//| Constructor                                                      |
//+------------------------------------------------------------------+
template<typename T>
void CHashTable::CHashTable(uint pSize)
  {
   uint i=3;

//--- check size
   if(pSize>=0x80000000)
     {
      //--- prevent overflow 
      _tableSize=0x80000000;
     }
   else
     {
      //--- table size is a power of 2
      while((uint(1)<<i)<pSize)
        {
         i++;
        }
      _tableSize=1<<i;
     }
//---
   _tableMask           = 0;                          //--- means that _buckets is uninitialized
   _listHead            = NULL;                       //
   _listTail            = NULL;
   _countItems          = 0;
   _nextFreeElement     = 0;
   _internalPointer     = NULL;
   nApplyCount          = 0;
  }
//+------------------------------------------------------------------+
//| Destructor                                                       |
//+------------------------------------------------------------------+
template<typename T>
void CHashTable::~CHashTable(void)
  {
   CBucket<T>*current,*next;

   current=_listHead;
   while(current!=NULL)
     {
      next=current.ListNext();
      delete current;
      current=next;
     }
   if(_tableMask!=0)
     {
      ArrayFree(_buckets);
     }
  }
//+------------------------------------------------------------------+
//| Reset all bucket pointers                                        |
//+------------------------------------------------------------------+
template<typename T>
CHashTable::_reset_buckets(void)
  {
   for(uint i=0;i<_tableSize;i++) _buckets[i]=NULL;
  }
//+------------------------------------------------------------------+
//| Initialize on first add/update                                   |
//+------------------------------------------------------------------+
template<typename T>
void CHashTable::_check_init(void)
  {
   if(_tableMask==0)
     {
      ArrayResize(_buckets,_tableSize);
      _tableMask=_tableSize-1;
     }
  }
//+------------------------------------------------------------------+
//| Add or Update a pair Key/Data                                    |
//+------------------------------------------------------------------+
template<typename T>
bool CHashTable::_add_or_update(string pKey,T *pData,int flag)
  {
   ulong hash;
   uint index,nKeyLength;
   CBucket<T>*current;

//TODO   ZEND_ASSERT(nKeyLength!=0);
//_tableMask ?
   _check_init();

   hash=Hash_DJBX33A(pKey,nKeyLength);
   index=uint(hash&_tableMask);

   current=_buckets[index];
   while(current!=NULL)
     {
      if(current.Key()==pKey || 
         (current.Hash()==hash && current.KeyLength()==nKeyLength && current.Key()==pKey))
        {
         if(bool(flag&HASH_ADD))
           {
            return(false);
           }
         //TODO ZEND_ASSERT(current.pData!=pData);
         //            UPDATE_DATA(ht,current,pData,nDataSize);
         current.DataPtr(pData);
         return(true);
        }
      current=current.Next();
     }

   current=new CBucket<T>(hash,nKeyLength,pKey);
   current.DataPtr(pData);
//   CONNECT_TO_BUCKET_DLLIST(current,_buckets[index]);
   current.Link(_buckets[index]);

//   CONNECT_TO_GLOBAL_DLLIST(current,ht);
   _link_new(current,_listTail,NULL);

   _buckets[index]=current;

   _countItems++;

//--- If the Hash table is full, resize it 
   if(_countItems>_tableSize)
     {
      _resize();
     }
//---
   return(true);
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename T>
void CHashTable::_link_new(CBucket<T>*newBucket,CBucket<T>*last,CBucket<T>*next)
  {
//   CONNECT_TO_GLOBAL_DLLIST_EX(current,ht,(ht)->_listTail,(Bucket *) NULL);   \
// CONNECT_TO_GLOBAL_DLLIST_EX(element, ht, last, next)
   newBucket.ListLast(_listTail);
   newBucket.ListNext(NULL);
   if(_listTail!=NULL)
     {
      _listTail.ListNext(newBucket);
     }
   else
     {
      _listHead=newBucket;
     }
   if(next!=NULL)
     {
      next.ListLast(newBucket);
     }
   else
     {
      _listTail=newBucket;
     }
//---
   if(_internalPointer==NULL)
     {
      _internalPointer=newBucket;
     }
  }
//+------------------------------------------------------------------+
//| Resize the hash table to next size (*2)                          |
//+------------------------------------------------------------------+
template<typename T>
void CHashTable::_resize(void)
  {
   uint newSize;

   if((newSize=(_tableSize<<1))>0)
     {
      //--- Let's double the table size
      ArrayResize(_buckets,newSize);
      _tableSize=newSize;
      _tableMask=_tableSize-1;
      _rehash();
     }
  }
//+------------------------------------------------------------------+
//| Re-allocate the hash table                                       |
//+------------------------------------------------------------------+
template<typename T>
bool CHashTable::_rehash(void)
  {
   CBucket<T>*current;
   uint index;

//--- check
   if(_countItems==0)
      return(true);

//--- reset all pointers
   _reset_buckets();

//--- re-link all buckets
   for(current=_listHead; current!=NULL; current=current.ListNext())
     {
      index=uint(current.Hash()&_tableMask);
      current.Link(_buckets[index]);
      _buckets[index]=current;
     }
//---
   return(true);
  }
//+------------------------------------------------------------------+
//| Reset all the hashtable                                          |
//+------------------------------------------------------------------+
template<typename T>
void CHashTable::Clear(void)
  {
   CBucket<T>*current,*next;

   current=_listHead;

   if(_tableMask!=0)
     {
      //--- reset all pointers
      _reset_buckets();
     }
   _listHead = NULL;
   _listTail = NULL;
   _countItems=0;
   _nextFreeElement = 0;
   _internalPointer = NULL;

   while(current!=NULL)
     {
      next=current.ListNext();
      delete current;
      current=next;
     }
  }
//+------------------------------------------------------------------+
//| Check if an integer key exists                                   |
//+------------------------------------------------------------------+
template<typename T>
bool CHashTable::ExistsIntegerKey(ulong iKey)
  {
   CBucket<T>*current;
   uint index=uint(iKey&_tableMask);
//---
   current=_buckets[index];
   while(current!=NULL)
     {
      if((current.Hash()==iKey) && (current.KeyLength()==0))
        {
         return(true);
        }
      current=current.Next();
     }
//---
   return(false);
  }
//+------------------------------------------------------------------+
//| Find a bucket by hash (integer key)                              |
//+------------------------------------------------------------------+
template<typename T>
bool CHashTable::Find(ulong pHash,T *&pData)
  {
   CBucket<T>*pointer;
   uint index=uint(pHash&_tableMask);

   pointer=_buckets[index];
   while(pointer!=NULL)
     {
      if(pointer.Hash()==pHash && pointer.KeyLength()==0)
        {
         pData=pointer.DataPtr();
         return(true);
        }
      pointer=pointer.Next();
     }
//---
   return(false);
  }
//+------------------------------------------------------------------+
//| Find a bucket by key (string key)                                |
//+------------------------------------------------------------------+
template<typename T>
bool CHashTable::Find(string pKey,T *&pData)
  {
   CBucket<T>*pointer;
   uint index,nKeyLength=0;

   ulong hash=Hash_DJBX33A(pKey,nKeyLength);
   index=uint(hash&_tableMask);

   pointer=_buckets[index];
   while(pointer!=NULL)
     {
      if(pointer.Key()==pKey || 
         (pointer.Hash()==hash && pointer.KeyLength()==nKeyLength && pointer.Key()==pKey))
        {
         pData=pointer.DataPtr();
         return(true);
        }
      pointer=pointer.Next();
     }
//---
   return(false);
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename T>
bool CHashTable::_del_key_or_index(string arKey,ulong h,int flag)
  {
   CBucket<T>*current;
   uint index,nKeyLength=0;

   if(flag==HASH_DEL_KEY)
     {
      h=Hash_DJBX33A(arKey,nKeyLength);
     }
   index=uint(h&_tableMask);

   current=_buckets[index];
   while(current!=NULL)
     {
      if(current.Hash()==h
         && current.KeyLength()==nKeyLength
         &&(current.KeyLength()==0 || current.Key()==arKey))
        {
         _bucket_delete(current);
         return(true);
        }
      current=current.Next();
     }
//---
   return(false);
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename T>
void CHashTable::_bucket_delete(CBucket<T>*p)
  {
   if(p.Last()!=NULL)
     {
      p.Last().Next(p.Next());
     }
   else
     {
      _buckets[uint(p.Hash()&_tableMask)]=p.Next();
     }
   if(p.Next()!=NULL)
     {
      p.Next().Last(p.Last());
     }
   if(p.ListLast()!=NULL)
     {
      p.ListLast().ListNext(p.ListNext());
     }
   else
     {
      //--- Deleting the head of the list
      _listHead=p.ListNext();
     }
   if(p.ListNext()!=NULL)
     {
      p.ListNext().ListLast(p.ListLast());
     }
   else
     {
      //--- Deleting the tail of the list
      _listTail=p.ListLast();
     }
   if(_internalPointer==p)
     {
      _internalPointer=p.ListNext();
     }
   _countItems--;
   delete p;
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename T>
bool CHashTable::_index_update_or_next_insert(ulong pHash,T *pData,int pFlag)
  {
   CBucket<T>*current;
   uint index;

//--- check table is initialized
   _check_init();

//--- check if auto insert (pHash=0)
   if(bool(pFlag&HASH_NEXT_INSERT))
     {
      pHash=_nextFreeElement;
     }
//--- get index
   index=uint(pHash&_tableMask);

//--- check if a bucket already exists with this key
   current=_buckets[index];
   while(current!=NULL)
     {
      if((current.KeyLength()==0) && (current.Hash()==pHash))
        {
         if(bool(pFlag&HASH_NEXT_INSERT) || bool(pFlag&HASH_ADD))
           {
            return(false);
           }
         //--- update data (if different)
         if(current.DataPtr()!=pData)
           {      //TODO delete old pointer ?
            if(CheckPointer(pData)==POINTER_DYNAMIC) delete current.DataPtr();
            current.DataPtr(pData);
           }
         //---
         return(true);
        }
      current=current.Next();
     }
//--- Numeric indices are marked by making the KeyLength == 0
   current=new CBucket<T>(pHash,0,NULL);
   current.DataPtr(pData);

//--- link new bucket ...
   current.Link(_buckets[index]);

   _buckets[index]=current;
//   CONNECT_TO_GLOBAL_DLLIST(current,ht);
//--- attach new bucket in the list
   _link_new(current,_listTail,NULL);

//--- update next free element
   if((long)pHash>=(long)_nextFreeElement)
     {
      _nextFreeElement=pHash<LONG_MAX ? pHash+1 : LONG_MAX;
     }
//--- adjust element count
   _countItems++;
   if(_countItems>_tableSize)
      _resize();
//---
   return(true);
  }
//+------------------------------------------------------------------+
//| Method of reindexing all buckets                                 |
//+------------------------------------------------------------------+
template<typename T>
void CHashTable::_reindex(bool only_integer_keys)
  {
   CBucket<T>*current;
   uint index;
   ulong offset=0;

   if(_countItems==0)
     {
      _nextFreeElement=0;
      return;
     }
//--- reset all pointers
   _reset_buckets();
//---
   for(current=_listHead; current!=NULL; current=current.ListNext())
     {
      if(!only_integer_keys || current.KeyLength()==0)
        {
         current.SetNewNumericKey(offset++);
        }

      index=uint(current.Hash()&_tableMask);
      current.Link(_buckets[index]);
      _buckets[index]=current;
     }
   _nextFreeElement=offset;
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename T>
T *CHashTable::First(void)
  {
   _internalPointer=_listHead;
//---
   return(_internalPointer==NULL ? NULL : _internalPointer.DataPtr());
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename T>
T *CHashTable::Next(void)
  {
   if(_internalPointer!=NULL)
     {
      _internalPointer=_internalPointer.ListNext();
     }
//---
   return(_internalPointer==NULL ? NULL : _internalPointer.DataPtr());
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename T>
bool CHashTable::IsEnding(void)
  {
   return(_internalPointer==NULL);
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename T>
string CHashTable::GetCurrentKey(bool &isNumeric)
  {
   if(_internalPointer!=NULL)
     {
      isNumeric=(_internalPointer.KeyLength()==0);
      return(isNumeric ? (string)_internalPointer.Hash() : _internalPointer.Key());
     }
//---
   return(NULL);
  }
//+------------------------------------------------------------------+
//| Associative array ala PHP                                        |
//+------------------------------------------------------------------+
template<typename T>
class CAssocArray : public CHashTable<T>
  {
private:

   //--- public interface
public:
                     CAssocArray(void) : CHashTable<T>(0) {};
                    ~CAssocArray(void) {};
   template<typename K>
   T                *operator[](K Key);
  };
//+------------------------------------------------------------------+
//| Overload [] operator                                             |
//+------------------------------------------------------------------+
template<typename T>
template<typename K>
T *CAssocArray::operator[](K key)
  {
   T          *__data;
   if(Find(key,__data))
     {
      return(__data);
     }
//---
   return(NULL);
  };
ulong Hash_DJBX33A(const string inKey,uint &outKeyLength)
  {
   char key[];
   outKeyLength=StringToCharArray(inKey,key);
   ulong hash=5381;

   for(uint i=0; i<outKeyLength;++i)
     {
      hash=((hash<<5)+hash)+key[i];
     }
//---
   return(hash);
  }//+------------------------------------------------------------------+