h// Decompiled by Jad v1.5.8g. Copyright 2001 Pavel Kouznetsov.
// Jad home page: http://www.kpdus.com/jad.html
// Decompiler options: packimports(3) 
// Source File Name:   DirectedGraph.java

import datastructures.PriQueHeap;
import datastructures.PriorityQueues;
import java.util.*;

public class DirectedGraph
{
    class PathObject
        implements Comparable
    {

        public int compareTo(PathObject pathobject)
        {
            return distance >= pathobject.distance ? ((int) (distance <= pathobject.distance ? 0 : 1)) : -1;
        }

        public volatile int compareTo(Object obj)
        {
            return compareTo((PathObject)obj);
        }

        int to;
        double distance;
        List path;
        final DirectedGraph this$0;

        PathObject(int i, double d, List list)
        {
            this$0 = DirectedGraph.this;
            super();
            to = i;
            distance = d;
            path = list;
        }
    }


    public DirectedGraph(int i)
    {
        noOfEdges = 0;
        neighbours = (LinkedList[])new LinkedList[i];
        for(int j = 0; j < i; j++)
            neighbours[j] = new LinkedList();

    }

    public void addEdge(Edge edge)
    {
        try
        {
            neighbours[edge.from].add(edge);
        }
        catch(IndexOutOfBoundsException indexoutofboundsexception)
        {
            throw new IndexOutOfBoundsException((new StringBuilder()).append("Wrong Node Number in Graph: ").append(edge.from).toString());
        }
        noOfEdges++;
    }

    public Iterator shortestPath(int i, int j)
    {
        PriQueHeap priqueheap = new PriQueHeap();
        boolean aflag[] = new boolean[neighbours.length];
        Arrays.fill(aflag, false);
        priqueheap.add(new PathObject(i, 0.0D, new LinkedList()));
        int k = 1;
        while(!priqueheap.isEmpty()) 
        {
            PathObject pathobject = (PathObject)priqueheap.removeMin();
            k--;
            if(pathobject.to == j)
                return pathobject.path.iterator();
            if(!aflag[pathobject.to])
            {
                aflag[pathobject.to] = true;
                Iterator iterator = neighbours[pathobject.to].iterator();
                while(iterator.hasNext()) 
                {
                    Edge edge = (Edge)iterator.next();
                    if(!aflag[edge.to])
                    {
                        k++;
                        LinkedList linkedlist = new LinkedList(pathobject.path);
                        linkedlist.add(edge);
                        priqueheap.add(new PathObject(edge.to, pathobject.distance + edge.weight(), linkedlist));
                    }
                }
            }
        }
        throw new RuntimeException((new StringBuilder()).append("No path exists from ").append(i).append(" till ").append(j).toString());
    }

    private LinkedList neighbours[];
    private int noOfEdges;
}