// Created by Igor Markov
// April 19, 2001 
//  This file implements the makeBalancedBST() function
//  for problem 4 of the practice final.
//  There is also a driver, so that this file can be compiled and ran
//  (drivers are not required for the actual final)

#include <math.h>
#include <iostream>
#include <algorithm>


unsigned getPivotIndex(unsigned u)
{  
   unsigned pow=1, tmp=u;
   while (tmp) { pow*=2; tmp/=2; }
   // now pow is the smallest power of two greater than u
   if ( pow-(pow/4)-1<=u) return pow/2-1;  // 50%+ of leaves are in
   else return (pow/4 + u % (pow/4));      //<50%  of leaves are in
}

void makeBalancedBST_rec(int *begin, int size);

void makeBalancedBST    (int *begin, int size)
{
    sort(begin,begin+size); // only need to sort once
    makeBalancedBST_rec(begin,size); // call recursive helper function
}

void makeBalancedBST_rec(int *begin, int size)
{
   if (size<=1) return;
   int pivotIndex= getPivotIndex(size);  // the index of the new BST root

   makeBalancedBST_rec(begin,pivotIndex);// BSTify the left side
   if (size>pivotIndex+1)                // BSTify the right side if exists
     makeBalancedBST_rec(begin+pivotIndex+1,size-pivotIndex-1);

   unsigned tmp[size], nCopy=1, i=0, j=pivotIndex+1, k=1;
   tmp[0]=begin[pivotIndex];             // write the pivot into root
   for( ; i<pivotIndex; nCopy*=2)        // merge two balanced BSTs into tmp
   {
      copy(begin+i,begin+i+nCopy,tmp+k);
      i+=nCopy;
      k+=nCopy;
      if (j < size)
      {
          copy(begin+j,begin+j+nCopy,tmp+k);
          j+=nCopy;
          k+=nCopy;
      }
   }
   copy(tmp,tmp+size,begin);             
}

int main()
{  // this is a driver program for the above function
   // it is not a part of the solution of problem 4
   const unsigned N=8;
   int a[N],i;
   for(i=0; i!=N; i++) a[i]=static_cast<int>(10*i*sin(i))-i*i/20; // populate a

   cout << " Input array: " << endl;
   for(i=0; i!=N; i++) cout << a[i] << " " ; cout << endl;
   makeBalancedBST(a,N); 

   cout << " BST-ordered array: " << endl;
   for(i=0; i!=N; i++) cout << a[i] << " " ; cout << endl;

   return 0;
}