/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package org.broad.igv.util;

import java.util.Comparator;
import java.util.List;

/* HeapSort.java
 * Copyright 1997 Joel Peterson.
 * All rights reserved.
 *
 * Permission to use and distribute unmodified copies of this file is freely
 * granted, provided that this notice is included and credit is given.
 *
 * The following HTML source is an example of acceptable credit.  It should
 * be included on your web page in close proximity to your use of this code:
 *
 * (APPLICATION NAME) makes use of Java classes provided by
 * <A HREF="http://www.geocities.com/SiliconValley/Peaks/3639/javastuff.html">
 * Joel Peterson</A>.
 *
 * Permission to modify, use and distribute copies of this file is granted
 * provided that the above terms are followed and a disclaimer of the changes
 * made is included.
 *
 * Because the program is licensed free of charge, there is no warranty
 * for the program, to the extent permitted by applicable law.  Except when
 * otherwise stated in writing the I provide the program "as is" without
 * warranty of any kind, either expressed or implied, including, but not
 * limited to, the implied warranties of merchantability and fitness for
 * a particular purpose.  The entire risk as to the quality and performance
 * of the program is with you.  Should the program prove defective, you
 * assume the cost of all necessary servicing, repair or correction.
 *
 * In no event unless required by applicable law or agreed to in writing will
 * I be liable to you for damages, including any general, special, incidental
 * or consequential damages arising out of the use or inability to use the
 * program (including but not limited to loss of data or data being rendered
 * inaccurate or losses sustained by you or third parties or a failure of the
 * program to operate with any other programs), even if such holder or other
 * party has been advised of the possibility of such damages.
 */
/** Class for JAVA 1.1 containing static methods to sort an arbitrary array
 *  of JAVA objects which implement the Comparable interface.
 * @author Joel Peterson, 1997
 * @modified Jim Robinosn 2009
 *     changed form arrays to lists
 *     introduced generics
 *
 * This algorithm is ~ 4x slower than the java collections sort,  but does not consume any extra
 * memory
 *
 **/
public class HeapSort {

    private static int left(int i) {
        return 2 * i + 1;
    }

    private static int right(int i) {
        return 2 * i + 2;
    }

    public static <T> void sort(List<T> list, Comparator<T> c) {
        sort(list, 0, list.size() - 1, c);
    }

    static <T> void sort(List<T> list, int lo0, int hi0, Comparator<T> c) {

        int sortsize = list.size();
        int i, top, t, largest, l, r, here;
        T temp;

        if (sortsize <= 1) {
            return;
        }

        top = sortsize - 1;
        t = sortsize / 2;

        do {
            --t;
            largest = t;

            /* heapify */

            do {
                i = largest;
                l = left(largest);
                r = right(largest);

                if (l <= top) {
                    if (c.compare(list.get(l), list.get(i)) > 0) {
                        largest = l;
                    }
                }
                if (r <= top) {
                    if (c.compare(list.get(r), list.get(largest)) > 0) {
                        largest = r;
                    }
                }
                if (largest != i) {
                    temp = list.get(largest);
                    list.set(largest, list.get(i));
                    list.set(i, temp);
                }
            } while (largest != i);
        } while (t > 0);

        t = sortsize;

        do {
            --top;
            --t;

            here = t;

            temp = list.get(here);
            list.set(here, list.get(0));
            list.set(0, temp);

            largest = 0;

            do {
                i = largest;
                l = left(largest);
                r = right(largest);

                if (l <= top) {
                    if (c.compare(list.get(l), list.get(i)) > 0) {
                        largest = l;
                    }
                }
                if (r <= top) {
                    if (c.compare(list.get(r), list.get(largest)) > 0) {
                        largest = r;
                    }
                }
                if (largest != i) {
                    temp = list.get(largest);
                    list.set(largest, list.get(i));
                    list.set(i, temp);
                }
            } while (largest != i);
        } while (t > 1);
    }

    static void sort(int[] array, int lo0, int hi0, Comparator<Integer> c) {

        int sortsize = array.length;
        int i, top, t, largest, l, r, here;
        Integer temp;

        if (sortsize <= 1) {
            return;
        }

        top = sortsize - 1;
        t = sortsize / 2;

        do {
            --t;
            largest = t;

            /* heapify */

            do {
                i = largest;
                l = left(largest);
                r = right(largest);

                if (l <= top) {
                    if (c.compare(array[l], array[i]) > 0) {
                        largest = l;
                    }
                }
                if (r <= top) {
                    if (c.compare(array[r], array[largest]) > 0) {
                        largest = r;
                    }
                }
                if (largest != i) {
                    temp = array[largest];
                    array[largest] = array[i];
                    array[i] = array[temp];
                }
            } while (largest != i);
        } while (t > 0);

        t = sortsize;

        do {
            --top;
            --t;

            here = t;

            temp = array[here];
            array[here] = array[0];
            array[0] = array[temp];

            largest = 0;

            do {
                i = largest;
                l = left(largest);
                r = right(largest);

                if (l <= top) {
                    if (c.compare(array[l], array[i]) > 0) {
                        largest = l;
                    }
                }
                if (r <= top) {
                    if (c.compare(array[r], array[largest]) > 0) {
                        largest = r;
                    }
                }
                if (largest != i) {
                    temp = array[largest];
                    array[largest] = array[i];
                    array[i] = array[temp];
                }
            } while (largest != i);
        } while (t > 1);
    }
}
