// (c) MIT 2003.  All rights reserved.

// $Id: WingGraph.java,v 1.6 2003/03/06 00:40:38 moltmans Exp $
// Time-stamp: <2000-03-11 18:59:35 moltmans>
package rec.util;


import java.util.*;

/**
 * IMPORTANT NOTE: WingPoint and WingEdge all use their enclosing object's
 * 'equal' method so you can look up with the inside object.  If the
 * inside object is null (this hsould never happen) it goes by pointer (??)
 */
public class WingGraph
{
  Hashtable pts;
  Hashtable edges;

  public WingGraph()
  {
    pts = new Hashtable();
    edges = new Hashtable();
  }
  
  public void addPoint( Object p )
  {
    WingPoint ep = new WingPoint( p );
    pts.put( p,  ep );
  }

  public void removePoint( Object p )
  {
    pts.remove( p );
  }

  public Iterator points( )
  {
    return pts.keySet().iterator();
  }

  public Iterator edges( )
  {
    return edges.keySet().iterator();
  }

  public void removeEdge( Object w )
  {
    WingEdge pp = (WingEdge) edges.get( w );
    
    Assert.check( pp != null, "removing nonexistant edge." );
    removeEdge( pp, pp.head );
    removeEdge( pp, pp.tail );
    edges.remove( pp );
  }
   
  public void replaceEdge( Object old_edge, Object new_edge )
  {
    WingEdge pp = (WingEdge)edges.get( old_edge );
    edges.remove( old_edge );
    Assert.check( new_edge != null, "Replacing good edge with null." );
    pp.edge = new_edge;
    edges.put( new_edge, pp );
  }
  
  protected void removeEdge( WingEdge ed, WingPoint pp )
  {
    pp.removeEdge( ed );
  }

  /**
   * Add edge with object 'edge' connecting objects 'head'
   * to 'tail'
   */
  public void addEdge( Object edge, Object head, Object tail )
  {
    WingPoint hp = (WingPoint) pts.get( head );
    WingPoint tp = (WingPoint) pts.get( tail );
    Assert.check( head != null, "Connecting head to null point" );
    Assert.check( tail != null, "Connecting tail to null point" );
    Assert.check( hp != null, "Connecting to nonexistant head point " + head );
    Assert.check( tp != null, "Connecting to nonexistant point " + tail );

    WingEdge pp = new WingEdge( edge );
    pp.head = hp;
    hp.addEdge( pp, true );
    pp.tail = tp;
    tp.addEdge( pp, false );

    edges.put( edge, pp );
  }


  public boolean hasEdge( Object edge )
  {
    return edges.containsKey( edge );
  }

  /**
   * Return points which are connected to this one.
   */
  public HashSet neighbors( Object point )
  {
    WingPoint pp = (WingPoint) pts.get( point );
    return pp.neighbors();
  }

  public int degree( Object point )
  {
    WingPoint pt = (WingPoint)pts.get( point );
    if ( pt == null )
      throw new RuntimeException( "point " + point + " not in graph." );
    
    return pt.size();
  }

  public Object[] getEdges( Object point )
  {
    WingPoint pt = (WingPoint)pts.get( point );
    Object[] ed = new Object[ pt.size() ];
    int i = 0;
    Console.writeln( "pulling out " + ed.length + " edges" );
    Iterator it = pt.edges();
    while( it.hasNext() )
      ed[i++] = ((WingEdge)it.next()).edge;

    return  ed;
  }

  public Object[] getEnds( Object edge )
  {
    WingEdge we = (WingEdge) edges.get( edge );
    Object[] ob = new Object[2];

    ob[0] = we.head.center;
    ob[1] = we.tail.center;

    return ob;
  }

  public Object getHead( Object edge )
  {
    WingEdge we = (WingEdge) edges.get( edge );
    return we.head.center;
  }

  public Object getTail( Object edge )
  {
    WingEdge we = (WingEdge) edges.get( edge );
    return we.tail.center;
  }


  /**
   * The edge of the graph.
   */
  protected class WingEdge {
    WingPoint head;
    WingPoint tail;
    
    Object edge;
    
    public WingEdge( Object edge )
    {
      this.edge = edge;
      Assert.check( edge != null,
		    "Making WingEdge with null internal object." );
    }

    public boolean equals( Object o )
    {
      if ( o instanceof WingEdge )
	return edge.equals( ( (WingEdge)o ).edge );
      else
	return edge.equals( o );
    }

    public int hashCode()
    {
      return edge.hashCode();
    }

    public String toString()
    {
      return "wingEdge[" + edge.toString() + "]";
    }

  } // end WingEdge
  
  
  /**
   * This is a point on the graph.
   */
  protected class WingPoint {
    
    private Hashtable edges;

    Object center;
    
    WingPoint( Object center)
    {
      edges = new Hashtable();
      this.center = center;
    }
    
    void removeEdge( WingEdge w )
    {
      // passing w.edge so the equals hack works--we go to the object
      // as soon as possible.
      Object o = edges.remove( w );
      Console.writeln( "removing " + w + " and going to " + size() );
      Assert.check( o != null, "Failed to remove key." );
    }
    
    void addEdge( WingEdge w, boolean h )
    {
      edges.put( w, new EdgeRec( w, h ) );
    }
    

    public HashSet neighbors( )
    {
      Enumeration e = edges.elements();
      HashSet s = new HashSet();
      while( e.hasMoreElements() )
	{
	  EdgeRec er = (EdgeRec)e.nextElement();
	  // get the end's object for the end not connected to us.
	  s.add( er.head ? er.w.tail.center : er.w.head.center );
	}

      return s;
    }

    /**
     * @return set of WingEdges bordering point.
     */
    public Iterator edges()
    {
      return edges.keySet().iterator();
    }

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

    public boolean equals( Object o )
    {
      return center.equals( o );
    }

    public int hashCode()
    {
      return center.hashCode();
    }

    public String toString()
    {
      return "wingPoint[" + center.toString() + "]";
    }

    protected class EdgeRec 
    {
      WingEdge w;
      boolean head;
      
      public EdgeRec( WingEdge w, boolean head )
      {
	this.w = w;
	this.head = head;
      }
      
      public int hashCode( )
      {
	return w.hashCode();
      }
      
      public boolean equals( Object o )
      {
	return w.equals( o );
      }

    }
    
  } //end WingPoint
  
  
} // end WingGraph


































