#include <iostream>
#include <math.h>
#include <time.h>
#include <fstream>

using namespace std;

class LinearProbing
{
private:
    int *table;
public:
    LinearProbing();
    int hashing(int key);
    bool insert(int key);
    void insertX(int X);
    bool find(int key);
    bool remove(int key);
    void showFromTo(int from, int to);
};

LinearProbing::LinearProbing()
{
    table = new int[997];
    for(int i = 0; i < 997; i++)
    {
        table[i] = 0;
    }
}
int LinearProbing::hashing(int key)
{
    return (((key % 1000) + int(pow(2,key % 10)) + 1) % 997);
}
bool LinearProbing::insert(int key)
{
    int index = hashing(key);
    if(table[index] <= 0)
    {
        table[index] = key;
        //cout<<key<<endl;
       // cout<<index<<endl;
        return true;
    }
    else
    {
        int next = index + 1;
        while(next != 997)
        {
            if(table[next] <= 0)
            {
                table[next] = key;
                return true;
            }
            next++;
        }
        next = 0;
        while(next != index)
        {
            if(table[next] <= 0)
            {
                table[next] = key;
                return true;
            }
            next++;
        }
    }
    return false;
}
void LinearProbing::insertX(int X)
{
    int key = 0;
    for(int i = 0; i < X; i++)
    {
        key = (rand()%20000)+20000;
        if(insert(key) == false)
            i--;
        //insert(key);
        //cout<<i<<")"<<table[i]<<"\t"<<endl;
    }
}
bool LinearProbing::remove(int key)
{
    int index = hashing(key);
    if (table[index] == key)
    {
        table[index] = -1;
        return true;
    }
    else
    {
        int next = index + 1;
        while (next != 997)
        {
            if (table[next] == key)
            {
                table[next] = -1;
                return true;
            }
            next++;
        }
        next = 0;
        while(next != index)
        {
            if (table[next] == key)
            {
                table[next] = -1;
                return true;
            }
            next++;
        }
    }
    return false;
}
bool LinearProbing::find(int key)
{
    int index = hashing(key);
    if(table[index] == key)
    {
        return true;
    }
    else
    {
        int next = index + 1;
        while(next != 997)
        {
            if(table[next] == key)
            {
                return true;
            }
            next++;
        }
        next = 0;
        while(next != index)
        {
            if(table[next] == key)
            {
                return true;
            }
            next++;
        }
    }
    return false;
}
void LinearProbing::showFromTo(int from, int to)
{
    if(from < 0 || to > 996)
    {
        cout<<"Wrong arguments! Choose from 0 to 996!"<<endl<<endl;
        return;
    }
    else
    {
        for(int i = from; i <= to; i++)
        {
            cout<<i<<") "<<table[i]<<"\t";
        }
        cout<<endl;
    }
}

class DoubleHashing
{
private:
    int tab
};

int main()
{
    LinearProbing x;
    x.showFromTo(0,5);
    //x.insertX(10);
    cout<<x.find(1)<<endl;
    x.insert(12);
    cout<<x.find(12)<<endl;
    x.remove(12);
    cout<<x.find(12)<<endl;
    x.insert(12);
    cout<<x.find(12)<<endl;
/*
    x.insert(11);
    x.insert(112);
    x.showFromTo(1,5);
    cout<<x.hashing(12)<<endl;
    cout<<x.hashing(11)<<endl;
    cout<<x.hashing(112)<<endl;
*/

    return 0;
}