#include <stdlib.h>
#include <ctype.h> 
// #define NDEBUG
#include "graph.h"
#include "c.h"

struct graph_node {
    BitSet parents;
    BitSet children;
    void* data;
};

typedef struct graph_node* GraphNode;

struct edge {
    int from;                 
    int to;
};

typedef struct edge* Edge;

struct graph {
    GraphNode* nodes;
    int capacity;
    int size;
    int set_size;
    ArrayList edges;
    int closed;
};

int graph_size(Graph graph)
{
    assert(graph->closed);
    return graph->size;    
}

BitSet graph_newNodeSet(Graph graph, int arena)
{
    assert(graph->closed);
    return set_new(graph->set_size);
}

BitSet graph_children(Graph graph, int parent) {
    assert(graph->closed);
    assert(graph->size > parent);
    assert(parent >= 0);
    assert(graph->nodes[parent]);
    assert(graph->nodes[parent]->children);
    return graph->nodes[parent]->children;
}

BitSet graph_parents(Graph graph, int child) {
    assert(graph->closed);
    assert(graph->size > child);
    assert(child >= 0);
    assert(graph->nodes[child]);
    assert(graph->nodes[child]->parents);
    return graph->nodes[child]->parents;
}

void integrity(Graph graph) {
    int i, j;
    assert(graph->closed);
    for(i = 0; i < graph->size; i++) {
        assert(graph->nodes[i]);    
    }
    for(i = 0; i < graph->size; i++) {
        for (j = 0; j < graph->size; j++) {
            int p, c;
            c = set_contains(graph->nodes[i]->children, j) ? 1 : 0;
            p = set_contains(graph->nodes[j]->parents, i) ? 1 : 0;
            if (p ^ c) {
                fprintf(stderr, "Integrity failed:\nNode %d child %d is %s\n", i, j, c ? "true" : "false");
                fprintf(stderr, "Node %d parent %d is %s\n", j, i, p ? "true" : "false");
                assert(0);
            }
        }
    }
}

static GraphNode createNode(void* data) {
    GraphNode node = allocate(sizeof(struct graph_node), FUNC);
    node->parents = NULL;
    node->children = NULL;
    node->data = data;
    return node;
}

static void growCapacity(Graph graph) {
    int i;
    int newCapacity = graph->capacity * 2;
    GraphNode* newNodes = allocate(sizeof(GraphNode) * newCapacity, FUNC);
    write_log("Grow capacity to %d\n", newCapacity);
    for (i = 0; i < graph->size; i++) {
        newNodes[i] = graph->nodes[i];    
    }
    graph->nodes = newNodes;
    graph->capacity = newCapacity;
}

int graph_addNode(Graph graph, void* data) {
    int id = graph->size;
    GraphNode node = createNode(data);
    assert(data);
    assert(!graph->closed);
    if    (graph->size == graph->capacity) {
        growCapacity(graph);
    }
    graph->nodes[id] = node;
    graph->size++;
    return id;
}

void graph_addEdge(Graph graph, int from, int to) {
    Edge edge = allocate(sizeof(struct edge), FUNC);
    assert(!graph->closed);
    assert(graph->size > from);
    assert(graph->size > to);
    assert(from >= 0);
    assert(to >= 0);
    LOG(("Adding edge %d to %d\n", from, to));
    edge->from = from;
    edge->to = to;
    list_add(graph->edges, edge);
}    

Graph graph_new() {
    Graph graph = allocate(sizeof(struct graph), FUNC);
    graph->size = 0;
    graph->capacity = 8;
    graph->nodes = allocate(sizeof(GraphNode) * 8, FUNC);
    graph->edges = list_new(16);
    graph->closed = 0;
    return graph;
}

static void moveNode(Graph graph, int from, int to) {
    int i;
    for(i = 0; i < graph->size; i++) {
        if (i != to) {
            GraphNode node = graph->nodes[i];
            set_moveBit(node->children, to, from);
            set_moveBit(node->parents, to, from);
        }
    }
    graph->nodes[to] = graph->nodes[from];
}

static void removeDeadNodes(Graph graph) {
    int i;
    for(i = 1; i < graph->size; i++) {
        // Check for isolated nodes.
        if (set_empty(graph_children(graph, i)) && set_empty(graph_parents(graph, i))) {
            moveNode(graph, graph->size - 1, i);
            graph->nodes[graph->size - 1] = NULL;    
            graph->size--;
        }
    }
}

static void mergePair(Graph graph, int parent, int child, void* (* merge)(void* node1, void* node2)) {
    int i;
    LOG(("Merging nodes %d %d\n", parent, child));
    graph->nodes[parent]->children = graph->nodes[child]->children;
    graph->nodes[parent]->data = merge(graph->nodes[parent]->data, graph->nodes[child]->data);
    for(i = 0; i < graph->size; i++) {
        set_moveBit(graph->nodes[i]->parents, parent, child);
    }
    if (child != graph->size - 1) {
        moveNode(graph, graph->size - 1, child);
    }    
    graph->nodes[graph->size - 1] = NULL;    
    graph->size--;
}

static void mergeNodes(Graph graph, void* (* merge)(void* node1, void* node2)) {
    int merged, i;
    LOG(("Looking for nodes to merge...\n"));
    do {
        merged = 0;
        for (i = 0; i < graph->size; i++) {
            assert(graph->nodes[i]);
            if (set_size(graph->nodes[i]->children) == 1) {
                int child = FIRST_IN(graph->nodes[i]->children);
                if (set_size(graph->nodes[child]->parents) == 1) {
                    int parent = FIRST_IN(graph->nodes[child]->parents);
                    mergePair(graph, parent, child, merge);    
                    merged = 1;
                }
            }
        }
    } while (merged);
}

void graph_close(Graph graph, void* (* merge)(void* node1, void* node2)) {
    int i, size;
    graph->set_size = graph->size;
    for (i = 0; i < graph->size; i++) {
        graph->nodes[i]->parents = set_new(graph->set_size);
        graph->nodes[i]->children = set_new(graph->set_size);
    }
    for(i = 0, size = list_size(graph->edges); i < size; i++) {
        Edge edge = (Edge)list_get(graph->edges, i);
        int to, from;
        from = edge->from;
        to = edge->to;
        set_add(graph->nodes[to]->parents, from);
        set_add(graph->nodes[from]->children, to);
    }
    if (merge != NULL)
        mergeNodes(graph, merge);
    graph->closed = 1;
    removeDeadNodes(graph);
    integrity(graph);
}

void* graph_node(Graph graph, int index) {
    return graph->nodes[index]->data;
}