import java.util.Comparator;
import java.util.StringTokenizer;

class Account implements Comparable, Comparator, Cloneable 
{
	private double balance;
	private byte   id;
	private Owner  owner;

	public Account() 
	{
		balance = 0;
		id      = -1;
		owner   = null;
	}

	public Account( double balance, byte id, Owner owner ) 
	{
		this.balance = balance;
		this.id      = id;
		this.owner   = owner;
	}

	public double getBalance()
	{
		return balance;
	}

	public byte getId()
	{
		return id;
	}

	public Owner getOwner()
	{
		return owner;
	}

	public void setBalance(double b)
	{
		balance = b;
	}

	public void setId(byte i)
	{
		id = i;
	}

	public void setOwner(Owner o)
	{
		owner = o;
	}

	// From Comparable -- compare by id
	public int compareTo( Object o ) 
	{
		Account a = null;
		if(!(o instanceof Account))
		{
			System.out.println("Wrong type comparison");
			return -100;
		}
		else
			a = (Account) o;

		if (id > a.getId())
            return 1;
		else if (id == a.getId())
			return 0;
		else
			return -1;
	}

	// From Comparator -- compare by balance
	public int compare( Object o1, Object o2 ) 
	{
		Account a1 = null, a2 = null;
		if(!((o1 instanceof Account) && (o2 instanceof Account)))
		{
			System.out.println("Wrong type comparison");
			return -100;
		}
		else
		{
			a1 = (Account) o1;
			a2 = (Account) o2;
		}

		if (a1.getBalance() > a2.getBalance())
		{
			return 1;
		}
		else if (a1.getBalance() < a2.getBalance())
		{
			return -1;
		}
		else
		{
			return 0;
		}
	}

	// From Comparator
	public boolean equals( Object o ) 
	{
		Account a = null;
		if(!(o instanceof Account))
		{
			System.out.println("Wrong type comparison");
			return false;
		}
		else
			a = (Account) o;
		
		if (a.getBalance() != balance)
            return false;
		if (a.getId() != id)
			return false;

		return owner.equals( a.getOwner() );
	}

	// For deep copy
	public Account clone() 
	{
		try 
		{
			Account account = (Account) super.clone();
			if(owner != null)
                account.setOwner(owner.clone());
			return account;
		}
		catch(Exception e) 
		{
			System.out.println("Problem!");
		}
		return null;
	}

	public String toString()
	{
		return ("Balance is: "+ balance + " ID is: "+id + " Owner is: " + owner);
	}
}


class Owner implements Comparable, Comparator, Cloneable 
{
	private String name;
	private String address;

	public Owner() 
	{
		name = address = "";
	}

	public Owner( String name, String address ) 
	{
		this.name    = name;
		this.address = address;
	}

	public String getName()
	{
		return name;
	}

	public String getAddress()
	{
		return address;
	}

	public void setName(String name)
	{
		this.name = name;
	}

	public void setAddress(String address)
	{
		this.address = address;
	}

	// From Comparable -- compare by name
	public int compareTo( Object o ) 
	{
		Owner w = null;
		if(!(o instanceof Owner))
		{
			System.out.println("Wrong type comparison");
			return -100;
		}
		else
			w = (Owner) o;

		return name.compareTo( w.getName() );
	}

	// From Comparator -- compare by address
	public int compare( Object o1, Object o2 ) 
	{
		Owner w1 = null, w2 = null;
		if(!((o1 instanceof Owner) && (o2 instanceof Owner)))
		{
			System.out.println("Wrong type comparison");
			return -100;
		}
		else
		{
			w1 = (Owner) o1;
			w2 = (Owner) o2;
		}

		return (w1.getAddress().compareTo(w2.getAddress()));
	}

	// From Comparator
	public boolean equals( Object o ) 
	{
		Owner w = null;
		if(!(o instanceof Owner))
		{
			System.out.println("Wrong type comparison");
			return false;
		}
		else
			w = (Owner) o;

		if (name.equals(w.getName()) && address.equals(w.getAddress()))
			return true;
		else
			return false;
	}

	// For deep copy
	public Owner clone() 
	{
		try 
		{
			Owner owner = (Owner) super.clone();
			owner.setName(new String(name));
			owner.setAddress(new String(address));
			return owner;
		}
		catch(Exception e) 
		{
			System.out.println("aa");
		}
		return null;
	}

	public String toString()
	{
		return ("The name is: " + name + ", and the address is: " + address);
	}
}

class AccountExercise{
	public static Account[] initAccounts(){
		int size = 0;
		System.out.println("Please enter the number of accounts : ");
		try{
			size = UserInput.readInt();
		}
		catch(NumberFormatException nfe){
			System.out.println("Your input is not valid. Please try again! ");
			initAccounts();
		}
		Account [] accounts = new Account[size];
		System.out.println("Please enter the account IDs in comma separated format : ");
		String IDs = UserInput.readString();
		System.out.println("Please enter the account balances in comma separated format : ");
		String balances = UserInput.readString();
		System.out.println("Please enter the owner names in comma separated format : ");
		String names = UserInput.readString();
		System.out.println("Please enter the owner adresses in comma separated format : ");
		String addresses = UserInput.readString();
		StringTokenizer st1 = new StringTokenizer(IDs, ",");
		StringTokenizer st2 = new StringTokenizer(balances, ",");
		StringTokenizer st3 = new StringTokenizer(names, ",");
		StringTokenizer st4 = new StringTokenizer(addresses, ",");
			
		for(int i=0; i<size; i++){
			byte id = Byte.parseByte(st1.nextToken());
			double balance = Double.parseDouble(st2.nextToken());
			String name = st3.nextToken();
			String address = st4.nextToken();
			accounts [i] = new Account(balance, id, new Owner(name, address));
		}
		return accounts;
	}
	
	public static void sortAccount(Account [] accounts)
	{
		String output = "";
		System.out.println("Please enter 1 to sort by id, 2 by balance: ");
		int choice = UserInput.readInt();
		
		output += "Accounts before Sorting\n";
		output += "-----------------------\n";
		for (int i = 0; i < accounts.length; ++i)
		{
			output += accounts[i]+"\n";
		}
		if(choice == 1){
			output += "\nAccounts Sorted by ID\n";
			output +=   "---------------------\n";

			java.util.Arrays.sort(accounts);
		}
		else{
			output += "\nAccounts Sorted by Balance\n";
			output +=   "--------------------------\n";

			java.util.Arrays.sort(accounts, accounts[0]);
		}


		for (int i = 0; i < accounts.length; ++i)
		{
			output += accounts[i]+"\n";
		}

		System.out.println(output);
	}

	public static void sortByOwner(Account[] accounts)
	{
		String output = "";

		output += "Accounts before Sorting\n";
		output += "-----------------------\n";
		for (int i = 0; i < accounts.length; ++i)
		{
			output += accounts[i]+"\n";
		}

		output += "\nAccounts Sorted by Owner\n";
		output +=   "------------------------\n";
		java.util.Arrays.sort(accounts, new OwnerSort());
		for (int i = 0; i < accounts.length; ++i)
		{
			output += accounts[i]+"\n";
		}
		System.out.println(output);
	}
	
	
	// helper
	public static int binarySearchRecursive(int id, Account [] accounts)
	{
		return binarySearchRecursive(id, accounts, 0, accounts.length-1);
	}
	public static int binarySearchRecursive(int id, Account[] accounts, int leftIdx, int rightIdx)
	{
		// base case #1
		if (leftIdx > rightIdx) return -1; // the searched id does not exist 
		
		int middleIdx = (leftIdx + rightIdx) / 2;
		int currentId = accounts[middleIdx].getId();
		
		// base case #2
		if (currentId == id) 
			return middleIdx; // id found
		
		// recursive case #1
		if (currentId > id)
			return binarySearchRecursive(id, accounts, leftIdx, middleIdx-1); // recursive step

		// recursive case #2		
		else //if (currentId > id)
			return binarySearchRecursive(id, accounts, middleIdx+1, rightIdx); // recursive step
	}
}

// We create another comparator to compare Account objects by their Owners
class OwnerSort implements Comparator{
	public int compare(Object o1, Object o2){
		Account a1 = null, a2 = null;
		if(!((o1 instanceof Account) && (o2 instanceof Account)))
		{
			System.out.println("Wrong type comparison");
			return -100;
		}
		else
		{
			a1 = (Account) o1;
			a2 = (Account) o2;
		}
		return a1.getOwner().compare(a1.getOwner(), a2.getOwner());
	}
}


/*
 * Problem 5: In this method, we assume that the user is trying to find the location of an Account with the specified id
 * Therefore the method gets two parameters: the array to be searched, and the id to be found
 * Binary search algorithm is based on the precondition that the array is sorted (with respect to what we are searching for - in this case id)
 * In each step, we check for the element in the mid position. If the Account in that position has the specified id, 
 * we have reached solution. So we return the corresponding index. If the Account in the mid position has a higher id value, we know that 
 * we should continue searching on the left side of the array (because each element on the right have a higher id value)
 * Otherwise, we search on the right. 
 * Eventually, we either find the element (and return the index), or we have the case that the left index value is greater than the right one.
 * This means that we have searched all the array but couldn't find any element with the specified id value. 
 * So we return -1 to signify that (since -1 is not a valid index)
 * Note that this algorithm can be easily extended for other properties of an Account object (instead of id) 
*/