#include "p382.cpp"
		int PageFind ( const TwoChars & key, const paddr PageNumber )
		//在由指針PageNumber所指的頁塊中搜索關鍵碼key, 如果找到則返回1, 否則返回0。
		//因為在頁塊內的搜索方法一般為順序搜索, 算法不再特別給出, 可參看程序9.1。
		{
			for (int i=0;i<PageNumber->Count;i++)
			{
				if (key==PageNumber->Names[i]) return 1;
			}
			return 0;
		};
		paddr Find ( const TwoChars & key ) {
		//在文件中搜索具有關鍵字key的記錄。若找到, 則返回該記錄所在頁塊的地址; 若沒有找到, 則返回 0。
		   unsigned int id = makeAddress ( key, DicDepth );			//按key與DicDepth計算目錄地址
		   paddr FoundPage;
		   FoundPage= Directory[id];					//在目錄中找到相應頁塊地址
		   if ( PageFind ( key, FoundPage ) ) return FoundPage;		//在該頁塊中搜索, 找到返回頁塊地址
		   else return 0;
		}



		void DirDouble ( ) {							//目錄成倍擴充的算法
		   unsigned int CurrentSize = Power2(DicDepth);
		   
		   paddr *TmpDir = Directory;				//創建臨時目錄		   
		   Directory = new paddr[2*CurrentSize];			//創建新目錄
		   for ( int i=0; i<CurrentSize; i++ )					//從臨時目錄向新目錄傳送頁塊指針
			 { Directory[i] = TmpDir[i];  Directory[CurrentSize+i] = TmpDir[i]; } 
		   DicDepth++;
		   delete [] TmpDir;
		}

		int buddy ( const unsigned int index ) {
		//根據一個頁塊的二進制地址index計算該頁塊的伙伴的二進制地址, 前端的二進位是互補的。
		   if (DicDepth == 0 ) return 0;						//目錄深度為0, 沒有伙伴
		   if ( Directory[index]->PgDepth < DicDepth ) 			//該頁塊的局部深度小于目錄深度
			 return -1;								//沒有伙伴
		   unsigned int mask = 1;						//工作變量
		   mask <<= DicDepth - 1;						//左移DicDepth - 1位, 將1移到最高位 
		   unsigned int buddyAddress = index ^ mask;			//做異或操作, 求伙伴
		   return buddyAddress;
		}

		void ReDisTribute ( paddr PageNumber, paddr NewPage )
			//將老頁塊中所有關鍵碼重新分布
		{
			int i=0;
			int CurrentSize=PageNumber->PgDepth;
			NewPage->Count=0;
			while (i<PageNumber->Count)
			{
				TwoChars key=PageNumber->Names[i];
				int NowPage=makeAddress ( key, CurrentSize );
				if (Directory[NowPage]==NewPage) 
				{
					NewPage->Names[NewPage->Count]=key;
					NewPage->Count++;

					PageNumber->Count--;
					PageNumber->Names[i]=PageNumber->Names[PageNumber->Count];
				}
				else
					i++;
			}
		}


		void Split ( const TwoChars key, paddr PageNumber ) {		//分裂頁塊
		   int CurrentSize = DicDepth;						//記下老的目錄大小
		   if ( PageNumber->PgDepth == DicDepth )			//頁塊深度等于目錄深度時
			 DirDouble( );							//頁塊分裂將導致目錄成倍擴充
		   paddr NewPage = new page;						//為伙伴頁塊分配存儲空間
		   PageNumber->PgDepth ++;						//老頁塊的局部深度加1
		   unsigned int id = makeAddress ( key, CurrentSize );		//按key與老DicDepth計算二進制地址
		   unsigned int bd = buddy ( id );					//找伙伴頁塊的二進制地址	
		   Directory [ bd ] = NewPage;						//建立伙伴頁塊的目錄項		   
		   NewPage->PgDepth = PageNumber->PgDepth;			//伙伴的局部深度等于老頁塊的局部深度
		   ReDisTribute ( PageNumber, NewPage );				//將老頁塊中所有關鍵碼重新分布
		} 

		int Add (const TwoChars & key ) ;

	   
		void Insert ( paddr PageNumber, const TwoChars & key ) {
		//將新關鍵碼key插入到由PageNumber指定的頁塊中。
		   if ( PageNumber->Count != PageSize ) {				//若本頁塊中關鍵碼個數未滿
			 PageNumber->Names [ PageNumber->Count ] = key;
			 PageNumber->Count++;						//直接插入
		   }
		   else {									//否則
			 Split ( key, PageNumber );						//將頁塊一分為二
			 Add ( key);								//插入
		   }
		}


		int Add (const TwoChars & key ) {
		//將一個新關鍵碼key插入到目錄所指定的文件中。
		   paddr foundPage = Find ( key );					//按key在文件中搜索
		   if ( foundPage ) return 0;						//若找到, 則不插入, 返回主程序
		   Insert ( Directory[makeAddress ( key, DicDepth )], key );						//將關鍵碼key插入foundPage頁塊
		   return 1;
		}