#include <iostream>
#include <vector>
#include <time.h>
#include "Profiler.h"
//#define TEST

using namespace std;

Profiler profile;
int BFS_Count;

typedef struct _QNODE {
    int key;
    struct _QNODE* next;
}QNODE;

int *gParentVect;

//LIFO
class Queue {
private:
    QNODE *Head;
    QNODE *Tail;
    int Count;

    QNODE* newNode(int key)
    {
        QNODE *node = new QNODE;
        node->key = key;
        node->next = NULL;
        return node;
    }

public:

    Queue()
    {
        Head = Tail = NULL;
        Count = 0;
    }

    ~Queue()
    {
        QNODE *temp = NULL;
        while (NULL != Head)
        {
            temp = Head;
            Head = Head->next;
            free(temp);
        }

        free(Head);
        free(Tail);
        Count = 0;
    }

    void enqueue(int Key)
    {
        QNODE *node = newNode(Key);

        if (NULL == Head)
        {
            BFS_Count += 2;
            Head = Tail = node;
        }
        else
        {
            BFS_Count += 2;
            Tail->next = node;
            Tail = Tail->next;
        }

        BFS_Count++;
        Count++;
    }

    bool isEmpty() { return 0 == Count; }

    int dequeue()
    {
        if (isEmpty())
        {
            return -1;
        }

        Count--;
        QNODE* temp = Head;
        int retKey = temp->key;
        Head = Head->next;

        free(temp);

        return retKey;
    }
};

class Graph {
private:
    vector<int> *Adjacence;
    int Count;

public:

    Graph(int nrVertices)
    {
        Count = nrVertices;
        Adjacence = new vector<int>[Count];
    }

    void addEdge(int A, int B)
    {
        Adjacence[A].push_back(B);
        Adjacence[B].push_back(A);
    }

    void genGraph(int nrEdges)
    {
        bool **connections = new bool*[Count];
        for (int i = 0; i < Count; i++)
        {
            connections[i] = (bool*)calloc(Count, sizeof(bool));
        }

        int VertexA, VertexB;
        while (NULL != nrEdges)
        {
            VertexA = rand() % Count;
            do {
                VertexB = rand() % Count;
            } while (VertexA == VertexB);

            if (true == connections[VertexA][VertexB])
            {
                continue;
            }

            connections[VertexA][VertexB] = connections[VertexB][VertexA] = true;
            addEdge(VertexA, VertexB);
            nrEdges--;
        }

        for (int i = 0; i < Count; i++)
        {
            free(connections[i]);
        }
        delete connections;
    }

    void clear()
    {
        delete[] Adjacence;
        Adjacence = new vector<int>[Count];
    }

    void print()
    {
        cout << "Node count: " << Count << '\n';
        for (int i = 0; i < Count; i++)
        {
            cout << "Node " << i << ": ";
            for (int j = 0; j < Adjacence[i].size(); j++)
            {
                cout << Adjacence[i][j] << " ";
            }
            cout << '\n';
        }
    }

    void BFS()
    {
        bool *visited = (bool*)calloc(Count, sizeof(bool));

        //mapping all connected components
        for (int i = 0; i < Count; i++)
        {
            if (false == visited[i])
            {
                Queue *Q = new Queue();
                Q->enqueue(i);
                visited[i] = true;

#ifdef TEST
                gParentVect[i] = -1;
#endif

                while (false == Q->isEmpty())
                {
                    BFS_Count += 2;
                    int key = Q->dequeue();

#ifdef TEST
                    cout << key << '\n';
#endif

                    for (int i = 0; i < Adjacence[key].size(); i++)
                    {
                        BFS_Count++;
                        if (false == visited[Adjacence[key][i]])
                        {
                            BFS_Count++;
                            Q->enqueue(Adjacence[key][i]);
                            visited[Adjacence[key][i]] = true;

#ifdef TEST
                            gParentVect[Adjacence[key][i]] = key;

#endif
                        }

                    }
                }

            }
        }

        delete visited;
    }
};

void prettyPrint(int *vect, int index, int tab, int n)
{
    for (int i = 0; i < tab; i++)
    {
        cout << '\t';
    }
    cout << index << '\n';

    for (int i = 0; i < n; i++)
    {
        if (vect[i] == index)
        {
            prettyPrint(vect, i, tab + 1, n);
        }
    }
}

void prettyPrint(int *vect, int n)
{
    int root = 0;
    while (vect[root] != -1)
    {
        root = vect[root] - 1;
    }
    prettyPrint(vect, root, 0, n);
}

int main()
{
    srand(time(NULL));
    //int n = 10, m = 15;
    //Graph *G = new Graph(n);
    //gParentVect = (int*)malloc(n * sizeof(int));
    //G->genGraph(m);
    //G->print();
    //G->BFS();
    //cout << '\n';
    //prettyPrint(gParentVect, n);

    //V fixed
    Graph *G = new Graph(100);
    for (int n = 1000; n < 4500; n += 100)
    {
        cout << n / 100 + 1 << "/" << 45 << '\n';
        BFS_Count = 0;
        G->genGraph(n);
        G->BFS();

        G->clear();
        profile.countOperation("V fixed", n, BFS_Count);
    }

    //E fixed
    for (int n = 100; n < 200; n += 10)
    {
        cout << n / 10 + 1 << "/" << 20 << '\n';
        BFS_Count = 0;

        Graph *G = new Graph(n);
        G->genGraph(4500);
        G->BFS();

        G->clear();
        delete G;
        profile.countOperation("E fixed", n, BFS_Count);
    }

    profile.showReport();

    system("pause");
}