#include <iostream>
#include <vector>
#include <string>
#include <ctime>
#include <fstream>
#include <map>
#include <math.h>
#include <stdlib.h>
using namespace std;
unsigned long bad_hash(const string key);
unsigned long good_hash(const string key);
//Описание класса
class service{
private:
    unsigned long b_hash;
    unsigned long g_hash;
public:
    unsigned long getB_hash() const;

    unsigned long getG_hash() const;

private:
    string s_name;
public:
    const string &getS_name() const;

private:
    int cost, s_time,prepay;
    friend bool Search(vector<service> f, string key);
    friend bool BinSearch(vector<service> mas, string key);
    friend void fill(multimap<string,service> &Map,vector<service> mas);
    friend bool b_hash_search(vector<service> mas, string key);
    friend bool g_hash_search(vector<service> mas, string key);
public:
    //Конструктор по умолчанию
    service()
    {
        s_name = "";
        cost=0;
        s_time=0;
        prepay=0;
    }
    //Конструктор класса
    service(string const s_name1, int cost1, int s_time1, int prepay1)
    {
        s_name = s_name1;
        cost= cost1;
        s_time= s_time1;
        prepay= prepay1;
        b_hash=bad_hash(s_name1);
    }

    //Печать элементов, важных при сравнении
    void print()
    {
        cout << s_name << " " << cost << " " << s_time << " " << prepay << endl;
    }

    bool operator>(const service &other);
    bool operator<(const service &other);
    bool operator>=(const service &other);
    bool operator<=(const service &other);

};

bool service::operator<(const service &other)
{
    return s_name<other.s_name || ( (s_name==other.s_name) && (cost<other.cost));
}

bool service::operator<=(const service &other)
{
    return s_name<other.s_name || ( (s_name==other.s_name) && (cost<=other.cost));
}

bool service::operator>(const service &other)
{
    return s_name>other.s_name || ( (s_name==other.s_name) && (cost>other.cost));
}

bool service::operator>=(const service &other)
{
    return s_name>other.s_name || ( (s_name==other.s_name) && (cost>=other.cost));
}

void read_list(ifstream& in, vector <string> &names, vector <int> &costs, vector <int> &times, vector <int> &prepays)
{
    string s;

    for (int i = 0; i < 10; i++){
        in >> s;
        names.push_back(s);
    }
    for (int i = 0; i < 10; i++){
        int s;
        in >> s;
        costs.push_back(s);
    }
    for (int i = 0; i < 10; i++){
        int s;
        in >> s;
        times.push_back(s);
    }
    for (int i = 0; i < 10; i++){
        int s;
        in >> s;
        prepays.push_back(s);
    }
}



vector <service> make_rand(vector <string>& names, vector <int>& costs, vector <int>& times, vector <int>& prepays, int num)
{
    vector <service> res;
    srand(time(NULL));
    for (int i = 0; i < num; i++){
        int n, s, m, k;
        n = rand() % 10;
        s = rand() % 10;
        m = rand() % 10;
        k = rand() % 10;
        service temp(names[n], costs[s], times[m],prepays[k]);
        res.push_back(temp);
    }
    return res;
}

void sort1(vector<service> &a)//простыми вставками
{
    for (size_t i = 1; i < a.size(); i++)
    {
        for (int j=i;j>0 && a[j-1]>a[j];j--)
        {
            swap(a[j-1],a[j]);
        }
    }
}


bool Search (vector<service> f, string key)
{
    bool flag = false;
    for(int i=0;i<f.size();i++)
    {
        if(key == f[i].s_name)
        {
            cout << "index" << i+1;
            f[i].print();
            flag = true;
        }
    }
    return flag;
}

// нужно переделать вывод   bool BinSearch(vector<service> mas, string key)/*
/*{
int low, high, middle;
bool flag=false;
low = 0;
high = mas.size() - 1;
while (low <= high)
{
middle = (low + high) / 2;
if (key < mas[middle].s_name)
high = middle - 1;
else if (key > mas[middle].s_name)
low = middle + 1;
else
{
flag=true;
cout << "Index: " << middle+1 << "\nElement: ";
mas[middle].print();
int i=middle, k=middle;
while(((i+1)<mas.size()) && (key == mas[i+1].s_name))
{
cout << "Index: " << i+2 << "\nElement: ";
mas[i+1].print();
i++;
}
while(((k-1)>=0) && (key == mas[k-1].s_name))
{
cout << "Index: " << k << "\nElement: ";
mas[k-1].print();
k--;
}
break;
}
}
return flag;
}
*/

void fill(multimap<string,service> &Map,vector<service> mas)
{
    for (int i = 0; i < mas.size(); i++)
    {
        Map.insert(pair<string, service>(mas[i].s_name, mas[i]));
    }
}

unsigned long bad_hash(const string key)
{
    unsigned int H = 0;
    for (int i = 0; i < key.size(); i++)
    {
        H+= key[i] * pow(3, i);
    }

    return H;
}

unsigned long good_hash(const string key)
{
    unsigned int H = 0;
    for (int i = 0; i < key.size(); i++)
    {
        H += key[i] + (H<<i);
    }
    return H;
}

bool b_hash_search(vector<service> mas, string key)
{
    bool flag=false;
    unsigned int hash_val=bad_hash(key);
    for(int i=0;i<mas.size();i++)
    {
        if(mas[i].b_hash==hash_val)
        {
            if(mas[i].s_name==key)
            {
                mas[i].print();
                flag=true;
            }
        }
    }
    return flag;
}

bool g_hash_search(vector<service> mas, string key) {
    bool flag=false;
    unsigned int hash_val=good_hash(key);
    for(int i=0;i<mas.size();i++)
    {
        if(mas[i].g_hash==hash_val)
        {
            if(mas[i].b_hash==hash_val)
            {
                mas[i].print();
                flag=true;
            }
        }
    }
    return flag;
}

unsigned long service::getB_hash() const {
    return b_hash;
}

unsigned long service::getG_hash() const {
    return g_hash;
}

const string &service::getS_name() const {
    return s_name;
}

int main(){
    int num;
    ifstream in;
    double s_time,e_time,f_time;
    string key;

    multimap<string,service> Map;

    cout << "Write number of elements";
    cin >> num;
    cout << "Write key" << endl;
    cin >> key;



    in.open("C:/Users/USER/Desktop/text1.txt");
    if(!in.is_open()) return -1;

    vector <string> names;
    vector<int> costs, times, prepays;
    read_list(in, names, costs, times, prepays);
    vector <service> f = make_rand(names, costs, times, prepays, num);


    s_time = clock() / 1000.0;

    if (!Search (f,key))
        cout << "element is not found" << endl;

    e_time = clock() / 1000.0;
    f_time = e_time - s_time;
    cout << f_time << endl;




    s_time = clock() / 1000.0;

    if(!g_hash_search(f,key)) cout<<"no elements";


    e_time = clock() / 1000.0;
    f_time = e_time - s_time;
    cout << f_time << endl;


    s_time = clock() / 1000.0;

    if(!b_hash_search(f,key)) cout<<"no elements";


    e_time = clock() / 1000.0;
    f_time = e_time - s_time;
    cout << f_time << endl;

    std::map<string, bool> keys;
    for(int i=0;i<=f.size();i++)
        keys.insert(std::pair<string, bool>(f[i].getS_name(), 0));

    std::map<unsigned int, bool> b_hashs;
    for(int i=0;i<=f.size();i++)
        b_hashs.insert(std::pair<unsigned int, bool>(f[i].getB_hash(),0));

    std::map<unsigned int, bool> g_hashs;
    for(int i=0;i<=f.size();i++)
        g_hashs.insert(std::pair<unsigned int, bool>(f[i].getG_hash(),0));

    cout<<"\nColis: "<<100-b_hashs.size()/(double)keys.size()*100;
    cout<<"\nColis: "<<100-g_hashs.size()/(double)keys.size()*100;



    fill(Map,f);

    sort1(f);


    s_time = clock() / 1000.0;

    if(!BinSearch(f, key)) {
        cout << "element is not found" << endl;
    }

    e_time = clock() / 1000.0;
    f_time = e_time - s_time;
    cout << f_time << endl;


    s_time = clock() / 1000.0;
    pair<map<string,service>::iterator, map<string,service>::iterator> q;
    //   переделать    q = Map.equal_range(key);
    for (map<string,service>::iterator it = q.first; it != q.second; it++){
        it->second.print();
    }
    e_time = clock() / 1000.0;
    f_time = e_time - s_time;
    cout << f_time << endl;





    in.close();
    return 0;
}