sortedarray.h

新的二维数组以及映射的快速算法的C语言实现.

//=========================================================
//	TITLE:		Sorted array
//				for WinNT, MSVC 6.0, MFC 6.00
//				Copyright (C) Matrix Baltic Software
//				Vilnius, Lithuania
//	MODULE:		SortedArray.h
//	PURPOSE:	Interface of the CSortedArray class.
//
//	AUTHOR:		Audrius Vasiliauskas
// 
//	NOTES:		TYPE: must have copy constructor, operator = , and operator <
//				Operator must be const 
//=========================================================


#ifndef __SORTED_ARRAY_H__
#define __SORTED_ARRAY_H__

#if _MSC_VER >= 1000
#pragma once
#endif // _MSC_VER >= 1000


#if _MSC_VER < 0x0600
	#pragma warning(disable : 4786) //identifier was truncated to '255' characters in the debug information
#endif

#ifndef __AFXTEMPL_H__
	#include <afxtempl.h>
#endif

#ifndef __SWAP_H__
	#include "Swap.h"
#endif

#ifndef __ARRAY_EX_H__
	#include "ArrayEx.h"
#endif

////////////////////////////////////////////////////////////////////////////
//
// Special compare functions for Sorted Array. 
//

template<class TYPE>
AFX_INLINE int __cdecl QSortCompareElements(const TYPE* pElement1, const TYPE* pElement2)
{
	ASSERT(AfxIsValidAddress(pElement1, sizeof(TYPE), FALSE));
	ASSERT(AfxIsValidAddress(pElement2, sizeof(TYPE), FALSE));

   if((*pElement1) == (*pElement2))
   {
      return 0;
   }
	
   if((*pElement1) < (*pElement2))
   {
      return -1;
   }

   return 1;
}

template<class TYPE>
AFX_INLINE int __cdecl QSortCompareElementsPointers(const TYPE* pElement1, const TYPE* pElement2)
{
	ASSERT(AfxIsValidAddress(pElement1, sizeof(TYPE), FALSE));
	ASSERT(AfxIsValidAddress(pElement2, sizeof(TYPE), FALSE));

   if((**pElement1) == (**pElement2))
   {
      return 0;
   }
	
   if((**pElement1) < (**pElement2))
   {
      return -1;
   }

   return 1;
}

//
////////////////////////////////////////////////////////////////////////////

template< class TYPE, class ARG_TYPE > 
class CSortedArray : public CArrayEx<TYPE, ARG_TYPE> 
{
// Types
public:
   typedef int    (__cdecl *QSortCompareFn)(const TYPE *pElement1, const TYPE *pElement2);

// Atributes
public:
	int m_nCutOff; // variable for sort speed tunning. Recommended range [3..128]


// Construction
public:
	CSortedArray();
	CSortedArray(const CSortedArray &x);
	virtual ~CSortedArray();

// Assigment
public:
	CSortedArray & operator = (const CSortedArray &x);

// Comparison 
public:
	BOOL operator <  (const CSortedArray &x) const;
	BOOL operator <= (const CSortedArray &x) const;
	BOOL operator == (const CSortedArray &x) const;
	BOOL operator != (const CSortedArray &x) const;
	BOOL operator >  (const CSortedArray &x) const;
	BOOL operator >= (const CSortedArray &x) const;

// Operator
public:
	operator CArrayEx<TYPE, ARG_TYPE>();

// Method
public:
	virtual int AddSorted(ARG_TYPE tValue);      // insert new element to sorted array and return insertion index
	virtual void Sort();					            // quick sort, use operator ==, <  and template functions CompareElements,CompareElementsLess

	virtual int Lookup(ARG_TYPE tValue) const;	// binary search if fail return -1 
	virtual int Search(ARG_TYPE tValue) const;	// binary search if fail return nearest item

   virtual void Sort(QSortCompareFn pCompareFn);
	virtual int Lookup(ARG_TYPE tValue,QSortCompareFn pCompareFn) const;	   // binary search if fail return -1 
	virtual int Search(ARG_TYPE tValue,QSortCompareFn pCompareFn) const;	   // binary search if fail return nearest item
   virtual int Find(ARG_TYPE tValue,QSortCompareFn pCompareFn) const;      // linear search for given value

// Private sort method
protected:
	void InsertionSort(int nLow, int nHigh);
	void QuickSort(int nLow, int nHigh);
};

// Implementation of the CSortedArray class.

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

template <class TYPE, class ARG_TYPE>
inline 
	CSortedArray<TYPE, ARG_TYPE>::CSortedArray ()
{
	m_nCutOff = 64;
}

template <class TYPE, class ARG_TYPE>
inline 
	CSortedArray<TYPE, ARG_TYPE>::CSortedArray (const CSortedArray &x)
{
	*this = x;
}

template <class TYPE, class ARG_TYPE>
inline 
	CSortedArray<TYPE, ARG_TYPE>::~CSortedArray ()
{
}

template <class TYPE, class ARG_TYPE>
inline CSortedArray<TYPE, ARG_TYPE> &
	   CSortedArray<TYPE, ARG_TYPE>::operator = (const CSortedArray &x)
{
	if(this != &x)
	{
		m_nCutOff = x.m_nCutOff;
		Copy(x);
	}

	return *this;
}

template <class TYPE, class ARG_TYPE>
inline int 
	CSortedArray<TYPE, ARG_TYPE>::Search(ARG_TYPE tValue) const
{	// binary search if fail return nearest item
	int nLow = 0, nHigh = GetSize(), nMid;

	while(nLow < nHigh)
	{
		nMid = (nLow + nHigh ) / 2;
		if(CompareElementsLess(&(m_pData[nMid]),&tValue))
		{
			nLow = nMid + 1;
		}
		else
		{
			nHigh = nMid;
		}
	}
	return nLow;
}

template <class TYPE, class ARG_TYPE>
inline int 
	CSortedArray<TYPE, ARG_TYPE>::Lookup(ARG_TYPE tValue) const
{	// binary search if fail return -1
	int nRet = Search(tValue);

	if(nRet < GetSize())
	{
		if(CompareElements(&(m_pData[nRet]),&tValue))
		{
			return nRet;
		}
	}

	return -1;
}

template <class TYPE, class ARG_TYPE>
inline void 
	CSortedArray<TYPE, ARG_TYPE>::InsertionSort(int nLow, int nHigh)
{
	int i;
	int j;
    for(i = nLow + 1;i <= nHigh; i++ )
    {
        TYPE tValue = DATA_ACCESS_OPERATOR(i);

        for(j = i;j > nLow && CompareElementsLess(&tValue,&(DATA_ACCESS_OPERATOR(j - 1)));j --)
		{
            DATA_ACCESS_OPERATOR(j) = DATA_ACCESS_OPERATOR(j - 1);
		}
        DATA_ACCESS_OPERATOR(j) = tValue;
    }
}


// Quicksort: sort first N items in array A
// TYPE: must have copy constructor, operator =, and operator <


template <class TYPE, class ARG_TYPE>
inline void 
	CSortedArray<TYPE, ARG_TYPE>::QuickSort(int nLow, int nHigh)
{
    if(nLow + m_nCutOff > nHigh )
	{
        InsertionSort(nLow,nHigh);
	}
    else
    {
            //Sort Low, Middle, High
        int nMid = (nLow + nHigh) / 2;	// middle value to partition about

        if(CompareElementsLess(&(DATA_ACCESS_OPERATOR(nMid)),&(DATA_ACCESS_OPERATOR(nLow))))
		{
            Swap(DATA_ACCESS_OPERATOR(nLow),DATA_ACCESS_OPERATOR(nMid));
		}
        if(CompareElementsLess(&(DATA_ACCESS_OPERATOR(nHigh)),&(DATA_ACCESS_OPERATOR(nLow))))
		{
            Swap(DATA_ACCESS_OPERATOR(nLow),DATA_ACCESS_OPERATOR(nHigh));
		}
        if(CompareElementsLess(&(DATA_ACCESS_OPERATOR(nHigh)),&(DATA_ACCESS_OPERATOR(nMid))))
		{
            Swap(DATA_ACCESS_OPERATOR(nMid),DATA_ACCESS_OPERATOR(nHigh));
		}

            // Place pivot at Position High-1
        TYPE tPivot = (DATA_ACCESS_OPERATOR(nMid));
        Swap(DATA_ACCESS_OPERATOR(nMid),DATA_ACCESS_OPERATOR(nHigh - 1));

            // Begin partitioning
        int i, j;
        for(i = nLow,j = nHigh - 1; ; )
        {
			// find first element too big to be in low partition
            while(CompareElementsLess(&(DATA_ACCESS_OPERATOR(++i)),&tPivot)) // Symantec may require { }
                ;                     // instead of ;

			// find first element too small to be in high partition
            while(CompareElementsLess(&tPivot,&(DATA_ACCESS_OPERATOR(--j)))) // for both these
                ;                     // loops. It should not.
            if(i < j)
			{
                Swap(DATA_ACCESS_OPERATOR(i),DATA_ACCESS_OPERATOR(j));
			}
            else
			{
                break;
			}
        }

        // Restore pivot
        Swap(DATA_ACCESS_OPERATOR(i),DATA_ACCESS_OPERATOR(nHigh - 1));

        QuickSort(nLow,i - 1);   // Sort small elements
        QuickSort(i + 1,nHigh);  // Sort large elements
    }
}

template <class TYPE, class ARG_TYPE>
inline void 
	CSortedArray<TYPE, ARG_TYPE>::Sort()
{
    QuickSort(0,GetSize() - 1);
}

template <class TYPE, class ARG_TYPE>
inline int		
	CSortedArray<TYPE, ARG_TYPE>::AddSorted(ARG_TYPE tValue)
{
	int nInsertIndex = Search(tValue);

	if(nInsertIndex < GetSize())
	{
		InsertAt(nInsertIndex,tValue);
	}
	else
	{
		nInsertIndex = Add(tValue);
	}

	return nInsertIndex;
}

template <class TYPE, class ARG_TYPE>
inline BOOL 
	CSortedArray<TYPE, ARG_TYPE>::operator <  (const CSortedArray &x) const
{
	return CArrayEx<TYPE, ARG_TYPE>::operator < (x);
}

template <class TYPE, class ARG_TYPE>
inline BOOL 
	CSortedArray<TYPE, ARG_TYPE>::operator <= (const CSortedArray &x) const
{
	return CArrayEx<TYPE, ARG_TYPE>::operator <= (x);
}

template <class TYPE, class ARG_TYPE>
inline BOOL 
	CSortedArray<TYPE, ARG_TYPE>::operator == (const CSortedArray &x) const
{
	return CArrayEx<TYPE, ARG_TYPE>::operator == (x);
}

template <class TYPE, class ARG_TYPE>
inline BOOL 
	CSortedArray<TYPE, ARG_TYPE>::operator != (const CSortedArray &x) const
{
	return CArrayEx<TYPE, ARG_TYPE>::operator != (x);
}

template <class TYPE, class ARG_TYPE>
inline BOOL 
	CSortedArray<TYPE, ARG_TYPE>::operator >  (const CSortedArray &x) const
{
	return CArrayEx<TYPE, ARG_TYPE>::operator > (x);
}

template <class TYPE, class ARG_TYPE>
inline BOOL 
	CSortedArray<TYPE, ARG_TYPE>::operator >= (const CSortedArray &x) const
{
	return CArrayEx<TYPE, ARG_TYPE>::operator >= (x);
}

template <class TYPE, class ARG_TYPE>
inline 
	CSortedArray<TYPE, ARG_TYPE>::operator CArrayEx<TYPE, ARG_TYPE>()
{
	return *this;
}

template <class TYPE, class ARG_TYPE>
inline void 
	CSortedArray<TYPE, ARG_TYPE>::Sort(QSortCompareFn pCompareFn)
{
   typedef int (__cdecl *compare )(const void *elem1,const void *elem2);

   ASSERT(pCompareFn);
   qsort(static_cast<void *>(GetData()),GetSize(),sizeof(TYPE),reinterpret_cast<compare>(pCompareFn));
}

template <class TYPE, class ARG_TYPE>
inline int 
	CSortedArray<TYPE, ARG_TYPE>::Find(ARG_TYPE tValue,QSortCompareFn pCompareFn) const
{
   int i;
   TYPE tItem = tValue;

   for(i = 0;i < GetSize();i ++)
   {
      if(pCompareFn(&(m_pData[i]),&tItem) == 0)
      {
         return i;
      }
   }

   return -1;
}

template <class TYPE, class ARG_TYPE>
inline int 
	CSortedArray<TYPE, ARG_TYPE>::Search(ARG_TYPE tValue,QSortCompareFn pCompareFn) const
{	// binary search if fail return nearest item
	int nLow = 0, nHigh = GetSize(), nMid;
   TYPE tItem = tValue;

	while(nLow < nHigh)
	{
		nMid = (nLow + nHigh ) / 2;
		if(pCompareFn(&(m_pData[nMid]),&tItem) < 0)
		{
			nLow = nMid + 1;
		}
		else
		{
			nHigh = nMid;
		}
	}
	return nLow;
}

template <class TYPE, class ARG_TYPE>
inline int 
	CSortedArray<TYPE, ARG_TYPE>::Lookup(ARG_TYPE tValue,QSortCompareFn pCompareFn) const
{	// binary search if fail return -1
	int nRet = Search(tValue,pCompareFn);
   TYPE tItem = tValue;

	if(nRet < GetSize())
	{
		if(pCompareFn(&(m_pData[nRet]),&tItem) == 0)
		{
			return nRet;
		}
	}

	return -1;
}


#endif // !defined(__SORTED_ARRAY_H__)