LAB 4

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <cmath>
#include <ctime>
using namespace std;

int hashing(string word) // hashing function
{
    int word_size = word.size(); //zwraca d³ugosc stinga
    int v = 0; //value
    int ascii = 0;

    if(word_size > 4)
    {
      word_size = 4;
    }

    for(int i = 0; i < word_size; i++)
    {
        ascii = word[i];
        v = v + (pow(39, i+1) * ascii);
    }
    return v;
}


int main()
{
    double avr_1;
    double avr_2;

    clock_t begin;
    clock_t end;
    ifstream file;
    file.open("words20k.txt");
    string word;
    string A[20000];
    string H[24000];
    int v;//vale
    for(int i = 0; i < 20000; i++)
    {
       file >> A[i];
    }

    for(int i = 0; i < 24000; i++)
    {
         H[i] = "";
    }

    for(int i = 0; i < 20000; i++)
    {
        if(i==0 || i==19499)
        {
            begin = clock();
        }
        word = A[i];
        v = hashing(word)%24000;
        while(H[v]!="" || v>=24000)
        {
            v++;
            if(v>=24000)
                v=0;
        }
        H[v]=word;
        if(i==499)
        {
            end = clock();
            avr_1 = double(end - begin) / CLOCKS_PER_SEC;
        }
        if(i==19999)
        {
            end = clock();
            avr_2 = double(end - begin) / CLOCKS_PER_SEC;
        }

    }
    for(int i = 0; i < 24000; i++)
    {
        cout<<H[i]<<" ";
    }

    int remove_start = 14000;
    int remove_end = 14999;
    int avg = remove_end - remove_start;
    for (int i = remove_start; i < remove_end; i++)
    {
        word = A[i];
        v = hashing(word)%24000;
        while(H[v]!=word || v>=24000)
        {
            v++;
            if(v>=24000)
               v=0;
        }
        cout<<"word: "<<word<<" removed: "<<H[v]<<endl;
        H[v]="";
    }
    cout.precision(20);
    cout<<avr_1<<" "<<avr_2;
    return 0;
}