package rpi.goldsd.graph;

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

/**
 * The Edge class is used to represent a single undirected
 * edge between two vertices.  An edge is associated with either
 * zero or one GraphBase objects.
 *
 * @see GraphBase
 * @see DirectedEdge
 * @version 2.0, 4/19/98
 * @author David Goldschmidt
 */
public class Edge implements Hashable
{
  protected static final IntSequence I = new IntSequence();
  protected static final Enumeration keys = I.sequence();



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

  /**
   * Constructs an undirected edge with the given pair of endpoint
   * vertices, the initial <tt>Hashable</tt> object to be associated with
   * this undirected edge, and the initial weight.
   * @param startVertex the first endpoint vertex of this undirected edge.
   * @param endVertex the second endpoint vertex of this undirected edge.
   * @param data the <tt>Hashable</tt> object to be associated with this
   *             undirected edge.
   * @param isWeighted indicates whether this edge is a directed edge.
   * @param weight the initial weight of this undirected edge.
   */
  protected Edge( Vertex startVertex, Vertex endVertex, Hashable data,
                  boolean isWeighted, double weight )
  {
    this.associatedGraph = null;
    this.startVertex = startVertex;
    this.endVertex = endVertex;
    this.data = data;
    this.isWeighted = isWeighted;
    if ( isWeighted ) this.weight = weight;
  }


  /**
   * Constructs an undirected edge with the given pair of endpoint
   * vertices, the initial <tt>Hashable</tt> object to be associated with
   * this undirected edge, and the initial weight.
   * @param startVertex the first endpoint vertex of this undirected edge.
   * @param endVertex the second endpoint vertex of this undirected edge.
   * @param data the <tt>Hashable</tt> object to be associated with this
   *             undirected edge.
   * @param weight the initial weight of this undirected edge.
   */
  public Edge( Vertex startVertex, Vertex endVertex, Hashable data,
               double weight )
  {
    this( startVertex, endVertex, data, true, weight );
  }


  /**
   * Constructs an undirected edge with the given pair of endpoint
   * vertices, and the initial weight.
   * @param startVertex the first endpoint vertex of this undirected edge.
   * @param endVertex the second endpoint vertex of this undirected edge.
   * @param weight the initial weight of this undirected edge.
   */
  public Edge( Vertex startVertex, Vertex endVertex, double weight )
  {
    this( startVertex, endVertex, (Hashable)keys.nextElement(), true, weight );
  }


  /**
   * Constructs an undirected edge with the given pair of endpoint
   * vertices, the initial <tt>Hashable</tt> object to be associated with
   * this undirected edge.
   * @param startVertex the first endpoint vertex of this undirected edge.
   * @param endVertex the second endpoint vertex of this undirected edge.
   * @param data the <tt>Hashable</tt> object to be associated with this
   *             undirected edge.
   */
  public Edge( Vertex startVertex, Vertex endVertex, Hashable data )
  {
    this( startVertex, endVertex, data, false, 0.0 );
  }


  /**
   * Constructs an undirected edge with the given pair of endpoint
   * vertices.
   * @param startVertex the first endpoint vertex of this undirected edge.
   * @param endVertex the second endpoint vertex of this undirected edge.
   */
  public Edge( Vertex startVertex, Vertex endVertex )
  {
    this( startVertex, endVertex, (Hashable)keys.nextElement(), false, 0.0 );
  }


  /**
   * The default constructor is not to be used, since an undirected edge
   * must have a given start and end vertex.
   */
  protected Edge()  { }



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

  /**
   * Returns a reference to the <tt>Hashable</tt> object that is
   * associated with this undirected edge.
   * @return a reference to the <tt>Hashable</tt> object that is
   *         associated with this undirected edge.
   */
  public Hashable data()  { return data; }


  /**
   * Returns the second vertex endpoint of this undirected edge.
   * Note that the name <tt>endVertex</tt> does not imply a directed edge.
   * @return the second vertex endpoint of this undirected edge.
   */
  public Vertex endVertex()  { return endVertex; }


  /**
   * Returns a reference to the graph that contains this undirected
   * edge, if any.
   * @return a reference to the graph that contains this undirected
   *         edge; or <tt>null</tt> if this undirected edge is not
   *         associated with a graph.
   */
  public GraphBase graph()  { return associatedGraph; }


  /**
   * Returns the hash value of the <tt>Hashable</tt> data associated with
   * this edge.
   * @return the hash value of the <tt>Hashable</tt> data associated with
   *         this edge.
   */
  public int hash()  { return data.hash(); }


  /**
   * Returns the hash value of the <tt>Hashable</tt> data associated with
   * this edge.
   * @param tableSize the size of the table that will potentially hold this
   *                  <tt>Edge</tt> object and others.
   * @return the hash value of the <tt>Hashable</tt> data associated with
   *         this edge.
   */
  public int hash( int tableSize )  { return data.hash( tableSize ); }


  /**
   * Tests if two edges are "equal" based on their <tt>Hashable</tt> data
   * objects.
   * @param C the right-hand side of the comparison.
   * @return <tt>true</tt> if this edge is "equal" to the given edge
   *         <tt>C</tt> based on the <tt>Hashable</tt> data objects;
   *         <tt>false</tt> otherwise.
   */
  public boolean isEqualTo( Comparable C )
  {
    if ( C instanceof Edge ) return data.isEqualTo( ((Edge)C).data() );
    else return data.isEqualTo( C );
  }


  /**
   * Tests if this undirected edge is associated with a graph.
   * @return <tt>true</tt> if this undirected edge is associated
   *         with a graph; <tt>false</tt> otherwise.
   */
  public boolean isInGraph()  { return ( associatedGraph != null ); }


  /**
   * Tests if this undirected edge is associated with the given graph.
   * @param G the graph to test.
   * @return <tt>true</tt> if this undirected edge is associated with
   *         the given graph <tt>G</tt>; <tt>false</tt> otherwise.
   */
  public boolean isInGraph( GraphBase G )
  {
    return ( associatedGraph == G );
  }


  /**
   * Tests if one edge is "less than" another based on their <tt>Hashable</tt>
   * data objects.
   * @param C the right-hand side of the comparison.
   * @return <tt>true</tt> if this edge is "less than" the given edge
   *         <tt>C</tt> based on the <tt>Hashable</tt> data objects;
   *         <tt>false</tt> otherwise.
   */
  public boolean isLessThan( Comparable C )
  {
    if ( C instanceof Edge ) return data.isLessThan( ((Edge)C).data() );
    else return data.isLessThan( C );
  }


  /**
   * Tests if this undirected edge is a self-loop.
   * @return <tt>true</tt> if this undirected edge is a self-loop (i.e. both
   *         endpoint vertices are the same); <tt>false</tt> otherwise.
   */
  public boolean isSelfLoop()  { return ( startVertex == endVertex ); }


  /**
   * Tests if this undirected edge is a weighted edge.
   * @return <tt>true</tt> if this undirected edge is a weighted
   *         edge; <tt>false</tt> otherwise.
   */
  public boolean isWeighted()  { return isWeighted; }


  /**
   * Returns the first vertex endpoint of this undirected edge.
   * Note that the name <tt>startVertex</tt> does not imply a directed edge.
   * @return the first vertex endpoint of this undirected edge.
   */
  public Vertex startVertex()  { return startVertex; }


  /**
   * Returns a <tt>String</tt> representation of this undirected edge.
   * The <tt>toString()</tt> method is applied to the <tt>Hashable</tt>
   * object that is associated with this edge.
   * @return a <tt>String</tt> representation of this undirected edge.
   */
  public String toString()
  {
    String s = "" + data;

    if ( isWeighted )
      s += "[W" + weight + "]";

    return s;
  }


  /**
   * Traverses this undirected edge from a given vertex, returning
   * the destination vertex.
   * @param V the vertex from which the traversal begins.
   * @return the vertex this undirected edge is adjacent to from <tt>V</tt>;
   *         or <tt>null</tt> if <tt>V</tt> is not one of the endpoint
   *         vertices of this undirected edge.
   */
  public Vertex traverseFrom( Vertex V )
  {
    if ( startVertex == V )
      return endVertex;
    else if ( endVertex == V )
      return startVertex;
    else
      return null;
  }


  /**
   * Returns the weight of this undirected edge, if any.
   * @return the weight of this undirected edge; or <tt>null</tt>
   *         if there is no weight associated with this undirected edge.
   */
  public double weight()  { return weight; }



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

  /**
   * Sets the <tt>Hashable</tt> object that is associated with this edge.
   * @param data the new <tt>Hashable</tt> object.
   * @return the old <tt>Hashable</tt> object associated with this edge.
   */
  public Hashable setData( Hashable data )
  {
    Hashable oldData = this.data;

    if ( isInGraph() )
      associatedGraph.rehash( oldData, data, this );
    else
      this.data = data;

    return oldData;
  }


  /**
   * Sets the <tt>associatedGraph</tt> reference to the given graph <tt>G</tt>.
   * @param G the graph that this undirected edge is to be associated with.
   */
  protected void setInGraph( GraphBase G )  { associatedGraph = G; }


  /**
   * Sets the weight of this edge.
   * @param weight the weight to be associated with this edge.
   * @return the old weight of this edge; or <tt>null</tt> if there
   *         was no weight associated with this edge.
   */
  public double setWeight( double weight )
  {
    double oldWeight = this.weight;
    this.weight = weight;
    return oldWeight;
  }



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

  /**
   * A reference to the graph that this undirected edge is associated
   * with; or <tt>null</tt> if this undirected edge is not associated
   * with a graph.
   */
  protected GraphBase associatedGraph;


  /**
   * A reference to the <tt>Hashable</tt> object associated with this
   * undirected edge.
   */
  protected Hashable data;


  /**
   * A reference to the second vertex endpoint associated with this
   * undirected edge.
   */
  protected Vertex endVertex;


  /** A flag used to indicate whether this edge is weighted. */
  protected boolean isWeighted;


  /**
   * A reference to the first vertex endpoint associated with this
   * undirected edge.
   */
  protected Vertex startVertex;


  /** The weight associated with this undirected edge. */
  protected double weight;


  /** Used by the static <tt>Algorithms</tt> class. */
  protected int status;
}