package mergeProgram;

import java.util.List;
import java.util.ArrayList;

public class Merge {
	private static List<Integer> merged = new ArrayList<Integer>();

	public static List<Integer> merge(List<Integer> list1, List<Integer> list2) {
		for (Integer i : list1) {
			merged.add(i);
		}
		for (Integer j : list2) {
			merged.add(j);
		}
		
		//Sort the array
		heapsort(merged, (merged.size()));
		//Delete any dublicates
		deleteDublicates(merged);
		//Print the resulting List
		return merged;
	}
	
	/**
	 * Accessor method
	 * @return merged
	 */
	public static List<Integer> getMerged() {
		return merged;
	}
	
	public static void deleteDublicates(List<Integer> list){
		int i = 0;
		while(i <= list.size()-3){
			if(list.get(i) == list.get(i+1)){
				list.remove(i);
			}
			i++;
		}
	}
	
	/**
	 * Sorts the List arr.
	 * @param arr The array to be sorted.
	 * @param n Size of the array to be sorted.
	 */
	public static void heapsort(List<Integer> arr, int n) {
		for (int m = n / 2; m >= 0; m--)
			heapify(arr, m, n - 1);
		for (int m = n - 1; m >= 1; m--) {
			swap(arr, 0, m);
			heapify(arr, 0, m - 1);
		}
	}
	
	/**
	 * Part of HeapSort
	 * 
	 * @param arr The List to be heapified.
	 * @param i 
	 * @param k 
	 */
	private static void heapify(List<Integer> arr, int i, int k) {
		int j = 2 * i + 1;
		if (j <= k) {
			if (j + 1 <= k && arr.get(j) < arr.get((j + 1)))
				j++;
			if (arr.get(i) < arr.get(j)) {
				swap(arr, i, j);
				heapify(arr, j, k);
			}
		}
	}

	/**
	 * Part of HeapSort
	 * 
	 * @param arr
	 * @param s
	 * @param t
	 */
	private static void swap(List<Integer> arr, int s, int t) {
		int tmp = arr.get(s);
		arr.set(s, arr.get(t));
		arr.set(t, tmp);
	}
}