#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "../include/coor.h"
#include "../include/prim.h"

Labyrinth* prim_(int n, int m, bool show);

Labyrinth* prim(int n, int m){
    return prim_(n, m, false);
}

Labyrinth* primShow(int n, int m){
    return prim_(n, m, true);
}

// creates a labyrinth using prim's algorithm
Labyrinth* prim_(int n, int m, bool show){
    int i, j, h, tmp, tp;
    Labyrinth* labyrinth = newLabyrinth(n, m);

    int arr[4] = {0, 1, 2, 3};
    
    coor frontier[n*m];
    coor current = {.x = rand()%n, .y = rand()%m};
    i = current.x;
    j = current.y;
    int frontierSize = 0;
    
    do{
        if(show){
            labyrinth->at[i][j].color = ORANGE;
            printLab(labyrinth);
            labyrinth->at[i][j].color = WHITE;
        }
            
        
        labyrinth->at[i][j].visited = 1;

        // adds frontier cells
        if(i > 0 && labyrinth->at[i-1][j].dp < 0){
            frontier[frontierSize].x = i-1;
            frontier[frontierSize].y = j;
            frontierSize++;
            labyrinth->at[i-1][j].dp = 1;
        }
        if(j < m-1 && labyrinth->at[i][j+1].dp < 0){
            frontier[frontierSize].x = i;
            frontier[frontierSize].y = j+1;
            frontierSize++;
            labyrinth->at[i][j+1].dp = 1;
        }
        if(i < n-1 && labyrinth->at[i+1][j].dp < 0){
            frontier[frontierSize].x = i+1;
            frontier[frontierSize].y = j;
            frontierSize++;
            labyrinth->at[i+1][j].dp = 1;
        }
        if(j > 0 && labyrinth->at[i][j-1].dp < 0){
            frontier[frontierSize].x = i;
            frontier[frontierSize].y = j-1;
            frontierSize++;
            labyrinth->at[i][j-1].dp = 1;
        }

        // randomly selects a frontier cell
        tmp = rand()%frontierSize;
        current = frontier[tmp];
        frontier[tmp] = frontier[frontierSize-1];
        frontierSize--;

        i = current.x;
        j = current.y;

        // randomly joins the selected cell to another cell
        for(h=3; h>0; h--){
            tmp = rand()%h;
            tp = arr[h];
            arr[h] = arr[tmp];
            arr[tmp] = tp;
        }

        tmp = 1;
        for(h=0; h<4 && tmp; h++){
            if(arr[h]==0){
                if(i>0 && labyrinth->at[i-1][j].visited){
                    labyrinth->at[i-1][j].south = 1;
                    tmp = 0;
                }
            }else if(arr[h]==1){
                if(j<m-1 && labyrinth->at[i][j+1].visited){
                    labyrinth->at[i][j].east = 1;
                    tmp = 0;
                }
            }else if(arr[h]==2){
                if(i<n-1 && labyrinth->at[i+1][j].visited){
                    labyrinth->at[i][j].south = 1;
                    tmp = 0;
                }
            }else if(arr[h]==3){
                if(j>0 && labyrinth->at[i][j-1].visited){
                    labyrinth->at[i][j-1].east = 1;
                    tmp = 0;
                }
            }

        }

    }while(frontierSize);

    if(show){    
        labyrinth->at[i][j].color = ORANGE;
        printLab(labyrinth);
        labyrinth->at[i][j].color = WHITE;
    }

    resetLabyrinth(labyrinth);

    return labyrinth;
}