// File:            treePrint.cpp
// ---------------------------------------------------------------------
//          Author: Russell Lowke,  lowke@fas.harvard.edu
//              TF: Francis Crick
//            Date: 7/29/2002
//      Assignment: Unit 6 Easy Supp programming exercises
//         Version: 1
//
//     Description: write a program that lets the user type a row of integers, and then
//					display the integers in a tree format, showing each position i above
//					positions 2 * i and 2 * i + 1
//
//         Methods:
//
//           Notes:
// 

#include <iostream>
#include <iomanip>
#include <cmath>
#include <values.h>

const int MAXENTERIES = 100;  				// max number of enteries

//
//  reads an integer from the keyboard,
//  uses error checking to ensure value is between minValue and maxValue
//
int getInt(char askStr[], int minValue, int maxValue)
{
	int mVar;
	bool inputOK = false;
	
	while (! inputOK) { 
		
		cout << askStr;						// ask query
		cin >> mVar;						// get input
		
		if ( (mVar >= minValue && mVar <= maxValue) )
			inputOK = true;					// input OK, exit loop
		else {
			cout << "Bad input: please enter a value between "
			     << minValue << " and " << maxValue << endl;
			cin.clear();					// clear error [see  cin.fail();]
			cin.ignore(80, '\n');			// empty buffer
		}
	}
	
	return mVar;
}


//
//  reads a list of integers from the keyboard,
//
int getIntList(char askStr[], int * intList, int endSig, int maxList)
{
	int  v = 0, n = 0;
	char c = '\0';
	
	// seed first value as 0
	*intList = 0;
	intList++;
	
	cout << askStr;
	
	do {
		cin >> v;
		c = cin.get();
		
		if ( cin.fail() ) {
			cout << "BAD input." << endl;
			cin.clear();					// clear error
			cin.ignore(80, '\n');			// empty buffer
			return -1;
		} else {
			*intList = v;
			intList++;
			n++;
		}
	} while ( c != '\n' && n < MAXENTERIES);
	
	return n;
}

bool testForSmallestAtTop(int * array, int n)
{
	bool smallest = true;
	int  leftChild, rightChild;
	
	// check that children are greater
	for (int i = 1; i <= n; i++) {
	
		if ( i * 2 > n) {
			leftChild = MAXINT;
		} else {
			leftChild  = array[i*2];
		}
		
		if ( i * 2 + 1 > n) {
			rightChild = MAXINT;
		} else {
			rightChild = array[i*2 + 1];
		}
		
		if ( array[i] > leftChild || array[i] > rightChild ) {
			smallest = false;
		}
	}
	
	return smallest;
}


//
// prints the array
//
void printArray(int * array, int n)
{
	cout << "{ ";
	for (int i = 0; i < n; i++) {
		cout << array[i] << " ";
	}
	cout << "}" << endl;
}


void printTree(int * array, int n)
{
	int    width = 80, shift = width / 2;
	int    lineCount = 0;
	double breakAt   = 0;
	bool   nwLine    = true;
	
	for (int i = 1; i <= n ; i++) {
	
		if (nwLine) {
			cout << setw(shift) << array[i];
			nwLine = false;
		} else {
			cout << setw(width) << array[i];
		}
		
		if ( i == breakAt + 1) {
		
			lineCount++;
			width = shift;
			shift = shift / 2;
			if (shift < 3) {
				shift = 3;
			}
			breakAt += pow(2, lineCount);
			
			cout << endl;
			nwLine = true;
		}
	}
	cout << endl;
}


int main()
{
	int array[MAXENTERIES];
	int n = -1;
	
	// get array of numbers
	while (n == -1) {
		n = getIntList("Type the numbers: ", array, -1, MAXENTERIES);
	}
	
	printArray(array, n);
	
	printTree(array, n);
	
	if ( testForSmallestAtTop(array, n) ) {
		cout << "This IS a smallest-at-top heap!" << endl;
	} else {
		cout << "This is NOT a smallest-at-top heap." << endl;
	}
	
	exit (0);
}