CS267_HW2/bin.cpp at master · vincentLiangBerkeley/CS267_HW2 · 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
119
120
#include "bin.h"

void init_grid(int num_bins, bin_t *bin_list)
{
    for(int i = 0; i < num_bins; i ++)
    {
        bin_list[i].capacity = 20;
        bin_list[i].bin_size = 0;
        // printf("capacity = %d\n", bin_list[i].capacity);
        bin_list[i].indeces = (int*)malloc(bin_list[i].capacity*sizeof(int));
    }

}

void clear_grid(int num_bins, bin_t *bin_list)
{
    for(int i = 0; i < num_bins; i ++)
    {
        free(bin_list[i].indeces);
        bin_list[i].indeces = NULL;
    }

}

void clear_bin_col(bin_t *bin_list, int start, int end, int col, int lda)
{
    for(int r = start; r < end; r ++)
    {
        int index = r + col * lda;
        free(bin_list[index].indeces);
        bin_list[index].indeces = (int*)malloc(sizeof(int)*bin_list[index].capacity);
        bin_list[index].bin_size = 0;
    }
}

// The list of bins will be separated into y*x
void set_grid_size(int &x, int &y, int num_bins)
{
    int m = static_cast<int>(sqrt(num_bins));
    for(int i=m; i>0; i --)
    {
        if(num_bins % i == 0)
        {
            y = i;
            break;
        }
    }

    x = num_bins / y;
}

// The size of the global board is known from outside of this file
// Also, this function will also dynamically adjust the size of the bins
void bin_particles(int n, particle_t *particles, int num_bins, bin_t *bin_list, double bin_x, double bin_y, int num_rows)
{
    int i;
    for(i=0;i<num_bins;i++) bin_list[i].bin_size = 0;
    // Binning particles to bins
    for(i=0;i<n;i++)
    {
        int x = particles[i].x / bin_x, y = particles[i].y / bin_y;
        int index = y+x*num_rows;
        add_particle(bin_list, i, index);
    }
}

// This function adds a particle to the end of a bin
void add_particle(bin_t *bin_list, int i, int j)
{
    if (bin_list[j].bin_size == bin_list[j].capacity)
        // Need to allocate more memory here
    {
        // printf("Reallocating memory to bin # %d\n", j);
        bin_list[j].indeces = (int*) realloc(bin_list[j].indeces, 2*bin_list[j].capacity*sizeof(int));
        bin_list[j].capacity  *= 2;
    }

    bin_list[j].indeces[bin_list[j].bin_size] = i;
    bin_list[j].bin_size ++;
}

void remove_particle(bin_t *bin_list, int i, int j)
{
    for (int k = 0; k < bin_list[j].bin_size; k++)
    {
        if (bin_list[j].indeces[k] == i) // Need to remove this particle
        {
            for (int l = k; l < bin_list[j].bin_size; l ++)
                bin_list[j].indeces[l] = bin_list[j].indeces[l+1];
            break;
        }
        if (k == bin_list[j].bin_size - 1)
        {
            printf("Failed to remove particle %d from bin %d\n", i, j);
            printf("bin %d has partiles: \n", j);
            for(int p = 0; p < bin_list[j].bin_size; p ++)
                printf("%d \n", bin_list[j].indeces[p]);
            printf("\n");

            exit(1);
        }
    }

    bin_list[j].bin_size --;
}


void sanity_check(int n, int num_bins, bin_t *bin_list)
{
    int sum = 0;
    for(int i = 0; i < num_bins; i ++)
    {
        // if(bin_list[i].bin_size > 2)
        //     printf("bin # %d has %d particles\n", i, bin_list[i].bin_size);
        sum += bin_list[i].bin_size;
    }

    if(sum == n) printf("The total number of particles is unchanged.\n");
    else printf("Sum = %d, n = %d\n", sum, n);
}