Edit D:\app\Administrator\product\11.2.0\dbhome_1\ide\src\javax\ide\util\Graph.java

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.
 *
 * @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).
 * 
 * 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 
 * unsorted, 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 not 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 connected to a
 * specified <tt>startVertex</tt>. Following standard graph theory 
 * terminology, a vertex A is connected to B if there is a path 
 * (not necessarily a direct path) from A to B.
 * 
 * In a dependency graph, this method essentially returns all of the
 * downstream dependencies of the given vertex in an order which
 * satisfies the dependencies.
 * 
 * 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();
        }
      };
    }
  }
}

Ms-Dos/Windows Unix Write backup

jsp File Browser version 1.2 by www.vonloesch.de