#include <iostream>
#include <vector>

using namespace std;


int hashFun(int v, int max){
    unsigned int suma=23;
    suma = suma*31 + v;
    return suma % max;
}

int nadjiIndex(vector<int>& niz, int j){
    int i = (j+1)%niz.size();
    do{
        if(niz[i]!=-1 && niz[i]!=0) i = (i+1) % niz.size();
        else break;
    }while(i!=j);
    if(i==j) return -1; // pun niz
    else return i;
}


int nadjiIndex(int *niz, int vel, int j){
    int i = (j+1)%vel;
    do{
        if(niz[i]!=-1 && niz[i]!=0) i = (i+1) % vel;
        else break;
    }while(i!=j);
    if(i==j) return -1; // pun niz
    else return i;
}

vector<int> LinearniHash(vector<int> niz){
    vector<int> rez(niz.size(),0);
    for(int i=0; i<niz.size(); i++){
        int j = hashFun(niz[i],niz.size());
        cout<<"Rez hashiranja  je indeks j = "<<j<<" za el = "<<niz[i]<<endl;
        if(rez[j]!=-1 && rez[j]!=0){ //nije slobodna vrijednost
            j = nadjiIndex(rez,j);
        }
        rez[j] = niz[i];
    }
    return rez;
}


vector<vector<int>> LancaniHash(vector<int> niz){
    vector<vector<int>> rez(niz.size());
    for(int i=0; i<niz.size(); i++){
        int j = hashFun(niz[i],niz.size());
        cout<<"Rez hashiranja je indeks j = "<<j<<" za el = "<<niz[i]<<endl;
        if(rez[j].size()!=0){ //nije slobodna vrijednost
            int k=0;
            for(; k<rez[j].size(); k++){
                if(niz[i]>rez[j][k]) break;
            }
            rez[j].insert(rez[j].begin()+k,niz[i]);
        }
        else
            rez[j].push_back(niz[i]);

    }
    return rez;
}

int prebrojElemente(vector<vector<int>>& a){
    int br(0);
    for(auto vek:a){
        for(auto el:vek) br++;
    }
    return br;
}

void prebaciHash(vector<vector<int>> h, int* &t, int &velT){
    int vel = prebrojElemente(h);
    if(vel>velT){
        delete[] t;
        t = new int[vel];
        velT=vel;
        for(int i=0; i<velT; i++) t[i]=0; //prazan element
    }

    for(auto vek:h){
        for(auto el:vek){
            int j = hashFun(el,velT);
            if(t[j]!=0 && t[j]!=-1){
                j = nadjiIndex(t,velT,j);
            }
            t[j]=el;
        }
    }

}



vector<int>  ocistiHash(int* t,int velT, int n){
    vector<int> rez;
    for(int i=0; i<velT; i++){
        int j = hashFun(t[i],velT);
        if(j!=i){
            int razmak2;
            if(i<j) razmak2 = velT-j+i;
            else razmak2 = i-j;
            if(razmak2==n){
                rez.push_back(t[i]);
                t[i]=-1;

            }
        }
    }
    return rez;
}


int main(){
    vector<int> tVektor{1,5,99,15,20,32,512,1042,124,54,125,12,13,14,15,16};
    cout<<endl<<"Lancani hash:"<<endl<<endl;
    auto rez(LancaniHash(tVektor));
    cout<<endl<<endl<<"Rezultat:"<<endl;
    for(int i=0; i<rez.size(); i++){
        cout<<"index = "<<i<<" "<<"elementi: ";
        for(auto b:rez[i]) cout<<b<<" ";
        cout<<endl;
    }
    cout<<endl<<endl;

    int* p = new int[5];
    int vel=5;
    prebaciHash(rez,p,vel);
    cout<<"HashNiz prije ciscenja: "<<endl;
        for(int i=0; i<vel; i++){
        cout<<"index = "<<i<<" el = "<<p[i]<<endl;
    }
    auto rezzi = ocistiHash(p,vel,2);
    cout<<"Izbaceni elementi:"<<endl;
    for(int b:rezzi)cout<<b<<" ";
    cout<<endl<<endl;
    cout<<"HashNiz nakon izbacivanja"<<endl;
    for(int i=0; i<vel; i++){
        cout<<"index = "<<i<<" el = "<<p[i]<<endl;
    }
    delete[] p;

    cout<<endl<<endl;

    cout<<endl<<endl<<"Linearni hash:"<<endl<<endl;
    auto rez2(LinearniHash(tVektor));
    cout<<endl<<"Rezultat: "<<endl;
    for(int i=0; i<rez2.size(); i++){
        cout<<"index = "<<i<<" el = "<<rez2[i]<<endl;
    }


    return 0;
}