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

#pragma warning (disable : 4800)
//  avoid bool (LastAccess);

//////////////////////////////////////////////////////////////////////
// Fixed, Fast-Access Array.
//////////////////////////////////////////////////////////////////////

template < class DATATYPE > class	FixArray
{
protected:
	mutable int	Top;
	int			ArraySize;
	DATATYPE *	DataTable;

public:
	bool		bAutoEnlarge;

public:
	inline FixArray ()
	{	
		ArraySize	= 0; 
		Top = 0;
		DataTable = NULL;
		bAutoEnlarge = false;
	}

	inline FixArray (UINT32 Size)
	{
		ArraySize	= Size; 
		Top = 0;
		DataTable = new DATATYPE [ ArraySize ];
		bAutoEnlarge = false;
	}

	~FixArray () { Reset ();}

	inline int GetTop () const		{ return ( Top ); }
	inline int GetCapacity () const	{ return ( ArraySize ); }
	inline int GetSize () const		{ return ( ArraySize ); }

	inline void RemoveAll (void)
	{
		if ( DataTable)	delete [] DataTable;
		DataTable = NULL;
		ArraySize = 0;
		Top = 0;
	}

	inline void Reset (void)
	{
		RemoveAll ();
	}

	inline bool IsEmpty (void) const
	{
		return (Top == 0);
	}

	inline void Empty (void)
	{
		Top = 0;
	}

	inline DATATYPE & operator [] (int Index) const
	{ 
		return (GetAt (Index)); 
	}

	inline DATATYPE & GetAt (int Index) const
	{
		if (Top <= Index)
			Top = Index + 1;
		if (Top > ArraySize)
		{
			DATATYPE * nul = NULL;
			return (*nul);
		}
		return (DataTable[Index]);
	}

	inline void MemorySet (const DATATYPE & toData)
	{
		for (int Index=0; Index<ArraySize; Index++)
			DataTable[Index] = toData;
	}

	inline int Add (const DATATYPE & Data)
	{
		if (Top >= ArraySize)
		{
			if (bAutoEnlarge)
				Enlarge (GetCapacity () + 1);
		}

		if (Top < ArraySize)
		{
			if (DataTable) 
				DataTable [ Top ] = Data;
			++Top;
		}
		else
		{
			throw ("Out of FixArray range in Add");
			return -1;
		}

		return Top;
	}

/*
	inline void RemoveAt (int nPos)
	{

#pragma message ("------------------------------------------")
#pragma message ("Call FixArray::RemoveAt is NOT recommended")
#pragma message ("------------------------------------------")

		if (nPos >= ArraySize)
			return;

		if (nPos < 0)
			return;

		for (int Index=nPos; Index<ArraySize-1; Index++)
		{
			DataTable[Index] = DataTable[Index+1];			
		}

		Top --;
	}
*/

	inline void SetCapacity (int NewSize)
	{
		Enlarge (NewSize);
	}

	inline int Enlarge (int NewSize)
	{
		if (NewSize <= ArraySize)
		{
			return ArraySize;
		}

		DATATYPE * oldDataTable = DataTable;
		DataTable = new DATATYPE [NewSize];

		if (oldDataTable)
		{
			for (int Index=0; Index<Top; Index++)
			{
				DataTable[Index] = oldDataTable[Index];
			}
		}

		ArraySize = NewSize; 

		if (oldDataTable)	delete [] oldDataTable;

		return NewSize;
	}

	inline BOOL CopyTo (FixArray <DATATYPE> & array) const
	{
		array.SetCapacity (GetCapacity ());
		for (int Index = 0; Index<GetSize (); Index++)
		{
			array.DataTable[Index] = DataTable[Index];
		}
		array.Top = Top;
		return true;
	}

	inline BOOL CopyTo (Array <DATATYPE> & array) const
	{
		for (int Index = 0; Index<GetSize (); Index++)
		{
			array.Add (DataTable[Index]);
		}
		return true;
	}

	inline int Append (const FixArray <DATATYPE> & from)
	{
		Enlarge (this->GetTop () + from.GetTop ());

		for (int Index=0; Index<from.GetTop (); Index++)
		{
			DATATYPE dt = from[Index];
			Add (dt);
		}

		return GetTop ();
	}

	inline int Append (const Array <DATATYPE> & from)
	{
		Enlarge (this->GetTop () + from.GetTop ());

		for (Array <DATATYPE>::Iterator Iter (from); Iter; Iter++)
		while (Iter)
		{
			DATATYPE value = Iter ();
			Add (value);
		}

		return GetTop ();
	}

	inline void Swap (int ia, int ib)
	{
		DATATYPE & a = GetAt (ia);
		DATATYPE & b = GetAt (ib);

		DATATYPE v;
		v = a;
		a = b;
		b = v;
	}


	void Sort (void)
	{
		if (Top == 0)
			return;
		Sort (0, Top - 1);
	}

	template <class ODT> void Sort (Array <ODT> & ar)
	{
		if (Top == 0)
			return;
		return Sort (0, Top - 1, ar);
	}

	template <class ODT> void Sort (FixArray <ODT> & ar)
	{
		if (Top == 0)
			return;
		return Sort (0, Top - 1, ar);
	}

	inline void HeapSort ()
	{
		HeapSort (ArraySize - 1);
	}


	inline bool IsExist (const DATATYPE & Value) const
	{
		return IndexOf (Value) != -1;
	}


	inline int IndexOf (const DATATYPE & Data) const
	{
		for (int Index=0; Index<Top; Index++)
		{
			if (Data == DataTable[Index])
				return Index;
		}
		return -1;
	}

	template <class ODT> inline int IndexOf (const ODT & Key) const
	{
		for (int Index=0; Index<Top; Index++)
		{
			if (Key == DataTable[Index])
				return Index;
		}
		return -1;
	}

	template <class Compare> inline int IndexOf (const DATATYPE & Key, Compare cf) const
	{
		for (int Index=0; Index<Top; Index++)
		{
			if (cf (Key, DataTable[Index]) == 0)
				return Index;
		}
		return -1;
	}

	template <class ODT, class Compare> inline int IndexOf (const ODT & Key, Compare cf) const
	{
		for (int Index=0; Index<Top; Index++)
		{
			if (cf (Key, DataTable[Index]) == 0)
				return Index;
		}
		return -1;
	}

	inline int LastIndexOf (const DATATYPE & Data) const
	{
		for (int Index=Top-1; Index>=0; Index--)
		{
			if (Data == DataTable[Index])
				return Index;
		}
		return -1;
	}


	inline int IndexOfSorted (const DATATYPE & Data) const
	{
		int Low  = 0;
		int High = Top - 1;
		while (Low <= High)
		{
			int Mid = (Low + High) >> 1;
			if (Data == DataTable[Mid])  return Mid;
			if (Data <  DataTable[Mid]) High = Mid -1;
			else Low = Mid + 1;
		}
		return -1;
	}

	template <class ODT> inline int IndexOfSorted (const ODT & Key) const
	{
		int Low  = 0;
		int High = Top - 1;
		while (Low <= High)
		{
			int Mid = (Low + High) >> 1;
			if (Key == DataTable[Mid])  return Mid;
			if (Key <  DataTable[Mid]) High = Mid -1;
			else Low = Mid + 1;
		}
		return -1;
	}

	template <class Compare> inline int IndexOfSorted (const DATATYPE & Key, Compare cf) const
	{
		int Low  = 0;
		int High = Top - 1;
		while (Low <= High)
		{
			int Mid = (Low + High) >> 1;
			if (cf (Key, DataTable[Mid]) == 0)  return Mid;
			if (cf (Key, DataTable[Mid]) < 0) High = Mid -1;
			else Low = Mid + 1;
		}
		return -1;
	}

	template <class ODT, class Compare> inline int IndexOfSorted (const ODT & Key, Compare cf) const
	{
		int Low  = 0;
		int High = Top - 1;
		while (Low <= High)
		{
			int Mid = (Low + High) >> 1;
			if (cf (Key, DataTable[Mid]) == 0)  return Mid;
			if (cf (Key, DataTable[Mid]) < 0) High = Mid -1;
			else Low = Mid + 1;
		}
		return -1;
	}


	inline DATATYPE * Find (const DATATYPE & Key) const
	{
		int Index = IndexOf (Key);
		if (Index != -1)
			return &GetAt (Index);
		return NULL;
	}

	template <class ODT> inline DATATYPE * Find (const ODT & Key) const
	{
		int Index = IndexOf (Key);
		if (Index != -1)
			return &GetAt (Index);
		return NULL;
	}

	template <class Compare> inline DATATYPE * Find (const DATATYPE & Key, Compare cf) const
	{
		int Index = IndexOf (Key);
		if (Index != -1)
			return &GetAt (Index);
		return NULL;
	}


	inline DATATYPE * FindSorted (const DATATYPE & Key) const
	{
		int Index = IndexOfSorted (Key);
		if (Index != -1)
			return &GetAt (Index);
		return NULL;
	}

	template <class ODT> inline DATATYPE * FindSorted (const ODT & Key) const
	{
		int Index = IndexOfSorted (Key);
		if (Index != -1)
			return &GetAt (Index);
		return NULL;
	}


	template <class Compare> inline DATATYPE * FindSorted (const DATATYPE & Key, Compare cf) const
	{
		int Index = IndexOfSorted (Key, cf);
		if (Index != -1)
			return &GetAt (Index);
		return NULL;
	}

	template <class ODT, class Compare> inline DATATYPE * FindSorted (const ODT & Key, Compare cf) const
	{
		int Index = IndexOfSorted (Key, cf);
		if (Index != -1)
			return &GetAt (Index);
		return NULL;
	}


	template <class pfnForEach> void ForEach (pfnForEach pf)
	{
		for (int Index=0; Index<Top; Index++)
		{
			DATATYPE & dt = GetAt (Index);
			if (! pf (dt))
				break;
		}
	}

	template <class pfnForEach> void ForEach (pfnForEach pf) const
	{
		for (int Index=0; Index<Top; Index++)
		{
			const DATATYPE & dt = GetAt (Index);
			if (! pf (dt))
				break;
		}
	}

protected:
	void Sort (int low, int high)
	{
		if (high <= low)
			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
		{
			while (scanUp <= scanDown && (*this)[scanUp] <= pivot)
			{
				scanUp ++;
			}

			while (pivot < (*this)[scanDown])
			{
				scanDown --;
			}

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

		(*this)[low] = (*this)[scanDown];
		(*this)[scanDown] = pivot;

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

	template <class ODT> void Sort (int low, int high, Array <ODT> & ar);
	template <class ODT> void Sort (int low, int high, FixArray <ODT> & ar);

//	template <class ODT> friend void Array <DATATYPE>::Sort (int low, int high, Array <ODT> & ar);
//	template <class ODT> friend void Array <DATATYPE>::Sort (int low, int high, FixArray <ODT> & ar);

protected:
	void HeapSort (int n);
	void HeapAdjust (int s, int m);
};


template <class DATATYPE> template <class ODT> void FixArray <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
	{
		while (scanUp <= scanDown && (*this)[scanUp] <= pivot)
		{
			scanUp ++;
		}

		while (pivot < (*this)[scanDown])
		{
			scanDown --;
		}

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

	(*this)[low] = (*this)[scanDown];
	(*this)[scanDown] = 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 FixArray <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
	{
		while (scanUp <= scanDown && (*this)[scanUp] <= pivot)
		{
			scanUp ++;
		}

		while (pivot < (*this)[scanDown])
		{
			scanDown --;
		}

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

	(*this)[low] = (*this)[scanDown];
	(*this)[scanDown] = 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);
};


template <class DATATYPE> void FixArray <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] 重新调整为大顶堆
	}
}


template <class DATATYPE> void FixArray <DATATYPE>::HeapAdjust (int s, int m)
{
	DATATYPE rc = GetAt (s);

	for (int j=2*s; j<=m; j*=2)
	{
		// 沿key较大的孩子结点向下筛选
		if (j < m && GetAt (j) < GetAt (j+1))
			j ++;

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

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

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