package javax.ide.util;

import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;


/**
 * A directed graph consisting of vertices of type T. The graph may contain
 * cycles, and is therefore not strictly a DAG. However, this class contains
 * a cycle detection algorithm in the {@link #getSortedVertices()} method.<p>
 *
 * @author Brian.Duff@oracle.com
 * @since 2.0
 */
public class Graph<T> extends AbstractCollection<T>
{
  // Use LinkedHashMap to ensure that the iteration order is the same as the
  // insertion order (see iterator()).
  protected Map<T,Vertex<T>> _vertices = new LinkedHashMap<T,Vertex<T>>();

  /**
   * Copy constructor. Creates a new graph instance that is identical to 
   * the specified original graph.
   * 
   * @param original a graph to copy.
   */
  public Graph( Graph<T> original )
  {
    _vertices.putAll( original._vertices );
  }

  public Graph()
  {
  }
  
  /**
   * Creates a comparator that can be used to compare any two items in the 
   * graph based on their sorted order (i.e. the order returned by the
   * {@link #getSortedVertices(T)} method).<p>
   * 
   * The returned Comparator is not live-connected to the graph. If you make
   * changes to the graph after retrieving a comparator, the comparator will
   * no longer be correct.
   * 
   * @return a comparator suitable for sorting vertices.
   */
  public Comparator<T> createComparator() throws CycleException
  {
    final List<T> sorted = getSortedVertices();
    
    return new Comparator<T>() 
    {
      public int compare(T o1, T o2)
      {
        return sorted.indexOf( o1 ) - sorted.indexOf( o2 );
      }
    };
  }
  
  /**
   * Constructs a graph containing all elements in the specified collection
   * as vertices.
   * 
   * @param vertices vertices to add to the collection. Note that, per the
   *    general contract of {@link #add(T)}, the collection must not contain
   *    any duplicate elements. If it does, this constructor will throw an
   *    IllegalArgumentException.
   */
  public Graph( Collection<T> vertices )
  {
    addAll( vertices );
  }
  
  public boolean contains( Object vertex )
  {
    return _vertices.containsKey( vertex );
  }
  
  /**
   * Adds a vertex to the graph. The vertex will initially be disconnected. 
   * 
   * @param vertex a vertex to add to the graph. It's illegal to add a vertex
   *    to the graph that is already present. Trying to do so will throw an
   *    IllegalArgumentException.
   */
  public boolean add( T vertex )
  {
    if ( _vertices.containsKey( vertex ) )
    {
      throw new IllegalArgumentException( "Already in graph: " + vertex );
    }
    _vertices.put( vertex, new Vertex<T>( vertex ) );
    return true;
  }
  
  /**
   * Creates a connection between two vertices.
   * 
   * @param from a vertex at the "from" end of a directed connection. The
   *    vertex must be added first using {@link #add(T)}.
   * @param to a vertex at the "to" end of a directed connection. The
   *    vertex must be added first using {@link #add(T)}.
   * 
   * @throws IllegalArgumentException if you attempt to connect a vertex to itself, 
   *    i.e. if <tt>from == to</tt>.
   */
  public void connect( T from, T to )
  {
    try
    {
      final Vertex<T> fromVertex = _vertices.get( from );
      if ( fromVertex == null ) throw new IllegalArgumentException( "from vertex is not in graph: " + from );
      final Vertex<T> toVertex = _vertices.get( to );
      if ( toVertex == null ) throw new IllegalArgumentException( "to vertex is not in graph: " + to );
  
      connectVertices( fromVertex, toVertex );
    }
    catch ( CycleException ce )
    {
      throw new IllegalArgumentException( ce );
    }
  }
  
  /**
   * Returns the list of vertices that a specified vertex connects to. The
   * resulting set of vertices is non transitive, i.e. only includes vertices
   * that have edges directly connected from the specified vertex.
   * 
   * @param from a vertex that must be in the graph.
   * @return a list of vertices that the specified vertex connects to.
   */
  public List<T> getOutwardEdges( T from )
  {
    final Vertex<T> v = _vertices.get( from );
    if ( v == null )
    {
      throw new IllegalArgumentException( "Not in graph: " + from );
    }
    return verticesToData( v._toEdges );
  }

  /**
   * Returns the list of vertices that a connects to a specified vertex. The
   * resulting set of vertices is non transitive, i.e. only includes vertices
   * that have edges directly connected to the specified vertex.
   * 
   * @param to a vertex that must be in the graph.
   * @return a list of vertices that connect to the specified vertex.
   */
  public List<T> getInwardEdges( T to )
  {
    final Vertex<T> v = _vertices.get( to );
    if ( v == null )
    {
      throw new IllegalArgumentException( "Not in graph: " + to );
    }
    return verticesToData( v._fromEdges );
  }
  
  private List<T> verticesToData( List<Vertex> l )
  {
    final List<T> connections = new ArrayList<T>( l.size() );
    for ( Vertex<T> vertex : l )
    {
      connections.add( vertex.getData() );
    }
    
    return Collections.unmodifiableList( connections );
  }

  
  private void connectVertices( Vertex<T> from, Vertex<T> to )
    throws CycleException
  {
    if ( from == to )
    {
      throw new CycleException(to.getData(),
        Collections.singletonList(from.getData()));
    }
    to._fromEdges.add( from );
    from._toEdges.add( to );
  }
  
  /**
   * Returns a new graph containing only the specified vertices. Any edges to 
   * vertices not in the specified collection are removed. <tt>this</tt> graph
   * is unaffected by this operation.
   * 
   * @param vertices a collection of vertices to retain.
   * @return a subgraph of this graph containing only the specified vertices.
   */
  public Graph<T> subgraph( Collection<T> vertices )
  {
    final Graph<T> newGraph = new Graph<T>( this );  
    newGraph.retainAll( vertices );
    return newGraph;
  }

  /**
   * Returns an iterator over the vertices in this graph. The iterator is 
   * <b>unsorted</b>, i.e. its iteration order does not take dependencies 
   * into account. In fact, the implementation will return the vertices in
   * the order in which they were added to the graph.
   * 
   * @return an iterator over all vertices in this graph.
   */
  public Iterator<T> iterator()
  {
    final Iterator<T> delegate = _vertices.keySet().iterator();
  
    return new Iterator<T>() 
    {
      private T current = null;
    
      public boolean hasNext()
      {
        return delegate.hasNext();
      }

      public T next()
      {
        current = delegate.next();
        return current;
      }

      public void remove()
      {
        if ( current == null )
        {
          throw new IllegalStateException( "You must use next() before remove()" );
        }
        removeAllReferencesTo( current );
        delegate.remove();
      }
    };
  }
  
  /**
   * @inheritDoc
   * @param vertex @inheritDoc
   * @return @inheritDoc
   */
  public boolean remove( Object vertex )
  {
    // Overridden for performance.
    removeAllReferencesTo( (T)vertex );
    return _vertices.remove( vertex ) != null;
  }
  
  /**
   * Removes all references to the specified vertex from other vertices in the
   * graph. This does <b>not</b> remove the vertex itself from the graph.
   * 
   * @param vertex a vertex to remove from the graph.
   */
  private void removeAllReferencesTo( T vertex )
  {
    for ( Vertex<T> v : _vertices.values() )
    {
      v._fromEdges.remove( _vertices.get( vertex ) );
      v._toEdges.remove( _vertices.get( vertex ) );
    }
  }

  public int size()
  {
    return _vertices.size();
  }

  /**
   * Get an ordered list of vertices, sorted such that for any given vertex 
   * A with a directed edge to vertex B, index(B) < index(A).
   * 
   * @return an ordered list of vertices.
   */
  public List<T> getSortedVertices() throws CycleException
  {
    return getSortedVertices( null );
  }
  
  /**
   * Get an ordered list of vertices, sorted such that for any given vertex
   * A with a directed edge to vertex B, index(B) < index(A). This version
   * of the method returns only vertices which are <i>connected to</i> a
   * specified <tt>startVertex</tt>. Following standard graph theory 
   * terminology, a vertex A is <i>connected to</i> B if there is a path 
   * (not necessarily a direct path) from A to B.<p>
   * 
   * In a dependency graph, this method essentially returns all of the
   * <b>downstream</b> dependencies of the given vertex in an order which
   * satisfies the dependencies.<p>
   * 
   * The first vertex in the returned list will always be <tt>startVertex</tt>.
   * 
   * @param startVertex the vertex to start from. If you pass null, this
   *    method will behave exactly the same as {@link #getSortedVertices()}.
   * @return
   * @throws CycleException
   */
  public List<T> getSortedVertices( T startVertex ) throws CycleException
  {
    final Map<T,Color> colors = new HashMap<T,Color>( _vertices.size() );
    final List<T> sortedList = new ArrayList<T>( _vertices.size() );
    
    if ( startVertex != null )
    {
      Color c = colors.get( startVertex );
      if ( c == null ) visit( new ArrayList<T>(), colors, startVertex, sortedList );
    }
    else
    {
      for ( T t : this )
      {
        Color c = colors.get( t );
        if ( c == null ) visit( new ArrayList<T>(), colors, t, sortedList );      
      }
    }    
    Collections.reverse( sortedList );
    return Collections.unmodifiableList( sortedList );
    
  }
  

  
  private void visit( List<T> visiting, Map<T,Color> colors, T vertex, List<T> sortedList )
    throws CycleException
  {  
    colors.put( vertex, Color.VISITING );
    visiting.add( vertex );
    for ( Vertex<T> to : _vertices.get( vertex ) )
    {
      final Color color = colors.get( to.getData() );
      if ( color == Color.VISITING )
      {
        throw new CycleException(to.getData(), visiting);
      }
      else if ( color != Color.VISITED )
      {
        visit( visiting, colors, to.getData(), sortedList );
      }
    }
    sortedList.add( vertex );
    visiting.remove( vertex );
    colors.put( vertex, Color.VISITED );
  }



  /**
   * Get all vertices connected to the specified vertex. A vertex A is 
   * connected to a vertex B if there is a path (not necessarily a direct
   * path) from A to B.
   * 
   * @param vertex a vertex. Must not be null.
   * @return a collection of vertices connected to the specified vertex. The 
   *   collection is unsorted.
   *  
   * @throws CycleException
   */
  public List<T> getVerticesConnectedTo( T vertex ) throws CycleException
  {
    if ( vertex == null ) 
      throw new NullPointerException( "vertex is null" );

    List<T> vertices = new ArrayList<T>();

    Map<T,Color> colors = new HashMap<T,Color>();
    visitInReverse( colors, vertex, vertices );
    vertices.remove( vertex );
    
    return Collections.unmodifiableList( vertices );
  }

  private void visitInReverse( Map<T,Color> colors, T startVertex, 
    List<T> vertices ) throws CycleException
  {
    colors.put( startVertex, Color.VISITING );
    Vertex<T> v = _vertices.get( startVertex );
    List<Vertex> from = v._fromEdges;
    for ( Vertex<T> fromVertex : from )
    {
      final Color color = colors.get( fromVertex.getData() );    
      if ( color == Color.VISITING )
      {
        throw new CycleException(fromVertex.getData(),
          vertices);
      }
      else if ( color != Color.VISITED )
      {
        visitInReverse( colors, fromVertex.getData(), vertices );
      }
    }
    vertices.add( startVertex );
    colors.put( startVertex, Color.VISITED );
  }

  private final class Vertex<T> implements Iterable<Vertex>
  {
    private final T _data;
    private final List<Vertex> _toEdges = new ArrayList<Vertex>();
    private final List<Vertex> _fromEdges = new ArrayList<Vertex>();

    Vertex( T data )
    {
      _data = data;
    }

    public T getData()
    {
      return _data;
    }

    /**
     * Iterator over the "to" edges of this vertex.
     * 
     * @return an iterator over the to edges for this vertex.
     */
    public Iterator<Vertex> iterator()
    {
      return _toEdges.iterator();
    }

  }
  
  public static class CycleException extends Exception 
  {
    private List vertices;
    private Object vertex;
    CycleException (Object vertex, List vertices)
    {
      this.vertices = vertices;
      this.vertex = vertex;
    }
    
    public String getMessage ()
    {
      if (vertices.size() == 1 && vertex == vertices.get(0))
      {
        return vertex + " depends on itself";
      }
      else
      {
        return vertex + " is in a dependency cycle: " + getDependencyChain();
      }
    }

    
    public String getDependencyChain( )
    {
      StringBuffer b = new StringBuffer();
      ArrayList l = new ArrayList( vertices );
      Collections.reverse( l );
      
      b.append( String.valueOf( vertex ) );
      
      for ( Iterator i = l.iterator(); i.hasNext();  )
      {
        Object t= i.next();

        b.append( "\n->" );
        b.append( String.valueOf( t ) );

        if ( t == vertex )
        {
          break;
        }        
      }
      b.append("\n");
      return b.toString();
      
    }

  }
  
  private enum Color
  {
    VISITING,
    VISITED
  }
  
  /**
   * Returns a graph based on the specified graph, but which does not permit
   * modification. Changes to the original graph will be reflected through the
   * non modifiable version.
   * 
   * @param graph the original graph.
   * @return an unmodifiable version of the graph.
   */
  public static <Z> Graph<Z> unmodifiableGraph( Graph<? extends Z> graph )
  {
    return new UnmodifiableGraph( graph );
  }
  
  private static class UnmodifiableGraph<E> extends Graph<E>
  {
    private Graph<E> _graph;
    UnmodifiableGraph( Graph<E> g )
    {
      super();
      _graph = g;
    }
    
    public boolean equals( Object o ) { return _graph.equals( o ); }
    public int hashCode() { return _graph.hashCode(); }
    public int size() { return _graph.size(); }
    public boolean isEmpty() { return _graph.isEmpty(); }
    public boolean contains( Object o ) { return _graph.contains( o ); }
    public Object[] toArray() { return _graph.toArray(); }
    public <E> E[] toArray(E[] a ) { return _graph.toArray( a ); }
  
    public boolean add( E e )
    {
      throw new UnsupportedOperationException();
    }
    
    public boolean remove( Object e )
    {
      throw new UnsupportedOperationException();
    }
    
    public void connect( E e, E e2 )
    {
      throw new UnsupportedOperationException();
    }
    
    public Iterator<E> iterator()
    {
      final Iterator<E> i = _graph.iterator();
      return new Iterator<E>() 
      {
        public boolean hasNext()
        {
          return i.hasNext();
        }

        public E next()
        {
          return i.next();
        }

        public void remove()
        {
          throw new UnsupportedOperationException();
        }
      };
    }
  }
}