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

////////////////////////////////////////////////////////////////////////////////
//
// FILE:	PolygonParser.java
//
// ID:          $Id: PolygonParser.java,v 1.7 2005/04/28 06:09:47 moltmans Exp $
//
// AUTHOR:	Manoj D. Muzumdar
//		archon@ai.mit.edu
//
// DATE:	07-XX-98
//
// COPYRIGHT:	Massachusetts Institute of Technology
//		All rights reserved.
//
// PURPOSE:     Polygon parser
//
// HISTORY:     11-15-98 archon
//              Now aware of new rec.geo package
//
////////////////////////////////////////////////////////////////////////////////

package rec.core.recognizers;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Vector;

import rec.core.widgets.PolygonInfo;
import rec.core.widgets.WLine;
import rec.geo.GPoint;
import rec.geo.Geometry;
import rec.sys.GeometryCalculator;
import rec.sys.Surface;
import rec.sys.Widget;
import rec.util.Assert;
import rec.util.Queue;

public final class PolygonParser
{
  private static final double RANGE = 20.0;

  private static final int MAX_REGION = 25;

  ////////////////////////////////////////////////////////////////////////////

  public static PolygonInfo parse( Surface s, WLine l )
  {
    GeometryCalculator gc = new GeometryCalculator( s );
    Iterator e = gc.getVisibleWidgets().iterator();
    if( e == null )
      return( null );

    HashSet line_pool = new HashSet();
    while ( e.hasNext() )
      {
	Object o = e.next();
	if ( o instanceof WLine )
	  line_pool.add( o );
      }

    return parse( line_pool, l );
  }


  public static PolygonInfo parse( HashSet lines, WLine l )
  {
    PolyFrame pf = findNextLine( lines, l );

    if ( pf != null )
      return new PolygonInfo( pf.points, pf.lines );
    
    return( null );
  }


  public static PolygonInfo parse( int sides, Surface s, WLine l )
  {
    HashSet line_pool = new HashSet( );
    Iterator e = s.getWidgetsIterator();
    while( e.hasNext() )
      line_pool.add( e.next() );

    Assert.check( ( sides >= 3),
		  "polygons must have at least 3 sides" );

    GPoint[] points = new GPoint[sides];
    WLine[] lines = new WLine[sides];

    if ( findNextLine( line_pool, sides, 0, points, lines,
		       l.getHead(), l.getHead(),
		       l, l.getTail() ) )
      return( new PolygonInfo( points, lines ) );

    /*
      by symmetry we should not need this, right?
	 || findNextLine( s, sides, 0, points, lines,
			  l.getTail(), l.getTail(),
			  l, l.getHead() ) )
    */
    
    return( null );
  }

  /////////////////////////////////////////////////////////////////////////////

  private static boolean findNextLine( HashSet line_pool,
				       int num_sides,
				       int currIndex,
				       GPoint[] points,
				       WLine[] lines,
				       GPoint firstPoint,
				       GPoint prevPoint,
				       WLine lastLine,
				       GPoint lastPoint )
  {
    int maxIndex = points.length - 1;

    if (( currIndex == num_sides-1) || ((num_sides == -1) && (currIndex>=2)) )
      {
	if( (points[currIndex] = connects( firstPoint, lastPoint ) )
	    != null ) {
	  lines[currIndex] = lastLine;
	  return( true );
	}
      }

    if ( currIndex == maxIndex )
      return( false );

    Iterator e = line_pool.iterator();
    while( e.hasNext() ) {

      Widget vw = (Widget)e.next();

      if( !( vw instanceof WLine ) )
	continue;

      WLine l = (WLine)vw;

      if( alreadyInPolygon( currIndex, lines, lastLine, l ) )
	continue;

      boolean shouldExecuteFirst = true;
      boolean shouldExecuteSecond = true;

      // If point is closer to other end of the line,
      //     skip it;
      // This is because it creates problems
      //     for small lines.

      if( Geometry.distance( prevPoint, l.getHead() ) <
	  Geometry.distance( lastPoint, l.getHead() ) )
	shouldExecuteFirst = false;

      if( Geometry.distance( prevPoint, l.getTail() ) <
	  Geometry.distance( lastPoint, l.getTail() ) )
	shouldExecuteSecond = false;

      // If both points connect, pick the closer one.

      if( connects( lastPoint, l.getHead() ) != null
	  && connects( lastPoint, l.getTail() ) != null ) {
	if( Geometry.distance( lastPoint, l.getHead() )
	    <= Geometry.distance( lastPoint, l.getTail() ) )
	  shouldExecuteSecond = false;
	else
	  shouldExecuteFirst = false;
      }

      if( shouldExecuteFirst
	  && (points[currIndex] = connects( lastPoint,
					    l.getHead() ))
	  != null ) {
	lines[currIndex] = lastLine;
	boolean res = findNextLine( line_pool, num_sides,
			      currIndex + 1,
			      points, lines,
			      firstPoint, l.getHead(),
			      l, l.getTail() );

	// if true, we found one!
	if ( res )
	  return true;
      }

      if( shouldExecuteSecond
	  && (points[currIndex] = connects( lastPoint,
					    l.getTail() ))
	  != null ) {
	lines[currIndex] = lastLine;
	boolean res = findNextLine( line_pool, num_sides,
			      currIndex + 1,
			      points, lines,
			      firstPoint, l.getTail(),
			      l, l.getHead() );

	// if true, we found one!
	if ( res )
	  return true;
      }
    }

    // we fail--no more lines to play with.
    return( false );
  }




  private static PolyFrame findNextLine( HashSet line_pool,
					 WLine new_line )
  {
    try {
    GPoint[] points = new GPoint[MAX_REGION];
    WLine[] lines = new WLine[MAX_REGION];

    Queue frames = new Queue();
    
    PolyFrame fr = new PolyFrame( 0,
				  points,
				  lines,
				  new_line.getHead(),
				  new_line.getHead(),
				  new_line,
				  new_line.getTail() );

    frames.append( fr );
    
    int maxIndex = points.length - 1;

    while( ! frames.isEmpty() )
      {
	// break down a frame, check each piece for a winner, else
	// stash on frames list.

	fr = (PolyFrame)frames.remove();

	if ( fr.currIndex >= 2 )
	  {
	    if( (fr.points[fr.currIndex] = connects( fr.firstPoint, fr.lastPoint))
		!= null ) {
	      fr.lines[fr.currIndex] = fr.lastLine;

	      // return the victor!
	      return fr;
	    }
	  }
	
	// this frame is dead.
	if ( fr.currIndex == fr.points.length )
	  continue;
	
	Iterator e = line_pool.iterator();
	while( e.hasNext() ) {

	  Object o = e.next();
	  // go through all lines on field
	  WLine l = (WLine)o;
	  
	  if ( fr.contains( l ) )
	    continue;
	  
	  boolean shouldExecuteFirst = true;
	  boolean shouldExecuteSecond = true;
	  
	  // If point is closer to other end of the line,
	  //     skip it;
	  // This is because it creates problems
	  //     for small lines.
	  
	  if( Geometry.distance( fr.prevPoint, l.getHead() ) <
	      Geometry.distance( fr.lastPoint, l.getHead() ) )
	    shouldExecuteFirst = false;
	  
	  if( Geometry.distance( fr.prevPoint, l.getTail() ) <
	      Geometry.distance( fr.lastPoint, l.getTail() ) )
	    shouldExecuteSecond = false;
	  
	  // If both points connect, pick the closer one.
	  if( shouldExecuteFirst && shouldExecuteSecond )
	    {
	      if( Geometry.distance( fr.lastPoint, l.getHead() )
		<= Geometry.distance( fr.lastPoint, l.getTail() ) )
		shouldExecuteSecond = false;
	      else
		shouldExecuteFirst = false;
	    }
	  
	  if( shouldExecuteFirst
	      && (fr.points[fr.currIndex] = connects( fr.lastPoint,
						l.getHead() ))
	      != null ) 
	    {
	      fr.lines[fr.currIndex] = fr.lastLine;
	      PolyFrame nfr = new PolyFrame( fr, l, true );
	      frames.append( nfr );
	    }
	  
	  if( shouldExecuteSecond
	      && (fr.points[fr.currIndex] = connects( fr.lastPoint,
						      l.getTail() ))
	      != null ) 
	    {
	      fr.lines[fr.currIndex] = fr.lastLine;
	      PolyFrame nfr = new PolyFrame( fr, l, false );

	      frames.append( nfr );
	    }
	}
      } // end while

    return null;
    }
    catch ( Exception e ) {
      //Console.writeln( "nabbed baddie." );
      e.printStackTrace();
      Assert.error("Error parsing a polygon");
    }
    return null;
  }




  public static PolyFrame[] findNextLine( WLine[] world,
					   int max_size,
					   boolean return_first,
					   WLine new_line )
  {
    Vector hits = new Vector();

    GPoint[] points = new GPoint[max_size];
    WLine[] lines = new WLine[max_size];

    Queue frames = new Queue();
    
    PolyFrame fr = new PolyFrame( 0,
				  points,
				  lines,
				  new_line.getHead(),
				  new_line.getHead(),
				  new_line,
				  new_line.getTail() );

    frames.append( fr );
    
    int maxIndex = points.length - 1;

    while( ! frames.isEmpty() )
      {
	// break down a frame, check each piece for a winner, else
	// stash on frames list.

	fr = (PolyFrame)frames.remove();

	if ( fr.currIndex >= 2 )
	  {
	    if( (fr.points[fr.currIndex] = connects( fr.firstPoint, fr.lastPoint))
		!= null ) {
	      fr.lines[fr.currIndex] = fr.lastLine;

	      if ( return_first )
		{
		  PolyFrame[] tmp = new PolyFrame[ 1 ];
		  tmp[0] = fr;
		  return tmp;
		}
	      else
		// stash the hit!
		hits.addElement( fr );
	    }
	  }
	
	// this frame is dead.
	if ( fr.currIndex == fr.points.length )
	  continue;
	
	for ( int x = 0; x < world.length; x++ ) {

	  WLine l = world[x];
	  
	  if ( fr.contains( l ) )
	    continue;
	  
	  boolean shouldExecuteFirst = true;
	  boolean shouldExecuteSecond = true;
	  
	  // If point is closer to other end of the line,
	  //     skip it;
	  // This is because it creates problems
	  //     for small lines.
	  
	  if( Geometry.distance( fr.prevPoint, l.getHead() ) <
	      Geometry.distance( fr.lastPoint, l.getHead() ) )
	    shouldExecuteFirst = false;
	  
	  if( Geometry.distance( fr.prevPoint, l.getTail() ) <
	      Geometry.distance( fr.lastPoint, l.getTail() ) )
	    shouldExecuteSecond = false;
	  
	  // If both points connect, pick the closer one.
	  if( shouldExecuteFirst && shouldExecuteSecond )
	    {
	      if( Geometry.distance( fr.lastPoint, l.getHead() )
		<= Geometry.distance( fr.lastPoint, l.getTail() ) )
		shouldExecuteSecond = false;
	      else
		shouldExecuteFirst = false;
	    }
	  
	  if( shouldExecuteFirst
	      && (fr.points[fr.currIndex] = connects( fr.lastPoint,
						l.getHead() ))
	      != null ) 
	    {
	      fr.lines[fr.currIndex] = fr.lastLine;
	      PolyFrame nfr = new PolyFrame( fr, l, true );
	      frames.append( nfr );
	    }
	  
	  if( shouldExecuteSecond
	      && (fr.points[fr.currIndex] = connects( fr.lastPoint,
						l.getTail() ))
	      != null ) 
	    {
	      fr.lines[fr.currIndex] = fr.lastLine;
	      PolyFrame nfr = new PolyFrame( fr, l, false );

	      frames.append( nfr );
	    }
	}
      } // end while

    PolyFrame[] ret = new PolyFrame[ hits.size() ];
    for ( int x = 0; x < ret.length; x++ )
      ret[x] = (PolyFrame) hits.elementAt( x );
    return ret;
  }



  public static PolyFrame[] findNextLine_shadow( WLine[] world,
					   int max_size,
					   boolean return_first,
					   WLine new_line )
  {
    Vector hits = new Vector();

    GPoint[] points = new GPoint[max_size];
    WLine[] lines = new WLine[max_size];

    Queue frames = new Queue();
    
    PolyFrame fr = new PolyFrame( 0,
				  points,
				  lines,
				  new_line.getHead(),
				  new_line.getHead(),
				  new_line,
				  new_line.getTail() );

    frames.append( fr );
    
    int maxIndex = points.length - 1;

    while( ! frames.isEmpty() )
      {
	// break down a frame, check each piece for a winner, else
	// stash on frames list.

	fr = (PolyFrame)frames.remove();

	if ( fr.currIndex >= 2 )
	  {
	    if( (fr.points[fr.currIndex] = connects( fr.firstPoint, fr.lastPoint))
		!= null ) {
	      fr.lines[fr.currIndex] = fr.lastLine;

	      if ( return_first )
		{
		  PolyFrame[] tmp = new PolyFrame[ 1 ];
		  tmp[0] = fr;
		  return tmp;
		}
	      else
		// stash the hit!
		hits.addElement( fr );
	    }
	  }
	
	// this frame is dead.
	if ( fr.currIndex == fr.points.length )
	  continue;
	
	for ( int x = 0; x < world.length; x++ ) {

	  WLine l = world[x];
	  
	  if ( fr.contains( l ) )
	    continue;
	  
	  boolean shouldExecuteFirst = true;
	  boolean shouldExecuteSecond = true;
	  
	  // If point is closer to other end of the line,
	  //     skip it;
	  // This is because it creates problems
	  //     for small lines.
	  
	  if( Geometry.distance( fr.prevPoint, l.getHead() ) <
	      Geometry.distance( fr.lastPoint, l.getHead() ) )
	    shouldExecuteFirst = false;
	  
	  if( Geometry.distance( fr.prevPoint, l.getTail() ) <
	      Geometry.distance( fr.lastPoint, l.getTail() ) )
	    shouldExecuteSecond = false;
	  
	  // If both points connect, pick the closer one.
	  if( shouldExecuteFirst && shouldExecuteSecond )
	    {
	      if( Geometry.distance( fr.lastPoint, l.getHead() )
		<= Geometry.distance( fr.lastPoint, l.getTail() ) )
		shouldExecuteSecond = false;
	      else
		shouldExecuteFirst = false;
	    }
	  
	  if( shouldExecuteFirst
	      && (fr.points[fr.currIndex] = connects( fr.lastPoint,
						l.getHead() ))
	      != null ) 
	    {
	      fr.lines[fr.currIndex] = fr.lastLine;
	      PolyFrame nfr = new PolyFrame( fr, l, true );
	      frames.append( nfr );
	    }
	  
	  if( shouldExecuteSecond
	      && (fr.points[fr.currIndex] = connects( fr.lastPoint,
						l.getTail() ))
	      != null ) 
	    {
	      fr.lines[fr.currIndex] = fr.lastLine;
	      PolyFrame nfr = new PolyFrame( fr, l, false );

	      frames.append( nfr );
	    }
	}

	// now make the shadow segments.
	
      } // end while

    PolyFrame[] ret = new PolyFrame[ hits.size() ];
    for ( int x = 0; x < ret.length; x++ )
      ret[x] = (PolyFrame) hits.elementAt( x );
    return ret;
  }


  private static GPoint connects( GPoint p1, GPoint p2 )
  {
    if( Geometry.distance( p1, p2 ) < RANGE )
      return( new GPoint( (p1.x + p2.x) / 2.0, (p1.y + p2.y) / 2.0 ) );

    return( null );
  }

  static boolean alreadyInPolygon( int currIndex,
				   WLine[] lines,
				   WLine lastLine,
				   WLine l )
  {
    if( l.equals( lastLine ) )
      return( true );

    for( int i = 0; i < currIndex; ++i ) {
      if( l.equals( lines[i] ) )
	return( true );
    }

    return( false );
  }

}



class PolyFrame {

  int currIndex;

  GPoint[] points;

  WLine[] lines;

  GPoint firstPoint;
  GPoint prevPoint;
  WLine lastLine;
  GPoint lastPoint;

  public PolyFrame( int curIndex, GPoint[] points, 
		    WLine[] lines, GPoint firstPoint, GPoint prevPoint, 
		    WLine lastLine, GPoint lastPoint )
  {
    this.currIndex =     currIndex;
    this.points =     points;
    this.lines =     lines;
    this.firstPoint =     firstPoint;
    this.prevPoint =     prevPoint;
    this.lastLine =     lastLine;
    this.lastPoint =     lastPoint;
  }

  public PolyFrame( PolyFrame from, WLine line, boolean head )
  {
    this.currIndex = from.currIndex + 1;
    this.points = (GPoint[])from.points.clone();
    this.lines = (WLine[])from.lines.clone();

    this.firstPoint = from.firstPoint;

    if ( head )
      {
	this.prevPoint = line.getHead();
	this.lastPoint = line.getTail();
      }
    else
      {
	this.prevPoint = line.getTail();
	this.lastPoint = line.getHead();
      }
    
    this.lastLine = line;
  }

  boolean contains( WLine l )
  {
    return PolygonParser.alreadyInPolygon( currIndex, lines, lastLine, l );
  }



}

/////////////////////////////////////////////////////////////////////////////

