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

// $Id: BasicSlowResolver.java,v 1.5 2003/03/06 00:40:40 moltmans Exp $
// Time-stamp: <2000-03-11 18:59:36 moltmans>
package rec.sys;



import java.io.*;
import java.util.*;
import rec.util.*;

public abstract class BasicSlowResolver extends Resolver 
{
  public BasicSlowResolver()
  {
    super();
    m_CurrentElects = new HashSet();
  }

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

  /**
   * Called by Surface after recognition is done.  Finds a representative
   * widget for the squiggle just added and elects it (and if necesary
   * changes the representation of other squiggles).
   *
   * @param w   The last thing added to the Surface, the root Widget
   *     which caused recognition to begin again.
   */
  public void resolve( Surface s, Widget w )
  {
    // turn all widgets into strength tree widgets representing the
    // current state of the world
    m_BranchStrengths = new Hashtable();
    // maybe do this here, maybe not
    buildStrengthTree( w );

    // how about this: get all the things which are on the surface 
    // which the new widget interferes with and find the best representation
    // for them.  that way, at least we avoid another factorial in our
    // running time... yes, this has gotten ugly
    WidgetSet affectedRoots = new WidgetSet( w.connectedRoots() );
    
    Iterator allconf_it = affectedRoots.iterator();
    WidgetSet all_conflicts = new WidgetSet();
    while ( allconf_it.hasNext() ) {
      Widget another_conflict = (Widget)allconf_it.next();
      all_conflicts.addAll( another_conflict.getAllChildrenAndMe() );
    }

    Iterator affected_it = affectedRoots.iterator();
    Console.writeln( "affected roots: " );
    while ( affected_it.hasNext() ) {
      Console.writeln( (Widget)affected_it.next() + "" );
    }

    Collection best_widgets = findBestRepresentatives( affectedRoots, 
						       new WidgetSet() );

    // now impeach the widgets which are no longer elected, and
    // elect the widgets which are no longer
    Iterator it = m_CurrentElects.iterator();
    HashSet impeached = new HashSet();
    while ( it.hasNext() ) {
      Widget q = (Widget)it.next();
      if ( all_conflicts.contains( q ) && !best_widgets.contains( q ) ) {
	q.impeach();
	// we want to remove these from the current elects list, but 
	// the iterator gets unhappy if we do it here.
	impeached.add( q );
      }
    }
    m_CurrentElects.removeAll( impeached );

    it = best_widgets.iterator();
    while ( it.hasNext() ) {
      Widget q = (Widget)it.next();
      q.elect( s );
      m_CurrentElects.add( q );
    }

  }

  private double buildStrengthTree( FamilyMember f )
  {
    if ( f instanceof Widget ) {
      return buildStrengthTree( (Widget)f );
    }
    else {
      return buildStrengthTree( (WidgetSet)f );
    }
  }

  /* returns the strongest interpretation for each widget, so that
   * the function can be used recursivly.  Only call this function once, 
   * for efficiency reasons, however.
   */
  private double buildStrengthTree( Widget w )
  {
    if ( !w.hasChildren() ) {
      m_BranchStrengths.put( w, new Double( w.getStrength() ) );
      return w.getStrength();
    }
    else {
      Iterator it = w.getChildrenIterator();
      double best_strength = -1;

      while ( it.hasNext() ) {
	FamilyMember f = (FamilyMember)it.next();
	double next_strength;
	
	if ( f instanceof Widget ) {
	  next_strength = buildStrengthTree( (Widget)f );
	}
	else { 
	  next_strength = buildStrengthTree( (WidgetSet)f );
	}
	if ( next_strength > best_strength ) {
	  best_strength = next_strength;
	}
      }
      
      // now check strength against widget's own strength
      if ( w.getStrength() > best_strength ) {
	best_strength = w.getStrength();
      }
      
      m_BranchStrengths.put( w, new Double( best_strength ) );
      return best_strength;
    }
  }
  
  /* this one is much more complicated, since we have to factor in
   * the combinations of widgets that could actually occur at once
   * i.e. one squiqqle --> 4 lines --> square.  but in order to use
   * the strength of the square, all four lines must be part of it
   */
  private double buildStrengthTree( WidgetSet ws )
  {
    
    Collection c = findBestRepresentatives( ws, new WidgetSet() );

    Assert.check( c.size() != 0 );

    double total = 0;
    Iterator it = c.iterator();
    while( it.hasNext() ) {
      FamilyMember bc = (FamilyMember)it.next();
      // i think these should all just be widgets
      Assert.check( bc instanceof Widget, 
		    "Best Children should all be Widgets" );
      Assert.check( m_BranchStrengths.containsKey( bc ) );
      
      total += ((Double)m_BranchStrengths.get( bc )).doubleValue();
    }
    
    double best_strength = total / c.size();
    m_BranchStrengths.put( ws, new Double( best_strength ) );
    
    return ( best_strength );
  }


  private Collection findBestRepresentatives( FamilyMember f, 
					      WidgetSet forbidden )
  {
    if ( f instanceof Widget ) {
      return findBestRepresentatives( (Widget)f, forbidden );
    }
    else {
      return findBestRepresentatives( (WidgetSet)f, forbidden );
    }
  }
  
  private Collection findBestRepresentatives( WidgetSet ws, 
					      WidgetSet forbidden )
  {
    Console.writeln( "Finding best representatives for WidgetSet" );
    
    Iterator child_it = ws.iterator();

    // any widget which could be more than one thing could be a 
    // problem because it could strand other widgets
    HashSet considered = new HashSet();

    WidgetSet best_set = new WidgetSet();
    double best_score = -1;
    double current_score;
    
    while ( child_it.hasNext() ) {
      WidgetSet current_set = new WidgetSet();
      Widget w = (Widget)child_it.next();

      // this part is unrestricted, use any combination of widgets
      Collection best_widgets = findBestRepresentatives( w, forbidden );
      
      Iterator it = best_widgets.iterator();
      
      // an efficiency hack -- this will catch many of the cases, i suspect
      if ( best_widgets.size() == 1 && 
	   considered.contains( best_widgets.iterator().next() ) ) {
	continue;
      } 
      
      else {
	if ( best_widgets.size() == 1 ) {
	  considered.add( best_widgets.iterator().next() );
	}

	WidgetSet remaining = new WidgetSet( ws );
	if ( forbidden == null ) {
	  forbidden = new WidgetSet();
	}	
	WidgetSet temp_forbidden = new WidgetSet( forbidden );
	remaining.remove( w );
	
	while ( it.hasNext() ) {
	  Object o = it.next();
	  
	  // quick debug check
	  Assert.check( o instanceof Widget );
	  
	  Widget good_child = (Widget)o;
	  if ( !good_child.equals( w ) ) {
	    Collection anc = good_child.getAncestors();
	    
	    WidgetSet printer = new WidgetSet( anc );
	    Console.writeln( "Ancestors of selected child are:" );
	    printer.printAll();
	    
	    temp_forbidden.addAll( anc );
	    remaining.removeAll( anc );
	  }
	  else {
	    temp_forbidden.add( good_child );
	  }
	  
	  current_set.add( good_child );
	}
	
	Console.writeln( "Ancestors remaining are:" );
	remaining.printAll();
	current_set.addAll( findBestRepresentatives( remaining, temp_forbidden ) );

	// calculate the score
	current_score = current_set.getStrength();
	if ( current_score > best_score ) {
	  best_set = new WidgetSet( current_set );
	}
      }
    }
    
    return best_set;
  }

  private Collection findBestRepresentatives( Widget w, WidgetSet forbidden )
  {
    Console.writeln( "Finding Best Representatives for Widget " + w );
    /*    Console.indent();
    Console.writeln( "the following widgets are forbidden" );
    Iterator display_it = forbidden.iterator();
    while ( display_it.hasNext() ) {
      Console.writeln( "" + (Widget)display_it.next() );
    }
    Console.outdent();
    */

    FamilyMember f = findBestChild( w, forbidden );
    Collection allBest = new WidgetSet();
    
    if ( f == null ) {
      allBest.add( w );
      return allBest;
    }

    // i think this should be true.
    Assert.check( m_BranchStrengths.containsKey( f ), 
		  "tree should contain " + f );
    
    if (((Double)m_BranchStrengths.get( f )).doubleValue() < 
	  w.getStrength()) {
      allBest.add( w );
    }
    else {
      allBest.addAll( findBestRepresentatives( f, forbidden ) );
    }
    
    return allBest;
  }

  /* null if widget has no children */
  /* best child which is not in forbidden */
  private FamilyMember findBestChild( Widget w, WidgetSet forbidden )
  {
    Assert.check( !forbidden.contains( w ), w + " is already forbidden, cannot find its best child" );

    Console.writeln( "Finding best child for Widget " + w );
    Console.indent();
    Console.writeln( "the following widgets are forbidden" );
    Iterator display_it = forbidden.iterator();
    while ( display_it.hasNext() ) {
      Console.writeln( "" + (Widget)display_it.next() );
    }
    Console.outdent();
    w.printFamily();

    if ( !m_BranchStrengths.containsKey( w ) ) {
      buildStrengthTree( w );
    }
	  
    if ( !w.hasChildren() ) {
      Console.writeln( w + " has no children" );
      return null;
    }

    Iterator it = w.getChildrenIterator();

    // for consistency of code
    if ( forbidden == null ) {
      forbidden = new WidgetSet();
    }

    boolean allowed = true;

    FamilyMember best = (FamilyMember)it.next();
    // if we haven't called build tree on the children of this widget, 
    // we should call that first
    if ( !m_BranchStrengths.containsKey( best ) ) {
      buildStrengthTree( best );
    }
    Double best_val = (Double)m_BranchStrengths.get( best );

    // if it's a widget set, we are OK, because it MUST just come
    // from the widget above us, and no other ancestors
    // if it's a Widget we might have problems
    if ( best instanceof Widget ) {
      Collection anc = ((Widget)best).getAncestors();
      Iterator it2 = anc.iterator();
      while ( it2.hasNext() && allowed ) {
	Widget w2 = (Widget)it2.next();
	if ( forbidden.contains( w2 ) ) {
	  allowed = false;
	}
      }
    }

    while ( it.hasNext() ) {
      FamilyMember f = (FamilyMember)it.next();
      if ( !m_BranchStrengths.containsKey( f ) ) {
	buildStrengthTree( f );
      }
      Double new_val = (Double)m_BranchStrengths.get( f );
      
      boolean curr_allowed = true;

      if ( best instanceof Widget ) {
	Collection anc = ((Widget)best).getAncestors();
	Iterator it3 = anc.iterator();
	while ( it3.hasNext() && curr_allowed ) {
	  Widget w3 = (Widget)it3.next();
	  if ( forbidden.contains( w3 ) ) {
	    curr_allowed = false;
	  }
	}
      }
      
      if ( curr_allowed ) {

	// if the new value is greater than the old
	if ( ( new_val.compareTo( best_val ) > 0 ) ||
	     !allowed ) {
	  best_val = new_val;
	  best = f;
	  allowed = true;
	}
      }
    }

    if ( !allowed ) {
      return null;
    }

    return best;
  }

  public Collection findRepresentatives( Widget w )
  {
    Assert.error( "function not implemented yet" );
    return null;
  }
  
  ///////////////////////////////////////////////////////////////////////////

  Hashtable m_BranchStrengths;        // map widgets to branch strengths
  HashSet m_CurrentElects;

}

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