/*

THIS SOFTWARE IS DISTRIBUTED UNDER GPL LICENSE

Copyright (C) 2006  Lukasz Grzegorz Maciak
http://terminally-incoherent.com

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA or visit http://www.gnu.org/licenses/gpl.txt.

*/



import java.util.Random;

/*
 * Created on Mar 25, 2006
 */

/**
 * Banker class - implements the Bankers' Algorithm.
 *
 * @author Lukasz Grzegorz Maciak
 */
public class Banker
{
	private volatile int[] avaliable;		// avaliable resources
	private volatile int[][] max;			// max resource claims for all threads
	private volatile int[][] allocation;	// current allocation of resources for all threads
	private volatile int[][] need;			// current need of resources for all threads

	/**
	 * The default constructor for the Banker object
	 *
	 * @param clients the number of client objects that will request resources from this banker
	 * @param resources an int[] array representing number of avaliable resources
	 */
	public Banker(int clients, int[] resources)
	{
		avaliable = resources;

		allocation = new int[clients][resources.length];
		initArray(allocation);

		need = new int[clients][resources.length];
		initArray(need);

		max = new int[clients][];

		System.out.println("( -*- ) " +"Welcome to Banker! Resources avaliable " + showArray(avaliable));
	}


	/**
	 * Initialize an array with all zeros.
	 *
	 * @param a and int[][] array to be initialized
	 */
	private void initArray(int[][] a)
	{
		for(int i=0; i<a.length; i++)
			for(int j=0; j<a[i].length; j++)
				a[i][j] = 0;
	}

	/**
	 * Returns true if all the cells of this int[][] array are equal to zero;
	 *
	 * @param a int[][] array to be tested
	 * @return true if a containz only zeros, false otherwise
	 */
	private boolean arrayEmpty(int[][] a)
	{
		int counter = 0;

		for(int i=0; i<a.length; i++)
			for(int j=0; j<a[i].length; j++)
				if(a[i][j] == 0)
					counter++;

		return ((counter == a.length*a[0].length) ? true : false);
	}

	/**
	 * Checks if all elements of a given array, are less or equal to elements
	 * of another array.
	 *
	 * @param a1 int[] array to be checked
	 * @param a2 int[] array to be tested against
	 *
	 * @return true if a1[i]<=a2[i] for all possible i, else otherwise
	 */
	private boolean arrayIsLessThan(int[] a1, int[] a2)
	{
		int counter = 0;

		for(int i=0; i<a1.length; i++)
			if(a1[i] <= a2[i])
				counter++;

		return ((counter == a1.length) ? true : false);
	}

	/**
	 * Subtracts elements a second arrray from the first array. This in fact is
	 * equivalent to a1[i] = a1[i]-a2[i] for all possible i
	 *
	 * @param a1 int[] array - the source
	 * @param a2 int[] array - the subtractor
	 */
	private synchronized void subtractArrays(int[] a1, int[] a2)
	{
		for(int i=0; i<a1.length; i++)
			a1[i] = a1[i]-a2[i];
	}

	/**
	 * Subtract elements of a2, from the elements of a1 and place tem in a new array.
	 * This is equivalent to:  new[*] = a1[*]-a2[*]
	 *
	 * @param a1 int[] source array
	 * @param a2 int[] subtractor array
	 * @return int[] result of a[*]-a2[*]
	 */
	private synchronized int[] subtractArraysCopy(int[] a1, int[] a2)
	{
		int[] tmp = new int[a1.length];
		System.arraycopy(a1, 0, tmp, 0, tmp.length);

		subtractArrays(tmp, a2);

		return tmp;
	}

	/**
	 * Add elements of two arrays together, and place the results in the
	 * first one.
	 *
	 * @param a1 int[] source array
	 * @param a2 int[] addition array
	 */
	private synchronized void addArrays(int[] a1, int[] a2)
	{
		for(int i=0; i<a1.length; i++)
			a1[i] = a1[i]+a2[i];
	}
	/**
	 * Check if the boolean array contains only true values.
	 *
	 * @param array a boolean[] array to be tested
	 * @return thrue if all balues of array are true, false otherwise
	 */
	private synchronized boolean arrayIsTrue(boolean[] array)
	{
		int counter = 0;

		for(int i=0; i<array.length; i++)
			if(array[i] == true)
				counter++;

		return ( (counter==array.length) ? true : false);

	}

	/**
	 * Remove this threads Max requirements from the Max pool of the banker.
	 * This method should be called beefore the thread teminates, so that it is
	 * no longer claiming to need resources (giving waiting threads a chance to
	 * execute)
	 *
	 * @param id - the id of a given thread
	 */
	public synchronized void releaseFromPool(int id)
	{
		for(int i=0; i<max[id].length; i++)
			max[id][i] = 0;

		need[id] = subtractArraysCopy(max[id], allocation[id]);
		notifyAll();
	}


	/**
	 * Communicate the maximum number of resources a given thread will need
	 * as it is executing.
	 *
	 * @param id the int id of the thread
	 * @param m and int[] matrix representing the claim
	 */
	public synchronized void setMax(int id, int[] m)
	{
		max[id] = m;
		need[id] = subtractArraysCopy(max[id], allocation[id]);
	}

	/**
	 * A blocking request resources from the banker. This method will block untill resourcess
	 * are avaliable. If it is detected that it would not be possible to execute this request
	 * without a deadlock, this method will terminate and return false
	 *
	 * @param id the int id of requesting thread
	 * @param request an int[] array of requested resources
	 * @return true if the request was granted, and false if it was aborted to prevent deadlock
	 */
	public synchronized boolean request(int id, int[] request)
	{
		System.out.println("(  ?  ) " + id + " requests " + showArray(request) + ". Current state " + showArray(avaliable));

		if(arrayIsLessThan(request, need[id]) && arrayIsLessThan(request, avaliable))
		{
			return (allocate(id, request));

		}
		else
		{
			System.out.println("( !!! ) " + "Error: " + id + " requested " + showArray(request) + " which is more than it's maximum claim of " + showArray(max[id]));
			return false;
		}
	}

	/**
	 * This method will test for deadlock, and allocate resources if possible, block and wait, or return
	 * false if a deadlock cannot be avoided by waiting.
	 *
	 * @param id the int id of the requesting thread
	 * @param request a int[] request array
	 * @return true if the request was allocate, or false if it was aborted
	 */
	private synchronized boolean allocate(int id, int[] request)
	{

		while(!checkSafeState(id, request))
		{
			System.out.println("(  !  ) request for " + showArray(request) + " from " + id + " denied - not a safe state. Possible state " + showArray(avaliable) + "\n\t\tNeed:\t" + showArray(need) + "\n\t\tAlloc:\t" + showArray(allocation));
			rollback(id, request);
			System.out.println("(  !  ) request for " + showArray(request) + " from " + id + " rolled back. Current state " + showArray(avaliable) + "\n\t\tNeed:\t" + showArray(need) + "\n\t\tAlloc:\t " + showArray(allocation));

			// if the allocation array is empty and thus all the resources are in the pool
			//abort the operation - the user will have to re-run this at some other point
			/*if(arrayEmpty(allocation))
			{
				System.out.println("( !!! ) request for " + showArray(request) + " from " + id + " ABORTED TO PREVENT DEADLOCK. Concurent execution is impossible - please run at a later time");
				return false;
			}	*/

			// wait untill the resources are avaliable
			try{ wait(); } catch (InterruptedException e){ e.printStackTrace();}


		}

		System.out.println("( <-- ) " + id + " allocated " + showArray(request) + ". Current state " + showArray(avaliable) + "\n\t\tNeed:\t" + showArray(need) + "\n\t\tAlloc:\t" + showArray(allocation));
		return true;
	}

	/**
	 * Realease resources held by a given thread. The resources are returned to the
	 * avaliable pool and the need, is modified.
	 *
	 * @param id int id of the releasing thread
	 * @param request and int[] of the resources that need to be released
	 */
	public synchronized void release(int id, int[] request)
	{
		addArrays(avaliable, request);
		subtractArrays(allocation[id], request);
		addArrays(need[id], request);

		System.out.println("( --> ) " +id + " releases " + showArray(request) + ". Current state " + showArray(avaliable));
		notifyAll();
	}


	/**
	 *
	 * Roll back the request after the banker's test has failed. This restores all the
	 * arrays to their previous state.
	 *
	 * @param id the int id of the requesting thread
	 * @param request the int[] of the actual request
	 */
	private synchronized void rollback(int id, int[] request)
	{
		addArrays(avaliable, request);
		subtractArrays(allocation[id], request);
		addArrays(need[id], request);
	}

	/**
	 * Check if the current request will leave the system in the safe state.
	 *
	 * @param id the int id of the requesting thread
	 * @param request int[], and actual request to be tested
	 * @return true if this request will result in a safe state, false otherwise
	 */
	private synchronized boolean checkSafeState(int id, int[] request)
	{
		subtractArrays(avaliable, request);
		addArrays(allocation[id], request);
		subtractArrays(need[id], request);

		int[] work = new int[avaliable.length];
		System.arraycopy(avaliable, 0, work, 0, work.length);

		boolean[] finish = new boolean[need.length];

		for(int i=0; i<finish.length; i++)
			finish[i] = false;

		for(int i=0; i<finish.length; i++)
		{
			if(arrayIsLessThan(need[i], work) && finish[i] == false)
			{
				addArrays(work, allocation[id]);
				finish[i] = true;
			}
		}

		return (arrayIsTrue(finish) ? true : false);
	}

	/**
	 * Return a String representation of an int[] array
	 *
	 * @param array and int[] array
	 * @return String representation of array
	 */
	public static String showArray(int[] array)
	{
		String tmp = " [ ";

		for(int i=0; i<array.length; i++)
			tmp += array[i] + " ";

		tmp += "]";

		return tmp;
	}


	/**
	 * Return a String reprsentation of an int[][] array
	 *
	 * @param array an int[][] array
	 * @return String representation of array
	 */
	public static String showArray(int[][] array)
	{
		String tmp = " ";

		for(int i=0; i<array.length; i++)
		{
			tmp += i + ":[ ";
			for(int j=0; j<array[i].length; j++)
				tmp += array[i][j] + " ";
			tmp += "]\t";
		}

		return tmp;
	}


	public static void main(String[] args)
	{

		// Sorry - no propper user interface
		// please tweak the values below to change
		// the runtime properties

		int clients = 5;
		int requests = 5;
		int[] resources = new int[]{10, 15, 10};

		Random r = new Random();

		Banker banker = new Banker(clients, resources);

		Requester[] tmp = new Requester[clients];

		for(int i=0; i<clients; i++)
		{
			int[] max = new int[resources.length];

			for(int j=0; j<max.length; j++)
				max[j] = r.nextInt(resources[j])+1;

			tmp[i] = new Requester(banker, i, max, requests);
		}

		for(int i=0; i<clients; i++)
			tmp[i].start();

	}

}