#include "iostream.h"
#ifndef MAXKEY
#define MAXKEY 32767
#endif
		const MaxM=100;
		template <class Type> class Mtree;
		template <class Type> class Btree;
		template <class Type> class Mnode {					// B_樹結點類定義
		public:
			void insertkey(int,Type,Mnode<Type>*);
			Mnode(){n=0;parent=NULL;for (int i=0;i<=MaxM;i++) ptr[i]=NULL;}
		private:
		   int n;									//當前結點中關鍵碼個數
		   Mnode<Type> *parent;						//雙親結點指針
		   Type key[MaxM+1];								//key[MaxM]為監視哨兼工作單元, key[0]未用
		   Mnode<Type> *ptr[MaxM+1];						//子樹結點指針數組, ptr[m]未用
		   friend ostream& operator <<(ostream& strm, Mnode<Type>& mn);
		   friend class Mtree<Type>;
		   friend class Btree<Type>;
		};
		
		template <class Type>
		class Triple {								//搜索結果
		public:
		   Mnode<Type> *r;							//B_樹結點地址
		   int i;  char tag;							//結點中關鍵碼序號及搜索成功標志
		   friend ostream& operator <<(ostream& strm, Triple<Type>& tp);
		};

		template <class Type> class Mtree {                 
		public:
		   Mtree(int d=3){root=NULL;m=d;};		   
		   void insertkey(Mnode<Type>*,int,Type,Mnode<Type>*);
		   Triple<Type>  Search ( const Type & );
		   friend ostream& operator <<(ostream& strm, Mtree<Type>& mt);
		protected:
			void move ( Mnode<Type>*p, Mnode<Type>*q, int s, int m );
			void print(ostream& strm,Mnode<Type> *p);
		   Mnode<Type> *root;
		   int m;
		};

		template <class Type> Triple<Type>  Mtree<Type>::Search ( const Type & x ) {
		//用關鍵碼x搜索駐留在磁盤上的m路搜索樹。各結點格式為n, A[0], (k[1],A[1]),……,  (K[n],A[n]), n < m。
		//函數返回一個類型為Triple (r, i, tag)的對象。tag=1, 表示x 在結點r找到, 是該結點的K[i];  tag=0, 表
		//示沒有找到x, 這時可以插入的結點是r, 插入到該結點的K[i]與K[i+1]之間。
		   Triple<int> result;							//存放結果的工作單元
		   GetNode ( root );						//從磁盤上讀取位于根root的結點
		   Mnode <Type> *p = root, *q = NULL;			//p是掃描指針, q是p的父結點指針
		   int i;
		   while ( p != NULL ) {						//繼續搜索
			 i = 0;  p->key[(p->n)+1] = MAXKEY;
			 while ( p->key[i+1] < x ) i++;				//在結點內順序搜索
			 if ( p->key[i+1] == x ) {					//搜索成功, 本結點有x
				result.r = p;  result.i = i+1;  result.tag = 0;
				return result;					//返回結果, 返回主程序
			 }
			 q = p;  p = p->ptr[i];					//本結點無x, q記下當前結點, p下降到相應子樹			 GetNode (p);							//從磁盤上讀取p結點
		   }
		   result.r = q;  result.i = i;  result.tag = 1;
		   return result;							//x可能落入的區間[ Ki, Ki+1 )
		}
		template <class Type> class Btree : public Mtree<Type> {		//B_樹的類定義
		public:
		   //Search從Mtree繼承;
		   int Insert ( const Type& x );						//插入關鍵碼x
		   int Remove ( const Type& x );					//刪除關鍵碼x
		private:		
		void LeftAdjust ( Mnode<Type> *p, Mnode<Type> *q, const int d, const int j );
		void RightAdjust ( Mnode<Type> *p, Mnode<Type> *q, const int d, const int j );
		void compress ( Mnode<Type> *p, const int j );
		void merge ( Mnode<Type> *p, Mnode<Type> *q, Mnode<Type> *p1, int j) ;

		};
		template <class Type>
			void GetNode(Mnode<Type> *p)
		{
			//理論上應該從磁盤讀入結點p,現在這里可以為空
		};		
		template <class Type>
			void PutNode(Mnode<Type> *p)
		{
			//理論上應該從磁盤寫結點p,現在這里可以為空
		};		

		template <class Type>
			void Mtree<Type>::print(ostream& strm,Mnode<Type> *p)
		{
			if (p)
			{		
			strm<<*p;
			if (p->n)
			{	strm<<"(";
				for (int i=0;i<=p->n;i++)				
					print(strm,p->ptr[i]);
			
				strm<<")";
			}
			}
		}
		template <class Type>
		ostream& operator <<(ostream& strm, Mtree<Type>& mt)
		{
			mt.print(strm,mt.root);
			return strm;
		}
		template <class Type>
		ostream& operator <<(ostream& strm, Mnode<Type>& mn)
		{
			strm<<"[";
			for (int i=1;i<=mn.n;i++)
			{
				if (i!=1) strm<<',';
				strm<<mn.key[i];
			}
			strm<<"]";
			return strm;
			
		}
	template <class Type>
	 ostream& operator <<(ostream& strm, Triple<Type>& tp)
	{
		if (tp.tag) strm<<"Key Not Found";
			else
			strm<<"Key Found at :"<<*tp.r<<" No. "<<tp.i<<" key";
		return strm;
	}
	template <class Type>
		void Mnode<Type>::
	insertkey(int i,Type K,Mnode<Type>* q)
	{
		for (int j=n;j>=i;j--)
		{
			key[j+1]=key[j];
			ptr[j+1]=ptr[j];
		}
		key[i]=K;
		ptr[i]=q;
		n++;
	};
	template <class Type>
		void Mtree<Type>::
	insertkey(Mnode<Type>* p,int i,Type K,Mnode<Type>* q)
	{
		p->insertkey(i,K,q);
	}
	template <class Type>
		void Mtree<Type>::move ( Mnode<Type>*p, Mnode<Type>*q, int s, int m )
	//將 p的key[s+1..m]和ptr[s..m]移到q的key[1..s-1]和ptr[0..s-1]
	//p->n改為s, q->n改為m-s
	{
		int j=0;
		q->ptr[0]=p->ptr[s];
		if (q->ptr[0])
			q->ptr[0]->parent=q; 
		for (int i=s+1;i<=m;i++)
		{
			j++;
			q->key[j]=p->key[i];
			q->ptr[j]=p->ptr[i];
			if (q->ptr[j])
				q->ptr[j]->parent=q;
		}
		q->n=m-s;
		p->n=s-1;
	}