/***************************************************************************
 * E-Com Technology Ltd.
 *
 * ECOMPACS DICOM Network Transport Libraries * Version 0.1 Beta
 ***************************************************************************/

/*********************************************************************
 * Class Array 
 *********************************************************************/

template < class DATATYPE >
Array < DATATYPE >::Array (const Array & theArray)
{
	ArraySize	= 0; 
	first		= NULL; 
	last		= NULL; 
	ClearType	= 1;

	theArray.CopyTo (*this);
}


template <class DATATYPE>
void Array<DATATYPE>::AddBefore (const DATATYPE & Value, int Index)
{
	if (Index >= ArraySize)
	{
		Add (Value) ;
		return;
	}

	ArrayItem<DATATYPE>	*dl;

	// scan the chain to get the element (from head or from tail)
	if (Index < ArraySize / 2)
	{	// scan from the head of chain
		dl = first;
		++Index;
		while (--Index > 0) dl = dl->next;
	}
	else
	{	// scan from the tail of chain
		dl = last;
		Index = (ArraySize - Index);
		while (--Index > 0) dl = dl->prev;
	}

	ArrayItem<DATATYPE>	*ndl;
	ndl = new ArrayItem<DATATYPE>;

	// relink chain before the element to be added

	ndl -> Data = Value;
	ndl -> next = dl;
	ndl -> prev = dl -> prev;
	
	dl -> prev = ndl;

	if (ndl->prev)
		ndl->prev->next = ndl;
	else
		first = ndl;

	++ ArraySize;
}

template <class DATATYPE>
void Array<DATATYPE>::AddAfter (const DATATYPE & Value, int Index)
{
	if (Index < 0)
	{
		InsertFirst (Value);
		return;
	}

	AddBefore (Value, Index+1);
}


template <class DATATYPE> 
template <class IterType>
void Array<DATATYPE>::AddBefore (const DATATYPE & Value, IterType & Iter)
{
	if (Iter.__GetArray () != this)	// not the same array
		return;

	ArrayItem<DATATYPE>	* dl = Iter.__GetCurrent ();
	if (! dl)
	{
		Add (Value);
		if (Iter.GetArraySize () == 0)	// Iter point to an empty array
			Iter.Restart ();
		return;
	}

	ArrayItem<DATATYPE>	*ndl;
	ndl = new ArrayItem <DATATYPE>;

	// relink chain before the element to be added
	ndl -> Data = Value;
	ndl -> next = dl;
	ndl -> prev = dl -> prev;
	
	dl -> prev = ndl;

	if (ndl->prev)
		ndl->prev->next = ndl;
	else
		first = ndl;

	++ ArraySize;
	Iter.__SetArraySize (ArraySize);
	Iter --;
}


template < class DATATYPE > 
BOOL Array < DATATYPE >::RemoveAt (int Index)
{
	if (Index >= ArraySize) return (FALSE);

	ArrayItem < DATATYPE > * dl;

	// scan the chain to get the element (from head or from tail)
	if (Index < ArraySize / 2)
	{	// scan from the head of chain
		dl = first;
		++ Index;
		while (--Index > 0) dl = dl->next;
	}
	else
	{	// scan from the tail of chain
		dl = last;
		Index = (ArraySize - Index);
		while (--Index > 0) dl = dl->prev;
	}

	// relink chain around element to be deleted

	if (dl->prev)
		dl->prev->next = dl->next;
	else
		first = dl->next;

	if (dl->next)
		dl->next->prev = dl->prev;
	else
		last = dl->prev;

	delete dl;

	--ArraySize;

	return (TRUE);
}


template < class DATATYPE >
template < class IterType >
BOOL Array < DATATYPE >::RemoveAt (IterType & Iter)
{
	if (Iter.__GetArray () != this)	// not the same array
		return false;

	ArrayItem < DATATYPE > * dl = Iter.__GetCurrent ();
	if (! dl)
		return false;

	Iter ++;

	// relink chain around element to be deleted
	if (dl->prev)
		dl->prev->next = dl->next;
	else
		first = dl->next;

	if (dl->next)
		dl->next->prev = dl->prev;
	else
		last = dl->prev;

	delete dl;

	-- ArraySize;
	Iter.__SetArraySize (ArraySize);

	return (TRUE);
}


template <class DATATYPE> 
void Array<DATATYPE>::AddBefore (const DATATYPE & Value, Iterator & Iter)
{
	AddBefore <Iterator> (Value, Iter);
}

template < class DATATYPE >
BOOL Array < DATATYPE >::RemoveAt (Iterator & Iter)
{
	return RemoveAt <Iterator> (Iter);
}


template <class DATATYPE> 
void Array<DATATYPE>::AddBefore (const DATATYPE & Value, ReverseIterator & Iter)
{
	AddBefore <ReverseIterator> (Value, Iter);
}

template <class DATATYPE>
BOOL Array<DATATYPE>::RemoveAt	(ReverseIterator & rIter)
{
	return RemoveAt <ReverseIterator> (rIter);
}


template <class DATATYPE> 
BOOL Array <DATATYPE>::TransferTo (Array & theArray)
{
	if (! first)
		return FALSE;

	if (ClearType != theArray.ClearType)
		return FALSE;

	first->prev = theArray.last;

	if (theArray.last)
		theArray.last->next = first;
	else
		theArray.first = first;

	theArray.last = last;

	theArray.ArraySize += ArraySize;

	ArraySize = 0;
	first = NULL;
	last  = NULL;

	return TRUE;
}


template <class DATATYPE> 
int Array <DATATYPE>::TransferTo (Array & theArray, DATATYPE & dt)
{
	if (! first)
		return 0;

	if (ClearType != theArray.ClearType)
		return 0;

	for (Iterator Iter (*this); Iter; Iter++)
	{
		DATATYPE & mydt = Iter ();
		if (dt == mydt)
		{
			RemoveAt (Iter);
			theArray.Add (dt);
			return 1;
		}
	}

	return 0;
}


/*
template <class DATATYPE> 
int Array <DATATYPE>::TransferTo (Array & theArray, DATATYPE dt)
{
	if (! first)
		return 0;

	if (ClearType != theArray.ClearType)
		return 0;

	for (Iterator Iter (*this); Iter; Iter++)
	{
		DATATYPE & mydt = Iter ();
		if (dt == mydt)
		{
			RemoveAt (Iter);
			theArray.Add (dt);
			return 1;
		}
	}

	return 0;
}
*/


template <class DATATYPE> 
int Array <DATATYPE>::TransferTo (Array & theArray, int fromIndex, int NbOfTransfer)
{
	if (! first)
		return 0;

	if (ClearType != theArray.ClearType)
		return 0;

	Iterator Iter (*this); Iter += fromIndex;
	for (int Index = 0; Iter && Index < NbOfTransfer; Index++)
	{
		DATATYPE & dt = Iter ();
		theArray.Add (dt);
		if (! RemoveAt (Iter))
			Iter ++;
	}

	return Index;
}


template <class DATATYPE>
int Array <DATATYPE>::CopyTo (FixArray <DATATYPE> & theArray) const
{
	if (theArray.GetCapacity () < this->GetSize ())
		return 0;

	for (Array <DATATYPE>::Iterator Iter (*this); Iter; Iter++)
	{
		theArray.Add (Iter ());
	}

	return GetSize ();
}


template <class DATATYPE>
int Array <DATATYPE>::CopyTo (Array <DATATYPE> & theArray) const
{
	for (Array <DATATYPE>::Iterator Iter (*this); Iter; Iter++)
	{
		theArray.Add (Iter ());
	}

	return GetSize ();
}


template <class DATATYPE>
int Array <DATATYPE>::CopyTo (DATATYPE * pArray, int NbOfElem) const
{
	if (NbOfElem == 0)
		return 0;
	int size = GetSize ();

	if (NbOfElem > size)
		NbOfElem = size;

	if (NbOfElem == 0)
		return NbOfElem;

	if (! pArray)
		return 0;

	if (NbOfElem == 1)
	{
		*pArray = first->Data;
		return NbOfElem;
	}
	if (NbOfElem == 2)
	{
		*pArray = first->Data;
		pArray++;
		*pArray = first->next->Data;
		return NbOfElem;
	}
	if (NbOfElem == 3)
	{
		ArrayItem < DATATYPE > * dl = first;
		*pArray = dl->Data;
		pArray++;  dl = dl->next;
		*pArray = dl->Data;
		pArray++;  dl = dl->next;
		*pArray = dl->Data;
		return NbOfElem;
	}
	if (NbOfElem == 4)
	{
		ArrayItem < DATATYPE > * dl = first;
		*pArray = dl->Data;
		pArray++;  dl = dl->next;
		*pArray = dl->Data;
		pArray++;  dl = dl->next;
		*pArray = dl->Data;
		pArray++;  dl = dl->next;
		*pArray = dl->Data;
		return NbOfElem;
	}

	Array <DATATYPE>::Iterator Iter (*this);
	for (int Index = 0; Index<NbOfElem; Index++, Iter++)
	// 因为前面已经确定NbOfElem <= size;因此这里不用再判定Iter是否已经到尾了
	{
		*pArray++ = Iter ();
	}

	return NbOfElem;
}


template <class DATATYPE>
int Array <DATATYPE>::Append (const Array <DATATYPE> & from)
{
	if (ClearType != from.ClearType)
		return -1;

	int Size = GetSize ();
	ArrayIterator <DATATYPE> Iter (from);
	while (Iter)
	{
		DATATYPE value = Iter ();
		Add (value);
	}

	return Size;
}


template <class DATATYPE>
void Array <DATATYPE>::SetCapacity (int nNewSize)
{
	if (nNewSize == 0)
	{
		RemoveAll ();
	}
	else
	{
		// it fits
		if (nNewSize > ArraySize)
		{
			// initialize the new elements
			for (int Index=0; Index<nNewSize-ArraySize; Index++)
			{
				DATATYPE value;
				Add (value);
			}
		}
		else if (ArraySize > nNewSize)
		{
			// destroy the old elements
			for (int Index=0; Index<ArraySize-nNewSize; Index++)
			{
				RemoveLast ();
			}
		}
	}
}


//////////////////////////////////////////////////////////////////////
// Quick Sort
//////////////////////////////////////////////////////////////////////
template <class DATATYPE>
void Array <DATATYPE>::Sort (int low, int high)
{
	if (high - low <= 0)
		return;

	if (high - low == 1)
	{
		if (GetAt (high) < GetAt (low))
			Swap (low, high);
		return;
	}

	// 存放中心索引及其值的局部变量及用于扫描的索引
	DATATYPE pivot;
	int scanUp, scanDown;
	int mid;

	mid		= (low + high) / 2;
	pivot	= GetAt (mid);
	Swap (mid, low);
	scanUp = low + 1;  scanDown = high;
	do
	{
		ArrayItem < DATATYPE > * dl;

		dl = PtrOfItemAt (scanUp);
		while (scanUp <= scanDown && dl->Data <= pivot)
		{
			scanUp ++;
			dl = dl->next;
		}

		dl = PtrOfItemAt (scanDown);
		while (pivot < dl->Data)
		{
			scanDown --;
			dl = dl->prev;
		}

		if (scanUp < scanDown)
		{
			Swap (scanUp, scanDown);
		}
	}
	while (scanUp < scanDown);

	ArrayItem < DATATYPE > * dl = PtrOfItemAt (scanDown);
	(*this)[low] = dl->Data;
	dl->Data = pivot;

	if (low < scanDown - 1)
		Sort (low, scanDown - 1);
	if (scanDown + 1 < high)
		Sort (scanDown + 1, high);
}


template <class DATATYPE>
template <class ODT> 
void Array <DATATYPE>::Sort (int low, int high, Array <ODT> & ar)
{
	if (high - low <= 0)
		return;

	if (high - low == 1)
	{
		if (GetAt (high) < GetAt (low))
		{
			Swap (low, high);
			ar.Swap (low, high);
		}
		return;
	}

	// 存放中心索引及其值的局部变量及用于扫描的索引
	int scanUp, scanDown;
	int mid;

	mid		= (low + high) / 2;
	DATATYPE pivot = GetAt (mid);

	ODT __fvalue;
	__fvalue = ar.GetAt (mid);

	Swap (mid, low);
	ar.Swap (mid, low);
	scanUp = low + 1;  scanDown = high;
	do
	{
		ArrayItem < DATATYPE > * dl;

		dl = PtrOfItemAt (scanUp);
		while (scanUp <= scanDown && dl->Data <= pivot)
		{
			scanUp ++;
			dl = dl->next;
		}

		dl = PtrOfItemAt (scanDown);
		while (pivot < dl->Data)
		{
			scanDown --;
			dl = dl->prev;
		}

		if (scanUp < scanDown)
		{
			Swap (scanUp, scanDown);
			ar.Swap (scanUp, scanDown);
		}
	}
	while (scanUp < scanDown);

	ArrayItem < DATATYPE > * dl;

	dl = PtrOfItemAt (scanDown);
	(*this)[low] = dl->Data;
	dl->Data = pivot;

	{
		ArrayItem < ODT > * fdl;

		fdl = ar.PtrOfItemAt (scanDown);
		ar[low] = fdl->Data;
		fdl->Data = __fvalue;
	}

	if (low < scanDown - 1)
		Sort (low, scanDown - 1, ar);
	if (scanDown + 1 < high)
		Sort (scanDown + 1, high, ar);
}

template <class DATATYPE>
template <class ODT> 
void Array <DATATYPE>::Sort (int low, int high, FixArray <ODT> & ar)
{
	if (high - low <= 0)
		return;

	if (high - low == 1)
	{
		if (GetAt (high) < GetAt (low))
		{
			Swap (low, high);
			ar.Swap (low, high);
		}
		return;
	}

	// 存放中心索引及其值的局部变量及用于扫描的索引
	int scanUp, scanDown;
	int mid;

	mid		= (low + high) / 2;
	DATATYPE pivot = GetAt (mid);

	ODT __fvalue;
	__fvalue = ar.GetAt (mid);

	Swap (mid, low);
	ar.Swap (mid, low);
	scanUp = low + 1;  scanDown = high;
	do
	{
		ArrayItem < DATATYPE > * dl;

		dl = PtrOfItemAt (scanUp);
		while (scanUp <= scanDown && dl->Data <= pivot)
		{
			scanUp ++;
			dl = dl->next;
		}

		dl = PtrOfItemAt (scanDown);
		while (pivot < dl->Data)
		{
			scanDown --;
			dl = dl->prev;
		}

		if (scanUp < scanDown)
		{
			Swap (scanUp, scanDown);
			ar.Swap (scanUp, scanDown);
		}
	}
	while (scanUp < scanDown);

	ArrayItem < DATATYPE > * dl;

	dl = PtrOfItemAt (scanDown);
	(*this)[low] = dl->Data;
	dl->Data = pivot;

	{
		ar[low] = ar[scanDown];
		ar[scanDown] = __fvalue;
	}

	if (low < scanDown - 1)
		Sort (low, scanDown - 1, ar);
	if (scanDown + 1 < high)
		Sort (scanDown + 1, high, ar);
}


//////////////////////////////////////////////////////////////////////
// Sort using the give compare function
//////////////////////////////////////////////////////////////////////
template <class DATATYPE>
template <class Compare>
void Array <DATATYPE>::Sort (int low, int high, Compare cf)
{
	if (high - low <= 0)
		return;

	if (high - low == 1)
	{
		if (cf (GetAt (high), GetAt (low)) < 0)
			Swap (low, high);
		return;
	}

	// 存放中心索引及其值的局部变量及用于扫描的索引
	DATATYPE pivot;
	int scanUp, scanDown;
	int mid;

	mid		= (low + high) / 2;
	pivot	= GetAt (mid);
	Swap (mid, low);
	scanUp = low + 1;  scanDown = high;
	do
	{
		ArrayItem < DATATYPE > * dl;

		dl = PtrOfItemAt (scanUp);
		while (scanUp <= scanDown && cf (dl->Data, pivot) <= 0)
		{
			scanUp ++;
			dl = dl->next;
		}

		dl = PtrOfItemAt (scanDown);
		while (cf (pivot, dl->Data) < 0)
		{
			scanDown --;
			dl = dl->prev;
		}

		if (scanUp < scanDown)
		{
			Swap (scanUp, scanDown);
		}
	}
	while (scanUp < scanDown);

	ArrayItem < DATATYPE > * dl= PtrOfItemAt (scanDown);
	(*this)[low] = dl->Data;
	dl->Data = pivot;

	if (low < scanDown - 1)
		Sort (low, scanDown - 1, cf);
	if (scanDown + 1 < high)
		Sort (scanDown + 1, high, cf);
}


template <class DATATYPE>
template <class ODT, class Compare> 
void Array <DATATYPE>::Sort (int low, int high, Array <ODT> & ar, Compare cf)
{
	if (high - low <= 0)
		return;

	if (high - low == 1)
	{
		if (cf (GetAt (high), GetAt (low)) < 0)
		{
			Swap (low, high);
			ar.Swap (low, high);
		}
		return;
	}

	// 存放中心索引及其值的局部变量及用于扫描的索引
	int scanUp, scanDown;
	int mid;

	mid		= (low + high) / 2;
	DATATYPE pivot = GetAt (mid);

	ODT __fvalue;
	__fvalue = ar.GetAt (mid);

	Swap (mid, low);
	ar.Swap (mid, low);
	scanUp = low + 1;  scanDown = high;
	do
	{
		ArrayItem < DATATYPE > * dl;

		dl = PtrOfItemAt (scanUp);
		while (scanUp <= scanDown && cf (dl->Data, pivot) <= 0)
		{
			scanUp ++;
			dl = dl->next;
		}

		dl = PtrOfItemAt (scanDown);
		while (cf (pivot, dl->Data) < 0)
		{
			scanDown --;
			dl = dl->prev;
		}

		if (scanUp < scanDown)
		{
			Swap (scanUp, scanDown);
			ar.Swap (scanUp, scanDown);
		}
	}
	while (scanUp < scanDown);

	ArrayItem < DATATYPE > * dl;

	dl = PtrOfItemAt (scanDown);
	(*this)[low] = dl->Data;
	dl->Data = pivot;

	{
		ArrayItem < ODT > * fdl;

		fdl = ar.PtrOfItemAt (scanDown);
		ar[low] = fdl->Data;
		fdl->Data = __fvalue;
	}

	if (low < scanDown - 1)
		Sort (low, scanDown - 1, ar, cf);
	if (scanDown + 1 < high)
		Sort (scanDown + 1, high, ar, cf);
}


template <class DATATYPE>
template <class ODT, class Compare>
void Array <DATATYPE>::Sort (int low, int high, FixArray <ODT> & ar, Compare cf)
{
	if (high - low <= 0)
		return;

	if (high - low == 1)
	{
		if (cf (GetAt (high), GetAt (low)) < 0)
		{
			Swap (low, high);
			ar.Swap (low, high);
		}
		return;
	}

	// 存放中心索引及其值的局部变量及用于扫描的索引
	int scanUp, scanDown;
	int mid;

	mid		= (low + high) / 2;
	DATATYPE pivot = GetAt (mid);

	ODT __fvalue;
	__fvalue = ar.GetAt (mid);

	Swap (mid, low);
	ar.Swap (mid, low);
	scanUp = low + 1;  scanDown = high;
	do
	{
		ArrayItem < DATATYPE > * dl;

		dl = PtrOfItemAt (scanUp);
		while (scanUp <= scanDown && cf (dl->Data, pivot) <= 0)
		{
			scanUp ++;
			dl = dl->next;
		}

		dl = PtrOfItemAt (scanDown);
		while (cf (pivot, dl->Data) < 0)
		{
			scanDown --;
			dl = dl->prev;
		}

		if (scanUp < scanDown)
		{
			Swap (scanUp, scanDown);
			ar.Swap (scanUp, scanDown);
		}
	}
	while (scanUp < scanDown);

	ArrayItem < DATATYPE > * dl;

	dl = PtrOfItemAt (scanDown);
	(*this)[low] = dl->Data;
	dl->Data = pivot;

	{
		ar[low] = ar[scanDown];
		ar[scanDown] = __fvalue;
	}

	if (low < scanDown - 1)
		Sort (low, scanDown - 1, ar, cf);
	if (scanDown + 1 < high)
		Sort (scanDown + 1, high, ar, cf);
}


//////////////////////////////////////////////////////////////////////
// Sort using the give compare function, with arg
//////////////////////////////////////////////////////////////////////
template <class DATATYPE>
template <class Compare, typename arg>
void Array <DATATYPE>::Sort (int low, int high, Compare cf, arg a)
{
	if (high - low <= 0)
		return;

	if (high - low == 1)
	{
		if (cf (GetAt (high), GetAt (low), a) < 0)
			Swap (low, high);
		return;
	}

	// 存放中心索引及其值的局部变量及用于扫描的索引
	DATATYPE pivot;
	int scanUp, scanDown;
	int mid;

	mid		= (low + high) / 2;
	pivot	= GetAt (mid);
	Swap (mid, low);
	scanUp = low + 1;  scanDown = high;
	do
	{
		ArrayItem < DATATYPE > * dl;

		dl = PtrOfItemAt (scanUp);
		while (scanUp <= scanDown && cf (dl->Data, pivot, a) <= 0)
		{
			scanUp ++;
			dl = dl->next;
		}

		dl = PtrOfItemAt (scanDown);
		while (cf (pivot, dl->Data, a) < 0)
		{
			scanDown --;
			dl = dl->prev;
		}

		if (scanUp < scanDown)
		{
			Swap (scanUp, scanDown);
		}
	}
	while (scanUp < scanDown);

	ArrayItem < DATATYPE > * dl= PtrOfItemAt (scanDown);
	(*this)[low] = dl->Data;
	dl->Data = pivot;

	if (low < scanDown - 1)
		Sort (low, scanDown - 1, cf, a);
	if (scanDown + 1 < high)
		Sort (scanDown + 1, high, cf, a);
}


template <class DATATYPE>
template <class ODT, class Compare, typename arg> 
void Array <DATATYPE>::Sort (int low, int high, Array <ODT> & ar, Compare cf, arg a)
{
	if (high - low <= 0)
		return;

	if (high - low == 1)
	{
		if (cf (GetAt (high), GetAt (low), a) < 0)
		{
			Swap (low, high);
			ar.Swap (low, high);
		}
		return;
	}

	// 存放中心索引及其值的局部变量及用于扫描的索引
	int scanUp, scanDown;
	int mid;

	mid		= (low + high) / 2;
	DATATYPE pivot = GetAt (mid);

	ODT __fvalue;
	__fvalue = ar.GetAt (mid);

	Swap (mid, low);
	ar.Swap (mid, low);
	scanUp = low + 1;  scanDown = high;
	do
	{
		ArrayItem < DATATYPE > * dl;

		dl = PtrOfItemAt (scanUp);
		while (scanUp <= scanDown && cf (dl->Data, pivot, a) <= 0)
		{
			scanUp ++;
			dl = dl->next;
		}

		dl = PtrOfItemAt (scanDown);
		while (cf (pivot, dl->Data, a) < 0)
		{
			scanDown --;
			dl = dl->prev;
		}

		if (scanUp < scanDown)
		{
			Swap (scanUp, scanDown);
			ar.Swap (scanUp, scanDown);
		}
	}
	while (scanUp < scanDown);

	ArrayItem < DATATYPE > * dl;

	dl = PtrOfItemAt (scanDown);
	(*this)[low] = dl->Data;
	dl->Data = pivot;

	{
		ArrayItem < ODT > * fdl;

		fdl = ar.PtrOfItemAt (scanDown);
		ar[low] = fdl->Data;
		fdl->Data = __fvalue;
	}

	if (low < scanDown - 1)
		Sort (low, scanDown - 1, ar, cf, a);
	if (scanDown + 1 < high)
		Sort (scanDown + 1, high, ar, cf, a);
}


template <class DATATYPE>
template <class ODT, class Compare, typename arg>
void Array <DATATYPE>::Sort (int low, int high, FixArray <ODT> & ar, Compare cf, arg a)
{
	if (high - low <= 0)
		return;

	if (high - low == 1)
	{
		if (cf (GetAt (high), GetAt (low), a) < 0)
		{
			Swap (low, high);
			ar.Swap (low, high);
		}
		return;
	}

	// 存放中心索引及其值的局部变量及用于扫描的索引
	int scanUp, scanDown;
	int mid;

	mid		= (low + high) / 2;
	DATATYPE pivot = GetAt (mid);

	ODT __fvalue;
	__fvalue = ar.GetAt (mid);

	Swap (mid, low);
	ar.Swap (mid, low);
	scanUp = low + 1;  scanDown = high;
	do
	{
		ArrayItem < DATATYPE > * dl;

		dl = PtrOfItemAt (scanUp);
		while (scanUp <= scanDown && cf (dl->Data, pivot, a) <= 0)
		{
			scanUp ++;
			dl = dl->next;
		}

		dl = PtrOfItemAt (scanDown);
		while (cf (pivot, dl->Data, a) < 0)
		{
			scanDown --;
			dl = dl->prev;
		}

		if (scanUp < scanDown)
		{
			Swap (scanUp, scanDown);
			ar.Swap (scanUp, scanDown);
		}
	}
	while (scanUp < scanDown);

	ArrayItem < DATATYPE > * dl;

	dl = PtrOfItemAt (scanDown);
	(*this)[low] = dl->Data;
	dl->Data = pivot;

	{
		ar[low] = ar[scanDown];
		ar[scanDown] = __fvalue;
	}

	if (low < scanDown - 1)
		Sort (low, scanDown - 1, ar, cf, a);
	if (scanDown + 1 < high)
		Sort (scanDown + 1, high, ar, cf, a);
}


//////////////////////////////////////////////////////////////////////
// 对记录序列 R[0..n]进行堆排序。
//////////////////////////////////////////////////////////////////////
template <class DATATYPE>
void Array <DATATYPE>::HeapSort (int n)
{
	for (int i=n/2; i>=0; --i)
		// 把R[1..n]建成大顶堆
		HeapAdjust (i, n);

	for (int i=n; i>=1; --i)
	{
		Swap (0, i);
		// 将堆顶记录和当前未经排序子序列
		// R[1..i]中最后一个记录相互交换

		HeapAdjust (0, i-1);            
		// 将R[1..i-1] 重新调整为大顶堆
	}
}


// 已知R[s..m]中记录的关键字除R[s].key之
// 外均满足堆的定义，本函数调整R[s] 的关
// 键字，使R[s..m]成为一个大顶堆（对其中
// 记录的关键字而言）
template <class DATATYPE>
void Array <DATATYPE>::HeapAdjust (int s, int m)
{
	DATATYPE rc = GetAt (s);

	for (int j=2*s; j<=m; j*=2)
	{
		ArrayItem < DATATYPE > * dl;
		dl = PtrOfItemAt (j);

		// 沿key较大的孩子结点向下筛选
		if (j < m && dl->Data < dl->next->Data)
		{
			j ++;
			dl = dl->next;
		}

		// j为key较大的记录的下标
		if (rc >= dl->Data)
			break;

		// rc应插入在位置s上
		Swap (s, j);  s = j;
	}

	(*this)[s] = rc;  // 插入
}


//////////////////////////////////////////////////////////////////////
// IsSorted
//////////////////////////////////////////////////////////////////////

template <class DATATYPE>
bool Array <DATATYPE>::IsSorted () const
{
	ArrayItem < DATATYPE > * prev = first;
	ArrayItem < DATATYPE > * next = prev;

	if (! next)
		return true;

	while (next->next)
	{
		prev = next;
		next = next->next;

		if (prev->Data > next->Data)
			return false;
	}

	return true;
}


template <class DATATYPE>
template <class Compare>
bool Array <DATATYPE>::IsSorted (Compare cf) const
{
	ArrayItem < DATATYPE > * prev = first;
	ArrayItem < DATATYPE > * next = prev;

	if (! next)
		return true;

	while (next->next)
	{
		prev = next;
		next = next->next;

		if (cf (prev->Data, next->Data) > 0)
			return false;
	}

	return true;
}


//////////////////////////////////////////////////////////////////////
// FindMin, FindMax
//////////////////////////////////////////////////////////////////////

template <class DATATYPE>
DATATYPE & Array <DATATYPE>::FindMin (void) const
{
	ArrayItem < DATATYPE > * pMin = first;

	if (! pMin)
		return pMin -> Data;

	ArrayItem < DATATYPE > * next = first->next;
	while (next)
	{
		if (next->Data < pMin->Data)
			pMin = next;
		next = next->next;
	}

	return pMin -> Data;
}

template <class DATATYPE>
DATATYPE & Array <DATATYPE>::FindMax (void) const
{
	ArrayItem < DATATYPE > * pMax = first;

	if (! pMax)
		return pMax -> Data;

	ArrayItem < DATATYPE > * next = first->next;
	while (next)
	{
		if (next->Data > pMax->Data)
			pMax = next;
		next = next->next;
	}

	return pMax -> Data;
}


template <class DATATYPE>
template <class Compare>
DATATYPE & Array <DATATYPE>::FindMin (Compare cf) const
{
	ArrayItem < DATATYPE > * pMin = first;

	if (! pMin)
		return pMin -> Data;

	ArrayItem < DATATYPE > * next = first->next;
	while (next)
	{
		if (cf (next->Data, pMin->Data) < 0)
			pMin = next;
		next = next->next;
	}

	return pMin -> Data;
}

template <class DATATYPE>
template <class Compare>
DATATYPE & Array <DATATYPE>::FindMax (Compare cf) const
{
	ArrayItem < DATATYPE > * pMax = first;

	if (! pMax)
		return pMax -> Data;

	ArrayItem < DATATYPE > * next = first->next;
	while (next)
	{
		if (cf (next->Data, pMax->Data) > 0)
			pMax = next;
		next = next->next;
	}

	return pMax -> Data;
}


//////////////////////////////////////////////////////////////////////
// IndexOfMin, IndexOfMax
//////////////////////////////////////////////////////////////////////

template <class DATATYPE>
int  Array <DATATYPE>::IndexOfMin (void) const
{
	ArrayItem < DATATYPE > * pMin = first;

	if (! pMin)
		return -1;

	int Index = 1;
	int LastIndex = 0;
	ArrayItem < DATATYPE > * next = first->next;
	while (next)
	{
		if (next->Data < pMin->Data)
		{
			pMin = next;
			LastIndex = Index;
		}
		next = next->next;
		Index ++;
	}

	return LastIndex;
}

template <class DATATYPE>
int  Array <DATATYPE>::IndexOfMax (void) const
{
	ArrayItem < DATATYPE > * pMax = first;

	if (! pMax)
		return -1;

	int Index = 1;
	int LastIndex = 0;
	ArrayItem < DATATYPE > * next = first->next;
	while (next)
	{
		if (next->Data > pMax->Data)
		{
			pMax = next;
			LastIndex = Index;
		}
		next = next->next;
		Index ++;
	}

	return LastIndex;
}


template <class DATATYPE>
template <class Compare>
int  Array <DATATYPE>::IndexOfMin (Compare cf) const
{
	ArrayItem < DATATYPE > * pMin = first;

	if (! pMin)
		return -1;

	int Index = 1;
	int LastIndex = 0;
	ArrayItem < DATATYPE > * next = first->next;
	while (next)
	{
		if (cf (next->Data, pMin->Data) < 0)
		{
			pMin = next;
			LastIndex = Index;
		}
		next = next->next;
		Index ++;
	}

	return LastIndex;
}

template <class DATATYPE>
template <class Compare>
int  Array <DATATYPE>::IndexOfMax (Compare cf) const
{
	ArrayItem < DATATYPE > * pMax = first;

	if (! pMax)
		return -1;

	int Index = 1;
	int LastIndex = 0;
	ArrayItem < DATATYPE > * next = first->next;
	while (next)
	{
		if (cf (next->Data, pMax->Data) > 0)
		{
			pMax = next;
			LastIndex = Index;
		}
		next = next->next;
		Index ++;
	}

	return LastIndex;
}


/*********************************************************************
 * Class ArrayOfPtr
 *********************************************************************/
template < class DATATYPE >
template < class IterType >
BOOL ArrayOfPtr < DATATYPE >::RemoveAt (IterType & Iter)
{
	if (Iter.__GetArray () != this)	// not the same array
		return false;

	ArrayItem < DATATYPE > * dl = Iter.__GetCurrent ();
	if (! dl)
		return false;

	delete dl->Data;

	return Array <DATATYPE>::RemoveAt (Iter);
}