import java.util.*;
import java.math.BigDecimal;




public class SortDemo3
{
    public static final int NO_OF_RECORDS = 10;
    public static final int STRING_LENGTH = 4;

    private static void printRecords(Data records) {
        for(int index = 0; index < records.size(); index++) {
            print(records.recordAt(index).getId() + "\t" +
                    records.recordAt(index).getVitality() + "\t" + records.recordAt(index).getTreatment());
        }
    }
    public static void print(String s) {
        System.out.println(s);
    }
    public static byte[] random(int len) {
        byte buffer[] = new byte[len];

        for(int i = 0; i < len; i++) {
            buffer[i] = (byte)(Math.random() * 26 + 97);
        }
        return buffer;
    }
    public static void main(String[] args)
    {
        SortObj soBubbleSort = new SortObj("Bubble Sort");
        SortObj soInsertionSort = new SortObj("Insertion Sort");
        SortObj soSelectionSort = new SortObj("Selection Sort");
        SortObj soQuickSort = new SortObj("Quick Sort");
        int noOfRecords = NO_OF_RECORDS;
        Record[] rec = new Record[NO_OF_RECORDS];
        String name;

        int iTotal = 0;

        Random generator = new Random();
        Scanner in = new Scanner(System.in);
        int iOption = 1000;

        for(int j = 0; j < noOfRecords; j++)
        {
            name = new String(random(STRING_LENGTH));
            rec[j] = new Record();
            rec[j].setTreatment(name);
            rec[j].setId(new String(random(6)));
            int iVitality = generator.nextInt(6);iTotal = (iVitality == 0) ? ++iTotal:iTotal;
            rec[j].setVitality(Integer.toString(iVitality));
            soBubbleSort.getData().addRecord(rec[j]);
            soInsertionSort.getData().addRecord(rec[j]);
            soSelectionSort.getData().addRecord(rec[j]);
            soQuickSort.getData().addRecord(rec[j]);
        }
        print("\t------INITIAL DATA STATISTICS------");
        print(noOfRecords+" records generated successfully.");
        BigDecimal bdResult = new BigDecimal((((double)iTotal/noOfRecords)*100)).setScale(1,BigDecimal.ROUND_HALF_UP);
        print(bdResult+ "% ("+iTotal+") of our indexed plants are dead (vitality 0)");
        print("meaning that " +(new BigDecimal((((double)(noOfRecords-iTotal)/noOfRecords)*100)).setScale(1,BigDecimal.ROUND_HALF_UP)) +
              "% (" +(noOfRecords-iTotal)+ ") of our specimens are alive.");
        print("\t------INITIAL DATA STATISTICS------");

        while(iOption != 0) {
            print("Menu");
            print("1.   BubbleSort record archive");
            print("2.   InsertionSort record archive");
            print("3.   SelectionSort record archive");
            print("4.   QuickSort record archive");
            print("5.   All of them!");
            print("0.   Quit");
            iOption = in.nextInt();

            if(iOption != 0) {
                print("\nThe sorting of the strings is about to start.");
            }
            switch(iOption) {
                case 1: case 5:
                    print("\nThe Bubble Sort");

                    print("\n\nThe unsorted data is:\n");
                    printRecords(soBubbleSort.getData());
                    soBubbleSort.startTimer();
                    SortBy.bubble1f(soBubbleSort.getData());
                    print("\n\nThe sorted data is (1 field):\n");
                    printRecords(soBubbleSort.getData());
                    SortBy.bubble2f(soBubbleSort.getData());
                    soBubbleSort.stopTimer();
                    print("\n\nThe sorted data is (2 fields):\n");
                    printRecords(soBubbleSort.getData());
                    print("---------------\n");
                    if(iOption != 5) {
                        print("Sorting stats:");
                        soBubbleSort.statistics();
                        print("\n\n");
                        break;
                    }
                case 2:
                    print("\nThe Insertion Sort");

                    print("\n\nThe unsorted data is:\n");
                    printRecords(soInsertionSort.getData());
                    soInsertionSort.startTimer();
                    SortBy.insertion1f(soInsertionSort.getData());
                    print("\n\nThe sorted data is (1 field):\n");
                    printRecords(soInsertionSort.getData());
                    SortBy.insertion2f(soInsertionSort.getData());
                    soInsertionSort.stopTimer();
                    print("\n\nThe sorted data is (2 fields):\n");
                    printRecords(soInsertionSort.getData());
                    print("---------------\n");
                    if(iOption != 5) {
                        print("Sorting stats:");
                        soInsertionSort.statistics();
                        print("\n\n");
                        break;
                    }
                case 3:
                    print("\nThe Selection Sort");

                    print("\n\nThe unsorted data is:\n");
                    printRecords(soSelectionSort.getData());
                    soSelectionSort.startTimer();
                    SortBy.selection1f(soSelectionSort.getData());
                    print("\n\nThe sorted data is (1 field):\n");
                    printRecords(soSelectionSort.getData());
                    SortBy.selection2f(soSelectionSort.getData());
                    soSelectionSort.stopTimer();
                    print("\n\nThe sorted data is (2 fields):\n");
                    printRecords(soSelectionSort.getData());
                    print("---------------\n");
                    if(iOption != 5) {
                        print("Sorting stats:");
                        soSelectionSort.statistics();
                        print("\n\n");
                        break;
                    }
                case 4: // doesnt work
                    print("\nThe Quick Sort");

                    print("\n\nThe unsorted data is:\n");
                    printRecords(soQuickSort.getData());
                    soQuickSort.startTimer();
                    soQuickSort.setData(SortBy.quickSort(soQuickSort.getData(),1));
                    print("\n\nThe sorted data is (1 field):\n");
                    printRecords(soQuickSort.getData());
                    soQuickSort.setData(SortBy.quickSort(soQuickSort.getData(),2));
                    soQuickSort.stopTimer();
                    print("\n\nThe sorted data is (2 fields):\n");
                    printRecords(soQuickSort.getData());
                    print("---------------\n");
                    if(iOption != 5) {
                        print("Sorting stats:");
                        soQuickSort.statistics();
                        break;
                    } else {
                        print("Overall stats:");
                        soBubbleSort.statistics();
                        soInsertionSort.statistics();
                        soSelectionSort.statistics();
                        soQuickSort.statistics();

                    }
                case 0:
                    print("Quitting...");
                    iOption = 0;
                    break;
                default:
                    print("Not a valid option");
            }
        }
    }
}

class Tools extends Display {
    private static final Runtime s_runtime = Runtime.getRuntime();

    public static int toInt(String n) {
        return Integer.parseInt(n);
    }
    public static int toInt(long l) {
        return (int)l;
    }
    public static long getTime() {
        return new Date().getTime();
    }
    protected static long getMemoryStatus()
    {
        long mem;

        runGC();
        mem = usedMemory();
        return mem;
    }

    private static void runGC()
    {
        for(int count = 0; count < 10; ++count)
        {
            _runGC();
        }
    }

    private static void _runGC()
    {
        long usedMem1 = usedMemory();
        long usedMem2 = Long.MAX_VALUE;

        for(int i = 0; usedMem1 < usedMem2 && i < 5000; ++i)
        {
            s_runtime.runFinalization();
            s_runtime.gc();
            Thread.currentThread();
            Thread.yield();
            usedMem2 = usedMem1;
            usedMem1 = usedMemory();
        }
    }

    private static long usedMemory()
    {
        return s_runtime.totalMemory() - s_runtime.freeMemory();
    }

}

class SortObj extends Tools {
    private String sName;
    private long lProcessStart;
    private long lProcessEnd;
    private long lSortDuration = 0;
    private long lInitialMem;
    private long lEndMem;
    private long lMemUse = 0;
    private Data sortData = new Data();

    public SortObj(String s) {
        this.sName = s;
    }

    public Data getData() {
        return this.sortData;
    }
    public void setData(Data d) {
        this.sortData = d;
    }
    public void startTimer() {
        this.setStartTime(getTime());
        this.setInitialMem(getMemoryStatus());
    }
    public void stopTimer() {
        this.setEndTime(getTime());
        this.setEndMem(getMemoryStatus());

        if(this.getStartTime() > 0) this.setSortDuration(this.getEndTime()-this.getStartTime());
    }
    private void setStartTime(long lProcessStart) {
        this.lProcessStart = lProcessStart;
    }
    private long getStartTime() {
        return lProcessStart;
    }
    private void setEndTime(long lProcessEnd) {
        this.lProcessEnd = lProcessEnd;
    }
    private long getEndTime() {
        return lProcessEnd;
    }
    public void setSortDuration(long lSortDuration) {
        this.lSortDuration = lSortDuration;
    }
    public long getSortDuration() {
        return lSortDuration;
    }
    private void setInitialMem(long lInitialMem) {
        this.lInitialMem = lInitialMem;
    }
    private long getInitialMem() {
        return lInitialMem;
    }
    private void setEndMem(long lEndMem) {
        this.lEndMem = lEndMem;

        if(!Integer.toString(toInt(this.getInitialMem())).equals(null)) this.setMemUsage(this.getEndMem()-this.getInitialMem());
    }
    private long getEndMem() {
        return lEndMem;
    }
    private void setMemUsage(long lMemUse) {
        this.lMemUse = lMemUse;
    }
    public long getMemUsage() {
        return Math.abs(lMemUse);
    }
    public void setName(String sName) {
        this.sName = sName;
    }
    public String getName() {
        return sName;
    }
    public void statistics() {
        showStatistics(this.getName(), this.getSortDuration(), this.getMemUsage());
    }
}

class SortBy extends Tools {
    public static void bubble1f(Data elements) {
        int n = elements.size();
        boolean swapMade = true;
        Record temp;
        int passNo = 0;

        while(swapMade) {
            passNo++;
            swapMade = false;
            for(int i = 0; i < n - passNo; i++) {
                if (elements.recordAt(i).getTreatment().compareTo(elements.recordAt(i+1).getTreatment()) > 0) {
                    temp = elements.recordAt(i + 1);
                    elements.removeRecordAt(i + 1);
                    elements.addRecord(i, temp);
                    swapMade = true;
                }
            }
        }
    }
    public static void bubble2f(Data elements) {
        int n = elements.size();
        boolean swapMade = true;
        Record temp;
        int passNo = 0;

        while(swapMade) {
            passNo++;
            swapMade = false;
            for(int i = 0; i < n - passNo; i++) {
                if (elements.recordAt(i).getVitality().compareTo(elements.recordAt(i + 1).getVitality()) > 0) {
                    //next if is important to make sure we sort by 2 fields PROPERLY.
                    if(toInt(elements.recordAt(i).getVitality()) >= toInt(elements.recordAt(i+1).getVitality())) {
                        temp = elements.recordAt(i + 1);
                        elements.removeRecordAt(i + 1);
                        elements.addRecord(i + 1, elements.recordAt(i));
                        elements.removeRecordAt(i);
                        elements.addRecord(i, temp);
                        swapMade = true;
                    }
                }
            }
        }
    }
    public static Data InsertionSort(Data rawdata){
        // Insertion Sort Method
        // Starts at the beginning of the list, compares the next object to the previous objects and shifts down until in the correct position

        for (int i=1;i<rawdata.size();i++){
                // Start at the second element of the list and compare each preceding element

                int cur = i;
                Record held = (Record) rawdata.remove(cur); // Hold the element in limbo

                while (cur > 0 && toInt(held.getVitality()) < toInt(((Record) rawdata.elementAt(cur-1)).getVitality())) {
                        // Compare the held item to the previous item. If it is smaller or not at the beining of the list then continue looping
                        cur--;
                }

                //once the right position is found, take the held element and insert it into that position and continue to the next object
                rawdata.insertElementAt(held, cur);
        }
        return rawdata;
    }
    public static void insertion1f(Data elements) {
        int n = elements.size();

        for (int i = n - 1; i > 0; i--) {
            Record current = elements.recordAt(i-1);
            int j = i - 1;
            for (; j < n - 1 && current.getTreatment().compareTo(elements.recordAt(j+1).getTreatment()) > 0; j++) {
                elements.setElementAt(elements.recordAt(j+1), j);
            }
            elements.setElementAt(current, j);
        }
    }
    public static void insertion2f(Data elements) {
        int n = elements.size();

        for (int i = n - 1; i > 0; i--) {
            Record current = elements.recordAt(i-1);
            int j = i - 1;
            for (; j < n - 1 && current.getVitality().compareTo(elements.recordAt(j+1).getVitality()) > 0; j++) {
                try {
                    if(toInt(elements.recordAt(i).getVitality()) >= toInt(elements.recordAt(i+1).getVitality())) {
                        elements.setElementAt(elements.recordAt(j+1), j);
                    }
                } catch(Exception e) {}
            }
            elements.setElementAt(current, j);
        }
    }
    public static void selection1f(Data elements) {
        int n = elements.size();
        for (int i = 0; i < n - 1; i++) {
            Record current = elements.recordAt(i);
            int k = i;
            for (int j = i + 1; j <= n - 1; j++) {
                if (current.getTreatment().compareTo(elements.recordAt(j).getTreatment()) > 0) {
                    k = j;
                    current = elements.recordAt(k);
                }
            }
            if (k != i) {
                elements.removeRecordAt(k);
                elements.addRecord(i, current);
            }
        }
    }
    public static void selection2f(Data elements) {
        int n = elements.size();
        for (int i = 0; i < n - 1; i++) {
            Record current = elements.recordAt(i);
            int k = i;
            for (int j = i + 1; j <= n - 1; j++) {
                if (current.getVitality().compareTo(elements.recordAt(j).getVitality()) > 0) {
                    if(toInt(elements.recordAt(i).getVitality()) >= toInt(elements.recordAt(i+1).getVitality())) {
                        k = j;
                        current = elements.recordAt(k);
                    }
                }
            }
            if (k != i) {
                elements.removeRecordAt(k);
                elements.addRecord(i, current);
            }
        }
    }
    private static void quickSortMain(Data rawdata, int low, int high) {

        int left = low;
        int right = high;
        Record pivot = (Record) rawdata.elementAt((left+right)/2);

        do {
                while (toInt(((Record) rawdata.elementAt(left)).getVitality()) < toInt(pivot.getVitality())) left++;
                while (toInt(((Record) rawdata.elementAt(right)).getVitality()) > toInt(pivot.getVitality())) right--;

                if (left <= right) {
                        Collections.swap(rawdata, left, right);
                        left++;
                        right--;
                }

        }while(left <= right);

        if (low < right) quickSortMain(rawdata, low, right);
        if (left < high) quickSortMain(rawdata, left, high);

    }

    private static void quickSortSub(Data rawdata, int low, int high){

        int left = low;
        int right = high;
        Record pivot = (Record) rawdata.elementAt((left+right)/2);

        do {
                while (((Record) rawdata.elementAt(left)).getTreatment().compareTo(pivot.getTreatment()) < 0) left++;
                while (((Record) rawdata.elementAt(right)).getTreatment().compareTo(pivot.getTreatment()) > 0) right--;

                if (left <= right) {
                        Collections.swap(rawdata, left, right);
                        left++;
                        right--;
                }
        }while(left <= right);

        if (low < right) quickSortSub(rawdata, low, right);
        if (left < high) quickSortSub(rawdata, left, high);
    }
    public static Data quickSort(Data rawdata, int fields) {

        quickSortMain(rawdata, 0, rawdata.size()-1);

        int lbound[] = new int[6];
        int ubound[] = new int[6];
        int index = 0;
        for (int i=0;i<6;i++){
            if (toInt(((Record) rawdata.elementAt(index)).getVitality()) != i) {
                continue;
            }else{
                lbound[i] = index;
            }
            while(toInt(((Record) rawdata.elementAt(index)).getVitality()) == i && index<rawdata.size()-1) index++;
            ubound[i] = (index == rawdata.size()-1) ? index : index-1;
        }

        if(fields == 2) {
            for (int i=0;i<6;i++) quickSortSub(rawdata, lbound[i], ubound[i]);
        }
        return rawdata;
    }
}

class Record
{
    private String id;
    private String vitality;
    private String treatment;


    public void setTreatment(String name) {
        this.treatment = name;
    }
    public void setVitality(String vitality) {
        this.vitality = vitality;
    }
    public void setId(String id) {
        this.id = id;
    }

    public String getId() {
        return id;
    }
    public String getTreatment() {
        return treatment;
    }
    public String getVitality() {
        return vitality;
    }
}

class Data extends Vector<Object>
{
    /**
     *
     */
    private static final long serialVersionUID = -5786785034903546138L;


    public Record recordAt(int index)
    {
        return (Record) elementAt(index);
    }

    public void addRecord(Record record)
    {
        addElement(record);
    }

    public void addRecord(int position, Record record)
    {
        add(position, record);
    }

    public void removeRecordAt(int position)
    {
        removeElementAt(position);
    }
}

class Display
{
    public static void showStatistics(String operation, long millis, long space)
    {
        showTime(operation, millis);
        showMemory(operation, space);
    }

    private static void showTime(String operation, long millis)
    {
        long millisecs = millis % 1000;
        long secsTemp = (millis - millisecs) / 1000;
        long secs = secsTemp % 60;
        long mins = (secsTemp - secs) / 60;
        String padding1;
        String padding2;
        String padding3;
        int padLength;

        padLength = 20 - operation.length();
        padding1 = new String();
        for(int index = 0; index < padLength; index++)
        {
            padding1 = padding1.concat(" ");
        }
        if(secs < 10)
        {
            padding2 = new String("0");
        }
        else
        {
            padding2 = new String("");
        }
        if(millisecs < 10)
        {
            padding3 = new String("00");
        }
        else if(millisecs < 100)
        {
            padding3 = new String("0");
        }
        else
        {
            padding3 = new String("");
        }
        System.out.print(operation + padding1 + " time: " + mins + ":" + padding2 + secs + ":");
        System.out.print(padding3 + millisecs);
    }

    private static void showMemory(String operation, long space)
    {
        if(!operation.equals("Saving to disk"))
        {
            System.out.println("\tSpace used: " + space + " bytes");
        }
    }