#include "P384.cpp"

			void PageRemove ( const TwoChars & key, const paddr p )
			//從p所指的頁塊中刪去關鍵碼key。這是順序表的刪除算法, 可參看第2章。
			{
				for (int i=0;i<p->Count;i++)
					if (p->Names[i]==key)
					{
						p->Count--;
						p->Names[i]=p->Names[p->Count];
						return;
					}				
			}
     	   void combine ( unsigned int index ) {		
		   if ( DicDepth == 0 ) return;					   
		   int buddyid= buddy (index);					//伙伴頁塊的二進制 地址	
		   paddr p = Directory[index];						//index頁塊和伙伴頁塊指針
		   paddr s = Directory[buddyid];
		   if ( (buddyid>=0) && ((p->Count + s->Count) <= PageSize )) {
				//看該頁塊與其伙伴的總關鍵碼個數是否超出一頁限制, 未超出, 合并頁塊
			 			 
			 for ( int i=0; i<s->Count; i++ ) {				//將伙伴中內容全部移到index頁塊			   
			   p->Names[p->Count] = s->Names[i];
			   p->Count++; 
			 }
			 delete s;   p->PgDepth--;					//釋放伙伴頁塊, index頁塊深度減1
			 Directory[buddyid] = p;				

			 unsigned int DirSize = Power2(DicDepth);				//計算目錄項數
			 unsigned int NewDirSize = DirSize / 2;					//如果緊縮,新的目錄項數
			 for ( i=0; i<NewDirSize; i++ )					//判斷是否要緊縮目錄
			   if ( Directory[i] != Directory[NewDirSize+i] ) return; 
															//不需緊縮目錄, 結束處理返回			 
			 paddr *NewDir = Directory;
			 DicDepth--;				//目錄深度減1
			 Directory = new paddr[NewDirSize];			//創建新目錄
			 for ( i=0; i<NewDirSize; i++ ) Directory[i] = NewDir[i];
			 delete [ ] NewDir;
			 if (index<NewDirSize) combine ( index ); else combine(buddyid);							//遞歸, 看是否繼續合并 
		   }
		}


		void Remove ( const TwoChars & key ) {				//搜索并刪去關鍵碼key
		   unsigned int id = makeAddress ( key, DicDepth );			//尋找關鍵碼key所在頁塊的二進制地址
		   paddr p = Directory [id];						//搜索key所在頁塊
		   if ( p ) {									//找到, p是指向該頁塊的指針
			 PageRemove ( key, p );						//從p所指頁塊中刪去關鍵碼key
			 combine ( id );							//判斷是否合并頁塊與緊縮目錄
		   }
		}