package rpi.goldsd.graph;

import java.util.Enumeration;
import java.util.Stack;
import rpi.goldsd.container.*;

/**
 * The abstract <tt>GraphBase</tt> class provides many of the fundamental
 * methods of a graph container.  The <tt>Graph</tt> and <tt>Tree</tt>
 * classes are subclasses of the abstract <tt>GraphBase</tt> class.
 *
 * @see Vertex
 * @see Edge
 * @see DirectedEdge
 * @see Graph
 * @see Tree
 * @version 2.1, 5/12/98
 * @author David Goldschmidt
 */
public abstract class GraphBase implements Cloneable, Drawable
{
  /* ******************  STATIC CLASS ATTRIBUTES  ****************** */

  /** The default name of a graph. */
  public static final String DEFAULT_NAME = "no-name";



  /* ******************  CONSTRUCTOR METHODS  ****************** */

  /**
   * Constructs an empty graph with the specified name, initial
   * vertex hashtable size, and initial edge hashtable size.
   * @param name the user-defined name of this graph.
   * @param vertexTableSize the initial hashtable size for the hashtable
   *                        used to contain the set of vertices.
   * @param edgeTableSize the initial hashtable size for the
   *                      hashtable used to contain the set of edges.
   */
  public GraphBase( String name, int vertexTableSize, int edgeTableSize )
  {
    this.name = name;
    this.vertices = new Table( vertexTableSize );
    this.edges = new Table( edgeTableSize );
  }


  /**
   * Constructs an empty graph with the specified initial vertex
   * hashtable size and initial edge hashtable size.
   * @param vertexTableSize the initial hashtable size for the hashtable
   *                        used to contain the set of vertices.
   * @param edgeTableSize the initial hashtable size for the
   *                      hashtable used to contain the set of edges.
   */
  public GraphBase( int vertexTableSize, int edgeTableSize )
  {
    this( DEFAULT_NAME, vertexTableSize, edgeTableSize );
  }


  /**
   * Constructs an empty graph with the specified name.
   * @param name the user-defined name of this graph.
   */
  public GraphBase( String name )
  {
    this( name, Table.DEFAULT_SIZE, Table.DEFAULT_SIZE );
  }


  /** Constructs an unnamed empty graph. */
  public GraphBase()  { this( DEFAULT_NAME ); }


  /**
   * Constructs a graph by copying another graph.
   * @param G the graph to copy.
   */
  public GraphBase( GraphBase G )
  {
    this( "Copy of " + G.name(), G.vertices.getTableSize(),
          G.edges.getTableSize() );

    graphCopyHelper( this, G );
  }


  /**
   * Clones this graph.  Classes that extend the <tt>GraphBase</tt>
   * class must implement the <tt>clone()</tt> method.
   * @return a new graph that is a clone of this graph.
   */
  public abstract Object clone();


  /**
   * This protected static method performs a deep copy of all edges
   * and vertices in the graph source to the graph target.  Note
   * that the target graph is assumed to be constructed, with
   * the name, vertices, and edges properly initialized (i.e. the
   * two <tt>Table</tt> objects should be empty).
   * @param target the target graph object (should be an empty graph).
   * @param source the source graph object.
   */
  protected static final void graphCopyHelper( GraphBase target,
                                               GraphBase source )
  {
    Enumeration e = source.vertices();
    while ( e.hasMoreElements() )
    {
      Vertex j = (Vertex)e.nextElement();
      target.addBase( (Vertex)j.clone() );
    }

    e = source.vertices();
    while ( e.hasMoreElements() )
    {
      Vertex q = (Vertex)e.nextElement();

      Enumeration w = source.vertices();
      while ( w.hasMoreElements() )
      {
        Vertex r = (Vertex)w.nextElement();

        if ( q != r )
        {
          Edge E = source.edgeBetween( q, r );
          if ( E != null )
          {
            Vertex qq = target.mapToVertex( q.data() );
            Vertex rr = target.mapToVertex( r.data() );
            if ( ! target.isEdgeBetween( qq, rr ) )
              target.addBase( new Edge( qq, rr, E.data() ) );
          }
        }
      }
    }
  }



  /* ******************  ACCESSOR METHODS  ****************** */

  /**
   * Tests if a given edge exists in this graph.
   * @param E the edge to test.
   * @return <tt>true</tt> if the given edge <tt>E</tt> is in this graph;
   *         <tt>false</tt> otherwise.
   */
  public boolean contains( Edge E )  { return ( edges.contains( E.data() ) ); }


  /**
   * Tests if a given vertex exists in this graph.
   * @param V the vertex to test.
   * @return <tt>true</tt> if the given vertex <tt>V</tt> is in this graph;
   *         <tt>false</tt> otherwise.
   */
  public boolean contains( Vertex V )
  {
    return ( vertices.contains( V.data() ) );
  }


  /**
   * Finds an edge of this graph that is between the two given vertices.
   * The two vertices and the corresponding edge, if present, must be part
   * of this graph for this method to return an <tt>Edge</tt> object.
   * @param V1 the first vertex of the pair.
   * @param V2 the second vertex of the pair.
   * @return the <tt>Edge</tt> object that is between the two given vertices
   *         <tt>V1</tt> and <tt>V2</tt>; or <tt>null</tt> if no such edge
   *         exists.
   */
  public Edge edgeBetween( Vertex V1, Vertex V2 )
  {
//issue with V1 being tail of directed edge ...
    if ( ! vertices.contains( V1.data() ) || ! vertices.contains( V2.data() ) )
      return null;

    Enumeration incidentEdges = V1.incidentEdges();

    while ( incidentEdges.hasMoreElements() )
    {
      Edge E = (Edge)incidentEdges.nextElement();
      if ( E.traverseFrom( V1 ) == V2 )
        return E;
    }

    incidentEdges = V2.incidentEdges();

    while ( incidentEdges.hasMoreElements() )
    {
      Edge E = (Edge)incidentEdges.nextElement();
      if ( E.traverseFrom( V2 ) == V1 )
        return E;
    }

    return null;
  }


  /**
   * Returns an enumeration of the edges in this graph.
   * @return an enumeration of the edges in this graph.
   */
  public Enumeration edges()  { return edges.elements(); }


  /**
   * Tests if this graph is a directed graph.
   * @return <tt>true</tt> if this graph is a directed graph (i.e. contains
   *         directed edges); <tt>false</tt> otherwise.
   */
  public boolean isDigraph()
  {
    Enumeration e = edges();
    if ( e.hasMoreElements() )
      return ( ((Edge)e.nextElement()) instanceof DirectedEdge );
    else
      return false;
  }


  /**
   * Tests if an edge exists in this graph that is between the two given
   * vertices.  The two vertices and the corresponding edge, if present,
   * must be part of this graph for this method to return <tt>true</tt>.
   * @param V1 the first vertex of the pair.
   * @param V2 the second vertex of the pair.
   * @return <tt>true</tt> if an edge exists in this graph that is between the
   *         two given vertices <tt>V1</tt> and <tt>V2</tt>; <tt>false</tt>
   *         otherwise.
   */
  public boolean isEdgeBetween( Vertex V1, Vertex V2 )
  {
    return ( edgeBetween( V1, V2 ) != null );
  }


  /**
   * Tests if this graph contains any vertices.
   * @return <tt>true</tt> if this graph contains no vertices;
   *         <tt>false</tt> otherwise.
   */
  public boolean isEmpty()  { return vertices.isEmpty(); }


  /**
   * Tests if this graph is a weighted graph.
   * @return <tt>true</tt> if this graph is a weighted graph (i.e. contains
   *         weighted edges); <tt>false</tt> otherwise.
   */
  public boolean isWeighted()
  {
    Enumeration e = edges();
    if ( e.hasMoreElements() )
      return ( ((Edge)e.nextElement()).isWeighted() );
    else
      return false;
  }


  /**
   * Maps the given key to an edge in this graph, if such a mapping
   * exists in the underlying hashtable.
   * @param key the unique key identifying an edge.
   * @return the edge identified by the given <tt>key</tt>; or <tt>null</tt>
   *         if <tt>key</tt> does not map to an edge of this graph.
   */
  public Edge mapToEdge( Hashable key )  { return ( (Edge)edges.map( key ) ); }


  /**
   * Maps the given key to a vertex in this graph, if such a mapping
   * exists in the underlying hashtable.
   * @param key the unique key identifying a vertex.
   * @return the vertex identified by the given <tt>key</tt>; or <tt>null</tt>
   *         if <tt>key</tt> does not map to a vertex of this graph.
   */
  public Vertex mapToVertex( Hashable key )
  {
    return ( (Vertex)vertices.map( key ) );
  }


  /**
   * Returns the user-defined name associated with this graph.
   * @return the user-defined name associated with this graph.
   */
  public String name()  { return name; }


  /**
   * Returns the number of edges in this graph.
   * @return the number of edges in this graph.
   */
  public int numEdges()  { return edges.getSize(); }


  /**
   * Returns the number of vertices in this graph.
   * @return the number of vertices in this graph.
   */
  public int numVertices()  { return vertices.getSize(); }


  /**
   * Displays basic information about this graph.
   * @param printVertices if set to <tt>true</tt>, this method displays summary
   *                      information for each of the vertices in this graph.
   */
  public void printSummary( boolean printVertices )
  {
    System.out.println( name + ":" );

    if ( isEmpty() )
      System.out.println( "  contains no vertices or edges." );
    else
    {
      System.out.println( "  # of vertices: " + numVertices() );
      System.out.print( "  # of " );
      if ( ! isDigraph() ) System.out.print( "un" );
      System.out.println( "directed edges: " + numEdges() );

      if ( printVertices )
      {
        System.out.println( "  Vertices and incident edges:" );
        Enumeration e = vertices();
        while ( e.hasMoreElements() )
          ((Vertex)e.nextElement()).printSummary();
      }
    }
  }


  /** Displays basic information about this graph. */
  public void printSummary()  { printSummary( true ); }


  /**
   * Returns a <tt>String</tt> representation of this graph (to keep output
   * concise, the <tt>String</tt> representation currently consists of the
   * name of the graph).
   * @return a <tt>String</tt> representation of this graph.
   */
  public String toString()  { return name; }


  /**
   * Returns an enumeration of the vertices in this graph.
   * @return an enumeration of the vertices in this graph.
   */
  public Enumeration vertices()  { return vertices.elements(); }



  /* ******************  MUTATOR METHODS  ****************** */

  /**
   * Adds the given edge to this graph if it is not already
   * in this graph.  The two endpoint vertices associated with
   * the given edge must already be in this graph.
   * @param E the edge to be added to this graph.
   * @exception rpi.goldsd.container.DuplicateElementException if
   *            the key is already present in the set of vertices.
   * @exception rpi.goldsd.graph.InAnotherGraphException if the
   *            edge is already in a different graph.
   * @exception rpi.goldsd.graph.VertexNotFoundException if either
   *            of the endpoint vertices of the edge are not in
   *            this graph.
   */
  protected synchronized void addBase( Edge E )
    throws rpi.goldsd.container.DuplicateElementException,
           InAnotherGraphException, VertexNotFoundException
  {
    if ( E.isInGraph( this ) ) throw
      new DuplicateElementException( "Duplicate edge: " + E );
    else if ( E.isInGraph() ) throw
      new InAnotherGraphException( "Edge " + E + " is in another graph." );
    else if ( numEdges() > 0 && E instanceof DirectedEdge && ! isDigraph() ) throw
      new IllegalArgumentException( "Cannot add directed edge to undirected graph." );
    else if ( numEdges() > 0 && ! ( E instanceof DirectedEdge ) && isDigraph() )
      throw new IllegalArgumentException( "Cannot add undirected edge to digraph." );

    Vertex startVertex = E.startVertex();
    Vertex endVertex = E.endVertex();

    if ( ! contains( startVertex ) ) throw
      new VertexNotFoundException( "Vertex " + startVertex + " not in graph." );
    else if ( ! contains( endVertex ) ) throw
      new VertexNotFoundException( "Vertex " + endVertex + " not in graph." );

    edges.add( E );
    E.setInGraph( this );
    startVertex.addIncidentEdge( E );

    if ( ! E.isSelfLoop() && ! ( E instanceof DirectedEdge ) )
      endVertex.addIncidentEdge( E );

    if ( E instanceof DirectedEdge )
      endVertex.addIncomingEdge( (DirectedEdge)E );
  }


  /**
   * Adds the given vertex to this graph if it is not already in this graph.
   * @param V the vertex to be added to this graph.
   * @exception rpi.goldsd.container.DuplicateElementException if
   *            the key is already present in the set of vertices.
   * @exception rpi.goldsd.graph.InAnotherGraphException if the
   *            vertex is already in a different graph.
   */
  protected synchronized void addBase( Vertex V )
    throws rpi.goldsd.container.DuplicateElementException,
           InAnotherGraphException
  {
    if ( V.isInGraph( this ) ) throw
      new DuplicateElementException( "Duplicate vertex: " + V );
    else if ( V.isInGraph() ) throw
      new InAnotherGraphException( "Vertex " + V + " is in another graph." );

    vertices.add( V );
    V.setInGraph( this );
  }


  /** Removes all vertices and edges from this graph. */
  public synchronized void clear()
  {
    Enumeration e = edges();
    while ( e.hasMoreElements() )
      ((Edge)e.nextElement()).setInGraph( null );

    e = vertices();
    while ( e.hasMoreElements() )
    {
      Vertex V = (Vertex)e.nextElement();
      V.removeAllIncidentEdges();
      V.removeAllIncomingEdges();
      V.setInGraph( null );
    }

    edges.clear();
    vertices.clear();
  }


  /**
   * Rehashes an existing <tt>Edge</tt> object that is part of this graph,
   * if necessary.
   * @param oldData the old <tt>Hashable</tt> object used to locate the
   *                old <tt>Edge</tt> object in the underlying hashtable.
   * @param newData the new <tt>Hashable</tt> object that should replace
   *                the old <tt>Hashable</tt> object associated with the
   *                given <tt>Edge</tt> object.
   * @param E the <tt>Edge</tt> object that contains the old <tt>Hashable</tt>
   *          object <tt>oldData</tt>.
   */
  protected void rehash( Hashable oldData, Hashable newData, Edge E )
  {
    int tableSize = edges.getTableSize();
    if ( oldData.hash( tableSize ) != newData.hash( tableSize ) )
    {
      edges.remove( oldData );
      E.data = newData;
      edges.add( E.data(), E );
    }
  }


  /**
   * Rehashes an existing <tt>Vertex</tt> object that is part of this graph,
   * if necessary.
   * @param oldData the old <tt>Hashable</tt> object used to locate the
   *                old <tt>Vertex</tt> object in the underlying hashtable.
   * @param V the <tt>Vertex</tt> object that contains a new <tt>Hashable</tt>
   *          object.
   */
  protected void rehash( Hashable oldData, Hashable newData, Vertex V )
  {
    int tableSize = vertices.getTableSize();
    if ( oldData.hash( tableSize ) != newData.hash( tableSize ) )
    {
      vertices.remove( oldData );
      V.data = newData;
      vertices.add( V.data(), V );
    }
  }


  /**
   * Sets the name of this graph to the given <tt>String</tt> argument.
   * @param name the new name of this graph.
   * @return the old name of this graph.
   */
  public String setName( String name )
  {
    String s = this.name;
    this.name = name;
    return s;
  }



  /* ******************  CLASS ATTRIBUTES  ****************** */

  /** Hashtable containing references to all edges in this graph. */
  protected Table edges;


  /** A reference to the user-defined name of this graph. */
  protected String name;


  /** Hashtable containing references to all vertices in this graph. */
  protected Table vertices;
}