Project-Algorithms/help_functions.cpp at master · Hepic/Project-Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <math.h>
#include "help_functions.h"

char *get_arguments(const char *argv[], int len, const char *flag, bool same) {
    for (int i = 0; i < len; ++i) {
        if(!strcmp(argv[i], flag)) {
            if (same) {
                return (char*)argv[i];
            } else {
                return (char*)argv[i+1];
            }
        }
    }

    return (char*)"";
}

void perror_exit(const char *msg) {
    perror(msg);
    exit(EXIT_FAILURE);
}

double uniform_distribution(double A, double B) {
    double zero_to_one = (double)rand() / ((double)RAND_MAX + 1.0);
    double ret = A + zero_to_one * (B - A);

    return ret;
}

double normal_distribution(double mean, double stddev) {
    double U, V, S;
    static double X, Y;
    static bool Y_time = false;

    if(Y_time)
    {
        Y_time = false;
        return (Y * stddev + mean);
    }

    do {
        U = uniform_distribution(-1, 1);
        V = uniform_distribution(-1, 1);
        S = U*U + V*V;
    } while (S >= 1.0);

    X = U * sqrt((-2.0 * log(S)) / S);
    Y = V * sqrt((-2.0 * log(S)) / S);
    Y_time = true;

    return (X*stddev + mean);
}

double dot_product(const vector<double> &vec_1, const vector<double> &vec_2) {
    double dot = 0;

    for (int i = 0; i < (int)vec_1.size(); ++i) {
        dot += vec_1[i] * vec_2[i];
    }

    return dot;
}

void insert_curves_into_hashtables(vector<HashTable> &hashtables, double delta, const char *hash_function) {
    vector<Curve> concat_curves(input_curves.size(), Curve());

    for (int i = 0; i < global_L; ++i) {
        multiple_grids(concat_curves, delta);

        for (int j = 0; j < (int)concat_curves.size(); ++j) {
            hashtables[i].insert(input_curves[j], concat_curves[j], hash_function);
            concat_curves[j].clear_curve();
        }
    }
}

void search_curves_from_hashtables(const vector<HashTable> &hashtables, double delta, double R, const char *hash_function, const char *dist_function, vector<set<Curve> > &R_closest_curves, const vector<bool> &grid_curves_found, const vector<const Curve*> &centroids, vector<bool> &visited, bool check) {
    vector<double> min_curve_dist((int)centroids.size(), -1);
    Curve concat_curve;

    for (int i = 0; i < (int)centroids.size(); ++i) {
        if (grid_curves_found[i] && R == 0) {
            continue;
        }

        for (int j = 0; j < global_L; ++j) {
            concat_curve.clear_curve();
            multiple_grids_curve(concat_curve, delta, hashtables[j].get_id(), *centroids[i]); // retrieve concatenated grid_curve

            vector<Curve> closer_curves;
            hashtables[j].search(closer_curves, *centroids[i], concat_curve, hash_function, dist_function, R, visited, check);

            if (!closer_curves.empty()) {
                for (int k = 0; k < (int)closer_curves.size(); ++k) {
                    R_closest_curves[i].insert(closer_curves[k]);
                }
            }
        }
    }
}

void general_search(const vector<HashTable> &hashtables, double delta, double R, const char *hash_function, const char *dist_function, vector<set<Curve> > &R_closest_curves, const vector<const Curve*> &centroids, vector<bool> &grid_curves_found, vector<bool> &visited) {
    // check first if grid_curve is same
    search_curves_from_hashtables(hashtables, delta, R, hash_function, dist_function, R_closest_curves, grid_curves_found, centroids, visited);

    for (int i = 0; i < (int)centroids.size(); ++i) {
        if (!R_closest_curves[i].empty()) {
            grid_curves_found[i] = true;
        }
    }

    // search without checking grid_curve for curves that we did not find anything before
    search_curves_from_hashtables(hashtables, delta, R, hash_function, dist_function, R_closest_curves, grid_curves_found, centroids, visited, false);
}