// Implementation of the Graph ADT
// Undirected, unweighted
// Vertices are given by integers between 0 and V - 1

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include "Graph.h"


struct adjNode {
    Vertex v;                  // Vertex number
    struct adjNode *next;      // Pointer to the next adjacent vertex
};

// Each vertex has a list of all the vertices it is connected to.
// These lists are stored in an array, where each index corresponds to a vertex.
struct graph {
	int nV;                    // Number of vertices
	int nE;                    // Number of edges
	struct adjNode **edges;   // Array of pointers to adjacency lists,  struct adjNode *edges[MAXNUM]
};

static struct adjNode *adjListInsert(struct adjNode *l, int v);
static struct adjNode *adjListDelete(struct adjNode *l, int v);
static struct adjNode *newAdjNode(int v);
static bool validVertex(Graph g, Vertex v);

/**
 * Returns a new graph with nV vertices
 */
Graph GraphNew(int nV) {
	Graph g = malloc(sizeof(struct graph));
	g->edges = calloc(nV, sizeof(struct adjNode *));        //O(nV): Initializing each pointer is an O(1) operation, and it is done nV times
	g->nV = nV;
	g->nE = 0;
	return g;
}

/**
 * Frees all memory allocated to a graph
 */
void GraphFree(Graph g) {
	for (int i = 0; i < g->nV; i++) {
		struct adjNode *curr = g->edges[i];
		while (curr != NULL) {
			struct adjNode *temp = curr;
			curr = curr->next;
			free(temp);
		}
	}
	free(g->edges);
	free(g);
}

/**
 * Returns the number of vertices in a graph
 */
int GraphNumVertices(Graph g) {
	return g->nV;
}

/**
 * Returns the number of edges in a graph
 */
int GraphNumEdges(Graph g) {
	return g->nE;
}

/**
 * Returns true if there is an edge between v and w,
 * and false otherwise
 */
bool GraphIsAdjacent(Graph g, Vertex v, Vertex w) {
	assert(validVertex(g, v));
	assert(validVertex(g, w));

	struct adjNode *curr = g->edges[v];
	for (; curr != NULL && w >= curr->v; curr = curr->next) {
		if (curr->v == w) {
			return true;
		}
	}
	return false;
}

/**
 * Inserts an edge between v and w
 */
void GraphInsertEdge(Graph g, Vertex v, Vertex w) {
	assert(validVertex(g, v));
	assert(validVertex(g, w));

	if (!GraphIsAdjacent(g, v, w)) {
		g->edges[v] = adjListInsert(g->edges[v], w);
		g->edges[w] = adjListInsert(g->edges[w], v);
		g->nE++;
	}
}

static struct adjNode *adjListInsert(struct adjNode *l, int v) {
	if (l == NULL || v < l->v) {                                   // base case (insert at the start of the list)
		struct adjNode *new = newAdjNode(v);                       // create a new adjNode
		new->next = l;
		return new;
	} else if (v == l->v) {                                         // if the vertex V is already in the list, no insertion is needed
		return l;
	} else {
		l->next = adjListInsert(l->next, v);
		return l;
	}
}

static struct adjNode *newAdjNode(int v) {
    struct adjNode *n = malloc(sizeof(*n));
    if (n == NULL) {
        fprintf(stderr, "error: out of memory\n");
        exit(EXIT_FAILURE);
    }
    n->v = v;
    n->next = NULL;
    return n;
}

/**
 * Removes an edge between v and w
 */
void GraphRemoveEdge(Graph g, Vertex v, Vertex w) {
	assert(validVertex(g, v));
	assert(validVertex(g, w));

	if (GraphIsAdjacent(g, v, w)) {
		g->edges[v] = adjListDelete(g->edges[v], w);
		g->edges[w] = adjListDelete(g->edges[w], v);
		g->nE--;
	}
}

static struct adjNode *adjListDelete(struct adjNode *l, int v) {
    if (l == NULL || v < l->v) {
        return l;
    } else if (v == l->v) {
        struct adjNode *newHead = l->next;
        free(l);
        return newHead;
    } else {
        l->next = adjListDelete(l->next, v);
        return l;
    }
}

/**
 * Returns the degree of a vertex
 */
int GraphDegree(Graph g, Vertex v) {
	assert(validVertex(g, v));

	int degree = 0;
	struct adjNode *curr;
	for (curr = g->edges[v]; curr != NULL; curr = curr->next) {
		degree++;
	}
	return degree;
}

/**
 * Displays a graph
 */
void GraphShow(Graph g) {
	printf("Number of vertices: %d\n", g->nV);
	printf("Number of edges: %d\n", g->nE);
	printf("Edges:\n");
	for (int i = 0; i < g->nV; i++) {
		printf("%2d:", i);
		for (struct adjNode *curr = g->edges[i]; curr != NULL; curr = curr->next) {
			printf(" %d", curr->v);
		}
		printf("\n");
	}
	printf("\n");
}

static bool validVertex(Graph g, Vertex v) {
	return (v >= 0 && v < g->nV);
}