/////////////////////////////////////////////////////////////////
//
//  heap-sort.h   --   heap implementation
//
/////////////////////////////////////////////////////////////////

#include <iostream.h>
#include <vector.h>

// Functions for sorting a vector<T> in-place.

// A bit unsafe -- what if the name is already taken?
typedef int Index;

// A few definitions to clarify the procedings
inline int get_parent( int i ){ return (i-1)/2; }
inline int get_lchild( int i ){ return 2*i + 1; }
inline int get_rchild( int i ){ return 2*i + 2; }

// swap the value at pos with the larger of its children, if the latter
// is larger then the former (i.e. the heap property is violated at pos).
// Return the Index of the node with which pos was swapped, or -1
// is no swap occured.

// the Index pos is invalid if and only if  pos > last  , because
// the heap is complete => stored as a vector has no gaps

template<class T>
Index swap_with_larger_child( vector<T, allocator<T> >& heap, 
                              Index pos, Index last ){
  if( pos > last ) cout << "Error: invalid node." << endl;
  else{
    Index rchild = get_rchild( pos );
    Index lchild = get_lchild( pos );
    Index target;                          // swap with this
    if( lchild > last ){ //no left child
      if( rchild > last ) //no right child either
        return -1;
      else{ //check the right node
        if( heap[rchild] <= heap[pos] ) return -1; //no swap nedeed
        else target = rchild;   
      }
    }  
    else{ //left child exists
      if( rchild > last ){ //no right child, check left
        if( heap[lchild] <= heap[pos] ) return -1; //no swap needed
        else target = lchild;
      }
      else{ //both children exist, swap with largest
        if( heap[lchild] > heap[rchild] ) target = lchild;
        else target = rchild;
        if( heap[pos] > heap[target] ) //no swap needed
          return -1;
      }    
    }
    //swap with target needed, do it
    T tmp = heap[pos];
    heap[pos] = heap[target];
    heap[target] = tmp;
    return target;
  }  
}

// generic  adjust_heap  takes a vector, the (only) position
// where the heap property is violated, and the last Index
// where the heap ends in the vector<T>

template<class T>
void adjust_heap( vector<T, allocator<T> > & heap, Index pos, Index last ){
  Index current = pos;
  while( current <= last ){ 
    current = swap_with_larger_child( heap, current, last );
    if( current == -1 ) break;
  }
} 

template<class T>
void heap_sort( vector<T, allocator<T> > & heap ){

  if( heap.empty() ) return;   // vector is empty, nothing to sort
  Index last = heap.size() - 1;
  
  // Step 1: Heapify

  // start with the last parent in the tree, move towards the root
  // (in backward level-order)  

  //inv: subtree under node i is now a heap 
  for( int i = get_parent(last); i >= 0; i-- )
    adjust_heap( heap, i, last );
    
  // Step 2: Now sort the heap, shrinking it
  while( last > 0 ){
    //swap the first and the last
    T tmp = heap[0];
    heap[0] = heap[last];
    heap[last] = tmp;
    
    last--;   //shrink heap
    //the heap property is now violated at root. Restore it.
    adjust_heap( heap, 0, last );
  }  
}

/************************** good for debugging 
template<class T> 
void print( T& v) {
  typename T::iterator p = v.begin(); 
  while (p != v.end() )
    cout << *p++ << " ";
  cout << endl;
} *******************************************/            

///////////////////////////////////////////////////////////////////
//
//  heap-sort.cc   --   test heapsort on random arrays of int
//
///////////////////////////////////////////////////////////////////


#include <iostream>
#include <stdlib.h>
#include <vector>


#include "heap-sort.h"

const int MAX_VECTOR_SIZE = 30;
const int MAX_ENTRY = 100;

// ******************* print a generic object ***
template<class T> 
void print( T& v) {
  typename T::iterator p = v.begin(); 
  typename T::iterator e = v.end(); 
  while (p != e ){
    typename T::value_type aux = *p++;  //unnecessary, really
    cout << aux << " "; 
  }  
 cout << endl; 
}

// *** verify non-decreasing order in the object ***
template<class T>
bool verify_order(  T& v ){
  typename T::iterator p = v.begin();
  typename T::iterator e = v.end();
  typename T::iterator prev; 

  ++p;
  while (p != e ){
    prev = p;
    if( *(--prev) > *p++ ) return false;
  }
  return true;
}

main(){
 
  srand( 777 );  //random seed -- change it to get different results

  // test heap_sort by vectors of size <= MAX_VECTOR_SIZE 
  for( int n=1; n < MAX_VECTOR_SIZE; n++){

    vector<int, allocator<int> > v(n); //define and sort the array on size n   

    for(int i=0; i < n ; i++){
      int r = rand() / ( RAND_MAX / MAX_ENTRY );
      v[i] = r;
    }
    print( v );
    heap_sort( v );  
    print( v );
    if( verify_order( v ) ) cout << "OK\n";
    else cout << "ERROR!\n";
    cout << endl;
  }
}

/********* this is OK, except that it prints no spaces between integers :-)
template<class T>
void print( const T& obj ){
  copy( obj.begin(), obj.end(), 
	ostream_iterator<typename T::value_type>( cout ) );  
} ************************************************************************/