boardhelper.java

good project for programmer,,

the path is guaranteed to only cross 'friendly' countries.
<p>
If <i>CCF</i> is invalid, or if no paths are found because all paths are
blocked by 'enemy' countries, null is returned.
<p>
* @param	CF 		the from country
* @param	CT 		the to country
* @param	countries  the board
* @return  			An array of country objects
* @see  	Country
* @see  	BoardHelper#closestCountryWithOwner
* @see  	BoardHelper#easyCostFromCountryToContinent
*/
public static Country[] friendlyPathBetweenCountries( 
							Country CF, Country CT, Country[] countries )
	{
	int ccf = CF.getCode();
	int cct = CT.getCode();
	int[] retval = BoardHelper.friendlyPathBetweenCountries(
  					ccf, cct, countries);
	if (retval == null)
		return null;
		
	Country[] rets = new Country[retval.length];
	for(int i = 0; i < retval.length; i++)
		{
		rets[i] = countries[retval[i]];
		}
	return(rets);
	}
	
/** This method finds the shortest path (in terms of countries) from 
country <i>CCF</i> (CCFrom) to <i>CCT</i> (CCTo), that ONLY goes through 
countries owned by <i>CCF</i>'s owner.
<p>
This method uses a self-sorting queueing mechanism to determine the shortest
path (in terms of countries crossed) between <i>CCF</i> and <i>CCT</i>.  
Starting with <i>CCF</i>,
it enqueues and follows every path outwards from its neighbors (and their
neighbors, and so on), making note of the ownership of the neighbors, 
until it finds a path that terminates in the desired country <i>CCT</i>
<p>
This method returns a list that contains the path. The list is simply an int 
array, each holding the next country code in line. The zero element of the array 
will be country <i>CCF</i>, while the last element of the array (the one with the
highest value index) will be <i>CCT</i>. 
<p>
Keep in mind that this method will  
take into account the ownership of intervening countries on the path returned.
The path is guaranteed to only cross 'friendly' countries if possible.
<p>
If <i>CCF</i> is invalid, or if no paths are found because all paths are
blocked by 'enemy' countries, null is returned.
<p>
* @param	CCF		the country code of the from country
* @param	CCT		the country code of the to country
* @param	countries  the board
* @return  			An array of integers
* @see  	Country
* @see  	BoardHelper#closestCountryWithOwner
* @see  	BoardHelper#easyCostFromCountryToContinent
*/
public static int[] friendlyPathBetweenCountries( 
 									int CCF, int CCT, Country[] countries )
	{
	if ( CCF < 0 || countries.length <= CCF 
 				|| CCT < 0 || countries.length <= CCT )
		{
		System.out.println(
   		"ERROR in friendlyPathBetweenCountries() -> bad parameters.");
		return null;
		}
	
	int CCFOwner = countries[CCF].getOwner();
	int testCode = CCF;
	int distanceSoFar = 0;
	int[] testCodeHistory = new int[1];
	testCodeHistory[0] = CCF;

	// We keep track of which countries we have already seen (so we don't 
	// consider the same country twice). We do it with a boolean array, with 
	// a true/false value for each of the countries:
	boolean[] haveSeenAlready = new boolean[countries.length];
	for (int i = 0; i < countries.length; i++)
		{
		haveSeenAlready[i] = false;
		}		
	haveSeenAlready[CCF] = true;
	
	// Create a Q (with a history) to store the country-codes and their cost
	// so far:
	CountryPathStack Q = new CountryPathStack();
	
	// Loop over the expand-enqueue until either the correct 
	// country is found or there are no more countries in the Q:
	while ( true )
		{
		// Get the current countries neighbors, and cycle through them:
		Country[] neighbors = countries[testCode].getAdjoiningList();
		for (int i = 0; i < neighbors.length; i++)
			{
			// We only care about them if we haven't seen them before and if they ARE owned by CCF's owner:
			if ( neighbors[i].getOwner() == CCFOwner && ! haveSeenAlready[ neighbors[i].getCode() ] )
				{
				// Create the new node's history array. (It is just testCode's history 
				// with its CC added at the end):
				int[] newHistory = new int[ testCodeHistory.length + 1 ];
				for (int j = 0; j < testCodeHistory.length; j++)
					{
					newHistory[j] = testCodeHistory[j];
					}
				newHistory[newHistory.length-1] = neighbors[i].getCode();

				Q.pushWithValueAndHistory( neighbors[i], distanceSoFar+1, newHistory );
				haveSeenAlready[ neighbors[i].getCode() ] = true;
				}
			}
	
	
		if ( Q.isEmpty() )
			{
			// Then there is no path. return null:
			return null;
			}
		
		distanceSoFar = Q.topValue();
		testCodeHistory = Q.topHistory();
		testCode = Q.pop();
		
		if ( testCode == CCT )
			return testCodeHistory;
		}
	} // End of friendlyPathBetweenCountries
	
/****** The New-age seeker methods **********/
  							
/** This method will return an array of country-codes consisting of the
cheapest route between a country owned by <i>owner</i> and the 
<i>continent</i>. 
<p>
This method uses a self-sorting queueing mechanism to determine the easiest
path (in terms of enemy armies in the way) between a country owned by 
<i>owner</i> and a country found in <i>continent</i>.  
Starting with each country in <i>continent</i>,
it enqueues and follows every path outwards from their neighbors (and their
neighbors, and so on), making note of the ownership of the neighbors and
the number of armies,
until it finds a path that terminates in any country owned by <i>owner</i>.
<p>
This method returns a list that contains the path. The list is simply an int 
array, each holding the next country code in line. Due to the method of
enqueueing, the zero element of the array will be the country owned by
<i>owner</i> that was found, while the last element of the array (the one 
with the highest value index) will be in <i>continent</i>. 
<p>
Keep in mind that this method only takes into account the ownership of 
countries as it searches outwards, looking for any owned by <i>owner</i>. 
<p>
If <i>CCF</i> is invalid, or if no paths are found, null is returned.
<p>
* @param	owner  	the index of the interested player
* @param	continent  the index of the interested continent
* @param	countries  the board
* @return  			An array of integers
* @see  	Country
*/
public static int[] cheapestRouteFromOwnerToCont( 
  							int owner, int continent, Country[] countries )
	{	
	if ( owner < 0 || continent < 0)
		{
		System.out.println(
			"ERROR in cheapestRouteFromOwnerToCont() -> bad parameters");
		return null;
		}
		
	if (playerOwnsContinentCountry(owner, continent, countries))
		{
		// the player owns a country in the continent already. That country itself is the cheapest route
		ContinentIterator iter = new ContinentIterator( continent, countries );
		while (iter.hasNext()) {
			Country next = iter.next();
			if ( next.getOwner() == owner ) {
				return new int[] { next.getCode() } ;
				}
			}
		
		}
		
	// We keep track of which countries we have already seen (so we don't
	// consider the same country twice). We do it with a boolean array, with 
	// a true/false value for each of the countries:
	boolean[] haveSeenAlready = new boolean[countries.length];
	for (int i = 0; i < countries.length; i++)
		{
		haveSeenAlready[i] = false;
		}		
		
	// Create a Q (with a history) to store the country-codes and their cost 
	// so far:
	CountryPathStack Q = new CountryPathStack();
		
	// We explore from all the borders of <continent>
	int testCode, armiesSoFar;
	int[] testCodeHistory;
	int[] borderCodes = BoardHelper.getContinentBorders( continent, countries );
	for (int i = 0; i < borderCodes.length; i++)
		{
		testCode = borderCodes[i];
		armiesSoFar = 0;
		testCodeHistory = new int[1];
		testCodeHistory[0] = testCode;
		haveSeenAlready[testCode] = true;
		
		Q.pushWithValueAndHistory(
 					countries[borderCodes[i]], 0, testCodeHistory );
		}
	
	// So now we have all the continent borders in the Q (all with cost 0),
	// expand every possible outward path (in the order of cost).
	// eventually we should find a country owned by <owner>,
	// then we return that path's history
	while ( true )
		{
		armiesSoFar = Q.topValue();
		testCodeHistory = Q.topHistory();
		testCode = Q.pop();
		
		if ( countries[testCode].getOwner() == owner )
			{
			// we have found the best path. return it
			return testCodeHistory;
			}
		
		Country[] neighbors = countries[testCode].getAdjoiningList();
		
		for (int i = 0; i < neighbors.length; i++)
			{
			if ( ! haveSeenAlready[ neighbors[i].getCode() ] )
				{
				// Create the new node's history array. (It is just 
				// testCode's history with its CC added at the beginning):
				int[] newHistory = new int[ testCodeHistory.length + 1 ];
				newHistory[0] = neighbors[i].getCode();
				for (int j = 1; j < newHistory.length; j++)
					{
					newHistory[j] = testCodeHistory[j-1];
					}
				Q.pushWithValueAndHistory( 
					neighbors[i], 
					// If the neighbor is owned by the proper person then minus 
					// its armies from the value so if gets pulled off the Q next.
					// Without this there is a bug					
					armiesSoFar + (neighbors[i].getOwner() == owner ? -neighbors[i].getArmies() : neighbors[i].getArmies()),
					newHistory );
				haveSeenAlready[ neighbors[i].getCode() ] = true;
				}
			}
		
		if ( Q.isEmpty() )
			{
			System.out.println(
				"ERROR in cheapestRouteFromOwnerToCont->can't pop");
			return null;
			}
		}
	} // End of cheapestRouteFromOwnerToCont

/** Create a copy of the countries array, for simulation. */ 
public static Country[] getCountriesCopy(Country[] countries) 
	{ 
		Country[] countriesCopy = new Country[countries.length]; 
		// pass 1: allocate the countries 
		for (int i = 0; i < countries.length; i++) 
		{ 
			countriesCopy[i] = new Country(i, countries[i].getContinent(), null); 
			countriesCopy[i].setArmies(countries[i].getArmies(), null); 
			countriesCopy[i].setName(countries[i].getName(), null); 
			countriesCopy[i].setOwner(countries[i].getOwner(), null); 
		} 
		// pass 2: create the AdjoiningLists 
		for (int i = 0; i < countries.length; i++) 
		{ 
			Country[] around = countries[i].getAdjoiningList(); 
			for (int j = 0; j < around.length; j++) 
				countriesCopy[i].addToAdjoiningList(countriesCopy[around[j].getCode()], null); 
		} 
		return countriesCopy; 
	}



/**  Get the defensible borders of a continent - those that can be used to attack the continent.
  The BoardHelper.getContinentBorders() gives only the borders with outgoing connections.
  With standard two-way connections maps, this will give the same result as BoardHelper.getContinentBorders()	*/
public static int[] getDefensibleBorders(int continent, Country[] countries)
    {
        // we need a Vector to store the results, since we do not know how many there will be
        Vector borders = new Vector();
        
        // for all the countries *not* in continent, can they see the continent?
        for (int c = 0; c < countries.length; c++)
            if (countries[c].getContinent() != continent)
            {
                Country[] neighbors = countries[c].getAdjoiningList();
                for (int i = 0; i < neighbors.length; i++)
                    if (neighbors[i].getContinent() == continent  &&  !borders.contains(neighbors[i]))
                        borders.add(neighbors[i]);
            }
        
        // Copy the results into an array and return it
        int[] result = new int[borders.size()];
        for (int i = 0; i < result.length; i++)
            result[i] = ((Country)borders.get(i)).getCode();
	return result;
    }

    
/**  Get the countries beyond the defensible borders of a continent - those that can be used to attack the continent.
  With standard two-way connections maps, this will give the same result as BoardHelper.getContinentBordersBeyond().	*/
public static int[] getDefensibleBordersBeyond(int continent, Country[] countries)
    {
        // we need a Vector to store the results, since we do not know how many there will be
        Vector beyond = new Vector();
        
        // for all the countries *not* in continent, can they see the continent?
        for (int c = 0; c < countries.length; c++)
            if (countries[c].getContinent() != continent)
            {
                Country[] neighbors = countries[c].getAdjoiningList();
                for (int i = 0; i < neighbors.length; i++)
                    if (neighbors[i].getContinent() == continent  &&  !beyond.contains(countries[c]))
                        beyond.add(countries[c]);
            }
        
        // Copy the results into an array and return it
        int[] result = new int[beyond.size()];
        for (int i = 0; i < result.length; i++)
            result[i] = ((Country)beyond.get(i)).getCode();
	return result;
    }


/**  Get the list of countries that can attack the target.
  With standard two-way connections maps, this will give the same result(CC instead of countries) as Country.getAdjoiningList() .	*/
public static int[] getAttackList(Country target, Country[] countries)
    {
        // we need a Vector to store the results, since we do not know how many there will be
        Vector attackList = new Vector();
        
        // for all the countries, can they see the target?
        for (int c = 0; c < countries.length; c++)
            if (countries[c].canGoto(target))
                attackList.add(countries[c]);
        
        // Copy the results into an array and return it
        int[] result = new int[attackList.size()];
        for (int i = 0; i < result.length; i++)
            result[i] = ((Country)attackList.get(i)).getCode();
	return result;
    }



}