#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h> //memset


#define MEM_SIZE 512

void init_arr(int* arr, int size, int seed, int max_chunk);
void print_arr(int* arr, int size);
double malloc_percentage(int* arr, int size);
int get_best_fit(int* arr, int size, int chunk_size);
int get_first_fit(int* arr, int size, int chunk_size);
int get_worst_fit(int* arr, int size, int chunk_size);
int get_next_fit(int* arr, int size, int chunk_size);

int main(){
    const int mem_size=MEM_SIZE;
    int my_mem[mem_size];
    memset(my_mem,0,mem_size*sizeof(int));
    int memory_seed=25;
    int max_chunk=32;
    int read_size;
    int best_fit, first_fit, worst_fit, next_fit;

    srand(time(NULL));
    init_arr(my_mem, mem_size, memory_seed, max_chunk);
    print_arr(my_mem, mem_size);
    printf("Malloc percentage: %f\n",malloc_percentage(my_mem, mem_size));
    printf("Enter malloc size: ");
    scanf("%d",&read_size);
    best_fit=get_best_fit(my_mem, mem_size, read_size);
    first_fit=get_first_fit(my_mem, mem_size, read_size);
    worst_fit=get_worst_fit(my_mem, mem_size, read_size);
    next_fit=get_next_fit(my_mem, mem_size, read_size);
    printf("Best Fit: %d\n",best_fit);
    printf("First Fit: %d\n",first_fit);
    printf("Worst Fit: %d\n",worst_fit);
    printf("Next Fit: %d\n",next_fit);









    return EXIT_SUCCESS;
}

void init_arr(int* arr, int size, int seed, int max_chunk){
    int random_seed;
    int random_size;
    for (int x=0; x<size; x++){
        random_seed=rand()%seed;
        if (random_seed==0){
            random_size=rand()%max_chunk+1;
            for (int y=0; y<random_size && x<size;y++){
                arr[x]=1;
                x++;
            }
        }
    }
}

void print_arr(int* arr, int size){
    for (int x=0; x < size; x++){
        printf("%d   ",arr[x]);
        if ((x+1)%10==0) printf("\n");
    }
    printf("\n");
}

double malloc_percentage(int* arr, int size){
    int count=0;
    for (int x=0; x < size; x++){
        if (arr[x]==1) count++;
    }
    return (double)count/size;
}

int get_best_fit(int* arr, int size, int chunk_size){
    int current_fit_index=-1;
    int temp_fit_index;
    int current_fit_size=size+1;
    int fragment_size=0;
    for (int x=0; x<size; x++){
        if(arr[x]!=1){
            temp_fit_index=x;
            while(x<size && arr[x]==0){
                fragment_size++;
                x++;
            }
            if (fragment_size>=chunk_size && fragment_size<current_fit_size){
                current_fit_index=temp_fit_index;
                current_fit_size=fragment_size;
            }
            fragment_size=0;
        }
    }
    return current_fit_index;
}

int get_first_fit(int* arr, int size, int chunk_size){
    int current_fit_index=-1;
    int temp_fit_index;
    int fragment_size=0;
    for (int x=0; x<size; x++){
        if(arr[x]!=1){
            temp_fit_index=x;
            while(x<size && arr[x]==0){
                fragment_size++;
                x++;
            }
            if (fragment_size>=chunk_size ){
                current_fit_index=temp_fit_index;
                break;
            }
            fragment_size=0;
        }
    }
    return current_fit_index;
}

int get_worst_fit(int* arr, int size, int chunk_size){
    int current_fit_index=-1;
    int temp_fit_index;
    int current_fit_size=0;
    int fragment_size=0;
    for (int x=0; x<size; x++){
        if(arr[x]!=1){
            temp_fit_index=x;
            while(x<size && arr[x]==0){
                fragment_size++;
                x++;
            }
            if (fragment_size>=chunk_size && fragment_size>current_fit_size){
                current_fit_index=temp_fit_index;
                current_fit_size=fragment_size;
            }
            fragment_size=0;
        }
    }
    return current_fit_index;
}

int get_next_fit(int* arr, int size, int chunk_size){
    int current_fit_index=-1;
    int temp_fit_index;
    int fragment_size=0;
    int last_fit_index=0;
    for (int x=0; x<size;x++){
        if (arr[x]==1) last_fit_index=x;
    }

    for (int x=last_fit_index; x<size; x++){
        if(arr[x]!=1){
            temp_fit_index=x;
            while(x<size && arr[x]==0){
                fragment_size++;
                x++;
            }
            if (fragment_size>=chunk_size ){
                current_fit_index=temp_fit_index;
                break;
            }
            fragment_size=0;
        }
    }

    if (current_fit_index!=-1) return current_fit_index;

    for (int x=0; x<last_fit_index; x++){
        if(arr[x]!=1){
            temp_fit_index=x;
            while(x<last_fit_index && arr[x]==0){
                fragment_size++;
                x++;
            }
            if (fragment_size>=chunk_size ){
                current_fit_index=temp_fit_index;
                break;
            }
            fragment_size=0;
        }
    }
    return current_fit_index;
}