#include <string>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

struct TItem {
    TItem(string key, string val, TItem* nextHash,TItem* nextOrd, TItem * prevOrd)
    :m_Key(key),m_Val(val),m_NextHash(nextHash),m_NextOrder(nextOrd),m_PrevOrder(prevOrd){}

    string m_Key,m_Val;
    TItem * m_NextHash, * m_NextOrder, * m_PrevOrder;
};

class CHash{
public:
    CHash (int m) : m_Table(NULL),m_Size(m),m_FirstOrder(NULL),m_LastOrder(NULL)
    {
      init(m);
    }

    ~CHash()
    {
      finalize();
    }

    bool IsSet(string key)
    {
      TItem * temp = m_Table[hashFn(key)];
      if (temp == NULL)
        return false;
      while (temp != NULL)
      {
        if (temp -> m_Key == key)
          return true;
        temp = temp -> m_NextOrder;
      }
      return false;
    }

    CHash(const CHash & src)
    {
      init(src.m_Size);
      copy(src.m_FirstOrder);
    }

    CHash & operator = (const CHash & src)
    {
      finalize();
      init(src.m_Size);
      copy(src.m_FirstOrder);
      return *this;
    }

    bool Ins(const string & key, const string & val)
    {
      string help = key;
      if (IsSet(help))
        return false;
      if (m_FirstOrder == NULL)
      {
        TItem * tmp01 = new TItem(key, val, NULL, NULL, NULL);
        m_Table[hashFn(help)] = tmp01;
        m_FirstOrder = m_LastOrder = tmp01;
        return true;
      }
      else
      {
        TItem * temp = m_Table[hashFn(help)];
        if (temp == NULL)
        {
          TItem * tmp02 = new TItem(key, val, NULL, NULL, m_LastOrder);
          m_Table[hashFn(help)] = tmp02;
          m_LastOrder -> m_NextOrder = tmp02;
          m_LastOrder = tmp02;
          return true;
        }
        while (temp -> m_NextHash != NULL)
        {
          if (temp -> m_Key == key)
            return false;
          temp = temp -> m_NextHash;
        }
        TItem * tmp03 = new TItem(key, val, NULL, NULL, m_LastOrder);
        m_Table[hashFn(help)] -> m_NextHash = tmp03;
        m_LastOrder -> m_NextOrder = tmp03;
        m_LastOrder = tmp03;
        return true;
      }
    }

    bool Del (const string & key)
    {
      string help = key;
      TItem * temp = m_Table[hashFn(help)];
      if (temp == NULL)
        return false;
      while (temp != NULL)
      {
        if (temp -> m_Key == key)
          break;
        temp = temp -> m_NextHash;
      }

      if (temp == NULL)
        return false;

      if (m_FirstOrder == temp)
        m_FirstOrder = m_FirstOrder -> m_NextOrder;
      else
        temp -> m_PrevOrder -> m_NextOrder = temp -> m_NextOrder;
      if (m_LastOrder == temp)
        m_LastOrder = m_LastOrder -> m_PrevOrder;

      m_Table[hashFn(help)] = temp -> m_NextHash;
      delete temp;
      return true;
    }

    template <typename func>
    void ForEach(func f)
    {

    }
    void printAll()
    {

    }

private:
    void init (int m)
    {
      m_Size = m;
      m_Table = new TItem * [m];
      for (int i = 0; i < m; i++)
        m_Table[i] = NULL;
      m_FirstOrder = NULL;
      m_LastOrder = NULL;
    }

    void finalize ()
    {
      TItem * temp = m_FirstOrder;
      while (temp != NULL)
      {
        TItem * tmp = temp;
        temp = temp -> m_NextOrder;
        delete tmp;
      }
      delete [] m_Table;
    }

    void copy (TItem * src)
    {
      while (src != NULL)
      {
        Ins(src -> m_Key, src -> m_Val);
        src = src -> m_NextOrder;
      }
    }

    TItem **        m_Table;
    unsigned int    m_Size;
    TItem *         m_FirstOrder, * m_LastOrder;
    unsigned int hashFn(string & str){
        std::hash<std::string> hash_fn;
        return hash_fn(str)%m_Size;
    }
};

int main(int argc, char** argv) {

    CHash hashtable(100);
    CHash hash2(50);
    hashtable.Ins("h1","car");
    assert ( !hashtable.Ins("h1","phone"));
    hashtable.Ins("h2","field");
    hashtable.Ins("h3","house");
    hashtable.Ins("h4","tree");
    hashtable.printAll();
    assert ( hashtable.Del("h3") );
    assert ( !hashtable.Ins("h4","tree") );
    assert(!hashtable.Del("h4d"));
    assert(hashtable.Del("h1"));
    assert(!hashtable.Del("h3"));
    assert(!hashtable.Del("h1"));
    cout << "ok" << endl;

    hash2 = hashtable;
    hashtable.printAll();
    hash2.printAll();
    CHash b(hash2);
    b.printAll();


    hashtable.ForEach([](TItem * it ){
        cout<<it->m_Key<<" - "<<it->m_Val<<endl;
    });

    return 0;
}