m1.chocobarlite/src/jeu/Strategy.java

package jeu;

import java.util.*;
import java.io.*;
import java.text.*;

import exception.*;
import graph.GenericGraph;

public class Strategy {
  private int[] nextConfigs;
  private int size;

  /**
   * Constructeur par defaut
   **/
  public Strategy(){
    this.nextConfigs=null;
    this.size=0;
  }

  /**
   * Constructeur a partir d'un tableau de int decrivant une strategie
   * on ne verifie pas que c'est une strategie valide
   **/
	public Strategy(int[] arrayEntry){
    this.size=arrayEntry.length;
    this.nextConfigs=arrayEntry;
  }
  
  /**
   * Fonction qui construit une strategie de maniere aleatoire
   **/
  public void constructRandomStrategy(GenericGraph g){
    int nbSommets=g.getCardV();
    this.nextConfigs=new int[nbSommets]; 
    int configChoisi;
    Object[] choix;
    Collection trad;
    
    this.size=nbSommets;
    for (int i=0; i<nbSommets; i++){
      try {
	trad=g.getAdjacent(i);
	if (trad==null){
		this.nextConfigs[i]=-1;
		continue;
	}
	choix=trad.toArray();
      } catch (Exception e){
	e.printStackTrace();
	return;
      }
      if (choix.length != 0){
	configChoisi=((Integer)choix[(new Double(Math.rint(Math.random() * (choix.length - 1)))).intValue()]).intValue();
	this.nextConfigs[i]=configChoisi;
      } else {
	this.nextConfigs[i]=-1;
      }
    }
  }

  /**
   * Fonction qui construit une strategie gagnante
   **/
  public void constructWinningStrategy(GenericGraph g){
    int nbSommets=g.getCardV();
    int configChoisi;
    int start,finish;
    Vector perdant, gagnant;
    LinkedList aTraiter;
    Collection incident;
    
    this.nextConfigs=new int[nbSommets]; 
    this.size=nbSommets;
    start=g.getInitialState();
    finish=g.getFinalState();
    
    //initialisation
    aTraiter=new LinkedList();
    for (int i=0; i<nbSommets; i++){
      if (i != finish){
	aTraiter.add(new Integer(i));
      }
    }
    perdant=new Vector(nbSommets/2);
    gagnant=new Vector(nbSommets/2);
    gagnant.add(new Integer(finish));
    this.nextConfigs[finish]=-1;
    
    //on finira quand on aura defini la strategie de la position initiale
    while (this.nextConfigs[start]==0){
      //recherche des sommets perdants
      Integer sommet=((Integer)aTraiter.removeFirst());
      int sommetInt=sommet.intValue();
      configChoisi=g.withOnlyEdges(sommetInt, gagnant);
      if (configChoisi!=-1){
	// sommet perdant
	perdant.add(sommet);
	this.nextConfigs[sommetInt]=configChoisi;
	// tout sommet pointant sur ce sommet est gagnant
	try {
	  incident=g.getIncident(sommetInt);
	} catch (Exception e){
	  e.printStackTrace();
	  return;
	}
	gagnant.addAll(incident); //rajout des sommets gagnants
	ListIterator lr=aTraiter.listIterator(); //enlever ces sommets gagnants de la liste aTraiter
	while (lr.hasNext()){
	  Integer aEnlever=((Integer)lr.next());
	  if (incident.contains(aEnlever)){
	    lr.remove();
	  }
	}
	Iterator r=incident.iterator(); //definition des coups gagnant
	while (r.hasNext()){
	  this.nextConfigs[((Integer)r.next()).intValue()]=sommetInt;
	}
      } else {
	// sommet non perdant, on le remet dans la liste non traites
	aTraiter.addLast(sommet);
      }
    }
  }

  /**
   * Fonction qui construit a partir d'un fichier de cette forme : 
   * la premiere ligne du fichier contient le nombre des configs du jeu
   * Les lignes suivantes sont de cette forme : la ieme ligne contient 
   * l'indice de coup a jouer si on arrive a la config (i-1) et on doit jouer.
   **/
  public void constructFromFile(String filename)
		throws ParseException, IOException, FileNotFoundException, 
					 OutOfRangeVerticeException {
	
    int verticeNb;
    FileReader fi=new FileReader(filename);
    StreamTokenizer si=new StreamTokenizer(fi);
    si.eolIsSignificant(false);
    si.lowerCaseMode(false);
    si.parseNumbers();

    /* Parse number of vertices */
    si.nextToken();				
    if (si.ttype==StreamTokenizer.TT_NUMBER){
      verticeNb=(int)si.nval;
      this.size=verticeNb;
      this.nextConfigs=new int[verticeNb];
    } else {
      throw new ParseException("Bad graph size",0);
    }
    
    /* Parse the strategy */
    for (int i=0; i<verticeNb;i++){
      si.nextToken();
      if (si.ttype==StreamTokenizer.TT_NUMBER){
	this.nextConfigs[i]=(int)si.nval;
	if ((this.nextConfigs[i] < -1)||(this.nextConfigs[i] >= this.size))
		throw new OutOfRangeVerticeException();
      } else {
	throw new ParseException("Bad strategy format",0);
      }
    }
  }

  /**
   * Fonction qui renvoie le hash contenant tous les coups a jouer 
   * a partir d'un etat quelconque
   **/
  public int[] getSteps(){
    return this.nextConfigs;
  }

  /**
   * Fonction qui renvoie le hash contenant tous les coups a jouer 
   * a partir d'un etat quelconque
   **/
  public int getNextConfig(int move){
    return this.nextConfigs[move];
  }
  
  /**
   * Fonction qui verifie si cette strategie partant de start est 
   * une strategie gagnante
   **/
  public boolean isWinning(GenericGraph g, int start, int finish){
    int courant, move;
    Collection adversPoss;
    Integer traiter; 

    LinkedList advers=new LinkedList(); //coups de l'adversaire a verifier
    Vector verif=new Vector(g.getCardV()); //tous les coups deja verifies
					
    advers.addFirst(new Integer(start));
    try{
      while (true){
	traiter=(Integer)advers.removeFirst(); //un coup de l'adversaire
	courant=traiter.intValue();
	verif.add(traiter);
	if (courant==finish){
	  continue;
	} 
	verif.add(traiter);
	move=this.nextConfigs[courant]; //notre coup contre l'adversaire
	if (move==finish){ //on vient de manger le carre empoisonne
	  return false;
	} else { //on doit verifier tous les coups possibles de l'adversaire
	  try {
	    Iterator y;
	    adversPoss=g.getAdjacent(move); //tous les coups possibles de l'adversaire a partir d'une certaine config
	    y=adversPoss.iterator();
	    while (y.hasNext()){
	      Integer x=((Integer)y.next());
	      if (!advers.contains(x)){
		advers.add(x);
	      }
	    }
	  } catch (Exception e){
	    e.printStackTrace();
	  }
	}
      }
    } catch (NoSuchElementException e){
      //on a deja vide la liste des coups (de l'adversaire) a verifier
    }
    return true;
  }
	
  /**
   * Fonction qui verifie si cette strategie est une strategie gagnante
   **/
  public boolean isWinning(GenericGraph g){
    int start, finish;
    
    start=g.getInitialState();
    finish=g.getFinalState();
    return isWinning(g, start, finish);
  }
  
  /**
   * Fonction qui represente cette strategie sous forme de String 
   * de format banal : i<>me ligne contient l'indice de coup a 
   * jouer et on a la config (i-1)
   **/
  public String toSimpleString(){
    int dest;
    StringBuffer res=new StringBuffer(4 *this.size);
   
    res.append(this.size+"\n");
    for (int i=0; i<this.size; i++){
      dest=nextConfigs[i];
      res.append(dest+"\n");
    }
    return res.toString();
  }
  
  /**
   * Fonction qui represente cette strategie sous forme de String
   **/
  public String toString(){
    int dest;
    StringBuffer res=new StringBuffer(16 * this.size);
   
    for (int i=0; i<this.size; i++){
      dest=nextConfigs[i];
      res.append(""+i);
      if (dest != -1) {
	res.append(" -> "+dest+"\n");
      } else {
	res.append(" -> fini\n");
      }
    }
    return res.toString();
  }
  
  /**
   * Fonction qui affiche cette strategie sur l'ecran
   **/
  public void display(){
    System.out.println(this.toString());
  }
}