// add, print and delete a number from a binary min heap

#include <iostream>
using namespace std;

// node containing int value and left and right pointers
// constructor, get value, get right, get left, set value, set left, set right
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

//insert print and delete methods for the min heap
class heap
{
  private:
  heapNode *root;
  int counter;

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

  //insert new value, check to see if swap is needed
  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())
      {
	int tempParentLeft = parent->getLeft()->getValue();
        int tempParent = parent->getValue();
        parent->setValue(tempParentLeft);
        parent->left->setValue(tempParent);
      }
    }
    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())
      {
        int tempParentRight = parent->getRight()->getValue();
        int tempParent = parent->getValue();
        parent->setValue(tempParentRight);
        parent->right->setValue(tempParent);
      }
    }
  }

  // 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);
    }
  }
   
  //call printNode
  void print()
  {
    cout << "Printing the heap...\n";
    printNode(root, 0);
  }
  
  //print tree with spaces for levels of the tree
  void printNode(heapNode *node, int level)
  {
    if(node != NULL)
    {
       printNode(node->getLeft(), level + 1);
      for(int i = 0; i < level; i++)
        cout << "\t";
      cout << node->getValue();
      cout << "\n";
      printNode(node->getRight(), level + 1);
     }
    }

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

  int realDelete(int ar[], int pos, heapNode *parent)
  {
    heapNode *tempNode;
    if(parent->getLeft() == NULL)
    {
      if (ar[pos] == 0)
      {
	tempNode = parent;
        parent = NULL;
      }
      else
	realDelete(ar, pos-1, parent->left);
    }
    else if(parent->getRight() == NULL)
    {
	if (ar[pos] == 1)
	{
	  tempNode = parent;
          parent = NULL;
        }
	else
	  realDelete(ar, pos-1, parent->right);
    }

    return tempNode->getValue();
  } 


  //delete the root
  /*int realDelete(int ar[], int pos, heapNode *parent)
  {
    heapNode *tempNode = NULL;
    if(pos == 0)
    {
      if (ar[pos] == 0)
      {
        tempNode = root;
        parent = NULL;
      }
      else if(ar[pos] == 1)
      {
	 tempNode = root;
         parent = NULL;
      }
    }
      else
       realDelete(ar, pos-1, parent);

    return tempNode->getValue();
    }*/

  //perculate down to reorganize tree
  void purculateDown(heapNode *parent)
  {
    if(parent->getValue() > parent->left->getValue())
    {
        int tempParentLeft = parent->getLeft()->getValue();
        int tempParent = parent->getValue();
        parent->setValue(tempParentLeft);
        parent->left->setValue(tempParent);
    }
    else if(parent->getValue() > parent->right->getValue())
    {
       int tempParentRight = parent->getRight()->getValue();
       int tempParent = parent->getValue();
       parent->setValue(tempParentRight);
       parent->right->setValue(tempParent);
    }
  } 

  // find the the last spot for deletion
  void deleteSpot()
  {
    //heapNode *newRoot = new heapNode(option);
    //heapNode *deleteNode = new heapNode(option);

    if (root == NULL) 
      cout << "Error.  The tree is empty.\n";
    else if(counter == 1)
      {
	root = NULL;
      }
    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;
      realDelete(ar, i, root);
      root->setValue(realDelete(ar, i, root));
      purculateDown(root);
      counter--;
    
    }
  }

  }; // end of heap class

// menu with add, print, delete choices  call methods from heap class
int main()
{
  int option;
  int value;
  heap *myHeap;
  myHeap = new heap();
 

  while(option != 4)
  {
    cout << "1. Add a value. \n"
         << "2. Print the heap. \n"
         << "3. Delete the root. \n"
         << "4. Quit. \n"
         << "Please make a selection: ";
    cin >> option;

    if(option == 1)
    {
      cout << "Please enter a value: ";
      cin >> value;
      myHeap->insertSpot(value);
    }

    if(option == 2)
      myHeap->print(); 

    if(option == 3)
      myHeap->deleteSpot();   
  }
  return 0;
}