// skewheap.cpp: implementation of the skewheap class.
//
//////////////////////////////////////////////////////////////////////

#include "skewheap.h"
#include <iostream.h>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

skewheap::skewheap()
{
	element = -1;
	root = true;
	left =0;
	right = 0;
}

skewheap::~skewheap()
{
	if ((left != 0) && !(left->root))
			delete left;
	if ((right !=0) && !(right->root))
			delete right;
}

skewheap::skewheap(int el)
{
	element = el;
	root = true;
	left = 0;
	right = 0;
}

skewheap::skewheap(int el, skewheap * l, skewheap * r)
{
	element = el;
	left = l;
	right = r;
}




void skewheap::print()
{
	print(0);
	char c;
	cout << "--------------";
	cin >> c;
}

void skewheap::print(int spaces)
{
	if (right != 0)
		right->print(spaces + 3);
	for (int i=0;i< spaces;i++)
		cout << " ";
	cout << element << endl;
	if (left != 0)
		left->print(spaces + 3);
}

void skewheap::insert(int x)
{
//forgot to put this in main.cpp, so it will not be graded.
}

int skewheap::deleteMin()
{
	int n = element;
	left = merge(left, right); //left is now new heap
	if (left == 0) return n;
	element = left->element; //move left "up"
	right = left->right;
	left = left->left;
	return n;
}

skewheap::skewheap(skewheap & s)
{
	element = s.element;
	if (s.left == 0)
		left = 0;
	else
		left = new skewheap(*s.left);
	if (s.right == 0)
		right = 0;
	else
		right = new skewheap(*s.right);
}

skewheap * merge(skewheap * h1, skewheap * h2)
// merges them.
{
//	h1 = mergethem(h1, new skewheap(*h2));
//	h1->root = false;
//	h2->root = false;
	skewheap * res = mergethem(h1, h2);
//	res->root = true;
	return res;
}


skewheap * mergethem(skewheap * h1, skewheap * h2)
{
	if (h1 == 0) 
		return h2;
	if (h2 == 0) 
		return h1; // h1 is the answer
	if (h2->element < h1->element) {
		skewheap * temp = h1;
		h1 = h2;
		h2 = temp;
	}
	if (h1->left == 0)
		h1->left = h2;
	else {
		h1->right = mergethem(h1->right, h2);//NOT merge
		skewheap * temp = h1->left;
		h1->left = h1->right;
		h1->right = temp;
	};
	return h1;
}