package rpi.goldsd.graph;

import java.util.Enumeration;
import java.util.Vector;

/**
 * The <tt>Path</tt> class is an <I>iterator</I> class used to
 * represent a path or walk through an associated graph.
 *
 * @see GraphBase
 * @version 2.0, 4/19/98
 * @author David Goldschmidt
 */
public class Path implements Cloneable, Drawable
{
  /* ******************  CONSTRUCTOR METHODS  ****************** */

  /**
   * Constructs an empty path with the initial path capacity.
   * If used, this value should indicate the number of vertices
   * and edges making up this path, including the start and
   * end vertices.
   * @param capacity the initial capacity for the vector used to represent
   *                 the path of alternating vertices and edges.
   */
  public Path( int capacity )  { path = new Vector( capacity ); }


  /**
   * Constructs a path with a given start vertex.
   * @param startVertex the initial start vertex of this path.
   * @exception IllegalArgumentException if the start vertex argument
   *                                     is not in a graph.
   */
  public Path( Vertex startVertex ) throws IllegalArgumentException
  {
    this();

    if ( ! startVertex.isInGraph() ) throw
      new IllegalArgumentException( "Vertex must be in a graph." );

    path.addElement( startVertex );
  }


  /**
   * Constructs a path by copying another path.
   * @param P the path to be copied.
   */
  public Path( Path P )
  {
    this( P.path.size() );
    pathCopyHelper( this, P );
  }


  /**
   * Clones this path.
   * @return a new path that is a clone of this path.
   */
  public Object clone()
  {
    Path P = new Path( this.path.size() );
    pathCopyHelper( P, this );
    return P;
  }


  /**
   * This protected static method performs a deep copy of all edges
   * and vertices in the path source to the path target.  Note
   * that the target path is assumed to be constructed.
   * @param target the target path object (should be an empty path).
   * @param source the source path object.
   */
  protected static final void pathCopyHelper( Path target, Path source )
  {
    Enumeration e = source.elements();
    while ( e.hasMoreElements() )
      target.path.addElement( e.nextElement() );
  }


  /** Constructs an empty path. */
  public Path()  { path = new Vector(); }



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

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


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


  /**
   * Returns an enumeration of the edges in this path.
   * @return an enumeration of the edges in this path.
   */
  public Enumeration edges()
  {
    return new Enumeration()
    {
      int index = 1;

      public boolean hasMoreElements()
      {
        return ( index < length() * 2 );
      }

      public Object nextElement()
      {
        Object E = path.elementAt( index );
        index += 2;
        return E;
      }
    };
  }


  /**
   * Returns an enumeration of the vertices and edges in this path.
   * Note that the <tt>nextElement()</tt> method of the enumeration returns
   * alternating vertex and edge objects.
   * @return an enumeration of the vertices and edges in this path.
   */
  public Enumeration elements()
  {
    return new Enumeration()
    {
      int index = 0;

      public boolean hasMoreElements()
      {
        return ( index <= length() * 2 );
      }

      public Object nextElement()
      {
        return ( path.elementAt( index++ ) );
      }
    };
  }


  /**
   * Returns a reference to the first vertex in this path.
   * @return a reference to the first vertex in this path.
   */
  public Vertex firstVertex()  { return ( (Vertex)path.firstElement() ); }


  /**
   * Returns a reference to the graph associated with this path.
   * @return a reference to the graph associated with this path; or
   *         <tt>null</tt> if this path is not associated with
   *         a graph (which implies that the path is empty).
   */
  public GraphBase graph()  { return ( firstVertex().graph() ); }


  /**
   * Tests if this path is a cycle.
   * @return <tt>true</tt> if the first and last vertices are the
   *         same; <tt>false</tt> otherwise.
   */
  public boolean isCycle()  { return ( firstVertex() == lastVertex() ); }


  /**
   * Tests if the given <tt>endVertex</tt> is reachable from the
   * <tt>startVertex</tt> in this path.  Note that if this path is a
   * cycle, then if the two given vertices exist in this path, then this
   * method returns <tt>true</tt>.  Also note that if duplicate vertices
   * appear in the path, then the first occurrence of the <tt>startVertex</tt>
   * is used as a starting place.
   * @param startVertex the vertex to start the traversal from.
   * @param endVertex the destination vertex.
   * @return <tt>true</tt> if <tt>endVertex</tt> is reachable from
   *         <tt>startVertex</tt>; <tt>false</tt> otherwise.
   */
  public boolean isReachable( Vertex startVertex, Vertex endVertex )
  {
    int startPosition = path.indexOf( startVertex );

    if ( startPosition == -1 )
      return false;

    if ( isCycle() )
      return ( path.contains( endVertex ) );

    int endPosition = path.indexOf( endVertex, startPosition );

    return ( endPosition != -1 );
  }


  /**
   * Returns a reference to the last vertex in this path.
   * @return a reference to the last vertex in this path.
   */
  public Vertex lastVertex()  { return ( (Vertex)path.lastElement() ); }


  /**
   * Returns the number of edges in this path.
   * @return the number of edges in this path.
   */
  public int length()  { return ( path.size() / 2 ); }


  /**
   * Returns the name of the graph this path is associated with.
   * @return the name of the graph this path is associated with.
   */
  public String name()  { return ( graph().name() ); }


  /**
   * Returns the number of occurrences of a given edge in this path.
   * @return the number of occurrences of the given edge <tt>E</tt> in this
   *         path.
   */
  public int occurrences( Edge E )
  {
    int count = 0;
    Enumeration e = edges();

    while ( e.hasMoreElements() )
      if ( e.nextElement() == E )
        count++;

    return count;
  }


  /**
   * Returns the number of occurrences of a given vertex in this path.
   * @return the number of occurrences of the given vertex <tt>V</tt> in
   *         this path.
   */
  public int occurrences( Vertex V )
  {
    int count = 0;
    Enumeration e = vertices();

    while ( e.hasMoreElements() )
      if ( e.nextElement() == V )
        count++;

    return count;
  }


  /**
   * Returns a <tt>String</tt> representation of this path.  The
   * <tt>String</tt> begins with "Path: " and then makes use of the
   * <tt>toString()</tt> method of each of the vertices of this path,
   * separating each vertex with "->" to represent an edge.
   * @return a <tt>String</tt> representation of this path.
   */
  public String toString()
  {
    Enumeration e = vertices();
    if ( ! e.hasMoreElements() )
      return ( "<empty>." );

    String s = "";

    while ( e.hasMoreElements() )
    {
      s = s + (Vertex)e.nextElement();

      if ( e.hasMoreElements() )
        s = s + "->";
    }

    return ( s + "." );
  }


  /**
   * Returns an enumeration of the vertices of this path.
   * @return an enumeration of the vertices of this path.
   */
  public Enumeration vertices()
  {
    return new Enumeration()
    {
      int index = 0;

      public boolean hasMoreElements()
      {
        return ( index <= length() * 2 );
      }

      public Object nextElement()
      {
        Object E = path.elementAt( index );
        index += 2;
        return E;
      }
    };
  }


  /**
   * Returns the weight of this path, which is simply the sum of all
   * weighted edges of this path.
   * @return the weight of this path.
   */
  public double weight()
  {
    double weight = 0.0;
    Enumeration e = edges();

    while ( e.hasMoreElements() )
      weight += ((Edge)e.nextElement()).weight();

    return weight;
  }



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

  /**
   * Adds an edge and its corresponding destination vertex to the
   * end of this path.  The edge must be associated with the last
   * vertex of this path.  Note that this method actually adds two
   * references to the end of this path: first the given edge <tt>E</tt>,
   * and second the destination vertex found by traversing <tt>E</tt> from
   * the last vertex of this path.
   * @param E the edge to be added.
   * @exception IllegalArgumentException if the edge is not associated with
   *                                     the last vertex of this path.
   */
  public void add( Edge E ) throws IllegalArgumentException
  {
    Vertex V = lastVertex();

    if ( ( V != E.startVertex() && V != E.endVertex() ) ||
         ( V == E.endVertex() && E instanceof DirectedEdge ) )
      throw new IllegalArgumentException( "Edge not part of path." );

    path.addElement( E );
    path.addElement( E.traverseFrom( V ) );
  }


  /**
   * Adds an edge and its corresponding destination vertex to the
   * end of this path.  The edge must be associated with the last
   * vertex of this path.  Note that this method actually adds two
   * references to the end of this path: first the given edge,
   * and second the given destination vertex.
   * @param V the vertex to be added.
   * @exception IllegalArgumentException if there is no edge connecting
   *            the last vertex of this path and the given vertex argument.
   */
  public void add( Vertex V ) throws IllegalArgumentException
  {
    Vertex lastV = lastVertex();
    Enumeration e = lastV.incidentEdges();
    while ( e.hasMoreElements() )
    {
      Edge E = (Edge)e.nextElement();
      if ( E.traverseFrom( lastV ) == V )
      {
        add( E );
        return;
      }
    }

    throw new IllegalArgumentException( "No such edge to given vertex." );
  }


  /**
   * Initializes this path and adds the starting vertex to this path.  Note
   * that this method removes all elements from the existing path, if any.
   * @param V the starting vertex of this path.
   * @exception IllegalArgumentException if the <tt>Vertex</tt> argument is
   *                                     not in a graph object.
   */
  public void addStartVertex( Vertex V ) throws IllegalArgumentException
  {
    if ( ! V.isInGraph() )
      throw new IllegalArgumentException( "Vertex must be in a graph." );

    path.removeAllElements();
    path.addElement( V );
  }


  /**
   * Removes the last vertex and edge from this path.
   * @return the edge removed from this path; or <tt>null</tt> if
   *         the path contains no edges.
   */
  public Edge backtrack()
  {
    if ( length() < 1 )
      return null;

    path.removeElementAt( path.size() - 1 );
    Edge E = (Edge)path.lastElement();
    path.removeElementAt( path.size() - 1 );
    return E;
  }


  /**
   * Concatenates the given path with this path by adding all
   * elements of the given path to the end of this path.  Note that
   * the last vertex of this path must be the same as the first
   * vertex of the given path <tt>P</tt>.
   * @param P the path to be added to this path.
   * @exception IllegalArgumentException if the last vertex of this path
   *            is not the first vertex of the given <tt>Path</tt> object.
   */
  public void concat( Path P ) throws IllegalArgumentException
  {
    if ( lastVertex() != P.firstVertex() )
      throw new IllegalArgumentException();

    Enumeration e = P.edges();
    while ( e.hasMoreElements() )
      add( (Edge)e.nextElement() );
  }


  /**
   * Inserts a given path into this path after the first occurrence of the
   * given vertex in this path.  The vertex <tt>V</tt> must exist in this
   * path and be the first and last vertex in the given path <tt>P</tt>
   * (i.e. the given path <tt>P</tt> must be a cycle).
   * @param P the path to be inserted.
   * @param V the vertex after which the path <tt>P</tt> is to be inserted.
   * @exception IllegalArgumentException if the given <tt>Path</tt> object
   *            is not a cycle, or if the given <tt>Vertex</tt> object does
   *            not begin the given <tt>Path</tt> object.
   * @exception VertexNotFoundException if the given <tt>Vertex</tt> object
   *            is not in this path.
   */
  public void insertAfter( Path P, Vertex V )
    throws IllegalArgumentException, VertexNotFoundException
  {
    if ( ! P.isCycle() ) throw
      new IllegalArgumentException( "Path argument is not a cycle." );

    if ( V != P.firstVertex() ) throw
      new IllegalArgumentException( "Vertex does not begin path argument." );

    int position = path.indexOf( V );

    if ( position == -1 ) throw
      new VertexNotFoundException();

    position++;

    Enumeration e = P.elements();
    e.nextElement();  // skip initial vertex ...

    while ( e.hasMoreElements() )
      path.insertElementAt( e.nextElement(), position++ );
  }



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

  /**
   * A <tt>Vector</tt> representing this path.  This <tt>Vector</tt>
   * contains an alternating series of vertices and edges.  Note that
   * this <tt>Vector</tt> must begin and end with a <tt>Vertex</tt>
   * object, thus the <tt>size()</tt> of the <tt>Vector</tt> will always
   * be odd (unless it is zero).
   */
  protected Vector path;
}