#include <iostream>
using namespace std;

class heapNode
{
  private:
  int value;

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

  //set value
  void setValue(int newValue)
  {
    value = newValue;
  }

  // set right
  void setRight(heapNode *newRight)
  {
    right = newRight;
  }

  // set left
  void setLeft(heapNode *newLeft)
  {
    left = newLeft;
  }
  
}; // end of heapNode class

class heap
{
  private:
  heapNode *root;
  int counter;

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
  {
    if(ar[pos] == 0)
    {
      if (parent->getLeft() == NULL)
	parent->setLeft(newNode);
      else
	realInsert(ar, pos-1, parent->left, newNode);
      if(parent->getLeft()->getValue() < parent->getValue())
      {
	heapNode *tempParentLeft = new heapNode(parent->getLeft()->getValue());
        heapNode *tempParent = new heapNode(parent->getValue());
        parent->setValue(tempParent->getValue());
        parent->left->setValue(tempParentLeft->getValue());
      }
    }
    else if(ar[pos] == 1)
    {
	if (parent->getRight() == NULL)
	  parent->setRight(newNode);
	else
	  realInsert(ar, pos-1, parent->right, newNode);
      if(parent->getRight()->getValue() < parent->getValue())
      {
	heapNode *tempParentRight = new heapNode(parent->getRight()->getValue());
        heapNode *tempParent = new heapNode(parent->getValue());
        parent->setValue(tempParent->getValue());
        parent->right->setValue(tempParentRight->getValue());
      }
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    counter++;
    if(root == NULL)
    {
      root = newNode;
    }

    else
    {
      int arrayValue;
      bool isOne = false;
      int ar[32];
      int i;
      int temp = counter;
      for(i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          temp = temp / 2;
          ar[i] = arrayValue;
      }
 
      for(i = 0; i < 32; i++)
        cout << ar[i] << " ";
      cout << endl;

      i=31;
      while(i >= 0)
      {
        if(ar[i] == 1)
          isOne = true;
        if(isOne == true)
          break;
        i--;
      }
      i--;
      cout << "Broke loop with i = " << i << endl;
      realInsert(ar, i, root, newNode);
    }
  }
   
  //print
  void print()
  {
    cout << "Printing the heap...\n";
    printNode(root, 0);
  }

  void printNode(heapNode *node, int level)
  {
    if(node != NULL)
    {
      for(int i = 0; i <= level; i++)
      {     
        //cout << node->getValue()
          cout   << "\t"
             << "\t"
             << "\t"
	     << node->getValue() 
             << endl;
        printNode(node->getLeft(), level + 1);
        printNode(node->getRight(), level + 1);
      }
    }
  }

  // get root
  heapNode* getRoot()
  {
    return root;
  }

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    myHeap->print();

    }

  myHeap->print();
  return 0;
}