#include <iostream>
#include <string>

const int prime=3571;

int _hash(std::string key, int len, int prime){
    int hash=len;
    for(int i=0;i<len;i++){
        hash= (hash<<5)^(hash>>27)^key[i];
    }
    return hash % prime;
}

template <class type2>
struct pair{
    std::string key_;
    type2 value;
};

template <class type2>
class map{
    private:
        //vector<pair> mas_;
        int size;
        pair<type2>** hash;
        friend class itmap;
    public:
        map(){
            size=0;
            hash=new pair<type2>* [prime];
            for(int i=0;i<prime;++i){
                hash[i]=nullptr;
            }
        }

        ~map(){
            for(int i=0;i<prime;++i){
                if(hash[i]!=nullptr){
                    delete [] hash[i];
                }
            }
            delete []  hash;
        }

        class itmap{
            private:
                pair<type2>** curr;
            public:
                itmap(pair<type2>** a){
                    curr=a;
                }
                itmap operator- (int n){
                    for(int i=0;i<n;++i){
                        --curr;
                    }
                    return curr;
                }

                itmap operator+ (int n){
                    for(int i=0;i<n;++i){
                        ++curr;
                    }
                    return curr;
                }

                itmap operator++(){
                    while(1){
                        ++curr;
                        if(*(curr)!=nullptr){
                            return curr;
                        }
                    }
                }

                itmap operator--(){
                    while(1){
                        --curr;
                        if(*(curr)!=nullptr){
                            return curr;
                        }
                    }
                }
                auto operator*(){ return *curr;}
        };

        void insert(std::string key,type2 a){
            if(size==prime){
                std::cout<<"mass full"<<std::endl;
                return;
            }
            int b=_hash(key,key.size(),prime);
            if (hash[b]==nullptr || hash[b]->key_==key){
                if(hash[b]==nullptr){
                    hash[b]=new pair<type2> [1];
                    hash[b]->key_=key;
                    hash[b]->value=a;
                    size++;
                    return;
                }
                hash[b]->key_=key;
                hash[b]->value;
                return;
            }
            //          std::cout<<key<<std::endl;
            while(true){
                b=(b+1)%prime;
                if (hash[b]==nullptr || hash[b]->key_==key){
                    if(hash[b]==nullptr){
                        hash[b]=new pair<type2> [1];
                        hash[b]->key_=key;
                        hash[b]->value=a;
                        size++;
                        return;
                    }
                    hash[b]->key_=key;
                    hash[b]->value;
                    return;
                }

            }
        }

        type2* find(std::string key){
            int b=_hash(key,key.size(),prime);
            int p=b;
            if(hash[b]!=nullptr){
                if(hash[b]->key_==key){
                    return &hash[b]->value;
                }
                b=(b+1)%prime;
                while(hash[b]!=nullptr && p!=b && _hash(hash[b]->key_,hash[b]->key_.size(),prime)==p){
                    if(hash[b]->key_==key){
                        return &(hash[b]->value);
                    }
                    b=(b+1)%prime;
                }
                std::cout<<"no such element"<<std::endl;
                return NULL;
            }
            b=(b+1)%prime;
            while(hash[b]==nullptr && b!=p){
                b=(b+1)%prime;
            }
            if(b==p){
                std::cout<<"no such elem"<<std::endl;
                return NULL;
            }
            while(hash[b]!=nullptr && p!=b && _hash(hash[b]->key_,hash[b]->key_.size(),prime)==p){
                if(hash[b]->key_==key){
                    return &(hash[b]->value);
                }
                b=(b+1)%prime;
            }
            std::cout<<"no such element"<<std::endl;
            return NULL;
        }

        void delet(std::string key){
            int b=_hash(key,key.size(),prime);
            if(hash[b]==nullptr){
                std::cout<<"no such element"<<std::endl;
                return;
            }
            if(hash[b]->key_==key){
                size--;
                delete [] hash[b];
                hash[b]=nullptr;
                return;
            }

            int p=b;
            b=(b+1)%prime;
            while(hash[b]!=nullptr && p!=b && _hash(hash[b]->key_,hash[b]->key_.size(),prime)==p){
                if(hash[b]->key_==key){
                    size--;
                    delete [] hash[b];
                    hash[b]=nullptr;
                    return;
                }
                b=(b+1)%prime;
            }
            std::cout<<"no such element"<<std::endl;

        }

        int getsize(){
            return size;
        }

        void print(){
            for(int i=0;i<prime;i++){
                if(hash[i]!=nullptr){
                    std::cout<<hash[i]->key_<<" :"<<_hash(hash[i]->key_,hash[i]->key_.size(),prime)<< ": "<<hash[i]->value<<std::endl;
                }
            }
        }

        itmap begin() {
            if(size==0)
                return NULL;
            for(int i=0;i<prime;++i){
                if(hash[i]!=nullptr){
                    itmap t(&hash[i]);
                    return t;
                }
            }
        }
        itmap end() {
            if(size==0)
                return NULL;
            for(int i=prime-1;i>-1;--i){
                if(hash[i]!=nullptr){
                    itmap t(&hash[i]);
                    return t;
                }
            }
        }

};

int main(){
    map<std::string> a;
    std::string s="asd";
    for(int i=0;i<100;++i){
        char b=i;
        std::string c=s+b,m=c+'a';
        a.insert(c,m);
    }
    /*
    for(int i=0;i<50;++i){
        char b=i;
        std::string c=s+b;
        a.delet(c);
    }
    std::cout<<a.getsize()<<std::endl;*/
    map<std::string>::itmap b=a.begin();
    for(int i=0;i<10;i++){
    b+5;
    (*b)->value="pobeda";
    }
    //std::cout<<(*b)->key_<<" : "<<(*(b))->value<<std::endl;
    a.print();
    return 0;
}