/* Copyright (C) 2009  CSE,IIT Bombay  http://www.cse.iitb.ac.in

This file is part of the ConStore open source storage facility for concept-nets.

ConStore is free software and distributed under the 
Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License;
you can copy, distribute and transmit the work
with the work attribution in the manner specified by the author or licensor.
You may not use this work for commercial purposes and may not alter, 
transform, or build upon this work.

Please refer the legal code of the license, available at
http://creativecommons.org/licenses/by-nc-nd/3.0/legalcode

ConStore is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  */

package iitb.con.util;

/**
 * 2D int array heap sort. Sorts based on the first column
 * 
 * @author Prathab K
 *
 */

/*
 * Based on the explanation of heap sort at 
 * http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm
 */

public class Int2DHeapSort {

    private static int[][] a;
    private static int n;
    private static int index = 0;

    /**
     * Sorts the 2d int array based on the first column as the key
     * @param array 2d int array
     */
    public static void sort(int[][] array)
    {
        a = array;
        n = a.length;
        heapsort();
    }

    private static void heapsort()
    {
        buildheap();
        while (n>1)
        {
            n--;
            exchange (0, n);
            downheap (0);
        } 
    }

    private static void buildheap()
    {
        for (int v=n/2-1; v >=0; v--)
            downheap (v);
    }

    private static void downheap(int v)
    {
        int w = 2 * v + 1;    
        while (w<n)
        {
            if (w+1<n)  
                if (a[w+1][index] > a[w][index]) 
                    w++;

            if (a[v][index] >= a[w][index]) 
                return;
            exchange(v, w); 
            v = w;        
            w = 2 * v + 1;
        }
    }

    private static void exchange(int i, int j)
    {
        int[] t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}