/* 
 * @(#)HeapSortAlgorithm.java 1.0 95/06/23 Jason Harrison
 *
 * Copyright (c) 1995 University of British Columbia
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation for NON-COMMERCIAL purposes and without fee is
 * hereby granted provided that this copyright notice appears in all
 * copies. Please refer to the file "copyright.html" for further
 * important copyright and licensing information.
 *
 * UBC MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT
 * LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
 * A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. UBC SHALL NOT BE
 * LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING,
 * MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 *
 * Modified for use with the Logger.java infrastructure
 */ 

/** 
 * A heap sort demonstration algorithm 
 * SortAlgorithm.java, Thu Oct 27 10:32:35 1994 
 *
 * We have modified this code to log events while sorting the array.
 * The final result is printed at the finish of sorting.
 *
 * @author Jason Harrison@cs.ubc.ca
 * @version 1.0, 23 Jun 1995
 */ 
public class HeapSortAlgorithm {
  private static Logger log = null;
  
  public static void sort(int a[]) {
    log.addMethodEntry(null,"HeapSortAlgorithm.sort");
    int N = a.length;
    for (int k = N/2; k > 0; k--) {
      downheap(a, k, N);
    }
    do {
      int T = a[0];
      a[0] = a[N - 1];
      a[N - 1] = T;
      N = N - 1;
      downheap(a, 1, N);
    } while (N > 1);
    log.addMethodExit(null,"HeapSortAlgorithm.sort");
  } 
  
  private static void downheap(int a[], int k, int N) {
    log.addMethodEntry(null,"HeapSortAlgorithm.downheap");
    int T = a[k - 1];
    while (k <= N/2) {
      int j = k + k;
      if ((j < N) && (a[j - 1] < a[j])) {
        j++;
      }
      if (T >= a[j - 1]) {
        break;
      } else {
        a[k - 1] = a[j - 1];
        k = j;
      }
    }
    a[k - 1] = T;
    log.addMethodExit(null,"HeapSortAlgorithm.downheap");
  }

  public static void main(String[] args) throws java.net.UnknownHostException {
    log = new Logger(new LocalLog(100));
//     log = new Logger(new RemoteLogClient
//      (java.net.InetAddress.getByName("localhost"),RemoteLogClient.PORT));
    int x[] = { 1, 5, 5, 7, 8, 10, 1, 5, 145, 2 };
    sort(x);
    log.printAll(1000);
  }
}