// ** This file was generated with DemFGen (vers:4/15/2011)

package hsr.avatar;

import edu.neu.ccs.demeterf.lib.*;
import edu.neu.ccs.demeterf.lib.*;
import scg.*;
import scg.protocol.*;
import hsr.*;
import java.util.Random;
import java.lang.reflect.Method;





/** Representation of HSRAvatar */
public class HSRAvatar implements AvatarI{

    /** Construct a(n) HSRAvatar Instance */
    public HSRAvatar(){
    }
    /** Is the given object Equal to this HSRAvatar? */
    public boolean equals(Object o){
        if(!(o instanceof HSRAvatar))return false;
        if(o == this)return true;
        HSRAvatar oo = (HSRAvatar)o;
        return true;
    }
    /** Parse an instance of HSRAvatar from the given String */
    public static HSRAvatar parse(String inpt) throws hsr.avatar.ParseException{
        return new hsr.avatar.TheParser(new java.io.StringReader(inpt)).parse_HSRAvatar();
    }
    /** Parse an instance of HSRAvatar from the given Stream */
    public static HSRAvatar parse(java.io.InputStream inpt) throws hsr.avatar.ParseException{
        return new hsr.avatar.TheParser(inpt).parse_HSRAvatar();
    }
    /** Parse an instance of HSRAvatar from the given Reader */
    public static HSRAvatar parse(java.io.Reader inpt) throws hsr.avatar.ParseException{
        return new hsr.avatar.TheParser(inpt).parse_HSRAvatar();
    }


	private Config config;
	private ModifiedPascalsTriangle mpt;
	
	/* Constructor to be called during registration where you supply config*/
	public HSRAvatar(Config cfg){
		config = cfg;
		mpt = new ModifiedPascalsTriangle();
	}
	
	/**proposing random unique claims which are not in the forbidden list**/
	public List<Claim> propose(List<Claim> forbiddenClaims){
		List<Claim> claims = List.create();
		Random rand = new Random();
		SCGConfig scg_cfg = config.getScgCfg();
		HSRConfig hsr_cfg = (HSRConfig)config.getDomainConfig();
		
		int maxProposals = scg_cfg.getMaxProposals() -1;

		for(int i =0; i< maxProposals;i++){
		    int n;
		    int k;
		
      		do {
      			n = rand.nextInt(hsr_cfg.getMaxN()) + 1;
      			k = rand.nextInt(hsr_cfg.getMaxN()) + 1;
      		} while (claimListContains(forbiddenClaims, n, k) || claimListContains(claims, n, k));
      		
      		HSRInstance instance = new HSRInstance(n, k);

      		HSRSolution solution = solve(instance);
		    HSRInstanceSet instanceSet = new HSRInstanceSet(instance);

			Claim claim = new Claim(
			    instanceSet, 
			    ForAllExistsMin.getInstance(), 
			    instance.quality(solution), 
			    1
			);

			claims = claims.append(claim);
		}

		return claims;
	}
	
    /**
     * oppose claims bsed on what we calculate the solution to be
     */
	public List<OpposeAction> oppose(List<Claim> claimsToBeOpposed){
		return claimsToBeOpposed.map(new List.Map<Claim, OpposeAction>() {
			public OpposeAction map(Claim claim){
			    SCGConfig scg_cfg = config.getScgCfg();
			     
			    HSRInstance instance = ((HSRInstanceSet)claim.getInstanceSet()).getSingleton();


				HSRSolution solution = solve(instance);
		
    			double quality = instance.quality(solution);
    			
    			if (quality < claim.getQuality() && claim.getQuality() - quality >= scg_cfg.getMinStrengthening()) {
    				return new Strengthening(quality);
    			} else if (quality > claim.getQuality()) {
    				return new Refuting();
    			} else {
    				return new Agreement();
    			}
            }
		});
	}
	
	/** providing instance - in HSR this is trivial as the instanceSet is singleton**/
	public InstanceI provide(Claim claimToBeProvided){
		HSRInstanceSet hsrInstanceSet = (HSRInstanceSet) claimToBeProvided.getInstanceSet();
		HSRInstance hsrInstance = new HSRInstance(hsrInstanceSet.getSingleton().getN(), hsrInstanceSet.getSingleton().getK());
		return hsrInstance;
	}
	
    /**
     * recursively generate a solution to the given request
     */
	public SolutionI solve(SolveRequest solveRequest){
		HSRInstance hsrInstance = (HSRInstance)solveRequest.getInstance();
		HSRSolution solution = solve(hsrInstance);

		return solution;
	}
	
	/**
	 * Given an HSRInstance, create the best solution for it.
	 * 
	 * @param hsrInstance The instance to solve.
	 * 
	 * @return A solution for the given instance.
	 */
	private HSRSolution solve(HSRInstance hsrInstance) {
		int n = hsrInstance.getN();
        // cap k at log(n)
		int k = (int)Math.min(hsrInstance.getK(), Math.ceil(Math.log(n)/Math.log(2)));
		
		int possibleN = 0;
		int q = k - 1;
		
		// walk the modified pascal's triangle to find out the least
		// number of questions we can ask to solve this problem.
		while(possibleN < n) {
			q++;
			possibleN = mpt.getEntry(q, k);
		}
		
		// once we know the number of questions to ask, we can recursively
		// generate a solution
		HSRSolution solution = 
			generateHSRSolution(q, k, new MutableInteger(0), n - 1);
		
		return solution;
	}
	
	/**
	 * Generate a solution to the HSR problem.
	 * 
	 * @param q The number of questions to ask
	 * @param k The number of jars we can break
	 * @param highestSafestRung The current known highest safest rung 
	 * (zero indexed)
	 * @param maxRung The maximum number of rungs we're dealing with 
	 * (zero indexed)
	 * @return A solution to the HSR problem.
	 */
	private HSRSolution generateHSRSolution(
		int q, 
		int k, 
		MutableInteger highestSafestRung,
		int maxRung
	) {
		// If we're at the max rung, we're out of jars, or we're out of
		// questions, return the current highest safest rung.
		if (highestSafestRung.value == maxRung || k == 0 || q == 0) {
			return new Simple(highestSafestRung.value++);
		} else {
			// otherwise recursively generate the solution tree for if the
			// jar breaks
			HSRSolution yes = 
				generateHSRSolution(q - 1, k - 1, highestSafestRung, maxRung);
			
			// Now we know what our question should be.
			int question = highestSafestRung.value;
			
			// If our question is out of bounds, we can just return the yes tree
			if (question > maxRung) {
				return yes;
			}
			
			// Otherwise, generate the tree for if the jar didn't break
			HSRSolution no = 
				generateHSRSolution(q - 1, k, highestSafestRung, maxRung);
			
			// combine all our results into a new solution
			return new Compound(
				question, yes, no
			);
		}
	}

	
	/**
	 * Does this list of claims contain a claim with the given n and k
	 * 
	 * @param claims The list of claims to check
	 * @param n The number of rungs in the ladder
	 * @param k The number of jars we have to break
	 * @return True if the list of claims contains a claim with the given
	 * n and k.  False otherwise.
	 */
	private boolean claimListContains(List<Claim> claims, int n, int k) {
		for (Claim claim : claims) {
			if (((HSRInstanceSet)claim.getInstanceSet()).getSingleton().getN() == n && 
				((HSRInstanceSet)claim.getInstanceSet()).getSingleton().getK() == k) 
			{
				return true;
			}
		}
		
		return false;
	}
	
	/**
	 * A mutable integer used to generate the solution trees.
	 */
	public static class MutableInteger {
		public int value;
		
		public MutableInteger(int value) {
			this.value = value;
		}
	}
}