package mgminterview;

import java.util.Arrays;

//Your task is to:
//- fix the code
//- improve the poor quality of this code.
//
//(You can change anything you want
//
//The class should sort food instances and output the following lines:
//
//Potato 1
//Potato 9
//Potato 11
//Tomato 11
//Potato 12
//Potato 42
//Potato 46
//Potato 55
//Potato 77
//Tomato 121
//


public class MgmInterviewFoodSort {

	public static FOOD[] foods = null;

	public abstract class FOOD {
		public int size;
		public FOOD () {
			this.size = -1;
		}

		//i removed the whoami method, since it wasn't serving any real purpose beyond what instanceof does



	}

	public class Potato extends FOOD {
		public Potato () {
			super();
		}
		public Potato (int size) {
			super();
			this.size = size;
		}

		public void setSize (int size) {
			this.size = size;
		}
		public int getSize () {
			return this.size;
		}
		public String toString () {
			return "Potato" + " " + this.getSize();
		}

	}

	public class Tomato extends FOOD {
		public Tomato () {
			super();
			this.size = 121;
		}
		public Tomato (int size) {
			super();
			this.size = size;
		}
		public void setSize (int size) {
			this.size = size;
		}
		public int getSize () {
			return this.size;
		}
		public String toString () {
			return "Tomato" + " " +this.getSize();
		}
	}

	/*replaced the O(n^2) sort method with merge sort. if the sizes equal, this favors potato over tomato
	 * not really necessary when you're sorting 10 things, but now the sort method scales up
	 */
	void merge(FOOD arr[], int l, int m, int r) {
		int n1 = m - l + 1;
		int n2 = r - m;

		FOOD L[] = new FOOD [n1];
		FOOD R[] = new FOOD [n2];

		for (int i=0; i<n1; ++i)
			L[i] = arr[l + i];
		for (int j=0; j<n2; ++j)
			R[j] = arr[m + 1+ j];



		int i = 0, j = 0;

		int k = l;
		while (i < n1 && j < n2)
		{

			int first =0;
			int second =0;

			if (L[i] instanceof Potato) {
				first = ((Potato)L[i]).getSize();
			}
			else {
				first = ((Tomato)L[i]).getSize();
			}

			if (R[j] instanceof Potato) {
				second = ((Potato)R[j]).getSize();
			}
			else {
				second = ((Tomato)R[j]).getSize();
			}


			if ((first == second && L[i] instanceof Potato) ||first < second) {
				arr[k] = L[i];
				i++;
			}
			else
			{
				arr[k] = R[j];
				j++;
			}
			k++;
		}

		while (i < n1)
		{
			arr[k] = L[i];
			i++;
			k++;
		}

		while (j < n2)
		{
			arr[k] = R[j];
			j++;
			k++;
		}
	}

	void sort(FOOD arr[], int l, int r) {
		if (l < r) {
			int m = (l+r)/2;

			sort(arr, l, m);
			sort(arr , m+1, r);

			merge(arr, l, m, r);
		}
	}

	public void print() {
		for (FOOD food : Arrays.asList(foods)) {
			if (food instanceof Potato) {
				System.out.println(((Potato)food).toString());
			}

			else {
				System.out.println(((Tomato)food).toString());

			}
		}
	}

	public static void main(final String[] args) {

		MgmInterviewFoodSort fs=new MgmInterviewFoodSort();

		foods = new FOOD[10];


		Tomato t1 = fs.new Tomato(11);
		foods[0] = t1;


		Tomato t2 = fs.new Tomato();
		foods[1] = t2;



		Potato p1 = fs.new Potato(1);
		foods[2] = p1;


		Potato p2 = fs.new Potato(42);
		foods[3] = p2;

		Potato p3 = fs.new Potato(77);
		foods[4] = p3;

		Potato p4 = fs.new Potato(55);
		foods[5] = p4;

		Potato p5 = fs.new Potato(46);
		foods[6] = p5;

		Potato p6 = fs.new Potato(12);
		foods[7] = p6;

		Potato p7 = fs.new Potato(11);
		foods[8] = p7;

		Potato p8 = fs.new Potato(9);
		foods[9] = p8;



		fs.sort(foods, 0, foods.length-1);
		fs.print();
	}

}