import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class SortByFreq {
	public static void main(String[] args) {
		Integer[] data0 = {1, 3, 2, 1, 1, 4, 2};
		sortByFreq(data0);

		Integer[] data1 = {7, 1, 7, 3, 6, 2, 5, 4, 4, 5, 6, 7};
		sortByFreq(data1);

		Integer[] data2 = {3, 2, 1, 4, 5, 3};
		sortByFreq(data2);
	}

	/*
	 * Sorting Priority
	 * 1. Frequency (ascending)
	 * 2. First Occurrence Index (ascending)
	 */
	public static void sortByFreq(Integer[] list){
		Map<Integer, Integer> frq = new HashMap<Integer,Integer>();
		Map<Integer, Integer> idx = new HashMap<Integer,Integer>();

		for (int i = 0; i < list.length; i++) {
			int x = list[i];

			int f = frq.getOrDefault(x, 0);
			frq.put(x, f + 1);

			if (!idx.containsKey(x))
				idx.put(x, i);
		}

		SortComparator sComp = new SortComparator(frq,idx);
		Arrays.sort(list, sComp);

		System.out.println("Result: " + Arrays.toString(list));
	}

}

class SortComparator implements Comparator<Integer>{
	private final Map<Integer, Integer> freqMap; //frequency map
	private final Map<Integer, Integer> indxMap; //index map

	SortComparator(Map<Integer, Integer> fMap, Map<Integer, Integer> xMap){
		this.freqMap = fMap;
		this.indxMap = xMap;
	}

	@Override
	public int compare(Integer o1, Integer o2) {
		int freqComp = freqMap.get(o1).compareTo(freqMap.get(o2));
		int indxComp = indxMap.get(o1).compareTo(indxMap.get(o2));
		//if the frequency are equal, then compare by index
		if (freqComp == 0) return indxComp;
		else return freqComp;
	}

}