import java.util.*;
/**
 * This class defines what a jump is and provides methods for obtaining jumps.
 * A jump is a LinkedList of Integers.  The first element in the list is
 * the starting position of the piece, the other elements are the positions on
 * the board where the piece lands after jumping over an opponent's piece.
 */
public class Jump{

    /**
     * Given a CheckerBoard and a player, returns a LinkedList containing
     * all jumps that the player can make.
     * Note that player must be 'p','P', 'o', or 'O'.
     */

    public static LinkedList GetJumps(CheckerBoard b, char player){
	LinkedList jmplist = new LinkedList();
	LinkedList tmp = new LinkedList();
	int i;
	
	switch(player){
	case 'p':case 'P':
	    for(i=0;i<32;i++){
		if(b.Piece(i)=='p'||b.Piece(i)=='P'){
		    tmp = GetJumps(b,i);
		    if(tmp!=null){
		    jmplist.addAll(GetJumps(b,i));
		    }
		    // else{System.out.println("Bad");}
		}
	    }
	    break;
	case 'o': case 'O':
	    for(i=0;i<32;i++){
		if(b.Piece(i)=='o'||b.Piece(i)=='O'){
		    tmp = GetJumps(b,i);
		    if(tmp!=null){
		    jmplist.addAll(GetJumps(b,i));
		    }
		}
	    }
		break;
	default:
	    break;
	}

	return jmplist;

    }

    /**
     * Given a CheckerBoard and a position on the board, returns a LinkedList
     * all possible jumps the piece at the position can make.
     */

    public  static LinkedList GetJumps(CheckerBoard b, int p){
	/* returns a linked list of all jumps for position p */

	LinkedList l = new LinkedList();
	Integer x = new Integer(p);
	int i,j,k;
	LinkedList tmp = new LinkedList();
	LinkedList tmp1 = new LinkedList();
	LinkedList tmplist = new LinkedList();
	tmp1.add(x);

	l.add(tmp1); // now have the start on the list
	
	//	System.out.println("GetJumps b,p");
	//	if(MoreJumps(b,l)){System.out.println("Nice");}
	//else{System.out.println("Bad");}
	while(MoreJumps(b,l)){
	    // System.out.println("About to expand");
	    tmplist = new LinkedList();
	    tmplist=Expand(b, l);
	    //  System.out.println("Size after expansions is " + tmplist.size());
	    //    System.out.println("GetJumps: size of jumps is " + ((LinkedList)tmplist.getFirst()).size());
	    l= new LinkedList();
	    l= (LinkedList)tmplist.clone();
       
	   
	}

	/* now need to process the list to get rid of nonexpanded jumps */
	//	System.out.println("Size of list is " + l.size());
	for(i=0;i<l.size();i++){
	    if(((LinkedList)l.get(i)).size()>1){
		tmp.add(l.get(i));
	    }
	}
	if(tmp.size()<1){
	    return null;}
	else{return tmp;}

    }

    
    private static LinkedList Expand(CheckerBoard b, LinkedList l){
	int i,position;
	CheckerBoard newb;
	LinkedList jmp = new LinkedList();
	LinkedList returnlst = new LinkedList();
	LinkedList newjump = new LinkedList();
	ArrayList nbrs = new ArrayList();
	ArrayList jmps = new ArrayList();
	int j,k,x,y;

	//System.out.println("Expand");
	i=0;
	//System.out.println(l.size());
	while(i<l.size()){
	    jmp = new LinkedList();
	    jmp = (LinkedList)l.get(i);
	    
	    // System.out.println("Expand:Size of jump is " + jmp.size());
	    position = ((Integer)jmp.get(jmp.size()-1)).intValue(); /*last place */
	    // System.out.println("Expand position: " + position);
	    nbrs = b.board[position].GetNeighbours();
	    jmps = b.board[position].GetJmps();
	    newb = MakeJump(b,jmp);
	    if(!CanJump(newb,position)){
		//System.out.println("Must be here ");
		returnlst.add(jmp);
	    } // end if
	       else{
		   if(WasKinged(newb,b,jmp)){
		       //   System.out.println("Here");
		        returnlst.add(jmp);
		   }
		      else{
			  //  System.out.println("Confused!");
		   /* I can jump so must figure out where */
		  
			  for(k=0;k<jmps.size();k++){
			      y = ((Integer)jmps.get(k)).intValue();
			   //  System.out.println("x and y are " + position+ " " +y);
			      if(JumpYes(newb,position,y)){
			       // System.out.println("Jumpyes!!");
				  newjump = new LinkedList();
				  newjump = NewJump(jmp,y);
			      	  returnlst.add(newjump);
			      } //end if
			  } // end for
			   
		      } // end inside else
		      } // end else

	
	    i=i+1;
	    // System.out.println(i);
	}
	//System.out.println(((LinkedList)returnlst.getLast()).size());
	return returnlst;
	   
    }


    private static boolean WasKinged(CheckerBoard newb, CheckerBoard b, LinkedList j){
	boolean kinged = false;
	int start;
	int pos = ((Integer)j.getLast()).intValue();
	//	System.out.println("What the ??");
	start = ((Integer)j.getFirst()).intValue();
	
	char newpiece = newb.Piece(pos);
	char oldpiece = b.Piece(start);

	
	if(newpiece != oldpiece){
	    //    System.out.println("True");
	    kinged = true;}
	//	b.PrintBoard();
	//	newb.PrintBoard();
	return kinged;
    }
    public static boolean JumpYes(CheckerBoard b, int start, int land){
	/* Is it possible to jump from start to land? */
	char piece;
	char landing_piece,over_piece;
	int over;
	boolean can_jmp = false;


	piece = b.Piece(start);
	//	System.out.println("Piece is " +  piece);
	landing_piece = b.Piece(land);
	over = GetOver(b,start,land);
	if(over == -1){
	    over_piece = 'e';}
	    else{
		over_piece = b.Piece(over);
	    }

	if (landing_piece !='e'){return false;}

	switch(piece){
	case 'P':
	    if(over_piece =='o' || over_piece=='O'){
		can_jmp=true;
	    }
	    break;
	case 'p':
	    if(((over_piece =='o') ||( over_piece =='O')) &&
	       (start<over)){
		can_jmp=true;
	    }
	    break;
    	case'O':
		if(over_piece=='p'||over_piece=='P'){
		can_jmp=true;
	    }
	    break;
	case 'o':
	    if(( (over_piece =='p')||(over_piece=='P')) 
		&& (over !=-1) &&( over<start)){
	    can_jmp=true;
	}
	break;
    default:
	break;

	}
	
	return can_jmp;

    }

    private static LinkedList NewJump(LinkedList l, int x){
	Integer z = new Integer(x);
	LinkedList newlist = new LinkedList();
	int i;

	for(i=0;i<l.size();i++){
	    newlist.add(l.get(i));
	}
	newlist.add(z);
	//System.out.println("NewJump size " + newlist.size());
	return newlist;
    }
	       

    private static boolean MoreJumps(CheckerBoard b,LinkedList l){
	/* process list and see if  possible to jump more! */
	int size,i,land;
	LinkedList jmp;
	boolean expand = false;
	CheckerBoard newb;
	int z =0;
	i=0;
	size = l.size();

	while(i<size&&!expand){
	   
	    jmp = new LinkedList();
	    jmp = (LinkedList)l.get(i);
	   
	    newb = MakeJump(b,jmp);
	   
	    //   newb.PrintBoard();
	    land = ((Integer)jmp.getLast()).intValue();
	    /* need another case to stop jumping once kinged */
		    
	    if(CanJump(newb,land)&& !WasKinged(newb, b, jmp)){
		expand = true;
	    }
		
	    i++;
	}

	return expand;

    }

  
    /**
     * Given a CheckerBoard and a position on the board, returns true
     * if the piece at position pos can make a jump, false otherwise.
     */

    public static boolean CanJump(CheckerBoard b, int pos){
	/* see if possible to jump from a given position */
	char piece;
	ArrayList nbrs = new ArrayList();
	ArrayList jmps = new ArrayList();
	ArrayList jmp_nbrs = new ArrayList();
	boolean can_jmp = false;
	int i,j,over,land;

	nbrs = b.board[pos].GetNeighbours();
	jmps = b.board[pos].GetJmps();

	piece = b.Piece(pos);
	//	System.out.println("Piece is "+piece);
	switch(piece){
	case 'p':
	    for(i=0;i<nbrs.size();i++){
		over = ((Integer)nbrs.get(i)).intValue();
		//System.out.println("OVer is " + over);
		if(over>pos &&(b.Piece(over)=='o'||b.Piece(over)=='O')){
		    //  System.out.println("Maybe jump!!");
		    /* maybe can jump */
		    /* must now check landing position */
		    for(j=0;j<jmps.size();j++){
			land = ((Integer)jmps.get(j)).intValue();
			//System.out.println("Landing is " + land);
			//System.out.println("Computed Over is " + GetOver(b,pos,land));
			if (GetOver(b,pos,land)==over && b.Piece(land)=='e'){
			    
			    can_jmp=true;
			}
		    }
		}
	    }
	    break;
	case 'o':
	      for(i=0;i<nbrs.size();i++){
		over = ((Integer)nbrs.get(i)).intValue();
		if(over<pos &&(b.Piece(over)=='p'||b.Piece(over)=='P')){
		    /* maybe can jump */
		    /* must now check landing position */
		    for(j=0;j<jmps.size();j++){
			land = ((Integer)jmps.get(j)).intValue();
			if (GetOver(b,pos,land)==over && b.Piece(land)=='e'){
			    can_jmp=true;
			}
		    }
		}
	    }
	    break;
	case 'P':
	     for(i=0;i<nbrs.size();i++){
		over = ((Integer)nbrs.get(i)).intValue();
		if(b.Piece(over)=='O'||b.Piece(over)=='o'){
		    /* maybe can jump */
		    /* must now check landing position */
		    for(j=0;j<jmps.size();j++){
			land = ((Integer)jmps.get(j)).intValue();
			if (GetOver(b,pos,land)==over && b.Piece(land)=='e'){
			    can_jmp=true;
			}
		    }
		}
	    }
	    break;
	case 'O':
	     for(i=0;i<nbrs.size();i++){
		over = ((Integer)nbrs.get(i)).intValue();
		if(b.Piece(over)=='p'||b.Piece(over)=='P'){
		    /* maybe can jump */
		    /* must now check landing position */
		    for(j=0;j<jmps.size();j++){
			land = ((Integer)jmps.get(j)).intValue();
			if (GetOver(b,pos,land)==over && b.Piece(land)=='e'){
			    can_jmp=true;
			}
		    }
		}
	     }
	    break;
	default:
	    break;
	}

	return can_jmp;

		
    }



    /**
     * Given a CheckerBoard and a jump, returns a new CheckerBoard after
     * the jump has been taken.
     */

    public static CheckerBoard MakeJump(CheckerBoard b, LinkedList jump){
	CheckerBoard newb;
	int length;
	int start,i;
	int land,over;

	length = jump.size();
	newb = CheckerBoard.Copy(b);
	for(i=0;i<length-1;i++){
	    start = ((Integer)jump.get(i)).intValue();
	    land = ((Integer)jump.get(i+1)).intValue();
	    over = GetOver(newb,start,land);
	    newb = MakeJump(newb,start,over,land);
	}
	
	return newb;
    }

    private static CheckerBoard MakeJump(CheckerBoard b, int start, int over, int land){
	CheckerBoard newb;
	char piece;

	newb = CheckerBoard.Copy(b);
	piece = b.Piece(start);
	if(piece =='p' && land>27){
	    newb.SetPiece(land,'P');
	}
	else{
	    if(piece =='o' && land<4 && land>-1){
		newb.SetPiece(land,'O');
	    }
	    else{
		newb.SetPiece(land,piece);
	    }

	}
	newb.SetPiece(over,'e');
	newb.SetPiece(start,'e');

	return newb;
	
    }

    private static int GetOver(CheckerBoard b,int start, int land){
	/* return -1 is no match */
	ArrayList nbrs_start = new ArrayList();
	ArrayList nbrs_land = new ArrayList();
	int i,j,over;
	boolean match = false;
	int x,y;

	//	System.out.println("GetOver: " + start +" " + land);
	nbrs_start = b.board[start].GetNeighbours();
	nbrs_land = b.board[land].GetNeighbours();
	over =-1;
	i=0;
	while(!match && i<nbrs_start.size()){
	    for(j=0;j<nbrs_land.size();j++){
		x=((Integer)nbrs_start.get(i)).intValue();
		y = ((Integer)nbrs_land.get(j)).intValue();
		if(x==y){
		    match = true;
		    over = x;
		}
	    }
	    i++;
	}
	return over;
    }
	
}