//Syed Rais AHmad
//Assignment # 9 Question 1
#include "stdafx.h"
#include<iostream.h>
#include<assert.h>

#define ORDER 3
//class Node of a multiway tree of order 3;
class mtNode
{
public:
	int info[ORDER-1];
	mtNode * subTree[ORDER];
	mtNode();
	bool IsEmpty();
	bool IsLeaf();
	int InsertInNode(int n);
};

mtNode::mtNode()
{
	int i=0;
	for(i=0;i<ORDER-1;i++) info[i]=-1;
	for(i=0;i<ORDER;i++) subTree[i]=NULL;
}

//if node is missing max # of elements in it return true
bool mtNode::IsEmpty()
{
	int i=0;bool result=false;
	if (this)
	{
		for(;i<ORDER-1 && !result;i++) if (info[i]==-1) result=true;
		return result;
	}
	return true;
}

bool mtNode::IsLeaf()
{
	int i=0;
	bool result = true;
	if (this)
	{
		for(i=0;i<ORDER;i++) if (subTree[i]) result=false;
		return result;
	}
	return false;
}

//insert int n in node in sorted order
int mtNode::InsertInNode(int n)
{
	int i=0,j=0,k=0,temp=0;
	if (IsEmpty())
	{
		for(i=0;i<ORDER-1;i++) if (info[i]==-1) {info[i]=n;break;}
		for(j=0;j<=i;j++)
		{
			for(k=j;k<=i;k++) 
				if (info[k]<info[j]) 
				{
					temp=info[j];
					info[j]=info[k];
					info[k]=temp;
				}
		}
		for(j=0;j<ORDER-1;j++) cout << info[j];cout << '\n';
		return 1;
	}
	return 0;
}


//CLASS TREE 
class Tree 
{
private:
	mtNode * root;
public:
	Tree(); 
	Insert(int);
	Delete(int);
	mtNode* Search(int);
};


Tree::Tree()
{
	root=new mtNode;
}

Tree::Insert(int n)
{
	mtNode * ptr;
	int i=0;
	bool last=true;
	
	ptr=root;
	while (!ptr->IsEmpty()) 
	{
		for(i=0;i<ORDER-1;i++) 
		{ 
			if (n<=ptr->info[i]) 
			{
				if (!ptr->subTree[i]) ptr->subTree[i]=new mtNode;
				ptr=ptr->subTree[i];
				last=false;
			}
		}
		if (last) {if (!ptr->subTree[i]) ptr->subTree[i]=new mtNode;ptr=ptr->subTree[i];}
		last=true;
		
	}
	ptr->InsertInNode(n);
}


mtNode* Tree::Search(int n)
{
	mtNode* ptr=root,*father=NULL;
	bool found=false;
	int i=0,index=0;
	while (ptr)
	{
		for(i=0;i<ORDER-1;i++) 
			if (ptr->info[i]==n) 
			{
				if (ptr->IsLeaf()) 
					father->subTree[index]=NULL;
				else
				{
					while(!ptr->IsLeaf())
					{	ptr->info[i]=ptr->subTree[i+1]->info[0];
						father=ptr;
						ptr=ptr->subTree[i+1];
					}
					father->subTree[i+1]=NULL;
				}
				return NULL;
			}
		for(i=0;i<ORDER-1;i++) 
			{
				if (n<ptr->info[i]) 
				{
					index=i;
					father=ptr;
					ptr=ptr->subTree[i];
				break;
				}
			}
			if (i==ORDER-1) {father=ptr;index=i;ptr=ptr->subTree[i];}
	}
	return NULL;
}


Tree::Delete(int n)
{
	//if key is in leaf node delete it.
	//otherwise replace it with leftmost key of its next-right subtree.
	//continue until hitting leaf node.
//cout << Search(3)->IsLeaf();

}


main()
{
Tree t;
int j=0;
t.Insert(20);
t.Insert(33);
t.Insert(1);
t.Insert(2);
t.Insert(3);
cout << t.Search(2)->IsLeaf();
return 0;
}