package org.javarosa.core.util;

import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Stack;
import java.util.Vector;

/**
 * Directed A-cyclic (NOT ENFORCED) graph datatype.
 *
 * Genericized with three types: An unique index value (representing the node), a generic
 * set of data to associate with that node, and a piece of data to associate with each
 * edge
 *
 * @author ctsims
 */
public class DAG<I, N, E> {
    //TODO: This is a really unsafe datatype. Needs an absurd amount of updating for representation
    //invariance, synchronicity, cycle detection, etc.

    private final Hashtable<I, N> nodes;
    private final Hashtable<I, Vector<Edge<I, E>>> edges;
    private final Hashtable<I, Vector<Edge<I, E>>> inverseEdges;

    public DAG() {
        nodes = new Hashtable<I, N>();
        edges = new Hashtable<I, Vector<Edge<I, E>>>();
        inverseEdges = new Hashtable<I, Vector<Edge<I, E>>>();
    }

    public void addNode(I i, N n) {
        nodes.put(i, n);
    }

    public void removeNode(I i) {
        nodes.remove(i);
    }

    /**
     * Connect Source -> Destination
     */
    public void setEdge(I source, I destination, E edgeData) {
        addToEdges(edges, source, destination, edgeData);
        addToEdges(inverseEdges, destination, source, edgeData);
    }

    private void addToEdges(Hashtable<I, Vector<Edge<I, E>>> edgeList, I source, I dest, E edgeData) {
        Vector<Edge<I, E>> edge;
        if (edgeList.containsKey(source)) {
            edge = edgeList.get(source);
        } else {
            edge = new Vector<Edge<I, E>>();
        }
        edge.addElement(new Edge<I, E>(dest, edgeData));
        edgeList.put(source, edge);
    }

    /**
     * If an edge exists in the graph from sourceIndex to destinationIndex, remove it
     */
    public void removeEdge(I sourceIndex, I destinationIndex) {
        Vector<Edge<I, E>> edgesFromSource = edges.get(sourceIndex);
        for (Edge<I, E> edge : edgesFromSource) {
            if (edge.i.equals(destinationIndex)) {
                // Remove the edge
                edgesFromSource.remove(edge);

                // If removing this edge has made it such that this source index no longer has
                // any edges from it, remove that entire index from the edges hashtable
                if (edgesFromSource.size() == 0) {
                    edges.remove(sourceIndex);
                }

                return;
            }
        }
    }

    public Vector<Edge<I, E>> getParents(I index) {
        if (inverseEdges.containsKey(index)) {
            return inverseEdges.get(index);
        } else {
            return new Vector<Edge<I, E>>();
        }
    }

    public Vector<Edge<I, E>> getChildren(I index) {
        if (!edges.containsKey(index)) {
            return new Vector<Edge<I, E>>();
        } else {
            return edges.get(index);
        }
    }

    public N getNode(I index) {
        return nodes.get(index);
    }

    /**
     * @return Indices for all nodes in the graph which are not the target of
     * any edges in the graph
     */
    public Stack<I> getSources() {
        Stack<I> sources = new Stack<I>();
        for (Enumeration en = nodes.keys(); en.hasMoreElements(); ) {
            I i = (I)en.nextElement();
            if (!inverseEdges.containsKey(i)) {
                sources.addElement(i);
            }
        }
        return sources;
    }

    /**
     * @return Indices for all nodes that do not have any outgoing edges
     */
    public Stack<I> getSinks() {
        Stack<I> roots = new Stack<I>();
        for (Enumeration en = nodes.keys(); en.hasMoreElements(); ) {
            I i = (I)en.nextElement();
            if (!edges.containsKey(i)) {
                roots.addElement(i);
            }
        }
        return roots;
    }

    public static class Edge<I, E> {
        public final I i;
        public final E e;

        public Edge(I i, E e) {
            this.i = i;
            this.e = e;
        }
    }

    public Enumeration getNodes() {
        return nodes.elements();
    }

    public Enumeration getIndices() {
        return nodes.keys();
    }

    public Hashtable<I, Vector<Edge<I, E>>> getEdges() {
        return this.edges;
    }
}

@@ -1728,38 +1728,279 @@
   * 
-If an edge exists in the graph
+Removes the given edge from both edge lists%0A     */%0A    public void removeEdge(I sourceIndex, I destinationIndex) %7B%0A        removeEdge(edges, sourceIndex, destinationIndex);%0A        removeEdge(inverseEdges, destinationIndex, sourceIndex);%0A    %7D%0A%0A    /**%0A     * If an edge
  fro
@@ -2032,16 +2032,46 @@
 ionIndex
+ exists in the given edge list
 , remove
@@ -2079,37 +2079,38 @@
 it%0A     */%0A    p
-ublic
+rivate
  void removeEdge
@@ -2102,32 +2102,75 @@
 void removeEdge(
+Hashtable%3CI, Vector%3CEdge%3CI, E%3E%3E%3E edgeList, 
 I sourceIndex, I
@@ -2235,25 +2235,28 @@
 ource = edge
-s
+List
 .get(sourceI
@@ -2254,32 +2254,75 @@
 t(sourceIndex);%0A
+        if (edgesFromSource != null) %7B%0A    
         for (Edg
@@ -2359,32 +2359,36 @@
 ) %7B%0A            
+  
+  
 if (edge.i.equal
@@ -2426,16 +2426,20 @@
         
+    
 // Remov
@@ -2461,24 +2461,28 @@
             
+ 
+   
 edgesFromSou
@@ -2500,16 +2500,20 @@
 edge);%0A%0A
+    
         
@@ -2615,16 +2615,20 @@
         
+    
 // any e
@@ -2699,32 +2699,36 @@
                 
+    
 if (edgesFromSou
@@ -2766,21 +2766,28 @@
         
-edges
+    edgeList
 .remove(
@@ -2812,24 +2812,28 @@
             
+    
 %7D%0A%0A         
@@ -2843,16 +2843,20 @@
     
+  
+  
 return;%0A
     
@@ -2851,16 +2851,34 @@
 return;%0A
+                %7D%0A
         

remove an edge from both edge lists; check for null before removing an edge