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

// $Id: BasicResolver.java,v 1.23 2003/05/23 18:26:48 rebecca8 Exp $
// Time-stamp: <2000-07-17 14:45:26 moltmans>
package rec.sys;



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

public class BasicResolver extends Resolver 
{
  protected HashSet m_CurrentElects;
  protected HashSet m_JustElected;
  protected HashSet m_LastRoots;

  private OrderGraph m_BaseGraph;
  private OrderGraph m_WorkingGraph;
  
  public BasicResolver()
  {
    super();
    m_CurrentElects = new HashSet();
  }

  private Collection getAttached( Widget w, HashSet old_roots )
  {
    WidgetSet affectedRoots = new WidgetSet( w.connectedRoots() );
    m_LastRoots = new HashSet( affectedRoots );
    
    affectedRoots.addAll( old_roots );
    
    Iterator allconf_it = affectedRoots.iterator();
    HashSet all_conflicts = new WidgetSet();
    while ( allconf_it.hasNext() ) {
      Widget another_conflict = (Widget)allconf_it.next();
      all_conflicts.addAll( another_conflict.getAllChildrenAndMe() );
    }

    return all_conflicts;
  }
  
  /**
   * 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 Collection resolve( Surface s, Widget w, boolean retry, OrderGraph g,
			     Vector newWidgets)
  {
    HashSet old_roots = new HashSet();
    if ( retry ) {
      old_roots.addAll( m_LastRoots );
    }
    
    Collection all_conflicts = getAttached( w, old_roots );

    for(int i = 0; i < newWidgets.size(); i++){
	all_conflicts.addAll(getAttached ((Widget)newWidgets.get(i), 
					  new HashSet()));
    }
    
    Iterator allconf_it = all_conflicts.iterator();
    HashSet nonwidgets = new HashSet();
    while ( allconf_it.hasNext() ) {
      FamilyMember f = (FamilyMember)allconf_it.next();
      if ( !( f instanceof Widget ) ) {
	nonwidgets.add( f );
      }
    }
    all_conflicts.removeAll( nonwidgets );
    WidgetSet all_widget_conflicts = new WidgetSet( all_conflicts );

    m_BaseGraph = g.copy();
    
    Collection best_widgets = findBestRepresentatives( all_widget_conflicts );
    m_JustElected = new HashSet( best_widgets );
    
    // now impeach the widgets which are no longer elected, and
    // elect the new widgets that weren't there before.
    Iterator it = m_CurrentElects.iterator();
    HashSet impeached = new HashSet();
    while ( it.hasNext() ) {
      Widget q = (Widget)it.next();
      if ( all_widget_conflicts.contains( q ) && 
	   !best_widgets.contains( q ) ) {
	Console.writeln( "impeaching " + q );
	q.impeach();

	// and record for posterity
	s.addTransition( new ElectTransition( s, q ).getFlip() );
	
	// 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 );
      // and record for posterity      
      s.addTransition( new ElectTransition( s, q ) );
      m_CurrentElects.add( q );
    }

    return best_widgets;
  }


  /** find the representative for widget w
   *  @param w the squiggle just considered
   */
  public Collection findRepresentatives( Widget w )
  {
    Collection c = w.getAllChildrenAndMe();
    Collection reps = new HashSet();
    Iterator it = m_CurrentElects.iterator();
    while ( it.hasNext() ) {
      Widget w2 = (Widget)it.next();
      if ( c.contains( w2 ) ) {
	reps.add( w2 );
      }
    }
    return reps;
  }

  public Collection getLastElects()
  {
    return m_JustElected;
  }

  public Collection getLastRelatedElects( Widget w )
  {
    Collection ret = new HashSet();
    Collection conf = getAttached( w, new HashSet() );
    Iterator it = m_JustElected.iterator();
    while ( it.hasNext() ) {
      Widget next = (Widget)it.next();
      if ( conf.contains( next ) ) {
	ret.add( next );
      }
    }

    return ret;
      
  }

  // this now requires some graph manipulation
  private Collection findBestRepresentatives( WidgetSet hs ) 
  {
    boolean debug = false; //true;
    HashSet best_set = new HashSet();

    while ( hs.size() > 0 ) {

      m_WorkingGraph = m_BaseGraph.copy();
      
      m_WorkingGraph.collapseCycles();
      
      // now assign weights based on the sorted list
      java.util.List bucketed = m_WorkingGraph.bucket();

      // debug output, uncomment if you want to see it.  don't delete
      // it though, because it is useful.
      int bucket_number = 0;
      Iterator bucketed_it = bucketed.iterator();
      if( debug ) {
        DebugWindow.clear( "Choices" );
      }
      while ( bucketed_it.hasNext() ) {
	Collection c = (Collection)bucketed_it.next();
	Iterator c_it = c.iterator();
  	Console.writeln( "The widgets in bucket " + bucket_number + " are:" );
	if( debug ) {
	  DebugWindow.addLine( "Choices", "The Widgets in bucket " +
			       bucket_number + " are:" );
	}
	
	Console.indent();
	while ( c_it.hasNext() ) {
	  Widget print_wid = (Widget)c_it.next();
	  Console.writeln( print_wid.toString() + " : "
			   + print_wid.getStrength() );
	  if( debug ) {
	    DebugWindow.addLine( "Choices", print_wid.toString() + " : " +
				 print_wid.getStrength() );
	  }
	}
  	Console.outdent();
	if( debug ) {
	  DebugWindow.addLine( "Choices", "-----------------------" );
	}
	
	bucket_number++;
      }

      scoreWidgets( bucketed );

      FamilyMember best_remaining = getBestMember( hs );
      
      if ( best_remaining instanceof Widget ) {
	best_set.add( best_remaining );
	hs = certain( (Widget)best_remaining, hs );
      }

    }
         
    
    return best_set;
  }

  private void scoreWidgets( java.util.List bucketed )
  {
    // rank the best and the worst
    int max_relscore = Widget.getMaxStrength();
    Assert.check( !bucketed.isEmpty(),
		  "there are no widgets to reason on" );
    HashSet best = (HashSet)bucketed.remove( 0 );
    HashSet worst;
    if ( bucketed.size() >= 1 ) {
      worst = (HashSet)bucketed.remove( bucketed.size() - 1 );
    }
    else {
      worst = new HashSet();
    }
    
    Iterator best_it = best.iterator();
    while ( best_it.hasNext() ) {
      Widget best_one = (Widget)best_it.next();
      best_one.setRelStrength( max_relscore );
    }

    Iterator worst_it = worst.iterator();
    while ( worst_it.hasNext() ) {
      Widget worst_one = (Widget)worst_it.next();
      worst_one.setRelStrength( 0 );
    }

    // if there were two or fewer objects, break right here
    if ( bucketed.size() < 1 ) {
      return;
    }

    max_relscore -= 1;
    // figure out how many (if any) are going to need to overlap in score
    int num_extra = (bucketed.size() - 1) / max_relscore;
    int num_big = bucketed.size() - (max_relscore * num_extra);
    int num_small = max_relscore - num_big;

    int curr_score = 1;
    int counter = 0;
    ListIterator li = bucketed.listIterator( bucketed.size() );
    while ( li.hasPrevious() ) {
      HashSet to_score = (HashSet)li.previous();
      Iterator set_it = to_score.iterator();
      while ( set_it.hasNext() ) {
	Widget next_one = (Widget)set_it.next();
	next_one.setRelStrength( curr_score );
      }

      counter++;
      if ( counter % (num_extra + 1) == 0 ) {
	curr_score++;
      }
      if ( counter == num_big*(num_extra + 1)) {
	num_extra--;
      }
      if ( curr_score > max_relscore ) {
	break;
      }
    }
 
  }

  // makes w certain by removing it from the possiblities and the
  // rank graph
  private WidgetSet certain( Widget w, WidgetSet allWidgets )
  {
    
    // first remove us, and all our children from the set
    WidgetSet new_hs = new WidgetSet( allWidgets );

    // now remove all the stuff that we are needed to make up
    // that is, all of our conflicts
    Collection conf = w.allConflicts();
    new_hs.removeAll( conf );

    //m_BaseGraph.print();
    
    Iterator it = conf.iterator();
    while ( it.hasNext() ) {
      Widget temp = (Widget)it.next();
      Console.writeln( "removing " + temp );
      m_BaseGraph.removeNodeSimple( temp );
    }

    
    
    Console.writeln( "****** " + w + " is now certain" );

    return new_hs;
  }



  /* gets the strongest member of a set */
  private FamilyMember getBestMember( Collection c ) 
  {
    FamilyMember best;
    Iterator it = c.iterator();
    
    if ( !it.hasNext() ) {
      return null;
    }

    best = (FamilyMember)it.next();
    //Console.writeln( best + " has strength " + best.getStrength() );
    
    while ( it.hasNext() ) {
      FamilyMember current = (FamilyMember)it.next();
      
      //Console.writeln( current + " has strength " + current.getStrength() );
      if ( current.getStrength() > best.getStrength() ) {
	best = current;
      }
    }

    return best;
  }



}
