package com.quui.tm2.agents.features.suffixtree;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.quui.tm2.agents.features.suffixtree.node.Node;
import com.quui.tm2.agents.features.suffixtree.node.SimpleNodeAccessor;

/**
 * A directed acyclic graph, a compact suffix tree
 * 
 * @author fsteeg
 * 
 */
public class DAG {
    /**
     * The DAG
     */
    public NumericSuffixTree graph;

    /**
     * @param tree
     *            The suffix tree to transform into a DAG
     */
    public DAG(NumericSuffixTree tree) {
        this.graph = tree;
        compact();
    }

    /**
     * Implementation of Gusfield, p. 131
     */
    private void compact() {
        Set<Pair> Q = identifyQ();
        for (Pair pair : Q) {
            if (inGraph(pair))
                merge(pair);
        }

    }

    private boolean inGraph(Pair pair) {
        ArrayList<Node> nodes = new ArrayList<Node>();
        nodes = graph.getAllNodes(graph.getRoot(), nodes, false);
        return nodes.contains(pair.p) && nodes.contains(pair.q);
    }

    // TODO correct indices are not preserved
    private void merge(Pair pair) {
        Map<Long, Node> children = graph.accessor.getChildren(pair.p);
        // merge p into q: remove edges out of p
        List<Node> parents = graph.accessor.getParents(pair.p);
        for (Node parentOfP : parents) {
            graph.accessor.getParents(pair.q).add(parentOfP);

        }
        children.clear();
        // clear parent of p
        graph.accessor.getParents(pair.p).clear();
    }

    private Set<Pair> identifyQ() {
        Set<Pair> result = new HashSet<Pair>();
        List<Node> nodes = new ArrayList<Node>();
        nodes = graph.getAllNodes(graph.getRoot(), (ArrayList<Node>) nodes,
                false);
        // nodes.add(tree.getRoot());
        for (Node p : nodes) {
            for (Node q : nodes) {
                if (!p.equals(q))
                    if (links(p, q) && equalsLeafNum(p, q))
                        result.add(new Pair(p, q));
            }
        }
        // System.out.println("Pairs: " + result.size());
        return result;
    }

    private boolean links(Node p, Node q) {
        Node linkedByP = graph.accessor.getSuffixLink(p);
        if (linkedByP != null)
            if (linkedByP.equals(q))
                return true;
        return false;
    }

    private boolean equalsLeafNum(Node p, Node q) {
        ArrayList<Node> pLeaves = new ArrayList<Node>();
        ArrayList<Node> qLeaves = new ArrayList<Node>();
        int leavesP = graph.getAllNodes(p, pLeaves, true).size();
        int leavesQ = graph.getAllNodes(q, qLeaves, true).size();
        return leavesP == leavesQ;
    }

    public void exportDot(String string) {
        if (graph instanceof AlphanumericSuffixTree)
            ((AlphanumericSuffixTree) graph).exportDot(string);
        else
            new Mapper(graph, new SimpleNodeAccessor()).exportDot(string);

    }
}

class Pair {

    Node q;

    Node p;

    public Pair(Node p, Node q) {
        this.p = p;
        this.q = q;
    }
}
