test-example-projects/c++_projects/84wsoui3/utilities/include/souicoll.h

// This is a part of the Active Template Library.
// Copyright (C) Microsoft Corporation
// All rights reserved.
//
// This source code is only intended as a supplement to the
// Active Template Library Reference and related
// electronic documentation provided with the library.
// See these sources for detailed information regarding the
// Active Template Library product.

#ifndef __SOUICOLL_H__
#define __SOUICOLL_H__

#pragma once

#include <windows.h>
#include <limits.h>
#include <soui_mem_wrapper.h>
#include "snew.h"

#pragma warning(push)
#pragma warning(disable: 4702)  // Unreachable code.  This file will have lots of it, especially without EH enabled.
#pragma warning(disable: 4512)  // assignment operator could not be generated
#pragma warning(disable: 4290)  // C++ Exception Specification ignored
#pragma warning(disable: 4127)  // conditional expression constant
#pragma warning(disable: 4571)  //catch(...) blocks compiled with /EHs do NOT catch or re-throw Structured Exceptions

// abstract iteration position

#ifndef _S_PACKING
#define _S_PACKING 8
#endif

#ifndef SASSERT
#define SASSERT(expr) __noop;
#endif // SASSERT

#define SThrow(expr) __noop;
#define SASSERT_VALID(x) __noop;

#ifndef SASSUME
#define SASSUME(expr) do { SASSERT(expr); __analysis_assume(!!(expr)); } while(0)
#endif // SASSUME

#ifndef SENSURE
#define SENSURE(expr) __noop;
#endif // SENSURE

/**
 * Avoid "unused parameter" warnings
 */
#ifndef SUNUSED
#define SUNUSED(x) (void)x;
#endif //SUNUSED

#if !defined(_W64)
#if !defined(__midl) &&    (defined(_X86_)    || defined(_M_IX86))
#define    _W64 __w64
#else
#define    _W64
#endif
#endif


#ifndef _STRY
#define _STRY try
#endif
#define _SCATCHALL() __pragma(warning(push)) __pragma(warning(disable: 4571)) catch( ... ) __pragma(warning(pop))


#pragma pack(push,_S_PACKING)
namespace SOUI
{

struct __SPOSITION
{
};
typedef __SPOSITION* SPOSITION;

template<typename T>
class SLimits;

template<>
class SLimits<int _W64>
{
public:
    static const int _Min=INT_MIN;
    static const int _Max=INT_MAX;
};

template<>
class SLimits<unsigned int _W64>
{
public:
    static const unsigned int _Min=0;
    static const unsigned int _Max=UINT_MAX;
};

template<>
class SLimits<long _W64>
{
public:
    static const long _Min=LONG_MIN;
    static const long _Max=LONG_MAX;
};

template<>
class SLimits<unsigned long _W64>
{
public:
    static const unsigned long _Min=0;
    static const unsigned long _Max=ULONG_MAX;
};

template<>
class SLimits<long long>
{
public:
    static const long long _Min=LLONG_MIN;
    static const long long _Max=LLONG_MAX;
};

template<>
class SLimits<unsigned long long>
{
public:
    static const unsigned long long _Min=0;
    static const unsigned long long _Max=ULLONG_MAX;
};

/* generic version */
template<typename T>
inline HRESULT SAdd(T* ptResult, T tLeft, T tRight)
{
    if(SLimits<T>::_Max-tLeft < tRight)
    {
        return E_INVALIDARG;
    }
    *ptResult= tLeft + tRight;
    return S_OK;
}

/* generic but compariatively slow version */
template<typename T>
inline HRESULT SMultiply(T* ptResult,    T tLeft, T tRight)
{
    /* avoid divide 0 */
    if(tLeft==0)
    {
        *ptResult=0;
        return S_OK;
    }
    if(SLimits<T>::_Max/tLeft < tRight)
    {
        return E_INVALIDARG;
    }
    *ptResult= tLeft * tRight;
    return S_OK;
}

/* fast    version    for    32 bit integers    */
template<>
inline HRESULT SMultiply(int _W64    *piResult, int _W64    iLeft, int _W64 iRight)
{
    __int64 i64Result=static_cast<__int64>(iLeft) * static_cast<__int64>(iRight);
    if(i64Result>INT_MAX || i64Result < INT_MIN)
    {
        return E_INVALIDARG;
    }
    *piResult=static_cast<int _W64>(i64Result);
    return S_OK;
}

template<>
inline HRESULT SMultiply(unsigned int    _W64 *piResult, unsigned int _W64 iLeft, unsigned int _W64 iRight)
{
    unsigned __int64 i64Result=static_cast<unsigned __int64>(iLeft) * static_cast<unsigned __int64>(iRight);
    if(i64Result>UINT_MAX)
    {
        return E_INVALIDARG;
    }
    *piResult=static_cast<unsigned int _W64>(i64Result);
    return S_OK;
}

template<>
inline HRESULT SMultiply(long    _W64 *piResult, long _W64 iLeft, long _W64 iRight)
{
    __int64 i64Result=static_cast<__int64>(iLeft) * static_cast<__int64>(iRight);
    if(i64Result>LONG_MAX || i64Result < LONG_MIN)
    {
        return E_INVALIDARG;
    }
    *piResult=static_cast<long _W64>(i64Result);
    return S_OK;
}

template<>
inline HRESULT SMultiply(unsigned long _W64 *piResult, unsigned long _W64 iLeft, unsigned long _W64 iRight)
{
    unsigned __int64 i64Result=static_cast<unsigned __int64>(iLeft) * static_cast<unsigned __int64>(iRight);
    if(i64Result>ULONG_MAX)
    {
        return E_INVALIDARG;
    }
    *piResult=static_cast<unsigned long _W64>(i64Result);
    return S_OK;
}

struct SPlex     // warning variable length structure
{
    SPlex* pNext;
#if (_S_PACKING >= 8)
    DWORD dwReserved[1];    // align on 8 byte boundary
#endif
    // BYTE data[maxNum*elementSize];

    void* data()
    {
        return this+1;
    }

    static SPlex* Create(SPlex*& head, size_t nMax, size_t cbElement);
    // like 'calloc' but no zero fill
    // may throw memory exceptions

    void FreeDataChain();       // soui_mem_wrapper::SouiFree this one and links
};

inline SPlex* SPlex::Create( SPlex*& pHead, size_t nMax, size_t nElementSize )
{
    SPlex* pPlex;

    SASSERT( nMax > 0 );
    SASSERT( nElementSize > 0 );

    size_t nBytes=0;
    if(     FAILED(SMultiply(&nBytes, nMax, nElementSize)) ||
            FAILED(SAdd(&nBytes, nBytes, sizeof(SPlex))) )
    {
        return NULL;
    }
    pPlex = static_cast< SPlex* >( soui_mem_wrapper::SouiMalloc( nBytes ) );
    if( pPlex == NULL )
    {
        return( NULL );
    }

    pPlex->pNext = pHead;
    pHead = pPlex;

    return( pPlex );
}

inline void SPlex::FreeDataChain()
{
    SPlex* pPlex;

    pPlex = this;
    while( pPlex != NULL )
    {
        SPlex* pNext;

        pNext = pPlex->pNext;
        soui_mem_wrapper::SouiFree( pPlex );
        pPlex = pNext;
    }
}

template< typename T >
class CElementTraitsBase
{
public:
    typedef const T& INARGTYPE;
    typedef T& OUTARGTYPE;

    static void CopyElements( T* pDest, const T* pSrc, size_t nElements )
    {
        for( size_t iElement = 0; iElement < nElements; iElement++ )
        {
            pDest[iElement] = pSrc[iElement];
        }
    }

    static void RelocateElements( T* pDest, T* pSrc, size_t nElements )
    {
        // A simple memmove works for nearly all types.
        // You'll have to override this for types that have pointers to their
        // own members.
        memmove_s( pDest, nElements*sizeof( T ), pSrc, nElements*sizeof( T ));
    }
};

template< typename T >
class CDefaultHashTraits
{
public:
    static ULONG Hash( const T& element )
    {
        return( ULONG( ULONG_PTR( element ) ) );
    }
};

template< typename T >
class CDefaultCompareTraits
{
public:
    static bool CompareElements( const T& element1, const T& element2 )
    {
        return( (element1 == element2) != 0 );  // != 0 to handle overloads of operator== that return BOOL instead of bool
    }

    static int CompareElementsOrdered( const T& element1, const T& element2 )
    {
        if( element1 < element2 )
        {
            return( -1 );
        }
        else if( element1 == element2 )
        {
            return( 0 );
        }
        else
        {
            SASSERT( element1 > element2 );
            return( 1 );
        }
    }
};

template< typename T >
class CDefaultElementTraits :
    public CElementTraitsBase< T >,
    public CDefaultHashTraits< T >,
    public CDefaultCompareTraits< T >
{
};

template< typename T >
class CElementTraits :
    public CDefaultElementTraits< T >
{
};

template<>
class CElementTraits< GUID > :
    public CElementTraitsBase< GUID >
{
public:
    static ULONG Hash( INARGTYPE guid )
    {
        const DWORD* pdwData = reinterpret_cast< const DWORD* >( &guid );

        return( pdwData[0]^pdwData[1]^pdwData[2]^pdwData[3] );
    }

    static bool CompareElements( INARGTYPE element1, INARGTYPE element2 )
    {
        return( (element1 == element2) != 0 );  // != 0 to handle overloads of operator== that return BOOL instead of bool
    }

    static int CompareElementsOrdered( INARGTYPE element1, INARGTYPE element2 )
    {
        const DWORD* pdwData1 = reinterpret_cast< const DWORD* >( &element1 );
        const DWORD* pdwData2 = reinterpret_cast< const DWORD* >( &element2 );

        for( int iDWORD = 3; iDWORD >= 0; iDWORD-- )
        {
            if( pdwData1[iDWORD] > pdwData2[iDWORD] )
            {
                return( 1 );
            }
            else if( pdwData1[iDWORD] < pdwData2[iDWORD] )
            {
                return( -1 );
            }
        }

        return( 0 );
    }
};
 

template< typename T >
class SStringRefElementTraits :
    public CElementTraitsBase< T >
{
public:
    static ULONG Hash(typename CElementTraitsBase<T>::INARGTYPE str )
    {
        ULONG nHash = 0;

        const T::XCHAR* pch = str;

        SENSURE( pch != NULL );

        while( *pch != 0 )
        {
            nHash = (nHash<<5)+nHash+(*pch);
            pch++;
        }

        return( nHash );
    }

    static bool CompareElements(typename CElementTraitsBase<T>::INARGTYPE element1, typename CElementTraitsBase<T>::INARGTYPE element2 )
    {
        return( element1 == element2 );
    }

    static int CompareElementsOrdered(typename CElementTraitsBase<T>::INARGTYPE str1, typename CElementTraitsBase<T>::INARGTYPE str2 )
    {
        return( str1.Compare( str2 ) );
    }
};

template< typename T >
class CPrimitiveElementTraits :
    public CDefaultElementTraits< T >
{
public:
    typedef T INARGTYPE;
    typedef T& OUTARGTYPE;
};

#define _DECLARE_PRIMITIVE_TRAITS( T ) \
    template<> \
    class CElementTraits< T > : \
    public CPrimitiveElementTraits< T > \
    { \
    };

_DECLARE_PRIMITIVE_TRAITS( unsigned char )
_DECLARE_PRIMITIVE_TRAITS( unsigned short )
_DECLARE_PRIMITIVE_TRAITS( unsigned int )
_DECLARE_PRIMITIVE_TRAITS( unsigned long )
_DECLARE_PRIMITIVE_TRAITS( unsigned __int64 )
_DECLARE_PRIMITIVE_TRAITS( signed char )
_DECLARE_PRIMITIVE_TRAITS( char )
_DECLARE_PRIMITIVE_TRAITS( short )
_DECLARE_PRIMITIVE_TRAITS( int )
_DECLARE_PRIMITIVE_TRAITS( long )
_DECLARE_PRIMITIVE_TRAITS( __int64 )
_DECLARE_PRIMITIVE_TRAITS( float )
_DECLARE_PRIMITIVE_TRAITS( double )
_DECLARE_PRIMITIVE_TRAITS( bool )
#ifdef _NATIVE_WCHAR_T_DEFINED
_DECLARE_PRIMITIVE_TRAITS( wchar_t )
#endif
_DECLARE_PRIMITIVE_TRAITS( void* )

template< typename E, class ETraits = CElementTraits< E > >
class SArray
{
public:
    typedef typename ETraits::INARGTYPE INARGTYPE;
    typedef typename ETraits::OUTARGTYPE OUTARGTYPE;

public:
    SArray();
	SArray(const SArray &src);

    size_t GetCount() const;
    bool IsEmpty() const;
    bool SetCount( size_t nNewSize, int nGrowBy = -1 );

    void FreeExtra();
    void RemoveAll();

    const E& GetAt( size_t iElement ) const;
    void SetAt( size_t iElement, INARGTYPE element );
    E& GetAt( size_t iElement );

    const E* GetData() const;
    E* GetData();

    void SetAtGrow( size_t iElement, INARGTYPE element );
    // Add an empty element to the end of the array
    size_t Add();
    // Add an element to the end of the array
    size_t Add( INARGTYPE element );
    size_t Append( const SArray< E, ETraits >& aSrc );
    void Copy( const SArray< E, ETraits >& aSrc );

    const E& operator[]( size_t iElement ) const;
    E& operator[]( size_t iElement );

    SArray< E, ETraits > & operator = (const SArray< E, ETraits >& src);

    void InsertAt( size_t iElement, INARGTYPE element, size_t nCount = 1 );
    void InsertArrayAt( size_t iStart, const SArray< E, ETraits >* paNew );
    void RemoveAt( size_t iElement, size_t nCount = 1 );

	int Find(const E & target) const;
#ifdef _DEBUG
    void AssertValid() const;
#endif  // _DEBUG

private:
    bool GrowBuffer( size_t nNewSize );

    // Implementation
private:
    E* m_pData;
    size_t m_nSize;
    size_t m_nMaxSize;
    int m_nGrowBy;

private:
    static void CallConstructors( E* pElements, size_t nElements );
    static void CallDestructors( E* pElements, size_t nElements );

public:
    ~SArray();

};

template< typename E, class ETraits /*= CElementTraits< E > */>
SArray< E, ETraits > & SArray<E, ETraits>::operator=(const SArray< E, ETraits >& src)
{
    this->Copy(src);
    return *this;
}

template< typename E, class ETraits >
int SArray<E, ETraits>::Find(const E & target) const
{
	for(size_t i=0;i<GetCount();i++)
	{
		if(GetAt(i) == target) return i;
	}
	return -1;
}


template< typename E, class ETraits >
inline size_t SArray< E, ETraits >::GetCount() const
{
    return( m_nSize );
}

template< typename E, class ETraits >
inline bool SArray< E, ETraits >::IsEmpty() const
{
    return( m_nSize == 0 );
}

template< typename E, class ETraits >
inline void SArray< E, ETraits >::RemoveAll()
{
    SetCount( 0, -1 );
}

template< typename E, class ETraits >
inline const E& SArray< E, ETraits >::GetAt( size_t iElement ) const
{
    SASSERT( iElement < m_nSize );
    if(iElement >= m_nSize)
        SThrow(E_INVALIDARG);

    return( m_pData[iElement] );
}

template< typename E, class ETraits >
inline void SArray< E, ETraits >::SetAt( size_t iElement, INARGTYPE element )
{
    SASSERT( iElement < m_nSize );
    if(iElement >= m_nSize)
        SThrow(E_INVALIDARG);

    m_pData[iElement] = element;
}

template< typename E, class ETraits >
inline E& SArray< E, ETraits >::GetAt( size_t iElement )
{
    SASSERT( iElement < m_nSize );
    if(iElement >= m_nSize)
        SThrow(E_INVALIDARG);

    return( m_pData[iElement] );
}

template< typename E, class ETraits >
inline const E* SArray< E, ETraits >::GetData() const
{
    return( m_pData );
}

template< typename E, class ETraits >
inline E* SArray< E, ETraits >::GetData()
{
    return( m_pData );
}

template< typename E, class ETraits >
inline size_t SArray< E, ETraits >::Add()
{
    size_t iElement;

    iElement = m_nSize;
    bool bSuccess=SetCount( m_nSize+1 );
    if( !bSuccess )
    {
        SThrow( E_OUTOFMEMORY );
    }

    return( iElement );
}

#pragma push_macro("new")
#undef new

template< typename E, class ETraits >
inline size_t SArray< E, ETraits >::Add( INARGTYPE element )
{
    size_t iElement;

    iElement = m_nSize;
    if( iElement >= m_nMaxSize )
    {
        bool bSuccess = GrowBuffer( iElement+1 );
        if( !bSuccess )
        {
            SThrow( E_OUTOFMEMORY );
        }
    }
    ::new( m_pData+iElement ) E( element );
    m_nSize++;

    return( iElement );
}

#pragma pop_macro("new")

template< typename E, class ETraits >
inline const E& SArray< E, ETraits >::operator[]( size_t iElement ) const
{
    SASSERT( iElement < m_nSize );
    if(iElement >= m_nSize)
        SThrow(E_INVALIDARG);

    return( m_pData[iElement] );
}

template< typename E, class ETraits >
inline E& SArray< E, ETraits >::operator[]( size_t iElement )
{
    SASSERT( iElement < m_nSize );
    if(iElement >= m_nSize)
        SThrow(E_INVALIDARG);

    return( m_pData[iElement] );
}

template< typename E, class ETraits >
SArray< E, ETraits >::SArray() :
    m_pData( NULL ),
    m_nSize( 0 ),
    m_nMaxSize( 0 ),
    m_nGrowBy( 0 )
{
}

template< typename E, class ETraits >
SArray< E, ETraits >::SArray(const SArray< E, ETraits > & src) :
    m_pData( NULL ),
    m_nSize( 0 ),
    m_nMaxSize( 0 ),
    m_nGrowBy( 0 )
{
	Copy(src);
}

template< typename E, class ETraits >
SArray< E, ETraits >::~SArray()
{
    if( m_pData != NULL )
    {
        CallDestructors( m_pData, m_nSize );
        soui_mem_wrapper::SouiFree( m_pData );
    }
}

template< typename E, class ETraits >
bool SArray< E, ETraits >::GrowBuffer( size_t nNewSize )
{
    if( nNewSize > m_nMaxSize )
    {
        if( m_pData == NULL )
        {
            size_t nAllocSize =  size_t( m_nGrowBy ) > nNewSize ? size_t( m_nGrowBy ) : nNewSize ;
            m_pData = static_cast< E* >( soui_mem_wrapper::SouiCalloc( nAllocSize,sizeof( E ) ) );
            if( m_pData == NULL )
            {
                return( false );
            }
            m_nMaxSize = nAllocSize;
        }
        else
        {
            // otherwise, grow array
            size_t nGrowBy = m_nGrowBy;
            if( nGrowBy == 0 )
            {
                // heuristically determine growth when nGrowBy == 0
                //  (this avoids heap fragmentation in many situations)
                nGrowBy = m_nSize/8;
                nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy);
            }
            size_t nNewMax;
            if( nNewSize < (m_nMaxSize+nGrowBy) )
                nNewMax = m_nMaxSize+nGrowBy;  // granularity
            else
                nNewMax = nNewSize;  // no slush

            SASSERT( nNewMax >= m_nMaxSize );  // no wrap around
#ifdef SIZE_T_MAX
            SASSERT( nNewMax <= SIZE_T_MAX/sizeof( E ) ); // no overflow
#endif
            E* pNewData = static_cast< E* >( soui_mem_wrapper::SouiCalloc( nNewMax,sizeof( E ) ) );
            if( pNewData == NULL )
            {
                return false;
            }

            // copy new data from old
            ETraits::RelocateElements( pNewData, m_pData, m_nSize );

            // get rid of old stuff (note: no destructors called)
            soui_mem_wrapper::SouiFree( m_pData );
            m_pData = pNewData;
            m_nMaxSize = nNewMax;
        }
    }

    return true;
}

template< typename E, class ETraits >
bool SArray< E, ETraits >::SetCount( size_t nNewSize, int nGrowBy )
{
    SASSERT_VALID(this);

    if( nGrowBy != -1 )
    {
        m_nGrowBy = nGrowBy;  // set new size
    }

    if( nNewSize == 0 )
    {
        // shrink to nothing
        if( m_pData != NULL )
        {
            CallDestructors( m_pData, m_nSize );
            soui_mem_wrapper::SouiFree( m_pData );
            m_pData = NULL;
        }
        m_nSize = 0;
        m_nMaxSize = 0;
    }
    else if( nNewSize <= m_nMaxSize )
    {
        // it fits
        if( nNewSize > m_nSize )
        {
            // initialize the new elements
            CallConstructors( m_pData+m_nSize, nNewSize-m_nSize );
        }
        else if( m_nSize > nNewSize )
        {
            // destroy the old elements
            CallDestructors( m_pData+nNewSize, m_nSize-nNewSize );
        }
        m_nSize = nNewSize;
    }
    else
    {
        bool bSuccess;

        bSuccess = GrowBuffer( nNewSize );
        if( !bSuccess )
        {
            return( false );
        }

        // construct new elements
        SASSERT( nNewSize > m_nSize );
        CallConstructors( m_pData+m_nSize, nNewSize-m_nSize );

        m_nSize = nNewSize;
    }

    return true;
}

template< typename E, class ETraits >
size_t SArray< E, ETraits >::Append( const SArray< E, ETraits >& aSrc )
{
    SASSERT_VALID(this);
    SASSERT( this != &aSrc );   // cannot append to itself

    size_t nOldSize = m_nSize;
    bool bSuccess=SetCount( m_nSize+aSrc.m_nSize );
    if( !bSuccess )
    {
        SThrow( E_OUTOFMEMORY );
    }

    ETraits::CopyElements( m_pData+nOldSize, aSrc.m_pData, aSrc.m_nSize );

    return( nOldSize );
}

template< typename E, class ETraits >
void SArray< E, ETraits >::Copy( const SArray< E, ETraits >& aSrc )
{
    SASSERT_VALID(this);
    SASSERT( this != &aSrc );   // cannot append to itself

    bool bSuccess=SetCount( aSrc.m_nSize );
    if( !bSuccess )
    {
        SThrow( E_OUTOFMEMORY );
    }

    ETraits::CopyElements( m_pData, aSrc.m_pData, aSrc.m_nSize );
}

template< typename E, class ETraits >
void SArray< E, ETraits >::FreeExtra()
{
    SASSERT_VALID(this);

    if( m_nSize != m_nMaxSize )
    {
        // shrink to desired size
#ifdef SIZE_T_MAX
        SASSUME( m_nSize <= (SIZE_T_MAX/sizeof( E )) ); // no overflow
#endif
        E* pNewData = NULL;
        if( m_nSize != 0 )
        {
            pNewData = (E*)soui_mem_wrapper::SouiCalloc( m_nSize,sizeof( E ) );
            if( pNewData == NULL )
            {
                return;
            }

            // copy new data from old
            ETraits::RelocateElements( pNewData, m_pData, m_nSize );
        }

        // get rid of old stuff (note: no destructors called)
        soui_mem_wrapper::SouiFree( m_pData );
        m_pData = pNewData;
        m_nMaxSize = m_nSize;
    }
}

template< typename E, class ETraits >
void SArray< E, ETraits >::SetAtGrow( size_t iElement, INARGTYPE element )
{
    SASSERT_VALID(this);
    size_t nOldSize;

    nOldSize = m_nSize;
    if( iElement >= m_nSize )
    {
        bool bSuccess=SetCount( iElement+1, -1 );
        if( !bSuccess )
        {
            SThrow( E_OUTOFMEMORY );
        }
    }

//     _STRY
    {
        m_pData[iElement] = element;
    }
//     _SCATCHALL()
//     {
//         if( m_nSize != nOldSize )
//         {
//             SetCount( nOldSize, -1 );
//         }
//     }
}

template< typename E, class ETraits >
void SArray< E, ETraits >::InsertAt( size_t iElement, INARGTYPE element, size_t nElements /*=1*/)
{
    SASSERT_VALID(this);
    SASSERT( nElements > 0 );     // zero size not allowed

    if( iElement >= m_nSize )
    {
        // adding after the end of the array
        bool bSuccess=SetCount( iElement+nElements, -1 );   // grow so nIndex is valid
        if( !bSuccess )
        {
            SThrow( E_OUTOFMEMORY );
        }
    }
    else
    {
        // inserting in the middle of the array
        size_t nOldSize = m_nSize;
        bool bSuccess=SetCount( m_nSize+nElements, -1 );  // grow it to new size
        if( !bSuccess )
        {
            SThrow( E_OUTOFMEMORY );
        }
        // destroy intial data before copying over it
        CallDestructors( m_pData+nOldSize, nElements );
        // shift old data up to fill gap
        ETraits::RelocateElements( m_pData+(iElement+nElements), m_pData+iElement,
                                   nOldSize-iElement );

		CallConstructors(m_pData + iElement, nElements);
	}

    // insert new value in the gap
    SASSERT( (iElement+nElements) <= m_nSize );
    for( size_t iNewElement = iElement; iNewElement < (iElement+nElements); iNewElement++ )
    {
        m_pData[iNewElement] = element;
    }
}

template< typename E, class ETraits >
void SArray< E, ETraits >::RemoveAt( size_t iElement, size_t nElements )
{
    SASSERT_VALID(this);
    SASSERT( (iElement+nElements) <= m_nSize );

    size_t newCount = iElement+nElements;
    if ((newCount < iElement) || (newCount < nElements) || (newCount > m_nSize))
        SThrow(E_INVALIDARG);

    // just remove a range
    size_t nMoveCount = m_nSize-(newCount);
    CallDestructors( m_pData+iElement, nElements );
    if( nMoveCount > 0 )
    {
        ETraits::RelocateElements( m_pData+iElement, m_pData+(newCount),
                                   nMoveCount );
    }
    m_nSize -= nElements;
}

template< typename E, class ETraits >
void SArray< E, ETraits >::InsertArrayAt( size_t iStartElement,
        const SArray< E, ETraits >* paNew )
{
    SASSERT_VALID( this );
    SENSURE( paNew != NULL );
    SASSERT_VALID( paNew );

    if( paNew->GetCount() > 0 )
    {
        InsertAt( iStartElement, paNew->GetAt( 0 ), paNew->GetCount() );
        for( size_t iElement = 0; iElement < paNew->GetCount(); iElement++ )
        {
            SetAt( iStartElement+iElement, paNew->GetAt( iElement ) );
        }
    }
}

#ifdef _DEBUG
template< typename E, class ETraits >
void SArray< E, ETraits >::AssertValid() const
{
    if( m_pData == NULL )
    {
        SASSUME( m_nSize == 0 );
        SASSUME( m_nMaxSize == 0 );
    }
    else
    {
        SASSUME( m_nSize <= m_nMaxSize );
    }
}
#endif

#pragma push_macro("new")
#undef new

template< typename E, class ETraits >
void SArray< E, ETraits >::CallConstructors( E* pElements, size_t nElements )
{
    size_t iElement = 0;
	for (iElement = 0; iElement < nElements; iElement++)
	{
		::new(pElements + iElement) E;
	}
}

#pragma pop_macro("new")

template< typename E, class ETraits >
void SArray< E, ETraits >::CallDestructors( E* pElements, size_t nElements )
{
    (void)pElements;

    for( size_t iElement = 0; iElement < nElements; iElement++ )
    {
        pElements[iElement].~E();
    }
}


template< typename E, class ETraits = CElementTraits< E > >
class SList
{
public:
    typedef typename ETraits::INARGTYPE INARGTYPE;

private:
    class CNode :
        public __SPOSITION
    {
    public:
        CNode()
        {
        }
        CNode( INARGTYPE element ) :
            m_element( element )
        {
        }
        ~CNode()
        {
        }

    public:
        CNode* m_pNext;
        CNode* m_pPrev;
        E m_element;

    private:
        CNode( const CNode& );
    };

public:
    SList( UINT nBlockSize = 10 );
	SList( const SList& src);
	~SList();


    size_t GetCount() const;
    bool IsEmpty() const;

	SList& operator=( const SList& src);
	void Copy(const SList & src);

    E& GetHead();
    const E& GetHead() const;
    E& GetTail();
    const E& GetTail() const;

    E RemoveHead();
    E RemoveTail();
    void RemoveHeadNoReturn();
    void RemoveTailNoReturn();

    SPOSITION AddHead();
    SPOSITION AddHead( INARGTYPE element );
    void AddHeadList( const SList< E, ETraits >* plNew );
    SPOSITION AddTail();
    SPOSITION AddTail( INARGTYPE element );
    void AddTailList( const SList< E, ETraits >* plNew );

    void RemoveAll();

    SPOSITION GetHeadPosition() const;
    SPOSITION GetTailPosition() const;
    SPOSITION Next(SPOSITION pos) const;
    SPOSITION Prev(SPOSITION pos) const;
    E& GetNext( SPOSITION& pos );
    const E& GetNext( SPOSITION& pos ) const;
    E& GetPrev( SPOSITION& pos );
    const E& GetPrev( SPOSITION& pos ) const;

    E& GetAt( SPOSITION pos );
    const E& GetAt( SPOSITION pos ) const;
    void SetAt( SPOSITION pos, INARGTYPE element );
    void RemoveAt( SPOSITION pos );

    SPOSITION InsertBefore( SPOSITION pos, INARGTYPE element );
    SPOSITION InsertAfter( SPOSITION pos, INARGTYPE element );

    SPOSITION Find( INARGTYPE element, SPOSITION posStartAfter = NULL ) const;
    SPOSITION FindIndex( size_t iElement ) const;

    void MoveToHead( SPOSITION pos );
    void MoveToTail( SPOSITION pos );
    void SwapElements( SPOSITION pos1, SPOSITION pos2 );
	void Swap(SList< E, ETraits > &src);

#ifdef _DEBUG
    void AssertValid() const;
#endif  // _DEBUG

    // Implementation
private:
    CNode* m_pHead;
    CNode* m_pTail;
    size_t m_nElements;
    SPlex* m_pBlocks;
    CNode* m_pFree;
    UINT m_nBlockSize;

private:
    void GetFreeNode();
    CNode* NewNode( CNode* pPrev, CNode* pNext );
    CNode* NewNode( INARGTYPE element, CNode* pPrev, CNode* pNext );
    void FreeNode( CNode* pNode );

};

template< typename E, class ETraits >
inline size_t SList< E, ETraits >::GetCount() const
{
    return( m_nElements );
}

template< typename E, class ETraits >
inline bool SList< E, ETraits >::IsEmpty() const
{
    return( m_nElements == 0 );
}

template< typename E, class ETraits >
inline E& SList< E, ETraits >::GetHead()
{
    SENSURE( m_pHead != NULL );
    return( m_pHead->m_element );
}

template< typename E, class ETraits >
inline const E& SList< E, ETraits >::GetHead() const
{
    SENSURE( m_pHead != NULL );
    return( m_pHead->m_element );
}

template< typename E, class ETraits >
inline E& SList< E, ETraits >::GetTail()
{
    SENSURE( m_pTail != NULL );
    return( m_pTail->m_element );
}

template< typename E, class ETraits >
inline const E& SList< E, ETraits >::GetTail() const
{
    SENSURE( m_pTail != NULL );
    return( m_pTail->m_element );
}

template< typename E, class ETraits >
inline SPOSITION SList< E, ETraits >::GetHeadPosition() const
{
    return( SPOSITION( m_pHead ) );
}

template< typename E, class ETraits >
inline SPOSITION SList< E, ETraits >::GetTailPosition() const
{
    return( SPOSITION( m_pTail ) );
}

template< typename E, class ETraits >
inline SPOSITION SList< E, ETraits >::Next( SPOSITION pos ) const
{
    CNode* pNode;

    SENSURE( pos != NULL );
    pNode = (CNode*)pos;
    return SPOSITION( pNode->m_pNext );
}

template< typename E, class ETraits >
inline SPOSITION SList< E, ETraits >::Prev( SPOSITION pos ) const
{
    CNode* pNode;

    SENSURE( pos != NULL );
    pNode = (CNode*)pos;
    return SPOSITION( pNode->m_pPrev );
}


template< typename E, class ETraits >
inline E& SList< E, ETraits >::GetNext( SPOSITION& pos )
{
    CNode* pNode;

    SENSURE( pos != NULL );
    pNode = (CNode*)pos;
    pos = SPOSITION( pNode->m_pNext );

    return( pNode->m_element );
}


template< typename E, class ETraits >
inline const E& SList< E, ETraits >::GetNext( SPOSITION& pos ) const
{
    CNode* pNode;

    SENSURE( pos != NULL );
    pNode = (CNode*)pos;
    pos = SPOSITION( pNode->m_pNext );

    return( pNode->m_element );
}

template< typename E, class ETraits >
inline E& SList< E, ETraits >::GetPrev( SPOSITION& pos )
{
    CNode* pNode;

    SENSURE( pos != NULL );
    pNode = (CNode*)pos;
    pos = SPOSITION( pNode->m_pPrev );

    return( pNode->m_element );
}

template< typename E, class ETraits >
inline const E& SList< E, ETraits >::GetPrev( SPOSITION& pos ) const
{
    CNode* pNode;

    SASSERT( pos != NULL );
    pNode = (CNode*)pos;
    pos = SPOSITION( pNode->m_pPrev );

    return( pNode->m_element );
}

template< typename E, class ETraits >
inline E& SList< E, ETraits >::GetAt( SPOSITION pos )
{
    SENSURE( pos != NULL );
    CNode* pNode = (CNode*)pos;
    return( pNode->m_element );
}

template< typename E, class ETraits >
inline const E& SList< E, ETraits >::GetAt( SPOSITION pos ) const
{
    SENSURE( pos != NULL );
    CNode* pNode = (CNode*)pos;
    return( pNode->m_element );
}

template< typename E, class ETraits >
inline void SList< E, ETraits >::SetAt( SPOSITION pos, INARGTYPE element )
{
    SENSURE( pos != NULL );
    CNode* pNode = (CNode*)pos;
    pNode->m_element = element;
}

template< typename E, class ETraits >
SList< E, ETraits >::SList( UINT nBlockSize ) :
    m_pHead( NULL ),
    m_pTail( NULL ),
    m_nElements(0),
    m_pBlocks( NULL ),
    m_pFree( NULL ),
    m_nBlockSize(nBlockSize)
{
    SASSERT( nBlockSize > 0 );
}

template< typename E, class ETraits >
inline SList< E, ETraits >::SList(const SList<E,ETraits> &src) :
    m_pHead( NULL ),
    m_pTail( NULL ),
    m_nElements(0),
    m_pBlocks( NULL ),
    m_pFree( NULL ),
    m_nBlockSize(src.m_nBlockSize)
{
	Copy(src);
}

template< typename E, class ETraits >
void SList< E, ETraits >::Copy(const SList<E,ETraits> &src) 
{
	RemoveAll();
	SPOSITION pos=src.GetHeadPosition();
	while(pos)
	{
		const E &t=src.GetNext(pos);
		AddTail(t);
	}
}

template< typename E, class ETraits >
SList< E, ETraits > & SList< E, ETraits >::operator = (const SList< E, ETraits > & src)
{
	Copy(src);
	return *this;
}

template< typename E, class ETraits >
void SList< E, ETraits >::RemoveAll()
{
    while( m_nElements > 0 )
    {
        CNode* pKill = m_pHead;
        SENSURE( pKill != NULL );

        m_pHead = m_pHead->m_pNext;
        FreeNode( pKill );
    }

    SASSUME( m_nElements == 0 );
    m_pHead = NULL;
    m_pTail = NULL;
    m_pFree = NULL;

    if( m_pBlocks != NULL )
    {
        m_pBlocks->FreeDataChain();
        m_pBlocks = NULL;
    }
}

template< typename E, class ETraits >
SList< E, ETraits >::~SList()
{
    RemoveAll();
    SASSUME( m_nElements == 0 );
}


template< typename E, class ETraits >
void SList< E, ETraits >::GetFreeNode()
{
    if( m_pFree == NULL )
    {
        SPlex* pPlex;
        CNode* pNode;

        pPlex = SPlex::Create( m_pBlocks, m_nBlockSize, sizeof( CNode ) );
        if( pPlex == NULL )
        {
            SThrow( E_OUTOFMEMORY );
        }
        pNode = (CNode*)pPlex->data();
        pNode += m_nBlockSize-1;
        for( int iBlock = m_nBlockSize-1; iBlock >= 0; iBlock-- )
        {
            pNode->m_pNext = m_pFree;
            m_pFree = pNode;
            pNode--;
        }
    }
    SASSUME( m_pFree != NULL );
}

#pragma push_macro("new")
#undef new
template< typename E, class ETraits >
typename SList< E, ETraits >::CNode* SList< E, ETraits >::NewNode( CNode* pPrev, CNode* pNext )
{
    GetFreeNode();

    CNode* pNewNode = m_pFree;
    CNode* pNextFree = m_pFree->m_pNext;

    ::new( pNewNode ) CNode;

    m_pFree = pNextFree;
    pNewNode->m_pPrev = pPrev;
    pNewNode->m_pNext = pNext;
    m_nElements++;
    SASSUME( m_nElements > 0 );

    return( pNewNode );
} 
    
template< typename E, class ETraits >
typename SList< E, ETraits >::CNode* SList< E, ETraits >::NewNode( INARGTYPE element, CNode* pPrev,
        CNode* pNext )
{
    GetFreeNode();

    CNode* pNewNode = m_pFree;
    CNode* pNextFree = m_pFree->m_pNext;

    ::new( pNewNode ) CNode( element );

    m_pFree = pNextFree;
    pNewNode->m_pPrev = pPrev;
    pNewNode->m_pNext = pNext;
    m_nElements++;
    SASSUME( m_nElements > 0 );

    return( pNewNode );
}

#pragma pop_macro("new")

template< typename E, class ETraits >
void SList< E, ETraits >::FreeNode( CNode* pNode )
{
    pNode->~CNode();
    pNode->m_pNext = m_pFree;
    m_pFree = pNode;
    SASSUME( m_nElements > 0 );
    m_nElements--;
    if( m_nElements == 0 )
    {
        RemoveAll();
    }
}

template< typename E, class ETraits >
SPOSITION SList< E, ETraits >::AddHead()
{
    CNode* pNode = NewNode( NULL, m_pHead );
    if( m_pHead != NULL )
    {
        m_pHead->m_pPrev = pNode;
    }
    else
    {
        m_pTail = pNode;
    }
    m_pHead = pNode;

    return( SPOSITION( pNode ) );
}

template< typename E, class ETraits >
SPOSITION SList< E, ETraits >::AddHead( INARGTYPE element )
{
    CNode* pNode;

    pNode = NewNode( element, NULL, m_pHead );

    if( m_pHead != NULL )
    {
        m_pHead->m_pPrev = pNode;
    }
    else
    {
        m_pTail = pNode;
    }
    m_pHead = pNode;

    return( SPOSITION( pNode ) );
}

template< typename E, class ETraits >
SPOSITION SList< E, ETraits >::AddTail()
{
    CNode* pNode = NewNode( m_pTail, NULL );
    if( m_pTail != NULL )
    {
        m_pTail->m_pNext = pNode;
    }
    else
    {
        m_pHead = pNode;
    }
    m_pTail = pNode;

    return( SPOSITION( pNode ) );
}

template< typename E, class ETraits >
SPOSITION SList< E, ETraits >::AddTail( INARGTYPE element )
{
    CNode* pNode;

    pNode = NewNode( element, m_pTail, NULL );

    if( m_pTail != NULL )
    {
        m_pTail->m_pNext = pNode;
    }
    else
    {
        m_pHead = pNode;
    }
    m_pTail = pNode;

    return( SPOSITION( pNode ) );
}

template< typename E, class ETraits >
void SList< E, ETraits >::AddHeadList( const SList< E, ETraits >* plNew )
{
    SENSURE( plNew != NULL );

    SPOSITION pos = plNew->GetTailPosition();
    while( pos != NULL )
    {
        INARGTYPE element = plNew->GetPrev( pos );
        AddHead( element );
    }
}

template< typename E, class ETraits >
void SList< E, ETraits >::AddTailList( const SList< E, ETraits >* plNew )
{
    SENSURE( plNew != NULL );

    SPOSITION pos = plNew->GetHeadPosition();
    while( pos != NULL )
    {
        INARGTYPE element = plNew->GetNext( pos );
        AddTail( element );
    }
}

template< typename E, class ETraits >
E SList< E, ETraits >::RemoveHead()
{
    SENSURE( m_pHead != NULL );

    CNode* pNode = m_pHead;
    E element( pNode->m_element );

    m_pHead = pNode->m_pNext;
    if( m_pHead != NULL )
    {
        m_pHead->m_pPrev = NULL;
    }
    else
    {
        m_pTail = NULL;
    }
    FreeNode( pNode );

    return( element );
}

template< typename E, class ETraits >
void SList< E, ETraits >::RemoveHeadNoReturn()
{
    SENSURE( m_pHead != NULL );

    CNode* pNode = m_pHead;

    m_pHead = pNode->m_pNext;
    if( m_pHead != NULL )
    {
        m_pHead->m_pPrev = NULL;
    }
    else
    {
        m_pTail = NULL;
    }
    FreeNode( pNode );
}

template< typename E, class ETraits >
E SList< E, ETraits >::RemoveTail()
{
    SENSURE( m_pTail != NULL );

    CNode* pNode = m_pTail;

    E element( pNode->m_element );

    m_pTail = pNode->m_pPrev;
    if( m_pTail != NULL )
    {
        m_pTail->m_pNext = NULL;
    }
    else
    {
        m_pHead = NULL;
    }
    FreeNode( pNode );

    return( element );
}

template< typename E, class ETraits >
void SList< E, ETraits >::RemoveTailNoReturn()
{
    SENSURE( m_pTail != NULL );

    CNode* pNode = m_pTail;

    m_pTail = pNode->m_pPrev;
    if( m_pTail != NULL )
    {
        m_pTail->m_pNext = NULL;
    }
    else
    {
        m_pHead = NULL;
    }
    FreeNode( pNode );
}

template< typename E, class ETraits >
SPOSITION SList< E, ETraits >::InsertBefore( SPOSITION pos, INARGTYPE element )
{
    SASSERT_VALID(this);

    if( pos == NULL )
        return AddHead( element ); // insert before nothing -> head of the list

    // Insert it before position
    CNode* pOldNode = (CNode*)pos;
    CNode* pNewNode = NewNode( element, pOldNode->m_pPrev, pOldNode );

    if( pOldNode->m_pPrev != NULL )
    {
        pOldNode->m_pPrev->m_pNext = pNewNode;
    }
    else
    {
        SASSERT( pOldNode == m_pHead );
        m_pHead = pNewNode;
    }
    pOldNode->m_pPrev = pNewNode;

    return( SPOSITION( pNewNode ) );
}

template< typename E, class ETraits >
SPOSITION SList< E, ETraits >::InsertAfter( SPOSITION pos, INARGTYPE element )
{
    SASSERT_VALID(this);

    if( pos == NULL )
        return AddTail( element ); // insert after nothing -> tail of the list

    // Insert it after position
    CNode* pOldNode = (CNode*)pos;
    CNode* pNewNode = NewNode( element, pOldNode, pOldNode->m_pNext );

    if( pOldNode->m_pNext != NULL )
    {
        pOldNode->m_pNext->m_pPrev = pNewNode;
    }
    else
    {
        SASSERT( pOldNode == m_pTail );
        m_pTail = pNewNode;
    }
    pOldNode->m_pNext = pNewNode;

    return( SPOSITION( pNewNode ) );
}

template< typename E, class ETraits >
void SList< E, ETraits >::RemoveAt( SPOSITION pos )
{
    SASSERT_VALID(this);
    SENSURE( pos != NULL );

    CNode* pOldNode = (CNode*)pos;

    // remove pOldNode from list
    if( pOldNode == m_pHead )
    {
        m_pHead = pOldNode->m_pNext;
    }
    else
    {
        pOldNode->m_pPrev->m_pNext = pOldNode->m_pNext;
    }
    if( pOldNode == m_pTail )
    {
        m_pTail = pOldNode->m_pPrev;
    }
    else
    {
        pOldNode->m_pNext->m_pPrev = pOldNode->m_pPrev;
    }
    FreeNode( pOldNode );
}

template< typename E, class ETraits >
SPOSITION SList< E, ETraits >::FindIndex( size_t iElement ) const
{
    SASSERT_VALID(this);

    if( iElement >= m_nElements )
        return NULL;  // went too far

    if(m_pHead == NULL)
        return NULL;

    CNode* pNode = m_pHead;
    for( size_t iSearch = 0; iSearch < iElement; iSearch++ )
    {
        pNode = pNode->m_pNext;
    }

    return( SPOSITION( pNode ) );
}

template< typename E, class ETraits >
void SList< E, ETraits >::MoveToHead( SPOSITION pos )
{
    SENSURE( pos != NULL );

    CNode* pNode = static_cast< CNode* >( pos );

    if( pNode == m_pHead )
    {
        // Already at the head
        return;
    }

    if( pNode->m_pNext == NULL )
    {
        SASSERT( pNode == m_pTail );
        m_pTail = pNode->m_pPrev;
    }
    else
    {
        pNode->m_pNext->m_pPrev = pNode->m_pPrev;
    }

    SASSERT( pNode->m_pPrev != NULL );  // This node can't be the head, since we already checked that case
    pNode->m_pPrev->m_pNext = pNode->m_pNext;

    m_pHead->m_pPrev = pNode;
    pNode->m_pNext = m_pHead;
    pNode->m_pPrev = NULL;
    m_pHead = pNode;
}

template< typename E, class ETraits >
void SList< E, ETraits >::MoveToTail( SPOSITION pos )
{
    SENSURE( pos != NULL );
    CNode* pNode = static_cast< CNode* >( pos );

    if( pNode == m_pTail )
    {
        // Already at the tail
        return;
    }

    if( pNode->m_pPrev == NULL )
    {
        SENSURE( pNode == m_pHead );
        m_pHead = pNode->m_pNext;
    }
    else
    {
        pNode->m_pPrev->m_pNext = pNode->m_pNext;
    }

    pNode->m_pNext->m_pPrev = pNode->m_pPrev;

    m_pTail->m_pNext = pNode;
    pNode->m_pPrev = m_pTail;
    pNode->m_pNext = NULL;
    m_pTail = pNode;
}

template< typename E, class ETraits >
void SList< E, ETraits >::Swap(SList<E,ETraits> &src)
{
	CNode* pHead = m_pHead;
	CNode* pTail = m_pTail;
	size_t nElements = m_nElements;
	SPlex* pBlocks = m_pBlocks;
	CNode* pFree = m_pFree;
	UINT nBlockSize = m_nBlockSize;

	m_pHead = src.m_pHead;
	m_pTail = src.m_pTail;
	m_nElements = src.m_nElements;
	m_pBlocks = src.m_pBlocks;
	m_pFree = src.m_pFree;
	m_nBlockSize = src.m_nBlockSize;

	src.m_pHead = pHead;
	src.m_pTail = pTail;
	src.m_nElements = nElements;
	src.m_pBlocks = pBlocks;
	src.m_pFree = pFree;
	src.m_nBlockSize = nBlockSize;
}

template< typename E, class ETraits >
void SList< E, ETraits >::SwapElements( SPOSITION pos1, SPOSITION pos2 )
{
    SASSERT( pos1 != NULL );
    SASSERT( pos2 != NULL );

    if( pos1 == pos2 )
    {
        // Nothing to do
        return;
    }

    CNode* pNode1 = static_cast< CNode* >( pos1 );
    CNode* pNode2 = static_cast< CNode* >( pos2 );
    if( pNode2->m_pNext == pNode1 )
    {
        // Swap pNode2 and pNode1 so that the next case works
        CNode* pNodeTemp = pNode1;
        pNode1 = pNode2;
        pNode2 = pNodeTemp;
    }
    if( pNode1->m_pNext == pNode2 )
    {
        // Node1 and Node2 are adjacent
        pNode2->m_pPrev = pNode1->m_pPrev;
        if( pNode1->m_pPrev != NULL )
        {
            pNode1->m_pPrev->m_pNext = pNode2;
        }
        else
        {
            SASSUME( m_pHead == pNode1 );
            m_pHead = pNode2;
        }
        pNode1->m_pNext = pNode2->m_pNext;
        if( pNode2->m_pNext != NULL )
        {
            pNode2->m_pNext->m_pPrev = pNode1;
        }
        else
        {
            SASSUME( m_pTail == pNode2 );
            m_pTail = pNode1;
        }
        pNode2->m_pNext = pNode1;
        pNode1->m_pPrev = pNode2;
    }
    else
    {
        // The two nodes are not adjacent
        CNode* pNodeTemp;

        pNodeTemp = pNode1->m_pPrev;
        pNode1->m_pPrev = pNode2->m_pPrev;
        pNode2->m_pPrev = pNodeTemp;

        pNodeTemp = pNode1->m_pNext;
        pNode1->m_pNext = pNode2->m_pNext;
        pNode2->m_pNext = pNodeTemp;

        if( pNode1->m_pNext != NULL )
        {
            pNode1->m_pNext->m_pPrev = pNode1;
        }
        else
        {
            SASSUME( m_pTail == pNode2 );
            m_pTail = pNode1;
        }
        if( pNode1->m_pPrev != NULL )
        {
            pNode1->m_pPrev->m_pNext = pNode1;
        }
        else
        {
            SASSUME( m_pHead == pNode2 );
            m_pHead = pNode1;
        }
        if( pNode2->m_pNext != NULL )
        {
            pNode2->m_pNext->m_pPrev = pNode2;
        }
        else
        {
            SASSUME( m_pTail == pNode1 );
            m_pTail = pNode2;
        }
        if( pNode2->m_pPrev != NULL )
        {
            pNode2->m_pPrev->m_pNext = pNode2;
        }
        else
        {
            SASSUME( m_pHead == pNode1 );
            m_pHead = pNode2;
        }
    }
}

template< typename E, class ETraits >
SPOSITION SList< E, ETraits >::Find( INARGTYPE element, SPOSITION posStartAfter ) const
{
    SASSERT_VALID(this);

    CNode* pNode = (CNode*)posStartAfter;
    if( pNode == NULL )
    {
        pNode = m_pHead;  // start at head
    }
    else
    {
        pNode = pNode->m_pNext;  // start after the one specified
    }

    for( ; pNode != NULL; pNode = pNode->m_pNext )
    {
        if( ETraits::CompareElements( pNode->m_element, element ) )
            return( SPOSITION( pNode ) );
    }

    return( NULL );
}

#ifdef _DEBUG
template< typename E, class ETraits >
void SList< E, ETraits >::AssertValid() const
{
    if( IsEmpty() )
    {
        // empty list
        SASSUME(m_pHead == NULL);
        SASSUME(m_pTail == NULL);
    }
    else
    {
        // non-empty list
    }
}
#endif

template< typename K, typename V, class KTraits = CElementTraits< K >, class VTraits = CElementTraits< V > >
class SMap
{
public:
    typedef typename KTraits::INARGTYPE KINARGTYPE;
    typedef typename KTraits::OUTARGTYPE KOUTARGTYPE;
    typedef typename VTraits::INARGTYPE VINARGTYPE;
    typedef typename VTraits::OUTARGTYPE VOUTARGTYPE;

    class CPair :
        public __SPOSITION
    {
    protected:
        CPair( KINARGTYPE key ) :
            m_key( key )
        {
        }

    public:
        const K m_key;
        V m_value;
    };

private:
    class CNode :
        public CPair
    {
    public:
        CNode( KINARGTYPE key, UINT nHash ) :
            CPair( key ),
            m_nHash( nHash )
        {
        }

    public:
        UINT GetHash() const
        {
            return( m_nHash );
        }

    public:
        CNode* m_pNext;
        UINT m_nHash;
    };

public:
    SMap( UINT nBins = 17, float fOptimalLoad = 0.75f,
             float fLoThreshold = 0.25f, float fHiThreshold = 2.25f, UINT nBlockSize = 10 );
	SMap(const SMap&);
	~SMap();
	SMap& operator=(const SMap& src);

	void Copy(const SMap & src);

    size_t GetCount() const;
    bool IsEmpty() const;

    bool Lookup( KINARGTYPE key, VOUTARGTYPE value ) const;
    const CPair* Lookup( KINARGTYPE key ) const;
    CPair* Lookup( KINARGTYPE key );
    V& operator[]( KINARGTYPE key ) ;
    const V& operator[]( KINARGTYPE key ) const;

    SPOSITION SetAt( KINARGTYPE key, VINARGTYPE value );
    void SetValueAt( SPOSITION pos, VINARGTYPE value );

    bool RemoveKey( KINARGTYPE key );
    void RemoveAll();
    void RemoveAtPos( SPOSITION pos );

    SPOSITION GetStartPosition() const;
    void GetNextAssoc( SPOSITION& pos, KOUTARGTYPE key, VOUTARGTYPE value ) const;
    const CPair* GetNext( SPOSITION& pos ) const;
    CPair* GetNext( SPOSITION& pos );
    const K& GetNextKey( SPOSITION& pos ) const;
    const V& GetNextValue( SPOSITION& pos ) const;
    V& GetNextValue( SPOSITION& pos );
    void GetAt( SPOSITION pos, KOUTARGTYPE key, VOUTARGTYPE value ) const;
    CPair* GetAt( SPOSITION pos );
    const CPair* GetAt( SPOSITION pos ) const;
    const K& GetKeyAt( SPOSITION pos ) const;
    const V& GetValueAt( SPOSITION pos ) const;
    V& GetValueAt( SPOSITION pos );

    UINT GetHashTableSize() const;
    bool InitHashTable( UINT nBins, bool bAllocNow = true );
    void EnableAutoRehash();
    void DisableAutoRehash();
    void Rehash( UINT nBins = 0 );
    void SetOptimalLoad( float fOptimalLoad, float fLoThreshold, float fHiThreshold,
                         bool bRehashNow = false );

#ifdef _DEBUG
    void AssertValid() const;
#endif  // _DEBUG

    // Implementation
private:
    CNode** m_ppBins;
    size_t m_nElements;
    UINT m_nBins;
    float m_fOptimalLoad;
    float m_fLoThreshold;
    float m_fHiThreshold;
    size_t m_nHiRehashThreshold;
    size_t m_nLoRehashThreshold;
    ULONG m_nLockCount;
    UINT m_nBlockSize;
    SPlex* m_pBlocks;
    CNode* m_pFree;

private:
    bool IsLocked() const;
    UINT PickSize( size_t nElements ) const;
    CNode* NewNode( KINARGTYPE key, UINT iBin, UINT nHash );
    void FreeNode( CNode* pNode );
    void FreePlexes();
    CNode* GetNode( KINARGTYPE key, UINT& iBin, UINT& nHash, CNode*& pPrev ) const;
    CNode* CreateNode( KINARGTYPE key, UINT iBin, UINT nHash ) ;
    void RemoveNode( CNode* pNode, CNode* pPrev );
    CNode* FindNextNode( CNode* pNode ) const;
    void UpdateRehashThresholds();
};


template< typename K, typename V, class KTraits, class VTraits >
inline size_t SMap< K, V, KTraits, VTraits >::GetCount() const
{
    return( m_nElements );
}

template< typename K, typename V, class KTraits, class VTraits >
inline bool SMap< K, V, KTraits, VTraits >::IsEmpty() const
{
    return( m_nElements == 0 );
}

template< typename K, typename V, class KTraits, class VTraits >
inline V& SMap< K, V, KTraits, VTraits >::operator[]( KINARGTYPE key ) 
{
    CNode* pNode;
    UINT iBin;
    UINT nHash;
    CNode* pPrev;

    pNode = GetNode( key, iBin, nHash, pPrev );
    if( pNode == NULL )
    {
        pNode = CreateNode( key, iBin, nHash );
    }

    return( pNode->m_value );
}

template< typename K, typename V, class KTraits, class VTraits >
inline const V& SMap< K, V, KTraits, VTraits >::operator[]( KINARGTYPE key ) const
{
    CNode* pNode;
    UINT iBin;
    UINT nHash;
    CNode* pPrev;

    pNode = GetNode( key, iBin, nHash, pPrev );
    SASSERT(pNode);
    return( pNode->m_value );
}


template< typename K, typename V, class KTraits, class VTraits >
inline UINT SMap< K, V, KTraits, VTraits >::GetHashTableSize() const
{
    return( m_nBins );
}

template< typename K, typename V, class KTraits, class VTraits >
inline void SMap< K, V, KTraits, VTraits >::GetAt( SPOSITION pos, KOUTARGTYPE key, VOUTARGTYPE value ) const
{
    SENSURE( pos != NULL );

    CNode* pNode = static_cast< CNode* >( pos );

    key = pNode->m_key;
    value = pNode->m_value;
}

template< typename K, typename V, class KTraits, class VTraits >
inline typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::GetAt( SPOSITION pos )
{
    SASSERT( pos != NULL );

    return( static_cast< CPair* >( pos ) );
}

template< typename K, typename V, class KTraits, class VTraits >
inline const typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::GetAt( SPOSITION pos ) const
{
    SASSERT( pos != NULL );

    return( static_cast< const CPair* >( pos ) );
}

template< typename K, typename V, class KTraits, class VTraits >
inline const K& SMap< K, V, KTraits, VTraits >::GetKeyAt( SPOSITION pos ) const
{
    SENSURE( pos != NULL );

    CNode* pNode = (CNode*)pos;

    return( pNode->m_key );
}

template< typename K, typename V, class KTraits, class VTraits >
inline const V& SMap< K, V, KTraits, VTraits >::GetValueAt( SPOSITION pos ) const
{
    SENSURE( pos != NULL );

    CNode* pNode = (CNode*)pos;

    return( pNode->m_value );
}

template< typename K, typename V, class KTraits, class VTraits >
inline V& SMap< K, V, KTraits, VTraits >::GetValueAt( SPOSITION pos )
{
    SENSURE( pos != NULL );

    CNode* pNode = (CNode*)pos;

    return( pNode->m_value );
}

template< typename K, typename V, class KTraits, class VTraits >
inline void SMap< K, V, KTraits, VTraits >::DisableAutoRehash()
{
    m_nLockCount++;
}

template< typename K, typename V, class KTraits, class VTraits >
inline void SMap< K, V, KTraits, VTraits >::EnableAutoRehash()
{
    SASSUME( m_nLockCount > 0 );
    m_nLockCount--;
}

template< typename K, typename V, class KTraits, class VTraits >
inline bool SMap< K, V, KTraits, VTraits >::IsLocked() const
{
    return( m_nLockCount != 0 );
}

template< typename K, typename V, class KTraits, class VTraits >
UINT SMap< K, V, KTraits, VTraits >::PickSize( size_t nElements ) const
{
    // List of primes such that s_anPrimes[i] is the smallest prime greater than 2^(5+i/3)
    static const UINT s_anPrimes[] =
    {
        17, 23, 29, 37, 41, 53, 67, 83, 103, 131, 163, 211, 257, 331, 409, 521, 647, 821,
        1031, 1291, 1627, 2053, 2591, 3251, 4099, 5167, 6521, 8209, 10331,
        13007, 16411, 20663, 26017, 32771, 41299, 52021, 65537, 82571, 104033,
        131101, 165161, 208067, 262147, 330287, 416147, 524309, 660563,
        832291, 1048583, 1321139, 1664543, 2097169, 2642257, 3329023, 4194319,
        5284493, 6658049, 8388617, 10568993, 13316089, UINT_MAX
    };

    size_t nBins = (size_t)(nElements/m_fOptimalLoad);
    UINT nBinsEstimate = UINT(  UINT_MAX < nBins ? UINT_MAX : nBins );

    // Find the smallest prime greater than our estimate
    int iPrime = 0;
    while( nBinsEstimate > s_anPrimes[iPrime] )
    {
        iPrime++;
    }

    if( s_anPrimes[iPrime] == UINT_MAX )
    {
        return( nBinsEstimate );
    }
    else
    {
        return( s_anPrimes[iPrime] );
    }
}

template< typename K, typename V, class KTraits, class VTraits >
typename SMap< K, V, KTraits, VTraits >::CNode* SMap< K, V, KTraits, VTraits >::CreateNode(
    KINARGTYPE key, UINT iBin, UINT nHash ) 
{
    CNode* pNode;

    if( m_ppBins == NULL )
    {
        bool bSuccess;

        bSuccess = InitHashTable( m_nBins );
        if( !bSuccess )
        {
            SThrow( E_OUTOFMEMORY );
        }
    }

    pNode = NewNode( key, iBin, nHash );

    return( pNode );
}

template< typename K, typename V, class KTraits, class VTraits >
SPOSITION SMap< K, V, KTraits, VTraits >::GetStartPosition() const
{
    if( IsEmpty() )
    {
        return( NULL );
    }

    for( UINT iBin = 0; iBin < m_nBins; iBin++ )
    {
        if( m_ppBins[iBin] != NULL )
        {
            return( SPOSITION( m_ppBins[iBin] ) );
        }
    }
    SASSERT( false );

    return( NULL );
}

template< typename K, typename V, class KTraits, class VTraits >
SPOSITION SMap< K, V, KTraits, VTraits >::SetAt( KINARGTYPE key, VINARGTYPE value )
{
    CNode* pNode;
    UINT iBin;
    UINT nHash;
    CNode* pPrev;

    pNode = GetNode( key, iBin, nHash, pPrev );
    if( pNode == NULL )
    {
        pNode = CreateNode( key, iBin, nHash );
//         _STRY
        {
            pNode->m_value = value;
        }
//         _SCATCHALL()
//         {
//             RemoveAtPos( SPOSITION( pNode ) );
//         }
    }
    else
    {
        pNode->m_value = value;
    }

    return( SPOSITION( pNode ) );
}

template< typename K, typename V, class KTraits, class VTraits >
void SMap< K, V, KTraits, VTraits >::SetValueAt( SPOSITION pos, VINARGTYPE value )
{
    SASSERT( pos != NULL );

    CNode* pNode = static_cast< CNode* >( pos );

    pNode->m_value = value;
}

template< typename K, typename V, class KTraits, class VTraits >
SMap< K, V, KTraits, VTraits >::SMap( UINT nBins, float fOptimalLoad,
        float fLoThreshold, float fHiThreshold, UINT nBlockSize ) :
    m_ppBins( NULL ),
    m_nElements( 0 ),
    m_nBins(nBins),
    m_fOptimalLoad( fOptimalLoad ),
    m_fLoThreshold( fLoThreshold ),
    m_fHiThreshold( fHiThreshold ),
    m_nHiRehashThreshold( UINT_MAX ),
    m_nLoRehashThreshold( 0 ),
    m_nLockCount(0),  // Start unlocked
    m_nBlockSize( nBlockSize ),
    m_pBlocks(NULL),
    m_pFree(NULL)
{
    SASSERT( nBins > 0 );
    SASSERT( nBlockSize > 0 );

    SetOptimalLoad( fOptimalLoad, fLoThreshold, fHiThreshold, false );
}

template< typename K, typename V, class KTraits, class VTraits >
SMap< K, V, KTraits, VTraits >::SMap(const SMap< K, V, KTraits, VTraits > & src) :
	m_ppBins(NULL),
	m_nElements(0),
	m_nBins(src.m_nBins),
	m_fOptimalLoad(src.m_fOptimalLoad),
	m_fLoThreshold(src.m_fLoThreshold),
	m_fHiThreshold(src.m_fHiThreshold),
	m_nHiRehashThreshold(src.m_nHiRehashThreshold),
	m_nLoRehashThreshold(src.m_nLoRehashThreshold),
	m_nLockCount(0),  // Start unlocked
	m_nBlockSize(src.m_nBlockSize),
	m_pBlocks(NULL),
	m_pFree(NULL)
{
	SetOptimalLoad(m_fOptimalLoad, m_fLoThreshold, m_fHiThreshold, false);
	Copy(src);
}

template< typename K, typename V, class KTraits, class VTraits >
void SMap< K, V, KTraits, VTraits >::Copy(const SMap< K, V, KTraits, VTraits > & src)
{
	RemoveAll();
	SPOSITION pos = src.GetStartPosition();
	while (pos)
	{
		const SMap< K, V, KTraits, VTraits >::CPair * p = src.GetNext(pos);
		this->SetAt(p->m_key, p->m_value);
	}
}

template< typename K, typename V, class KTraits, class VTraits >
SMap< K, V, KTraits, VTraits >&  SMap< K, V, KTraits, VTraits >::operator=(const SMap< K, V, KTraits, VTraits > & src)
{
	Copy(src);
	return *this;
}


template< typename K, typename V, class KTraits, class VTraits >
void SMap< K, V, KTraits, VTraits >::SetOptimalLoad( float fOptimalLoad, float fLoThreshold,
        float fHiThreshold, bool bRehashNow )
{
    SASSERT( fOptimalLoad > 0 );
    SASSERT( (fLoThreshold >= 0) && (fLoThreshold < fOptimalLoad) );
    SASSERT( fHiThreshold > fOptimalLoad );

    m_fOptimalLoad = fOptimalLoad;
    m_fLoThreshold = fLoThreshold;
    m_fHiThreshold = fHiThreshold;

    UpdateRehashThresholds();

    if( bRehashNow && ((m_nElements > m_nHiRehashThreshold) ||
                       (m_nElements < m_nLoRehashThreshold)) )
    {
        Rehash( PickSize( m_nElements ) );
    }
}

template< typename K, typename V, class KTraits, class VTraits >
void SMap< K, V, KTraits, VTraits >::UpdateRehashThresholds()
{
    m_nHiRehashThreshold = size_t( m_fHiThreshold*m_nBins );
    m_nLoRehashThreshold = size_t( m_fLoThreshold*m_nBins );
    if( m_nLoRehashThreshold < 17 )
    {
        m_nLoRehashThreshold = 0;
    }
}

template< typename K, typename V, class KTraits, class VTraits >
bool SMap< K, V, KTraits, VTraits >::InitHashTable( UINT nBins, bool bAllocNow )
{
    SASSUME( m_nElements == 0 );
    SASSERT( nBins > 0 );

    if( m_ppBins != NULL )
    {
        soui_mem_wrapper::SouiFree(m_ppBins);
        m_ppBins = NULL;
    }

    if( bAllocNow )
    {
        //hjx            STRY( m_ppBins = new CNode*[nBins] );
        m_ppBins = (CNode**)soui_mem_wrapper::SouiMalloc(nBins*sizeof(CNode*));
        if( m_ppBins == NULL )
        {
            return false;
        }

        SENSURE( UINT_MAX / sizeof( CNode* ) >= nBins );
        memset( m_ppBins, 0, sizeof( CNode* )*nBins );
    }
    m_nBins = nBins;

    UpdateRehashThresholds();

    return true;
}

template< typename K, typename V, class KTraits, class VTraits >
void SMap< K, V, KTraits, VTraits >::RemoveAll()
{
    DisableAutoRehash();
    if( m_ppBins != NULL )
    {
        for( UINT iBin = 0; iBin < m_nBins; iBin++ )
        {
            CNode* pNext;

            pNext = m_ppBins[iBin];
            while( pNext != NULL )
            {
                CNode* pKill;

                pKill = pNext;
                pNext = pNext->m_pNext;
                FreeNode( pKill );
            }
        }
    }

    soui_mem_wrapper::SouiFree(m_ppBins);
    m_ppBins = NULL;
    m_nElements = 0;

    if( !IsLocked() )
    {
        InitHashTable( PickSize( m_nElements ), false );
    }

    FreePlexes();
    EnableAutoRehash();
}

template< typename K, typename V, class KTraits, class VTraits >
SMap< K, V, KTraits, VTraits >::~SMap()
{
    RemoveAll();
}

#pragma push_macro("new")
#undef new

template< typename K, typename V, class KTraits, class VTraits >
typename SMap< K, V, KTraits, VTraits >::CNode* SMap< K, V, KTraits, VTraits >::NewNode(
    KINARGTYPE key, UINT iBin, UINT nHash )
{
    CNode* pNewNode;

    if( m_pFree == NULL )
    {
        SPlex* pPlex;
        CNode* pNode;

        pPlex = SPlex::Create( m_pBlocks, m_nBlockSize, sizeof( CNode ) );
        if( pPlex == NULL )
        {
            SThrow( E_OUTOFMEMORY );
        }
        pNode = (CNode*)pPlex->data();
        pNode += m_nBlockSize-1;
        for( int iBlock = m_nBlockSize-1; iBlock >= 0; iBlock-- )
        {
            pNode->m_pNext = m_pFree;
            m_pFree = pNode;
            pNode--;
        }
    }
    SENSURE(m_pFree != NULL );
    pNewNode = m_pFree;
    m_pFree = pNewNode->m_pNext;

//     _STRY
    {
        ::new( pNewNode ) CNode( key, nHash );
    }
//     _SCATCHALL()
//     {
//         pNewNode->m_pNext = m_pFree;
//         m_pFree = pNewNode;
// 
//     }
    m_nElements++;

    pNewNode->m_pNext = m_ppBins[iBin];
    m_ppBins[iBin] = pNewNode;

    if( (m_nElements > m_nHiRehashThreshold) && !IsLocked() )
    {
        Rehash( PickSize( m_nElements ) );
    }

    return( pNewNode );
}

#pragma pop_macro("new")

template< typename K, typename V, class KTraits, class VTraits >
void SMap< K, V, KTraits, VTraits >::FreeNode( CNode* pNode )
{
    SENSURE( pNode != NULL );

    pNode->~CNode();
    pNode->m_pNext = m_pFree;
    m_pFree = pNode;

    SASSUME( m_nElements > 0 );
    m_nElements--;

    if( (m_nElements < m_nLoRehashThreshold) && !IsLocked() )
    {
        Rehash( PickSize( m_nElements ) );
    }

    if( m_nElements == 0 )
    {
        FreePlexes();
    }
}

template< typename K, typename V, class KTraits, class VTraits >
void SMap< K, V, KTraits, VTraits >::FreePlexes()
{
    m_pFree = NULL;
    if( m_pBlocks != NULL )
    {
        m_pBlocks->FreeDataChain();
        m_pBlocks = NULL;
    }
}

template< typename K, typename V, class KTraits, class VTraits >
typename SMap< K, V, KTraits, VTraits >::CNode* SMap< K, V, KTraits, VTraits >::GetNode(
    KINARGTYPE key, UINT& iBin, UINT& nHash, CNode*& pPrev ) const
{
    CNode* pFollow;

    nHash = KTraits::Hash( key );
    iBin = nHash%m_nBins;

    if( m_ppBins == NULL )
    {
        return( NULL );
    }

    pFollow = NULL;
    pPrev = NULL;
    for( CNode* pNode = m_ppBins[iBin]; pNode != NULL; pNode = pNode->m_pNext )
    {
        if( (pNode->GetHash() == nHash) && KTraits::CompareElements( pNode->m_key, key ) )
        {
            pPrev = pFollow;
            return( pNode );
        }
        pFollow = pNode;
    }

    return( NULL );
}

template< typename K, typename V, class KTraits, class VTraits >
bool SMap< K, V, KTraits, VTraits >::Lookup( KINARGTYPE key, VOUTARGTYPE value ) const
{
    UINT iBin;
    UINT nHash;
    CNode* pNode;
    CNode* pPrev;

    pNode = GetNode( key, iBin, nHash, pPrev );
    if( pNode == NULL )
    {
        return( false );
    }

    value = pNode->m_value;

    return( true );
}

template< typename K, typename V, class KTraits, class VTraits >
const typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::Lookup( KINARGTYPE key ) const
{
    UINT iBin;
    UINT nHash;
    CNode* pNode;
    CNode* pPrev;

    pNode = GetNode( key, iBin, nHash, pPrev );

    return( pNode );
}

template< typename K, typename V, class KTraits, class VTraits >
typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::Lookup( KINARGTYPE key )
{
    UINT iBin;
    UINT nHash;
    CNode* pNode;
    CNode* pPrev;

    pNode = GetNode( key, iBin, nHash, pPrev );

    return( pNode );
}

template< typename K, typename V, class KTraits, class VTraits >
bool SMap< K, V, KTraits, VTraits >::RemoveKey( KINARGTYPE key )
{
    CNode* pNode;
    UINT iBin;
    UINT nHash;
    CNode* pPrev;

    pPrev = NULL;
    pNode = GetNode( key, iBin, nHash, pPrev );
    if( pNode == NULL )
    {
        return( false );
    }

    RemoveNode( pNode, pPrev );

    return( true );
}

template< typename K, typename V, class KTraits, class VTraits >
void SMap< K, V, KTraits, VTraits >::RemoveNode( CNode* pNode, CNode* pPrev )
{
    SENSURE( pNode != NULL );

    UINT iBin = pNode->GetHash() % m_nBins;

    if( pPrev == NULL )
    {
        SASSUME( m_ppBins[iBin] == pNode );
        m_ppBins[iBin] = pNode->m_pNext;
    }
    else
    {
        SASSERT( pPrev->m_pNext == pNode );
        pPrev->m_pNext = pNode->m_pNext;
    }
    FreeNode( pNode );
}

template< typename K, typename V, class KTraits, class VTraits >
void SMap< K, V, KTraits, VTraits >::RemoveAtPos( SPOSITION pos )
{
    SENSURE( pos != NULL );

    CNode* pNode = static_cast< CNode* >( pos );
    CNode* pPrev = NULL;
    UINT iBin = pNode->GetHash() % m_nBins;

    SASSUME( m_ppBins[iBin] != NULL );
    if( pNode == m_ppBins[iBin] )
    {
        pPrev = NULL;
    }
    else
    {
        pPrev = m_ppBins[iBin];
        while( pPrev->m_pNext != pNode )
        {
            pPrev = pPrev->m_pNext;
            SASSERT( pPrev != NULL );
        }
    }
    RemoveNode( pNode, pPrev );
}

template< typename K, typename V, class KTraits, class VTraits >
void SMap< K, V, KTraits, VTraits >::Rehash( UINT nBins )
{
    CNode** ppBins = NULL;

    if( nBins == 0 )
    {
        nBins = PickSize( m_nElements );
    }

    if( nBins == m_nBins )
    {
        return;
    }

    if( m_ppBins == NULL )
    {
        // Just set the new number of bins
        InitHashTable( nBins, false );
        return;
    }

    //hjx        STRY(ppBins = new CNode*[nBins]);
    ppBins = (CNode**)soui_mem_wrapper::SouiMalloc(nBins*sizeof(CNode*));
    if (ppBins == NULL)
    {
        return;
    }

    SENSURE( UINT_MAX / sizeof( CNode* ) >= nBins );
    memset( ppBins, 0, nBins*sizeof( CNode* ) );

    // Nothing gets copied.  We just rewire the old nodes
    // into the new bins.
    for( UINT iSrcBin = 0; iSrcBin < m_nBins; iSrcBin++ )
    {
        CNode* pNode;

        pNode = m_ppBins[iSrcBin];
        while( pNode != NULL )
        {
            CNode* pNext;
            UINT iDestBin;

            pNext = pNode->m_pNext;  // Save so we don't trash it
            iDestBin = pNode->GetHash()%nBins;
            pNode->m_pNext = ppBins[iDestBin];
            ppBins[iDestBin] = pNode;

            pNode = pNext;
        }
    }

    soui_mem_wrapper::SouiFree(m_ppBins);
    m_ppBins = ppBins;
    m_nBins = nBins;

    UpdateRehashThresholds();
}

template< typename K, typename V, class KTraits, class VTraits >
void SMap< K, V, KTraits, VTraits >::GetNextAssoc( SPOSITION& pos, KOUTARGTYPE key,
        VOUTARGTYPE value ) const
{
    CNode* pNode;
    CNode* pNext;

    SASSUME( m_ppBins != NULL );
    SENSURE( pos != NULL );

    pNode = (CNode*)pos;
    pNext = FindNextNode( pNode );

    pos = SPOSITION( pNext );
    key = pNode->m_key;
    value = pNode->m_value;
}

template< typename K, typename V, class KTraits, class VTraits >
const typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::GetNext( SPOSITION& pos ) const
{
    CNode* pNode;
    CNode* pNext;

    SASSUME( m_ppBins != NULL );
    SASSERT( pos != NULL );

    pNode = (CNode*)pos;
    pNext = FindNextNode( pNode );

    pos = SPOSITION( pNext );

    return( pNode );
}

template< typename K, typename V, class KTraits, class VTraits >
typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::GetNext(
    SPOSITION& pos )
{
    SASSUME( m_ppBins != NULL );
    SASSERT( pos != NULL );

    CNode* pNode = static_cast< CNode* >( pos );
    CNode* pNext = FindNextNode( pNode );

    pos = SPOSITION( pNext );

    return( pNode );
}

template< typename K, typename V, class KTraits, class VTraits >
const K& SMap< K, V, KTraits, VTraits >::GetNextKey( SPOSITION& pos ) const
{
    CNode* pNode;
    CNode* pNext;

    SASSUME( m_ppBins != NULL );
    SENSURE( pos != NULL );

    pNode = (CNode*)pos;
    pNext = FindNextNode( pNode );

    pos = SPOSITION( pNext );

    return( pNode->m_key );
}

template< typename K, typename V, class KTraits, class VTraits >
const V& SMap< K, V, KTraits, VTraits >::GetNextValue( SPOSITION& pos ) const
{
    CNode* pNode;
    CNode* pNext;

    SASSUME( m_ppBins != NULL );
    SENSURE( pos != NULL );

    pNode = (CNode*)pos;
    pNext = FindNextNode( pNode );

    pos = SPOSITION( pNext );

    return( pNode->m_value );
}

template< typename K, typename V, class KTraits, class VTraits >
V& SMap< K, V, KTraits, VTraits >::GetNextValue( SPOSITION& pos )
{
    CNode* pNode;
    CNode* pNext;

    SASSUME( m_ppBins != NULL );
    SENSURE( pos != NULL );

    pNode = (CNode*)pos;
    pNext = FindNextNode( pNode );

    pos = SPOSITION( pNext );

    return( pNode->m_value );
}

template< typename K, typename V, class KTraits, class VTraits >
typename SMap< K, V, KTraits, VTraits >::CNode* SMap< K, V, KTraits, VTraits >::FindNextNode( CNode* pNode ) const
{
    CNode* pNext;

    if(pNode == NULL)
    {
        SASSERT(FALSE);
        return NULL;
    }

    if( pNode->m_pNext != NULL )
    {
        pNext = pNode->m_pNext;
    }
    else
    {
        UINT iBin;

        pNext = NULL;
        iBin = (pNode->GetHash()%m_nBins)+1;
        while( (pNext == NULL) && (iBin < m_nBins) )
        {
            if( m_ppBins[iBin] != NULL )
            {
                pNext = m_ppBins[iBin];
            }

            iBin++;
        }
    }

    return( pNext );
}

#ifdef _DEBUG
template< typename K, typename V, class KTraits, class VTraits >
void SMap< K, V, KTraits, VTraits >::AssertValid() const
{
    SASSUME( m_nBins > 0 );
    // non-empty map should have hash table
    SASSERT( IsEmpty() || (m_ppBins != NULL) );
}
#endif

//
// The red-black tree code is based on the the descriptions in
// "Introduction to Algorithms", by Cormen, Leiserson, and Rivest
//
template< typename K, typename V, class KTraits = CElementTraits< K >, class VTraits = CElementTraits< V > >
class SRBTree
{
public:
    typedef typename KTraits::INARGTYPE KINARGTYPE;
    typedef typename KTraits::OUTARGTYPE KOUTARGTYPE;
    typedef typename VTraits::INARGTYPE VINARGTYPE;
    typedef typename VTraits::OUTARGTYPE VOUTARGTYPE;

public:
    class CPair : 
        public __SPOSITION
    {
    protected:

        CPair( KINARGTYPE key, VINARGTYPE value ) : 
             m_key( key ),
                 m_value( value )
             {
             }
             ~CPair()
             {
             }

    public:
        const K m_key;
        V m_value;
    };

private:

    class CNode : 
        public CPair
    {
    public:
        enum RB_COLOR
        {
            RB_RED, 
            RB_BLACK
        };

    public:
        RB_COLOR m_eColor;
        CNode* m_pLeft;
        CNode* m_pRight;
        CNode* m_pParent;

        CNode( KINARGTYPE key, VINARGTYPE value ) : 
        CPair( key, value ),
            m_pParent( NULL ),
            m_eColor( RB_BLACK )
        {
        }
        ~CNode() 
        {
        }
    };

private:
    CNode* m_pRoot;
    size_t m_nCount;
    CNode* m_pFree;
    SPlex* m_pBlocks;
    size_t m_nBlockSize;

    // sentinel node
    CNode *m_pNil;

    // methods
    bool IsNil(CNode *p) const ;
    void SetNil(CNode **p) ;

    CNode* NewNode( KINARGTYPE key, VINARGTYPE value );
    void FreeNode(CNode* pNode) ;
    void RemovePostOrder(CNode* pNode) ;
    CNode* LeftRotate(CNode* pNode) ;
    CNode* RightRotate(CNode* pNode) ;
    void SwapNode(CNode* pDest, CNode* pSrc) ;
    CNode* InsertImpl( KINARGTYPE key, VINARGTYPE value );
    void RBDeleteFixup(CNode* pNode) ;
    bool RBDelete(CNode* pZ) ;

#ifdef _DEBUG

    // internal debugging code to verify red-black properties of tree:
    // 1) Every node is either red or black
    // 2) Every leaf (NIL) is black
    // 3) If a node is red, both its children are black
    // 4) Every simple path from a node to a descendant leaf node contains 
    //    the same number of black nodes
private:
    void VerifyIntegrity(const CNode *pNode, int nCurrBlackDepth, int &nBlackDepth) const ;

public:
    void VerifyIntegrity() const ;

#endif // _DEBUG

protected:
    CNode* Minimum(CNode* pNode) const ;
    CNode* Maximum(CNode* pNode) const ;
    CNode* Predecessor( CNode* pNode ) const ;
    CNode* Successor(CNode* pNode) const ;
    CNode* RBInsert( KINARGTYPE key, VINARGTYPE value ) ;
    CNode* Find(KINARGTYPE key) const ;
    CNode* FindPrefix( KINARGTYPE key ) const ;

public:
	explicit SRBTree(size_t nBlockSize = 10); 
	~SRBTree() ;

    void RemoveAll() ;
    void RemoveAt(SPOSITION pos) ;

    size_t GetCount() const ;
    bool IsEmpty() const ;

    SPOSITION FindFirstKeyAfter( KINARGTYPE key ) const ;

    SPOSITION GetHeadPosition() const ;
    SPOSITION GetTailPosition() const ;
    void GetNextAssoc( SPOSITION& pos, KOUTARGTYPE key, VOUTARGTYPE value ) const;
    const CPair* GetNext(SPOSITION& pos) const ;
    CPair* GetNext(SPOSITION& pos) ;
    const CPair* GetPrev(SPOSITION& pos) const ;
    CPair* GetPrev(SPOSITION& pos) ;
    const K& GetNextKey(SPOSITION& pos) const ;
    const V& GetNextValue(SPOSITION& pos) const ;
    V& GetNextValue(SPOSITION& pos) ;

    CPair* GetAt( SPOSITION pos ) ;
    const CPair* GetAt( SPOSITION pos ) const ;
    void GetAt(SPOSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const;
    const K& GetKeyAt(SPOSITION pos) const;
    const V& GetValueAt(SPOSITION pos) const;
    V& GetValueAt(SPOSITION pos);
    void SetValueAt(SPOSITION pos, VINARGTYPE value);

private:
    // Private to prevent use
    SRBTree( const SRBTree& ) ;
    SRBTree& operator=( const SRBTree& ) ;
};

template< typename K, typename V, class KTraits, class VTraits >
inline bool SRBTree< K, V, KTraits, VTraits >::IsNil(CNode *p) const 
{
    return ( p == m_pNil );
}

template< typename K, typename V, class KTraits, class VTraits >
inline void SRBTree< K, V, KTraits, VTraits >::SetNil(CNode **p)
{
    SENSURE( p != NULL );
    *p = m_pNil;
}

template< typename K, typename V, class KTraits, class VTraits >
SRBTree< K, V, KTraits, VTraits >::SRBTree( size_t nBlockSize )  :
m_pRoot( NULL ),
m_nCount( 0 ),
m_nBlockSize( nBlockSize ),
m_pFree( NULL ),
m_pBlocks( NULL ),
m_pNil( NULL )
{
    SASSERT( nBlockSize > 0 );
}

template< typename K, typename V, class KTraits, class VTraits >
SRBTree< K, V, KTraits, VTraits >::~SRBTree() 
{
    RemoveAll();
    if (m_pNil != NULL)
    {
        soui_mem_wrapper::SouiFree(m_pNil);
    }
}

template< typename K, typename V, class KTraits, class VTraits >
void SRBTree< K, V, KTraits, VTraits >::RemoveAll() 
{
    if (!IsNil(m_pRoot))
        RemovePostOrder(m_pRoot);
    m_nCount = 0;
    m_pBlocks->FreeDataChain();
    m_pBlocks = NULL;
    m_pFree = NULL;
    m_pRoot = m_pNil;
}

template< typename K, typename V, class KTraits, class VTraits >
size_t SRBTree< K, V, KTraits, VTraits >::GetCount() const 
{
    return m_nCount;
}

template< typename K, typename V, class KTraits, class VTraits >
bool SRBTree< K, V, KTraits, VTraits >::IsEmpty() const 
{
    return( m_nCount == 0 );
}

template< typename K, typename V, class KTraits, class VTraits >
SPOSITION SRBTree< K, V, KTraits, VTraits >::FindFirstKeyAfter( KINARGTYPE key ) const 
{
    return( FindPrefix( key ) );
}

template< typename K, typename V, class KTraits, class VTraits >
void SRBTree< K, V, KTraits, VTraits >::RemoveAt(SPOSITION pos) 
{
    SASSERT(pos != NULL);
    RBDelete(static_cast<CNode*>(pos));
}

template< typename K, typename V, class KTraits, class VTraits >
SPOSITION SRBTree< K, V, KTraits, VTraits >::GetHeadPosition() const 
{
    return( Minimum( m_pRoot ) );
}

template< typename K, typename V, class KTraits, class VTraits >
SPOSITION SRBTree< K, V, KTraits, VTraits >::GetTailPosition() const 
{
    return( Maximum( m_pRoot ) );
}

template< typename K, typename V, class KTraits, class VTraits >
void SRBTree< K, V, KTraits, VTraits >::GetNextAssoc( SPOSITION& pos, KOUTARGTYPE key, VOUTARGTYPE value ) const
{
    SASSERT(pos != NULL);
    CNode* pNode = static_cast< CNode* >(pos);

    key = pNode->m_key;
    value = pNode->m_value;

    pos = Successor(pNode);
}

template< typename K, typename V, class KTraits, class VTraits >
const typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetNext(SPOSITION& pos) const 
{
    SASSERT(pos != NULL);
    CNode* pNode = static_cast< CNode* >(pos);
    pos = Successor(pNode);
    return pNode;
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetNext(SPOSITION& pos) 
{
    SASSERT(pos != NULL);
    CNode* pNode = static_cast< CNode* >(pos);
    pos = Successor(pNode);
    return pNode;
}

template< typename K, typename V, class KTraits, class VTraits >
const typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetPrev(SPOSITION& pos) const 
{
    SASSERT(pos != NULL);
    CNode* pNode = static_cast< CNode* >(pos);
    pos = Predecessor(pNode);

    return pNode;
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetPrev(SPOSITION& pos) 
{
    SASSERT(pos != NULL);
    CNode* pNode = static_cast< CNode* >(pos);
    pos = Predecessor(pNode);

    return pNode;
}

template< typename K, typename V, class KTraits, class VTraits >
const K& SRBTree< K, V, KTraits, VTraits >::GetNextKey(SPOSITION& pos) const 
{
    SASSERT(pos != NULL);
    CNode* pNode = static_cast<CNode*>(pos);
    pos = Successor(pNode);

    return pNode->m_key;
}

template< typename K, typename V, class KTraits, class VTraits >
const V& SRBTree< K, V, KTraits, VTraits >::GetNextValue(SPOSITION& pos) const 
{
    SASSERT(pos != NULL);
    CNode* pNode = static_cast<CNode*>(pos);
    pos = Successor(pNode);

    return pNode->m_value;
}

template< typename K, typename V, class KTraits, class VTraits >
V& SRBTree< K, V, KTraits, VTraits >::GetNextValue(SPOSITION& pos) 
{
    SASSERT(pos != NULL);
    CNode* pNode = static_cast<CNode*>(pos);
    pos = Successor(pNode);

    return pNode->m_value;
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetAt( SPOSITION pos ) 
{
    SASSERT( pos != NULL );

    return( static_cast< CPair* >( pos ) );
}

template< typename K, typename V, class KTraits, class VTraits >
const typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetAt( SPOSITION pos ) const 
{
    SASSERT( pos != NULL );

    return( static_cast< const CPair* >( pos ) );
}

template< typename K, typename V, class KTraits, class VTraits >
void SRBTree< K, V, KTraits, VTraits >::GetAt(SPOSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const
{
    SENSURE( pos != NULL );
    key = static_cast<CNode*>(pos)->m_key;
    value = static_cast<CNode*>(pos)->m_value;
}

template< typename K, typename V, class KTraits, class VTraits >
const K& SRBTree< K, V, KTraits, VTraits >::GetKeyAt(SPOSITION pos) const
{
    SENSURE( pos != NULL );
    return static_cast<CNode*>(pos)->m_key;
}

template< typename K, typename V, class KTraits, class VTraits >
const V& SRBTree< K, V, KTraits, VTraits >::GetValueAt(SPOSITION pos) const
{
    SENSURE( pos != NULL );
    return static_cast<CNode*>(pos)->m_value;
}

template< typename K, typename V, class KTraits, class VTraits >
V& SRBTree< K, V, KTraits, VTraits >::GetValueAt(SPOSITION pos)
{
    SENSURE( pos != NULL );
    return static_cast<CNode*>(pos)->m_value;
}

template< typename K, typename V, class KTraits, class VTraits >
void SRBTree< K, V, KTraits, VTraits >::SetValueAt(SPOSITION pos, VINARGTYPE value)
{
    SENSURE( pos != NULL );
    static_cast<CNode*>(pos)->m_value = value;
}

#pragma push_macro("new")
#undef new

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::NewNode( KINARGTYPE key, VINARGTYPE value )
{
    if( m_pFree == NULL )
    {
        if (m_pNil == NULL)
        {
            m_pNil = reinterpret_cast<CNode *>(soui_mem_wrapper::SouiMalloc(sizeof( CNode )));
            if (m_pNil == NULL)
            {
                SThrow( E_OUTOFMEMORY );
            }
            memset(m_pNil, 0x00, sizeof(CNode));
            m_pNil->m_eColor = CNode::RB_BLACK;
            m_pNil->m_pParent = m_pNil->m_pLeft = m_pNil->m_pRight = m_pNil;
            m_pRoot = m_pNil;
        }

        SPlex* pPlex = SPlex::Create( m_pBlocks, m_nBlockSize, sizeof( CNode ) );
        if( pPlex == NULL )
        {
            SThrow( E_OUTOFMEMORY );
        }
        CNode* pNode = static_cast< CNode* >( pPlex->data() );
        pNode += m_nBlockSize-1;
        for( INT_PTR iBlock = m_nBlockSize-1; iBlock >= 0; iBlock-- )
        {
            pNode->m_pLeft = m_pFree;
            m_pFree = pNode;
            pNode--;
        }
    }
    SASSUME( m_pFree != NULL );

    CNode* pNewNode = m_pFree;
    ::new( pNewNode ) CNode( key, value );

    m_pFree = m_pFree->m_pLeft;
    pNewNode->m_eColor = CNode::RB_RED;
    SetNil(&pNewNode->m_pLeft);
    SetNil(&pNewNode->m_pRight);
    SetNil(&pNewNode->m_pParent);

    m_nCount++;
    SASSUME( m_nCount > 0 );

    return( pNewNode );
}
#pragma pop_macro("new")

template< typename K, typename V, class KTraits, class VTraits >
void SRBTree< K, V, KTraits, VTraits >::FreeNode(CNode* pNode)
{
    SENSURE( pNode != NULL );
    pNode->~CNode();
    pNode->m_pLeft = m_pFree;
    m_pFree = pNode;
    SASSUME( m_nCount > 0 );
    m_nCount--;
}

template< typename K, typename V, class KTraits, class VTraits >
void SRBTree< K, V, KTraits, VTraits >::RemovePostOrder(CNode* pNode)
{
    if (IsNil(pNode))
        return;
    RemovePostOrder(pNode->m_pLeft);
    RemovePostOrder(pNode->m_pRight);
    FreeNode( pNode );
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::LeftRotate(CNode* pNode)
{
    SASSERT(pNode != NULL);
    if(pNode == NULL)
        return NULL;

    CNode* pRight = pNode->m_pRight;
    pNode->m_pRight = pRight->m_pLeft;
    if (!IsNil(pRight->m_pLeft))
        pRight->m_pLeft->m_pParent = pNode;

    pRight->m_pParent = pNode->m_pParent;
    if (IsNil(pNode->m_pParent))
        m_pRoot = pRight;
    else if (pNode == pNode->m_pParent->m_pLeft)
        pNode->m_pParent->m_pLeft = pRight;
    else 
        pNode->m_pParent->m_pRight = pRight;

    pRight->m_pLeft = pNode;
    pNode->m_pParent = pRight;
    return pNode;

}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::RightRotate(CNode* pNode)
{
    SASSERT(pNode != NULL);
    if(pNode == NULL)
        return NULL;

    CNode* pLeft = pNode->m_pLeft;
    pNode->m_pLeft = pLeft->m_pRight;
    if (!IsNil(pLeft->m_pRight))
        pLeft->m_pRight->m_pParent = pNode;

    pLeft->m_pParent = pNode->m_pParent;
    if (IsNil(pNode->m_pParent))
        m_pRoot = pLeft;
    else if (pNode == pNode->m_pParent->m_pRight)
        pNode->m_pParent->m_pRight = pLeft;
    else
        pNode->m_pParent->m_pLeft = pLeft;

    pLeft->m_pRight = pNode;
    pNode->m_pParent = pLeft;
    return pNode;
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Find(KINARGTYPE key) const
{
    CNode* pKey = NULL;
    CNode* pNode = m_pRoot;
    while( !IsNil(pNode) && (pKey == NULL) )
    {
        int nCompare = KTraits::CompareElementsOrdered( key, pNode->m_key );
        if( nCompare == 0 )
        {
            pKey = pNode;
        }
        else
        {
            if( nCompare < 0 )
            {
                pNode = pNode->m_pLeft;
            }
            else
            {
                pNode = pNode->m_pRight;
            }
        }
    }

    if( pKey == NULL )
    {
        return( NULL );
    }

#pragma warning(push)
#pragma warning(disable:4127)

    while( true )
    {
        CNode* pPrev = Predecessor( pKey );
        if( (pPrev != NULL) && KTraits::CompareElements( key, pPrev->m_key ) )
        {
            pKey = pPrev;
        }
        else
        {
            return( pKey );
        }
    }

#pragma warning(pop)
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::FindPrefix( KINARGTYPE key ) const
{
    // First, attempt to find a node that matches the key exactly
    CNode* pParent = NULL;
    CNode* pKey = NULL;
    CNode* pNode = m_pRoot;
    while( !IsNil(pNode) && (pKey == NULL) )
    {
        pParent = pNode;
        int nCompare = KTraits::CompareElementsOrdered( key, pNode->m_key );
        if( nCompare == 0 )
        {
            pKey = pNode;
        }
        else if( nCompare < 0 )
        {
            pNode = pNode->m_pLeft;
        }
        else
        {
            pNode = pNode->m_pRight;
        }
    }

    if( pKey != NULL )
    {
        // We found a node with the exact key, so find the first node after 
        // this one with a different key 
        while( true )
        {
            CNode* pNext = Successor( pKey );
            if ((pNext != NULL) && KTraits::CompareElements( key, pNext->m_key ))
            {
                pKey = pNext;
            }
            else
            {
                return pNext;
            }
        }
    }
    else if (pParent != NULL)
    {
        // No node matched the key exactly, so pick the first node with 
        // a key greater than the given key
        int nCompare = KTraits::CompareElementsOrdered( key, pParent->m_key );
        if( nCompare < 0 )
        {
            pKey = pParent;
        }
        else
        {
            SASSERT( nCompare > 0 );
            pKey = Successor( pParent );
        }
    }

    return( pKey );
}

template< typename K, typename V, class KTraits, class VTraits >
void SRBTree< K, V, KTraits, VTraits >::SwapNode(CNode* pDest, CNode* pSrc)
{
    SENSURE( pDest != NULL );
    SENSURE( pSrc != NULL );

    pDest->m_pParent = pSrc->m_pParent;
    if (pSrc->m_pParent->m_pLeft == pSrc)
    {
        pSrc->m_pParent->m_pLeft = pDest;
    }
    else
    {
        pSrc->m_pParent->m_pRight = pDest;
    }

    pDest->m_pRight = pSrc->m_pRight;
    pDest->m_pLeft = pSrc->m_pLeft;
    pDest->m_eColor = pSrc->m_eColor;
    pDest->m_pRight->m_pParent = pDest;
    pDest->m_pLeft->m_pParent = pDest;

    if (m_pRoot == pSrc)
    {
        m_pRoot = pDest;
    }
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::InsertImpl( KINARGTYPE key, VINARGTYPE value ) 
{
    CNode* pNew = NewNode( key, value );

    CNode* pY = NULL;
    CNode* pX = m_pRoot;

    while (!IsNil(pX))
    {
        pY = pX;
        if( KTraits::CompareElementsOrdered( key, pX->m_key ) <= 0 )
            pX = pX->m_pLeft;
        else
            pX = pX->m_pRight;
    }

    pNew->m_pParent = pY;
    if (pY == NULL)
    {
        m_pRoot = pNew;
    }
    else if( KTraits::CompareElementsOrdered( key, pY->m_key ) <= 0 )
        pY->m_pLeft = pNew;
    else
        pY->m_pRight = pNew;

    return pNew;
}

template< typename K, typename V, class KTraits, class VTraits >
void SRBTree< K, V, KTraits, VTraits >::RBDeleteFixup(CNode* pNode)
{
    SENSURE( pNode != NULL );

    CNode* pX = pNode;
    CNode* pW = NULL;

    while (( pX != m_pRoot ) && ( pX->m_eColor == CNode::RB_BLACK ))
    {
        if (pX == pX->m_pParent->m_pLeft)
        {
            pW = pX->m_pParent->m_pRight;
            if (pW->m_eColor == CNode::RB_RED)
            {
                pW->m_eColor = CNode::RB_BLACK;
                pW->m_pParent->m_eColor = CNode::RB_RED;
                LeftRotate(pX->m_pParent);
                pW = pX->m_pParent->m_pRight;
            }
            if (pW->m_pLeft->m_eColor == CNode::RB_BLACK && pW->m_pRight->m_eColor == CNode::RB_BLACK)
            {
                pW->m_eColor = CNode::RB_RED;
                pX = pX->m_pParent;
            }
            else
            {
                if (pW->m_pRight->m_eColor == CNode::RB_BLACK)
                {
                    pW->m_pLeft->m_eColor = CNode::RB_BLACK;
                    pW->m_eColor = CNode::RB_RED;
                    RightRotate(pW);
                    pW = pX->m_pParent->m_pRight;
                }
                pW->m_eColor = pX->m_pParent->m_eColor;
                pX->m_pParent->m_eColor = CNode::RB_BLACK;
                pW->m_pRight->m_eColor = CNode::RB_BLACK;
                LeftRotate(pX->m_pParent);
                pX = m_pRoot;
            }
        }
        else
        {
            pW = pX->m_pParent->m_pLeft;
            if (pW->m_eColor == CNode::RB_RED)
            {
                pW->m_eColor = CNode::RB_BLACK;
                pW->m_pParent->m_eColor = CNode::RB_RED;
                RightRotate(pX->m_pParent);
                pW = pX->m_pParent->m_pLeft;
            }
            if (pW->m_pRight->m_eColor == CNode::RB_BLACK && pW->m_pLeft->m_eColor == CNode::RB_BLACK)
            {
                pW->m_eColor = CNode::RB_RED;
                pX = pX->m_pParent;
            }
            else
            {
                if (pW->m_pLeft->m_eColor == CNode::RB_BLACK)
                {
                    pW->m_pRight->m_eColor = CNode::RB_BLACK;
                    pW->m_eColor = CNode::RB_RED;
                    LeftRotate(pW);
                    pW = pX->m_pParent->m_pLeft;
                }
                pW->m_eColor = pX->m_pParent->m_eColor;
                pX->m_pParent->m_eColor = CNode::RB_BLACK;
                pW->m_pLeft->m_eColor = CNode::RB_BLACK;
                RightRotate(pX->m_pParent);
                pX = m_pRoot;
            }
        }
    }

    pX->m_eColor = CNode::RB_BLACK;
}


template< typename K, typename V, class KTraits, class VTraits >
bool SRBTree< K, V, KTraits, VTraits >::RBDelete(CNode* pZ) 
{
    if (pZ == NULL)
        return false;

    CNode* pY = NULL;
    CNode* pX = NULL;
    if (IsNil(pZ->m_pLeft) || IsNil(pZ->m_pRight))
        pY = pZ;
    else
        pY = Successor(pZ);

    if (!IsNil(pY->m_pLeft))
        pX = pY->m_pLeft;
    else
        pX = pY->m_pRight;

    pX->m_pParent = pY->m_pParent;

    if (IsNil(pY->m_pParent))
        m_pRoot = pX;
    else if (pY == pY->m_pParent->m_pLeft)
        pY->m_pParent->m_pLeft = pX;
    else
        pY->m_pParent->m_pRight = pX;

    if (pY->m_eColor == CNode::RB_BLACK)
        RBDeleteFixup(pX);

    if (pY != pZ)
        SwapNode(pY, pZ);

    if (m_pRoot != NULL)
        SetNil(&m_pRoot->m_pParent);

    FreeNode( pZ );

    return true;
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Minimum(CNode* pNode) const 
{
    if (pNode == NULL || IsNil(pNode))
    {
        return NULL;
    }

    CNode* pMin = pNode;
    while (!IsNil(pMin->m_pLeft))
    {
        pMin = pMin->m_pLeft;
    }

    return pMin;
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Maximum(CNode* pNode) const 
{
    if (pNode == NULL || IsNil(pNode))
    {
        return NULL;
    }

    CNode* pMax = pNode;
    while (!IsNil(pMax->m_pRight))
    {
        pMax = pMax->m_pRight;
    }

    return pMax;
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Predecessor( CNode* pNode ) const 
{
    if( pNode == NULL )
    {
        return( NULL );
    }
    if( !IsNil(pNode->m_pLeft) )
    {
        return( Maximum( pNode->m_pLeft ) );
    }

    CNode* pParent = pNode->m_pParent;
    CNode* pLeft = pNode;
    while( !IsNil(pParent) && (pLeft == pParent->m_pLeft) )
    {
        pLeft = pParent;
        pParent = pParent->m_pParent;
    }

    if (IsNil(pParent))
    {
        pParent = NULL;
    }
    return( pParent );
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Successor(CNode* pNode) const 
{
    if ( pNode == NULL )
    {
        return NULL;
    }
    if ( !IsNil(pNode->m_pRight) )
    {
        return Minimum(pNode->m_pRight);
    }

    CNode* pParent = pNode->m_pParent;
    CNode* pRight = pNode;
    while ( !IsNil(pParent) && (pRight == pParent->m_pRight) )
    {
        pRight = pParent;
        pParent = pParent->m_pParent;
    }

    if (IsNil(pParent))
    {
        pParent = NULL;
    }
    return pParent;
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::RBInsert( KINARGTYPE key, VINARGTYPE value ) 
{
    CNode* pNewNode = InsertImpl( key, value );

    CNode* pX = pNewNode;
    pX->m_eColor = CNode::RB_RED;
    CNode* pY = NULL;
    while (pX != m_pRoot && pX->m_pParent->m_eColor == CNode::RB_RED)
    {
        if (pX->m_pParent == pX->m_pParent->m_pParent->m_pLeft)
        {
            pY = pX->m_pParent->m_pParent->m_pRight;
            if (pY != NULL && pY->m_eColor == CNode::RB_RED)
            {
                pX->m_pParent->m_eColor = CNode::RB_BLACK;
                pY->m_eColor = CNode::RB_BLACK;
                pX->m_pParent->m_pParent->m_eColor = CNode::RB_RED;
                pX = pX->m_pParent->m_pParent;
            }
            else
            {
                if (pX == pX->m_pParent->m_pRight)
                {
                    pX = pX->m_pParent;
                    LeftRotate(pX);
                }
                pX->m_pParent->m_eColor = CNode::RB_BLACK;
                pX->m_pParent->m_pParent->m_eColor = CNode::RB_RED;
                RightRotate(pX->m_pParent->m_pParent);
            }
        }
        else
        {
            pY = pX->m_pParent->m_pParent->m_pLeft;
            if (pY != NULL && pY->m_eColor == CNode::RB_RED)
            {
                pX->m_pParent->m_eColor = CNode::RB_BLACK;
                pY->m_eColor = CNode::RB_BLACK;
                pX->m_pParent->m_pParent->m_eColor = CNode::RB_RED;
                pX = pX->m_pParent->m_pParent;
            }
            else
            {
                if (pX == pX->m_pParent->m_pLeft)
                {
                    pX = pX->m_pParent;
                    RightRotate(pX);
                }
                pX->m_pParent->m_eColor = CNode::RB_BLACK;
                pX->m_pParent->m_pParent->m_eColor = CNode::RB_RED;
                LeftRotate(pX->m_pParent->m_pParent);
            }
        }
    }

    m_pRoot->m_eColor = CNode::RB_BLACK;
    SetNil(&m_pRoot->m_pParent);

    return( pNewNode );
}

#ifdef _DEBUG

template< typename K, typename V, class KTraits, class VTraits >
void SRBTree< K, V, KTraits, VTraits >::VerifyIntegrity(const CNode *pNode, int nCurrBlackDepth, int &nBlackDepth) const 
{
    bool bCheckForBlack = false;
    bool bLeaf = true;

    if (pNode->m_eColor == CNode::RB_RED) 
        bCheckForBlack = true;
    else
        nCurrBlackDepth++;

    SASSERT(pNode->m_pLeft != NULL);
    if (!IsNil(pNode->m_pLeft))
    {
        bLeaf = false;
        if (bCheckForBlack)
        {
            SASSERT(pNode->m_pLeft->m_eColor == CNode::RB_BLACK);
        }

        VerifyIntegrity(pNode->m_pLeft, nCurrBlackDepth, nBlackDepth);
    }

    SASSERT(pNode->m_pRight != NULL);
    if (!IsNil(pNode->m_pRight))
    {
        bLeaf = false;
        if (bCheckForBlack)
        {
            SASSERT(pNode->m_pRight->m_eColor == CNode::RB_BLACK);
        }

        VerifyIntegrity(pNode->m_pRight, nCurrBlackDepth, nBlackDepth);
    }

    SASSERT( pNode->m_pParent != NULL );
    SASSERT( ( IsNil(pNode->m_pParent) ) ||
        ( pNode->m_pParent->m_pLeft == pNode ) ||
        ( pNode->m_pParent->m_pRight == pNode ) );

    if (bLeaf) 
    {
        if (nBlackDepth == 0)
        {
            nBlackDepth = nCurrBlackDepth;
        }
        else 
        {
            SASSERT(nBlackDepth == nCurrBlackDepth);
        }
    }
}

template< typename K, typename V, class KTraits, class VTraits >
void SRBTree< K, V, KTraits, VTraits >::VerifyIntegrity() const 
{
    if ((m_pRoot == NULL) || (IsNil(m_pRoot)))
        return;

    SASSUME(m_pRoot->m_eColor == CNode::RB_BLACK);
    int nBlackDepth = 0;
    VerifyIntegrity(m_pRoot, 0, nBlackDepth);
}

#endif // _DEBUG

template< typename K, typename V, class KTraits = CElementTraits< K >, class VTraits = CElementTraits< V > >
class SRBMap :
    public SRBTree< K, V, KTraits, VTraits >
{
public:
    explicit SRBMap( size_t nBlockSize = 10 ) ;
    ~SRBMap() ;

    bool Lookup( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VOUTARGTYPE value ) const ;
    const typename SRBMap< K, V, KTraits, VTraits >::CPair* Lookup(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const ;
    typename SRBMap< K, V, KTraits, VTraits >::CPair* Lookup(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) ;
    typename SRBMap< K, V, KTraits, VTraits >::SPOSITION SetAt(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VINARGTYPE value)
    {
		SRBTree::CPair* pNode = Find(key);
        if (pNode == NULL)
        {
            return(RBInsert(key, value));
        }
        else
        {
            pNode->m_value = value;

            return(pNode);
        }
    }

    bool RemoveKey(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) ;

};


template< typename K, typename V, class KTraits, class VTraits >
SRBMap< K, V, KTraits, VTraits >::SRBMap( size_t nBlockSize )  :
SRBTree< K, V, KTraits, VTraits >( nBlockSize )
{
}

template< typename K, typename V, class KTraits, class VTraits >
SRBMap< K, V, KTraits, VTraits >::~SRBMap() 
{
}

template< typename K, typename V, class KTraits, class VTraits >
const typename SRBMap< K, V, KTraits, VTraits >::CPair* SRBMap< K, V, KTraits, VTraits >::Lookup( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const 
{
    return Find(key);
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBMap< K, V, KTraits, VTraits >::CPair* SRBMap< K, V, KTraits, VTraits >::Lookup(  typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) 
{
    return Find(key);
}

template< typename K, typename V, class KTraits, class VTraits >
bool SRBMap< K, V, KTraits, VTraits >::Lookup(  typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VOUTARGTYPE value ) const 
{
    const SRBTree::CPair* pLookup = Find( key );
    if( pLookup == NULL )
        return false;

    value = pLookup->m_value;
    return true;
}

template< typename K, typename V, class KTraits, class VTraits >
bool SRBMap< K, V, KTraits, VTraits >::RemoveKey( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) 
{
    SPOSITION pos = Lookup( key );
    if( pos != NULL )
    {
        RemoveAt( pos );

        return( true );
    }
    else
    {
        return( false );
    }
}

template< typename K, typename V, class KTraits = CElementTraits< K >, class VTraits = CElementTraits< V > >
class SRBMultiMap :
    public SRBTree< K, V, KTraits, VTraits >
{
public:
    explicit SRBMultiMap( size_t nBlockSize = 10 ) ;
    ~SRBMultiMap() ;

    typename SRBMap< K, V, KTraits, VTraits >::SPOSITION Insert( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VINARGTYPE value ) ;
    size_t RemoveKey( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) ;

    typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION FindFirstWithKey(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key) const
    {
        return(Find(key));
    }

    const typename SRBMultiMap< K, V, KTraits, VTraits >::CPair* GetNextWithKey( typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const ;
    typename SRBMultiMap< K, V, KTraits, VTraits >::CPair* GetNextWithKey(typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key);
    const V& GetNextValueWithKey( typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const ;
    V& GetNextValueWithKey( typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) ;
};

template< typename K, typename V, class KTraits, class VTraits >
SRBMultiMap< K, V, KTraits, VTraits >::SRBMultiMap( size_t nBlockSize )  :
SRBTree< K, V, KTraits, VTraits >( nBlockSize )
{
}

template< typename K, typename V, class KTraits, class VTraits >
SRBMultiMap< K, V, KTraits, VTraits >::~SRBMultiMap() 
{
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBMap< K, V, KTraits, VTraits >::SPOSITION SRBMultiMap< K, V, KTraits, VTraits >::Insert( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VINARGTYPE value ) 
{
    return( RBInsert( key, value ) );
}

template< typename K, typename V, class KTraits, class VTraits >
size_t SRBMultiMap< K, V, KTraits, VTraits >::RemoveKey( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) 
{
    size_t nElementsDeleted = 0;

    SPOSITION pos = FindFirstWithKey( key );
    while( pos != NULL )
    {
        SPOSITION posDelete = pos;
        GetNextWithKey( pos, key );
        RemoveAt( posDelete );
        nElementsDeleted++;
    }

    return( nElementsDeleted );
}



template< typename K, typename V, class KTraits, class VTraits >
const typename SRBMultiMap< K, V, KTraits, VTraits >::CPair* SRBMultiMap< K, V, KTraits, VTraits >::GetNextWithKey( typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const
{
    SASSERT( pos != NULL );
    const SRBTree::CPair* pNode = GetNext( pos );
    if( (pos == NULL) || !KTraits::CompareElements( static_cast<SRBTree::CPair* >( pos )->m_key, key ) )
    {
        pos = NULL;
    }

    return( pNode );
}

template< typename K, typename V, class KTraits, class VTraits >
typename SRBMultiMap< K, V, KTraits, VTraits >::CPair* SRBMultiMap< K, V, KTraits, VTraits >::GetNextWithKey(typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key)
{
    SASSERT( pos != NULL );
	SRBTree::CPair* pNode = GetNext( pos );
    if( (pos == NULL) || !KTraits::CompareElements( static_cast<SRBTree::CPair* >( pos )->m_key, key ) )
    {
        pos = NULL;
    }

    return( pNode );
}

template< typename K, typename V, class KTraits, class VTraits >
const V& SRBMultiMap< K, V, KTraits, VTraits >::GetNextValueWithKey( typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const
{
    const SRBTree::CPair* pPair = GetNextWithKey( pos, key );

    return( pPair->m_value );
}

template< typename K, typename V, class KTraits, class VTraits >
V& SRBMultiMap< K, V, KTraits, VTraits >::GetNextValueWithKey( typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key )
{
	SRBTree::CPair* pPair = GetNextWithKey( pos, key );

    return( pPair->m_value );
}

}; // namespace SOUI
#pragma pack(pop)

#pragma warning(pop)

#endif  // __SOUICOLL_H__