#include <stddef.h>
#include <stdlib.h>
#include <stdbool.h>

#ifndef min
#define min(x, y) ((x)<(y) ? (x) : (y))
#endif

struct edge {
	void *from;
	void *to;
};

struct components {
	int nnodes;
	void **nodes;
	struct components *next;
};

struct node {
	int index;
	int lowlink;
	bool onStack;
	void *data;
};

struct tjstate {
	int index;
	int sp;
	int nedges;
	struct edge *edges;
	struct node **stack;
	struct components *head;
	struct components *tail;
};

static int nodecmp(const void *l, const void *r)
{
	return (ptrdiff_t)l -(ptrdiff_t)((struct node *)r)->data;
}

static int strongconnect(struct node *v, struct tjstate *tj)
{
	struct node *w;

	/* Set the depth index for v to the smallest unused index */
	v->index = tj->index;
	v->lowlink = tj->index;
	tj->index++;
	tj->stack[tj->sp] = v;
	tj->sp++;
	v->onStack = true;

	for (int i = 0; i<tj->nedges; i++) {
		/* Only consider nodes reachable from v */
		if (tj->edges[i].from != v) {
			continue;
		}
		w = tj->edges[i].to;
		/* Successor w has not yet been visited; recurse on it */
		if (w->index == -1) {
			int r = strongconnect(w, tj);
			if (r != 0)
				return r;
			v->lowlink = min(v->lowlink, w->lowlink);
		/* Successor w is in stack S and hence in the current SCC */
		} else if (w->onStack) {
			v->lowlink = min(v->lowlink, w->index);
		}
	}

	/* If v is a root node, pop the stack and generate an SCC */
	if (v->lowlink == v->index) {
		struct components *ng = malloc(sizeof(struct components));
		if (ng == NULL) {
			return 2;
		}
		if (tj->tail == NULL) {
			tj->head = ng;
		} else {
			tj->tail->next = ng;
		}
		tj->tail = ng;
		ng->next = NULL;
		ng->nnodes = 0;
		do {
			tj->sp--;
			w = tj->stack[tj->sp];
			w->onStack = false;
			ng->nnodes++;
		} while (w != v);
		ng->nodes = malloc(ng->nnodes*sizeof(void *));
		if (ng == NULL) {
			return 2;
		}
		for (int i = 0; i<ng->nnodes; i++) {
			ng->nodes[i] = tj->stack[tj->sp+i]->data;
		}
	}
	return 0;
}

static int ptrcmp(const void *l, const void *r)
{
	return (ptrdiff_t)((struct node *)l)->data
		- (ptrdiff_t)((struct node *)r)->data;
}

/**
 * Calculate the strongly connected components using Tarjan's algorithm:
 * en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
 *
 * Returns NULL when there are invalid edges and sets the error to:
 * 1 if there was a malformed edge
 * 2 if malloc failed
 *
 * @param number of nodes
 * @param data of the nodes (assumed to be unique)
 * @param number of edges
 * @param data of edges
 * @param pointer to error code
 */
struct components *tarjans(
		int nnodes, void *nodedata[],
		int nedges, struct edge *edgedata[],
		int *error)
{
	struct node nodes[nnodes];
	struct edge edges[nedges];
	struct node *stack[nnodes];
	struct node *from, *to;
	struct tjstate tj = {0, 0, nedges, edges, stack, NULL, .tail=NULL};

	// Populate the nodes
	for (int i = 0; i<nnodes; i++) {
		nodes[i] = (struct node){-1, -1, false, nodedata[i]};
	}
	qsort(nodes, nnodes, sizeof(struct node), ptrcmp);

	// Populate the edges
	for (int i = 0; i<nedges; i++) {
		from = bsearch(edgedata[i]->from, nodes, nnodes,
			sizeof(struct node), nodecmp);
		if (from == NULL) {
			*error = 1;
			return NULL;
		}
		to = bsearch(edgedata[i]->to, nodes, nnodes,
			sizeof(struct node), nodecmp);
		if (to == NULL) {
			*error = 1;
			return NULL;
		}
		edges[i] = (struct edge){.from=from, .to=to};
	}

	//Tarjan's
	for (int i = 0; i < nnodes; i++) {
		if (nodes[i].index == -1) {
			*error = strongconnect(&nodes[i], &tj);
			if (*error != 0)
				return NULL;
		}
	}
	return tj.head;
}