531 lines
38 KiB
MQL5
531 lines
38 KiB
MQL5
//+------------------------------------------------------------------+
|
||
//| CDictionary.mqh |
|
||
//| Copyright 2015, Vasiliy Sokolov. |
|
||
//| http://www.mql5.com |
|
||
//+------------------------------------------------------------------+
|
||
#property copyright "Copyright 2015, Vasiliy Sokolov."
|
||
#property link "http://www.mql5.com"
|
||
|
||
#include <Object.mqh>
|
||
#include <Arrays\List.mqh>
|
||
//+------------------------------------------------------------------+
|
||
//| Контейнер для хранения элементов CObject |
|
||
//+------------------------------------------------------------------+
|
||
class KeyValuePair : public CObject
|
||
{
|
||
private:
|
||
string m_string_key; // Хранит строковый ключ.
|
||
double m_double_key; // Хранит ключ с плавающей запятой.
|
||
ulong m_ulong_key; // Хранит безнаковый целочисленный ключ.
|
||
ulong m_hash;
|
||
bool m_free_mode; // Режим освобождения памяти объекта
|
||
public:
|
||
CObject *object;
|
||
KeyValuePair *next_kvp;
|
||
KeyValuePair *prev_kvp;
|
||
template<typename T>
|
||
KeyValuePair(T key,ulong hash,CObject *obj);
|
||
~KeyValuePair();
|
||
template<typename T>
|
||
bool EqualKey(T key);
|
||
template<typename T>
|
||
void GetKey(T &gkey);
|
||
ulong GetHash(){return m_hash;}
|
||
void FreeMode(bool free_mode){m_free_mode=free_mode;}
|
||
bool FreeMode(void){return m_free_mode;}
|
||
};
|
||
//+------------------------------------------------------------------+
|
||
//| Конструктор по умолчанию. |
|
||
//+------------------------------------------------------------------+
|
||
template<typename T>
|
||
void KeyValuePair::KeyValuePair(T key,ulong hash,CObject *obj)
|
||
{
|
||
m_hash=hash;
|
||
string name=typename(key);
|
||
if(name=="string")
|
||
m_string_key=(string)key;
|
||
else if(name=="double" || name=="float")
|
||
m_double_key=(double)key;
|
||
else
|
||
m_ulong_key=(ulong)key;
|
||
object=obj;
|
||
m_free_mode=true;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| |
|
||
//+------------------------------------------------------------------+
|
||
template<typename T>
|
||
void KeyValuePair::GetKey(T &gkey)
|
||
{
|
||
string name=typename(gkey);
|
||
if(name=="string")
|
||
gkey=(T)m_string_key;
|
||
else if(name=="double" || name=="float")
|
||
gkey=(T)m_double_key;
|
||
else
|
||
gkey=(T)m_ulong_key;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Диструктор. |
|
||
//+------------------------------------------------------------------+
|
||
KeyValuePair::~KeyValuePair()
|
||
{
|
||
if(m_free_mode)
|
||
delete object;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Возвращает истину, если ключи равны. |
|
||
//+------------------------------------------------------------------+
|
||
template<typename T>
|
||
bool KeyValuePair::EqualKey(T key)
|
||
{
|
||
string name=typename(key);
|
||
if(name=="string")
|
||
return m_string_key == (string)key;
|
||
if(name=="double" || name=="float")
|
||
return m_double_key == (double)key;
|
||
else
|
||
return m_ulong_key == (ulong)key;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Ассоциативный массив или словарь, хранящий элементы в виде |
|
||
//| <ключ - значение>. Где ключом может являться любой базовый тип, |
|
||
//| а значением - объект типа CObject. |
|
||
//+------------------------------------------------------------------+
|
||
class CDictionary : public CObject
|
||
{
|
||
private:
|
||
int m_array_size;
|
||
int m_total;
|
||
bool m_free_mode;
|
||
bool m_auto_free;
|
||
int m_index;
|
||
ulong m_hash;
|
||
CList *m_array[];
|
||
union casting_struct
|
||
{
|
||
double d_value;
|
||
ulong l_value;
|
||
}casting;
|
||
KeyValuePair *m_first_kvp;
|
||
KeyValuePair *m_current_kvp;
|
||
KeyValuePair *m_last_kvp;
|
||
|
||
ulong Adler32(string line);
|
||
int GetIndexByHash(ulong hash);
|
||
template<typename T>
|
||
ulong GetHashByKey(T key);
|
||
void Resize();
|
||
int FindNextSimpleNumber(int number);
|
||
int FindNextLevel();
|
||
void Init(int capacity);
|
||
public:
|
||
CDictionary();
|
||
CDictionary(int capacity);
|
||
~CDictionary();
|
||
void Compress(void);
|
||
///
|
||
/// Returns the total number of items.
|
||
///
|
||
int Total(void){return m_total;}
|
||
/// Returns the element at key
|
||
template<typename T>
|
||
CObject *GetObjectByKey(T key);
|
||
template<typename T>
|
||
bool AddObject(T key,CObject *value);
|
||
template<typename T>
|
||
bool DeleteObjectByKey(T key);
|
||
template<typename T>
|
||
bool ContainsKey(T key);
|
||
template<typename T>
|
||
void GetCurrentKey(T &key);
|
||
bool DeleteCurrentNode(void);
|
||
bool FreeMode(void) { return(m_free_mode); }
|
||
void FreeMode(bool free_mode);
|
||
void AutoFreeMemory(bool autoFree){m_auto_free=autoFree;}
|
||
void Clear();
|
||
|
||
CObject *GetNextNode(void);
|
||
CObject *GetPrevNode(void);
|
||
CObject *GetCurrentNode(void);
|
||
CObject *GetFirstNode(void);
|
||
CObject *GetLastNode(void);
|
||
|
||
};
|
||
//+------------------------------------------------------------------+
|
||
//| Конструктор по умолчанию. |
|
||
//+------------------------------------------------------------------+
|
||
CDictionary::CDictionary()
|
||
{
|
||
Init(3);
|
||
m_free_mode = true;
|
||
m_auto_free=true;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Создает словарь, с заранее определенной емкостью capacity. |
|
||
//+------------------------------------------------------------------+
|
||
CDictionary::CDictionary(int capacity)
|
||
{
|
||
if(capacity < 3)
|
||
Init(3);
|
||
else
|
||
Init(capacity);
|
||
m_free_mode = true;
|
||
m_auto_free=true;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Диструктор. |
|
||
//+------------------------------------------------------------------+
|
||
CDictionary::~CDictionary()
|
||
{
|
||
Clear();
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Режим устанавливает режим памяти для всех подузлов |
|
||
//+------------------------------------------------------------------+
|
||
void CDictionary::FreeMode(bool free_mode)
|
||
{
|
||
if(free_mode==m_free_mode)
|
||
return;
|
||
m_free_mode=free_mode;
|
||
for(int i=0; i<ArraySize(m_array); i++)
|
||
{
|
||
CList *list=m_array[i];
|
||
if(CheckPointer(list)==POINTER_INVALID)
|
||
continue;
|
||
for(KeyValuePair *kvp=list.GetFirstNode(); kvp!=NULL; kvp=list.GetNextNode())
|
||
kvp.FreeMode(m_free_mode);
|
||
}
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Выполняет инициализацию словаря. |
|
||
//+------------------------------------------------------------------+
|
||
void CDictionary::Init(int capacity)
|
||
{
|
||
m_array_size=ArrayResize(m_array,capacity);
|
||
m_index= 0;
|
||
m_hash = 0;
|
||
m_total=0;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Находит следующий размер для словаря. |
|
||
//+------------------------------------------------------------------+
|
||
int CDictionary::FindNextLevel()
|
||
{
|
||
double value=4;
|
||
for(int i=2; i<=31; i++)
|
||
{
|
||
value=MathPow(2.0,(double)i);
|
||
if(value > m_total)return (int)value;
|
||
}
|
||
return (int)value;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Принимает строку и возвращает хэширующее 32 битное число, |
|
||
//| характеризующее эту строку. |
|
||
//+------------------------------------------------------------------+
|
||
ulong CDictionary::Adler32(string line)
|
||
{
|
||
ulong s1 = 1;
|
||
ulong s2 = 0;
|
||
uint buflength=StringLen(line);
|
||
uchar char_array[];
|
||
ArrayResize(char_array,buflength,0);
|
||
StringToCharArray(line,char_array,0,-1,CP_ACP);
|
||
for(uint n=0; n<buflength; n++)
|
||
{
|
||
s1 = (s1 + char_array[n]) % 65521;
|
||
s2 = (s2 + s1) % 65521;
|
||
}
|
||
return ((s2 << 16) + s1);
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Рассчитывает хэш на основе переданного ключа. Ключом может быть |
|
||
//| любой базовый MQL тип.
|
||
//+------------------------------------------------------------------+
|
||
template<typename T>
|
||
ulong CDictionary::GetHashByKey(T key)
|
||
{
|
||
ulong ukey = 0;
|
||
string name=typename(key);
|
||
if(name=="string")
|
||
return Adler32((string)key);
|
||
if(name=="double" || name=="float")
|
||
{
|
||
casting.d_value = (double)key;
|
||
ukey=casting.l_value;
|
||
}
|
||
else
|
||
ukey=(ulong)key;
|
||
return ukey;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Возвращает ключ текущего элемента. |
|
||
//+------------------------------------------------------------------+
|
||
template<typename T>
|
||
void CDictionary::GetCurrentKey(T &key)
|
||
{
|
||
m_current_kvp.GetKey(key);
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Возвращает индекс по ключу. |
|
||
//+------------------------------------------------------------------+
|
||
int CDictionary::GetIndexByHash(ulong key)
|
||
{
|
||
return (int)(key%m_array_size);
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Очищает словарь от всех значений. |
|
||
//+------------------------------------------------------------------+
|
||
void CDictionary::Clear(void)
|
||
{
|
||
int size=ArraySize(m_array);
|
||
for(int i=0; i<size; i++)
|
||
{
|
||
if(CheckPointer(m_array[i])!=POINTER_INVALID)
|
||
{
|
||
m_array[i].FreeMode(true); // Элементы типа KeyValuePair удаляются всегда
|
||
delete m_array[i];
|
||
}
|
||
}
|
||
ArrayFree(m_array);
|
||
if(m_auto_free)
|
||
Init(3);
|
||
else
|
||
Init(size);
|
||
m_first_kvp=m_last_kvp=m_current_kvp=NULL;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Переразмечает контейнер хранения данных. |
|
||
//+------------------------------------------------------------------+
|
||
void CDictionary::Resize(void)
|
||
{
|
||
int level=FindNextLevel();
|
||
int n=level;
|
||
CList *temp_array[];
|
||
ArrayCopy(temp_array,m_array);
|
||
ArrayFree(m_array);
|
||
m_array_size=ArrayResize(m_array,n);
|
||
int total=ArraySize(temp_array);
|
||
KeyValuePair *kv=NULL;
|
||
for(int i=0; i<total; i++)
|
||
{
|
||
if(temp_array[i]==NULL)continue;
|
||
CList *list=temp_array[i];
|
||
int count=list.Total();
|
||
list.FreeMode(false);
|
||
kv=list.GetFirstNode();
|
||
while(kv!=NULL)
|
||
{
|
||
int index=GetIndexByHash(kv.GetHash());
|
||
if(CheckPointer(m_array[index])==POINTER_INVALID)
|
||
{
|
||
m_array[index]=new CList();
|
||
m_array[index].FreeMode(true); // Элементы KeyValuePair удаляются всегда
|
||
}
|
||
list.DetachCurrent();
|
||
m_array[index].Add(kv);
|
||
kv=list.GetCurrentNode();
|
||
}
|
||
delete list;
|
||
}
|
||
int size=ArraySize(temp_array);
|
||
ArrayFree(temp_array);
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Сжимает словарь. |
|
||
//+------------------------------------------------------------------+
|
||
void CDictionary::Compress(void)
|
||
{
|
||
if(!m_auto_free)return;
|
||
double koeff=m_array_size/(double)(m_total+1);
|
||
if(koeff < 2.0 || m_total <= 4)return;
|
||
Resize();
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Возвращет объект по ключу. |
|
||
//+------------------------------------------------------------------+
|
||
template<typename T>
|
||
CObject *CDictionary::GetObjectByKey(T key)
|
||
{
|
||
if(!ContainsKey(key))
|
||
return NULL;
|
||
CObject *obj=m_current_kvp.object;
|
||
return obj;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Проверяет содержит ли словарь ключ произвольного типа T. |
|
||
//| RETURNS: |
|
||
//| Возвращает истину, если объект с таким ключом уже существует |
|
||
//| и ложь в противном случае. |
|
||
//+------------------------------------------------------------------+
|
||
template<typename T>
|
||
bool CDictionary::ContainsKey(T key)
|
||
{
|
||
m_hash=GetHashByKey(key);
|
||
m_index=GetIndexByHash(m_hash);
|
||
if(CheckPointer(m_array[m_index])==POINTER_INVALID)
|
||
return false;
|
||
CList *list=m_array[m_index];
|
||
KeyValuePair *current_kvp=list.GetCurrentNode();
|
||
if(current_kvp == NULL)return false;
|
||
if(current_kvp.EqualKey(key))
|
||
{
|
||
m_current_kvp=current_kvp;
|
||
return true;
|
||
}
|
||
current_kvp=list.GetFirstNode();
|
||
while(true)
|
||
{
|
||
if(current_kvp.EqualKey(key))
|
||
{
|
||
m_current_kvp=current_kvp;
|
||
return true;
|
||
}
|
||
current_kvp=list.GetNextNode();
|
||
if(current_kvp==NULL)
|
||
return false;
|
||
}
|
||
return false;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Добавляет в словарь элемент типа CObject с ключом T key. |
|
||
//| INPUT PARAMETRS: |
|
||
//| T key - любой базовый тип, например int, double или string. |
|
||
//| value - класс, производный от CObject. |
|
||
//| RETURNS: |
|
||
//| Истина, если элемент был добавлен и ложь в противном случае. |
|
||
//+------------------------------------------------------------------+
|
||
template<typename T>
|
||
bool CDictionary::AddObject(T key,CObject *value)
|
||
{
|
||
if(ContainsKey(key))
|
||
return false;
|
||
if(m_total==m_array_size)
|
||
{
|
||
Resize();
|
||
ContainsKey(key);
|
||
}
|
||
if(CheckPointer(m_array[m_index])==POINTER_INVALID)
|
||
{
|
||
m_array[m_index]=new CList();
|
||
m_array[m_index].FreeMode(true); // Элементы KeyValuePair удаляются всегда
|
||
}
|
||
KeyValuePair *kv=new KeyValuePair(key,m_hash,value);
|
||
kv.FreeMode(m_free_mode);
|
||
if(m_array[m_index].Add(kv)!=-1)
|
||
m_total++;
|
||
if(CheckPointer(m_current_kvp)==POINTER_INVALID)
|
||
{
|
||
m_first_kvp=kv;
|
||
m_current_kvp=kv;
|
||
m_last_kvp=kv;
|
||
}
|
||
else
|
||
{
|
||
//добавляем в самый конец, т.к. текущий узел может быть где угодно
|
||
while(m_current_kvp.next_kvp!=NULL)
|
||
m_current_kvp=m_current_kvp.next_kvp;
|
||
m_current_kvp.next_kvp=kv;
|
||
kv.prev_kvp=m_current_kvp;
|
||
m_current_kvp=kv;
|
||
m_last_kvp=kv;
|
||
}
|
||
return true;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Возвращает текущий объект. Если объект не выбран возвращает |
|
||
//| NULL. |
|
||
//+------------------------------------------------------------------+
|
||
CObject *CDictionary::GetCurrentNode(void)
|
||
{
|
||
if(m_current_kvp==NULL)
|
||
return NULL;
|
||
return m_current_kvp.object;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Возвращает предыдущий объект. После вызова метода текущий |
|
||
//| объект становиться предыдущим. Если объект не выбран, возвращает |
|
||
//| NULL. |
|
||
//+------------------------------------------------------------------+
|
||
CObject *CDictionary:: GetPrevNode(void)
|
||
{
|
||
if(m_current_kvp==NULL)
|
||
return NULL;
|
||
if(m_current_kvp.prev_kvp==NULL)
|
||
return NULL;
|
||
KeyValuePair *kvp=m_current_kvp.prev_kvp;
|
||
m_current_kvp=kvp;
|
||
return kvp.object;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Возвращает следующий объект. После вызова метода текущий |
|
||
//| объект становиться следующим. Если объект не выбран, возвращает |
|
||
//| NULL. |
|
||
//+------------------------------------------------------------------+
|
||
CObject *CDictionary::GetNextNode(void)
|
||
{
|
||
if(m_current_kvp==NULL)
|
||
return NULL;
|
||
if(m_current_kvp.next_kvp==NULL)
|
||
return NULL;
|
||
m_current_kvp=m_current_kvp.next_kvp;
|
||
return m_current_kvp.object;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Возвращает первый узел в списке узлов. Если в словаре узлов нет, |
|
||
//| возвращает NULL. |
|
||
//+------------------------------------------------------------------+
|
||
CObject *CDictionary::GetFirstNode(void)
|
||
{
|
||
if(m_first_kvp==NULL)
|
||
return NULL;
|
||
m_current_kvp=m_first_kvp;
|
||
return m_first_kvp.object;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Возвращает последний узел в списке узлов. Если в словаре узлов |
|
||
//| нет возвращает NULL. |
|
||
//+------------------------------------------------------------------+
|
||
CObject *CDictionary::GetLastNode(void)
|
||
{
|
||
if(m_last_kvp==NULL)
|
||
return NULL;
|
||
m_current_kvp=m_last_kvp;
|
||
return m_last_kvp.object;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Удаляет текущий узел |
|
||
//+------------------------------------------------------------------+
|
||
bool CDictionary::DeleteCurrentNode(void)
|
||
{
|
||
if(m_current_kvp==NULL)
|
||
return false;
|
||
KeyValuePair* p_kvp = m_current_kvp.prev_kvp;
|
||
KeyValuePair* n_kvp = m_current_kvp.next_kvp;
|
||
if(CheckPointer(p_kvp)!=POINTER_INVALID)
|
||
p_kvp.next_kvp=n_kvp;
|
||
if(CheckPointer(n_kvp)!=POINTER_INVALID)
|
||
n_kvp.prev_kvp=p_kvp;
|
||
m_array[m_index].FreeMode(m_free_mode);
|
||
bool res=m_array[m_index].DeleteCurrent();
|
||
if(res)
|
||
{
|
||
m_total--;
|
||
Compress();
|
||
}
|
||
return res;
|
||
}
|
||
//+------------------------------------------------------------------+
|
||
//| Удаляет объект с ключом key из словаря. |
|
||
//+------------------------------------------------------------------+
|
||
template<typename T>
|
||
bool CDictionary::DeleteObjectByKey(T key)
|
||
{
|
||
if(!ContainsKey(key))
|
||
return false;
|
||
return DeleteCurrentNode();
|
||
}
|
||
|
||
#define FOREACH_DICT(dict) for(CObject* node = (dict).GetFirstNode(); node != NULL; node = (dict).GetNextNode())
|
||
//+------------------------------------------------------------------+
|