utils/HelpGen/src/wxstlac.h

/////////////////////////////////////////////////////////////////////////////
// Name:        No names yet.
// Purpose:     Contrib. demo
// Author:      Aleksandras Gluchovas
// Modified by:
// Created:     27/09/98
// RCS-ID:      $Id$
// Copyright:   (c) Aleskandars Gluchovas
// Licence:   	wxWindows licence
/////////////////////////////////////////////////////////////////////////////

#ifndef __WXSTLAC_G__
#define __WXSTLAC_G__

#ifdef new
#undef new
#endif

#include <stddef.h>
#if !defined(__WXMAC__) || defined(__DARWIN__)
#  include <sys/types.h>
#endif
#include <memory.h>
#include <limits.h>
#include <new.h>

// the below macro used internally (see actual interface after this macro)

// arguments:
//
//	    ARG_IS_UNIQUE
//		ASSOC_CONT_CLASS_NAME
//
//	    ARG_VALUE_TYPE
//      ARG_KEY_TYPE
//      ARG_ACTUAL_VALUE_TYPE
//
//      _KEY_NAME
//      _VALUE_NAME
//
//		_X_KEY_NAME
// 		_X_VALUE_NAME
//
//      _INSERT_METHOD_DEFINITION

#define __DEFINE_ASOC_CLASS( ARG_IS_UNIQUE, \
FUNCTOR,\
ASSOC_CONT_CLASS_NAME, \
ARG_VALUE_TYPE, \
ARG_KEY_TYPE, \
ARG_ACTUAL_VALUE_TYPE, \
_KEY_NAME, \
_VALUE_NAME, \
_X_KEY_NAME, \
_X_VALUE_NAME, \
_INSERT_METHOD_DEFINITION \
) class \
ASSOC_CONT_CLASS_NAME\
{\
protected:\
\
public:\
	typedef ARG_VALUE_TYPE        value_type;\
	typedef ARG_KEY_TYPE          key_type;\
	typedef ARG_ACTUAL_VALUE_TYPE actual_value_type;\
\
	typedef value_type*			  pointer;\
	typedef value_type&			  reference;\
\
	typedef const value_type&	  const_reference;\
\
	typedef FUNCTOR				  key_compare;\
	typedef key_compare           Compare;\
\
protected:\
\
	struct tree_node \
	{\
		tree_node*  mpParent;\
		tree_node*  mpLeft;\
		tree_node*  mpRight;\
\
		value_type  mData;\
	};\
\
	typedef tree_node* node_ref_type;\
\
	node_ref_type   mpRoot;\
	node_ref_type   mpLeftMost;\
	node_ref_type   mpRightMost;\
\
	node_ref_type   mpFreeListHead;\
	int             mKeyIsUnique;\
\
	key_compare     mCmpFunctorObj;\
\
public:\
\
	static inline node_ref_type next( node_ref_type pNode )\
	{\
		if ( pNode->mpRight ) \
		{\
			pNode = pNode->mpRight;\
\
			while ( pNode->mpLeft ) pNode = pNode->mpLeft;\
\
			return pNode;\
		}\
		else\
		if ( pNode->mpParent )\
		{\
			if ( pNode == pNode->mpParent->mpLeft )\
\
				return pNode->mpParent;\
\
			pNode = pNode->mpParent;\
\
			node_ref_type prevNode = pNode;\
			pNode = pNode->mpParent;\
\
			while(pNode)\
			{\
				if ( pNode->mpRight &&\
					 pNode->mpRight != prevNode\
				   ) return pNode;\
\
				prevNode = pNode;\
				pNode= pNode->mpParent;\
			}\
\
			return 0;\
		}\
		else\
			return 0;\
	}\
\
	static inline node_ref_type prev( node_ref_type pNode )\
	{\
		if ( pNode->mpLeft ) \
		{\
			pNode = pNode->mpLeft;\
\
			while ( pNode->mpRight ) pNode = pNode->mpRight;\
\
			return pNode;\
		}\
		else\
		if ( pNode->mpParent )\
		{\
			if ( pNode == pNode->mpParent->mpRight )\
				return pNode->mpParent;\
\
			pNode = pNode->mpParent;\
\
			node_ref_type prevNode = pNode;\
			pNode = pNode->mpParent;\
\
			while(pNode)\
			{\
				if ( pNode->mpLeft &&\
					 pNode->mpLeft != prevNode\
				   ) return pNode;\
\
				prevNode = pNode;\
				pNode= pNode->mpParent;\
			}\
\
			return 0;\
		}\
		else \
			return 0;\
	}\
\
protected:\
\
	inline int are_equel( const key_type& x, const key_type& y )\
	{\
		return ( !mCmpFunctorObj(x,y) && !mCmpFunctorObj(y,x) );\
	}\
\
	inline int is_less( const key_type& x, const key_type& y )\
	{\
		return mCmpFunctorObj(x,y);\
	}\
\
	static inline const actual_value_type& value( node_ref_type pNode )\
	{\
		return pNode->_VALUE_NAME;\
	}\
\
	static inline const key_type& key( node_ref_type pNode )\
	{\
		return pNode->_KEY_NAME;\
	}\
\
	inline node_ref_type AllocNode() \
	{ \
		if ( mpFreeListHead ) \
		{\
			node_ref_type pFreeNode = mpFreeListHead;\
			mpFreeListHead = mpFreeListHead->mpLeft;\
\
			return pFreeNode;\
		}\
		else\
		{\
			char* pHeapBlock = new char[sizeof(tree_node)];\
\
			return (node_ref_type)pHeapBlock;\
		}\
	}\
\
	inline void DestroyFreeList()\
	{\
		while ( mpFreeListHead )\
		{\
			node_ref_type tmp = mpFreeListHead;\
			mpFreeListHead = mpFreeListHead->mpLeft;\
\
			delete [](char*)tmp;\
		}\
	}\
\
	inline void RecycleNode( node_ref_type pNode ) \
	{\
		pNode->mpLeft = mpFreeListHead;\
		mpFreeListHead = pNode;\
	}\
\
	inline node_ref_type do_insert(const value_type& x = value_type() )\
	{\
		node_ref_type pNewNode = AllocNode();\
\
		pNewNode->mpParent = \
			pNewNode->mpLeft =\
				pNewNode->mpRight = 0;\
\
	    node_ref_type pCurrent = mpRoot;\
		node_ref_type pParent = 0;\
    \
		while (pCurrent) \
		{\
			if ( mKeyIsUnique && are_equel( _X_KEY_NAME, value(pCurrent) ) )\
			{\
				RecycleNode(pNewNode);\
				return 0;\
			}\
\
			pParent = pCurrent;\
\
			pCurrent = is_less( _X_KEY_NAME, value(pCurrent) ) \
				? pCurrent->mpLeft \
				: pCurrent->mpRight;\
		}\
    \
		pNewNode->mpParent = pParent;\
\
	    if(pParent)\
\
			if( is_less(_X_KEY_NAME, value(pParent) ) )\
            \
				pParent->mpLeft = pNewNode;\
			else\
				pParent->mpRight = pNewNode;\
			else\
				mpRoot = pNewNode;\
\
		new ( &pNewNode->_KEY_NAME   ) key_type(_X_KEY_NAME);\
		new ( &pNewNode->_VALUE_NAME ) actual_value_type(_X_VALUE_NAME);\
\
		if ( prev(pNewNode) == 0 ) mpLeftMost = pNewNode;\
		if ( next(pNewNode) == 0 ) mpRightMost = pNewNode;\
\
		return pNewNode;\
	}\
\
	friend class iterator;\
\
public:\
\
	class iterator;\
	class const_iterator;\
\
	class iterator \
	{\
	public:\
		node_ref_type mpNode;\
		friend class CONT_CLASS_NAME;\
		friend class const_iterator;\
		friend class const_reverse_iterator;\
\
		inline iterator( node_ref_type pNode )\
		{\
			mpNode = pNode;\
		}\
	\
	public:\
		inline iterator() {}\
		inline int operator==( const iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
		inline int operator!=( const iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
\
		inline iterator( const iterator& other )\
		{\
			mpNode = other.mpNode;\
		}\
\
		inline const iterator& operator=( const iterator& other )\
		{\
			mpNode = other.mpNode;\
			return *this;\
		}\
\
		inline const iterator& operator--() \
		{\
			mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
			return *this;\
		}\
\
		inline iterator operator--(int)\
		{\
			iterator tmp = *this;\
			mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
			return tmp;\
		}\
\
		inline const iterator& operator++() \
		{\
			mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
			return *this;\
		}\
\
		inline iterator operator++(int)\
		{\
			iterator tmp = *this;\
			mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
			return tmp;\
		}\
\
		inline reference operator*() const { return mpNode->mData; }\
	};\
\
\
	class const_iterator \
	{\
	public:\
		node_ref_type mpNode;\
		friend class CONT_CLASS_NAME;\
		friend class const_reverse_iterator;\
\
		inline const_iterator( node_ref_type pNode )\
		{\
			mpNode = pNode;\
		}\
	\
	public:\
		inline const_iterator() {}\
\
		inline int operator==( const const_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
		inline int operator!=( const const_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
\
		inline const_iterator( const iterator& other )\
		{\
			mpNode = other.mpNode;\
		}\
\
		inline const_iterator( const const_iterator& other )\
		{\
			mpNode = other.mpNode;\
		}\
\
		inline const const_iterator& operator=( const const_iterator& other )\
		{\
			mpNode = other.mpNode;\
			return *this;\
		}\
\
		inline const const_iterator& operator--() \
		{\
			mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
			return *this;\
		}\
\
		inline const_iterator operator--(int)\
		{\
			const_iterator tmp = *this;\
			mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
			return tmp;\
		}\
\
		inline const const_iterator& operator++() \
		{\
			mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
			return *this;\
		}\
\
		inline const_iterator operator++(int)\
		{\
			const_iterator tmp = *this;\
			mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
			return tmp;\
		}\
\
		inline const_reference operator*() const { return mpNode->mData; }\
	};\
\
public:\
\
	inline ASSOC_CONT_CLASS_NAME( key_compare cmpFunctorObj = key_compare(),\
								  int keyIsUnique = ARG_IS_UNIQUE )\
			: mpFreeListHead( 0 ),\
			  mKeyIsUnique( keyIsUnique ),\
			  mCmpFunctorObj( cmpFunctorObj )\
	{\
		mpLeftMost = 0;\
		mpRightMost = 0;\
		mpRoot = 0;\
	}\
\
	inline ~ASSOC_CONT_CLASS_NAME() \
	{ \
		erase( begin(), end() ); \
\
		DestroyFreeList();\
	}\
\
	inline iterator begin() { return mpLeftMost; }\
	inline iterator end()   { return 0; }\
\
	inline const_iterator begin() const { return mpLeftMost; }\
	inline const_iterator end()   const { return 0; }\
\
	inline iterator lower_bound( const key_type& x )\
	{ \
		node_ref_type pCurrent = mpRoot;\
    \
		while( pCurrent )\
		{\
			node_ref_type pParent = pCurrent;\
\
			if( are_equel( x, key(pCurrent) ) )\
				\
				return (pCurrent);\
			else\
				pCurrent = is_less( x, key(pCurrent) ) \
					? pCurrent->mpLeft \
					: pCurrent->mpRight;\
\
			if ( !pCurrent ) return (pParent);\
		}\
\
		return begin();\
	}\
\
	inline const_iterator lower_bound( const key_type& x ) const\
\
		{ return const_iterator( lower_bound(x).mpNode ); }\
\
	inline iterator upper_bound( const key_type& x )\
	{\
		node_ref_type pCurrent = mpRoot;\
    \
		while( pCurrent )\
		{\
			node_ref_type pParent = pCurrent;\
\
			if( are_equel( x, key(pCurrent) ) )\
				\
				return (pCurrent);\
			else\
				pCurrent = is_less( x, key(pCurrent) ) \
					? pCurrent->mpLeft \
					: pCurrent->mpRight;\
\
			if ( !pCurrent ) return next(pParent);\
		}\
\
		return end();\
	}\
\
	inline const_iterator upper_bound( const key_type& x ) const\
\
		{ return const_iterator( upper_bound(x).mpNode ); }\
\
	inline iterator find( const key_type& x )\
	{\
		node_ref_type pCurrent = mpRoot;\
    \
		while( pCurrent )\
		{\
			if( are_equel( x, key(pCurrent) ) )\
				\
				return (pCurrent);\
			else\
				pCurrent = is_less( x, key(pCurrent) ) \
					? pCurrent->mpLeft \
					: pCurrent->mpRight;\
		}\
\
		return end();\
	}\
\
	inline const_iterator find( const key_type& x ) const\
\
		{ return const_iterator( find(x).mpNode ); }\
\
	inline void erase(iterator first, iterator last)\
	{\
		if ( first.mpNode == 0 ) return;\
\
		while( first != last ) \
		{\
			iterator next = first;\
			++next;\
			erase( first );\
			first = next;\
		}\
	}\
\
	inline void erase(iterator position)\
	{\
		if ( position.mpNode == 0 ) return;\
\
		node_ref_type pZ = position.mpNode;\
		node_ref_type pX, pY;\
\
		if ( pZ == mpLeftMost ) mpLeftMost   = next(pZ);\
		if ( pZ == mpRightMost ) mpRightMost = prev( pZ );\
\
        if ( !pZ->mpLeft || !pZ->mpRight )\
	    \
            pY = pZ;\
        else \
		{\
            pY = pZ->mpRight;\
	    \
            while (pY->mpLeft) \
				\
				pY = pY->mpLeft;\
        }\
	    \
        if ( pY->mpLeft)\
	    \
            pX = pY->mpLeft;\
        else\
            pX = pY->mpRight;\
	    \
        if ( pX ) pX->mpParent = pY->mpParent;\
	    \
        if (pY->mpParent)\
	    \
            if (pY == pY->mpParent->mpLeft )\
	    \
                pY->mpParent->mpLeft = pX;\
		    else\
                pY->mpParent->mpRight = pX;\
        else\
            mpRoot = pX;\
	    \
		node_ref_type toRemove = 0;\
		\
        if (pY != pZ) {\
	    \
            pY->mpLeft = pZ->mpLeft;\
	    \
            if (pY->mpLeft) pY->mpLeft->mpParent = pY;\
	    \
            pY->mpRight = pZ->mpRight;\
	    \
            if ( pY->mpRight ) \
				\
				pY->mpRight->mpParent = pY;\
	    \
            pY->mpParent = pZ->mpParent;\
	    \
            if (pZ->mpParent)\
	    \
                if (pZ == pZ->mpParent->mpLeft)\
	    \
                    pZ->mpParent->mpLeft = pY;\
                else\
                    pZ->mpParent->mpRight = pY;\
            else\
                mpRoot = pY;\
	    \
            toRemove = pZ;\
        } \
		else \
            toRemove = pY;\
	    \
		value(toRemove).~actual_value_type();\
		key(toRemove).~actual_value_type();\
\
		RecycleNode( toRemove );\
	}\
\
	_INSERT_METHOD_DEFINITION\
}

// do not undefine ___WXSTL_COMMA, where associated containers are defined!
// (it is used as workaround for constraints of C-Preprocessor's nested macros)

#define ___WXSTL_COMMA ,

#define __DEFINE_MAP(ARG_IS_UNIQUE, KEY_TYPE, VAL_TYPE, FUNCTOR ) \
__DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
FUNCTOR,\
__WXSTLMAP_##KEY_TYPE##VAL_TYPE##ARG_IS_UNIQUE, \
struct key_value_pair   { KEY_TYPE first ; \
                          VAL_TYPE second;\
                          key_value_pair() {}\
                          key_value_pair( const KEY_TYPE& key ___WXSTL_COMMA const VAL_TYPE& value ) \
                            : first(key) ___WXSTL_COMMA second( value ) {} \
                         } , \
KEY_TYPE,\
VAL_TYPE,\
mData.first, mData.second, x.first, x.second, \
struct insert_result_iterator\
{\
	iterator first;\
	int      second;\
};\
inline insert_result_iterator insert( const value_type& x )\
{\
	insert_result_iterator result;\
\
	result.first = do_insert(x);\
	result.second  = ( result.first == end() ) ? 0 : 1;\
\
	return result;\
} )

#define __DEFINE_SET(ARG_IS_UNIQUE, KEY_TYPE, FUNCTOR ) \
__DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
FUNCTOR,\
__WXSTLSET_##TYPE##ARG_IS_UNIQUE, \
KEY_TYPE,\
KEY_TYPE,\
KEY_TYPE,\
mData, mData, x, x, \
struct insert_result_iterator\
{\
	iterator first;\
	int      second;\
};\
inline insert_result_iterator insert( const value_type& x )\
{\
	insert_result_iterator result;\
\
	result.first = do_insert(x);\
	result.second  = ( result.first == end() ) ? 0 : 1;\
\
	return result;\
} )

// helper macros to create functor objects for associative containers of the given type

#define LESS_THEN_FUNCTOR(TYPE) struct \
{ inline int operator()(const TYPE& x, const TYPE& y ) const { return x < y; } }

#define GREATER_THEN_FUNCTOR(TYPE) struct \
{ inline int operator()(const TYPE& x, const TYPE& y ) const { return x > y; } }

// functor argument should be created using the two above macros
// or passing own class with method "operator()(const TYPE&,cosnt TYPE&)" defined in it

#define WXSTL_MAP( KEY_TYPE, VALUE_TYPE, FUNCTOR )      __DEFINE_MAP( 1 ,KEY_TYPE, VALUE_TYPE, FUNCTOR)
#define WXSTL_MULTIMAP( KEY_TYPE, VALUE_TYPE, FUNCTOR ) __DEFINE_MAP( 0 ,KEY_TYPE, VALUE_TYPE, FUNCTOR)
#define WXSTL_SET( KEY_TYPE, FUNCTOR )                  __DEFINE_SET( 1 ,KEY_TYPE, FUNCTOR )
#define WXSTL_MULTISET( KEY_TYPE, FUNCTOR )             __DEFINE_SET( 0 ,KEY_TYPE, FUNCTOR )

#endif
Commit	Line	Data
	1	/////////////////////////////////////////////////////////////////////////////
	2	// Name: No names yet.
	3	// Purpose: Contrib. demo
	4	// Author: Aleksandras Gluchovas
	5	// Modified by:
	6	// Created: 27/09/98
	7	// RCS-ID: $Id$
	8	// Copyright: (c) Aleskandars Gluchovas
	9	// Licence: wxWindows licence
	10	/////////////////////////////////////////////////////////////////////////////
	11
	12	#ifndef __WXSTLAC_G__
	13	#define __WXSTLAC_G__
	14
	15	#ifdef new
	16	#undef new
	17	#endif
	18
	19	#include <stddef.h>
	20	#if !defined(__WXMAC__) \|\| defined(__DARWIN__)
	21	# include <sys/types.h>
	22	#endif
	23	#include <memory.h>
	24	#include <limits.h>
	25	#include <new.h>
	26
	27	// the below macro used internally (see actual interface after this macro)
	28
	29	// arguments:
	30	//
	31	// ARG_IS_UNIQUE
	32	// ASSOC_CONT_CLASS_NAME
	33	//
	34	// ARG_VALUE_TYPE
	35	// ARG_KEY_TYPE
	36	// ARG_ACTUAL_VALUE_TYPE
	37	//
	38	// _KEY_NAME
	39	// _VALUE_NAME
	40	//
	41	// _X_KEY_NAME
	42	// _X_VALUE_NAME
	43	//
	44	// _INSERT_METHOD_DEFINITION
	45
	46	#define __DEFINE_ASOC_CLASS( ARG_IS_UNIQUE, \
	47	FUNCTOR,\
	48	ASSOC_CONT_CLASS_NAME, \
	49	ARG_VALUE_TYPE, \
	50	ARG_KEY_TYPE, \
	51	ARG_ACTUAL_VALUE_TYPE, \
	52	_KEY_NAME, \
	53	_VALUE_NAME, \
	54	_X_KEY_NAME, \
	55	_X_VALUE_NAME, \
	56	_INSERT_METHOD_DEFINITION \
	57	) class \
	58	ASSOC_CONT_CLASS_NAME\
	59	{\
	60	protected:\
	61	\
	62	public:\
	63	typedef ARG_VALUE_TYPE value_type;\
	64	typedef ARG_KEY_TYPE key_type;\
	65	typedef ARG_ACTUAL_VALUE_TYPE actual_value_type;\
	66	\
	67	typedef value_type* pointer;\
	68	typedef value_type& reference;\
	69	\
	70	typedef const value_type& const_reference;\
	71	\
	72	typedef FUNCTOR key_compare;\
	73	typedef key_compare Compare;\
	74	\
	75	protected:\
	76	\
	77	struct tree_node \
	78	{\
	79	tree_node* mpParent;\
	80	tree_node* mpLeft;\
	81	tree_node* mpRight;\
	82	\
	83	value_type mData;\
	84	};\
	85	\
	86	typedef tree_node* node_ref_type;\
	87	\
	88	node_ref_type mpRoot;\
	89	node_ref_type mpLeftMost;\
	90	node_ref_type mpRightMost;\
	91	\
	92	node_ref_type mpFreeListHead;\
	93	int mKeyIsUnique;\
	94	\
	95	key_compare mCmpFunctorObj;\
	96	\
	97	public:\
	98	\
	99	static inline node_ref_type next( node_ref_type pNode )\
	100	{\
	101	if ( pNode->mpRight ) \
	102	{\
	103	pNode = pNode->mpRight;\
	104	\
	105	while ( pNode->mpLeft ) pNode = pNode->mpLeft;\
	106	\
	107	return pNode;\
	108	}\
	109	else\
	110	if ( pNode->mpParent )\
	111	{\
	112	if ( pNode == pNode->mpParent->mpLeft )\
	113	\
	114	return pNode->mpParent;\
	115	\
	116	pNode = pNode->mpParent;\
	117	\
	118	node_ref_type prevNode = pNode;\
	119	pNode = pNode->mpParent;\
	120	\
	121	while(pNode)\
	122	{\
	123	if ( pNode->mpRight &&\
	124	pNode->mpRight != prevNode\
	125	) return pNode;\
	126	\
	127	prevNode = pNode;\
	128	pNode= pNode->mpParent;\
	129	}\
	130	\
	131	return 0;\
	132	}\
	133	else\
	134	return 0;\
	135	}\
	136	\
	137	static inline node_ref_type prev( node_ref_type pNode )\
	138	{\
	139	if ( pNode->mpLeft ) \
	140	{\
	141	pNode = pNode->mpLeft;\
	142	\
	143	while ( pNode->mpRight ) pNode = pNode->mpRight;\
	144	\
	145	return pNode;\
	146	}\
	147	else\
	148	if ( pNode->mpParent )\
	149	{\
	150	if ( pNode == pNode->mpParent->mpRight )\
	151	return pNode->mpParent;\
	152	\
	153	pNode = pNode->mpParent;\
	154	\
	155	node_ref_type prevNode = pNode;\
	156	pNode = pNode->mpParent;\
	157	\
	158	while(pNode)\
	159	{\
	160	if ( pNode->mpLeft &&\
	161	pNode->mpLeft != prevNode\
	162	) return pNode;\
	163	\
	164	prevNode = pNode;\
	165	pNode= pNode->mpParent;\
	166	}\
	167	\
	168	return 0;\
	169	}\
	170	else \
	171	return 0;\
	172	}\
	173	\
	174	protected:\
	175	\
	176	inline int are_equel( const key_type& x, const key_type& y )\
	177	{\
	178	return ( !mCmpFunctorObj(x,y) && !mCmpFunctorObj(y,x) );\
	179	}\
	180	\
	181	inline int is_less( const key_type& x, const key_type& y )\
	182	{\
	183	return mCmpFunctorObj(x,y);\
	184	}\
	185	\
	186	static inline const actual_value_type& value( node_ref_type pNode )\
	187	{\
	188	return pNode->_VALUE_NAME;\
	189	}\
	190	\
	191	static inline const key_type& key( node_ref_type pNode )\
	192	{\
	193	return pNode->_KEY_NAME;\
	194	}\
	195	\
	196	inline node_ref_type AllocNode() \
	197	{ \
	198	if ( mpFreeListHead ) \
	199	{\
	200	node_ref_type pFreeNode = mpFreeListHead;\
	201	mpFreeListHead = mpFreeListHead->mpLeft;\
	202	\
	203	return pFreeNode;\
	204	}\
	205	else\
	206	{\
	207	char* pHeapBlock = new char[sizeof(tree_node)];\
	208	\
	209	return (node_ref_type)pHeapBlock;\
	210	}\
	211	}\
	212	\
	213	inline void DestroyFreeList()\
	214	{\
	215	while ( mpFreeListHead )\
	216	{\
	217	node_ref_type tmp = mpFreeListHead;\
	218	mpFreeListHead = mpFreeListHead->mpLeft;\
	219	\
	220	delete [](char*)tmp;\
	221	}\
	222	}\
	223	\
	224	inline void RecycleNode( node_ref_type pNode ) \
	225	{\
	226	pNode->mpLeft = mpFreeListHead;\
	227	mpFreeListHead = pNode;\
	228	}\
	229	\
	230	inline node_ref_type do_insert(const value_type& x = value_type() )\
	231	{\
	232	node_ref_type pNewNode = AllocNode();\
	233	\
	234	pNewNode->mpParent = \
	235	pNewNode->mpLeft =\
	236	pNewNode->mpRight = 0;\
	237	\
	238	node_ref_type pCurrent = mpRoot;\
	239	node_ref_type pParent = 0;\
	240	\
	241	while (pCurrent) \
	242	{\
	243	if ( mKeyIsUnique && are_equel( _X_KEY_NAME, value(pCurrent) ) )\
	244	{\
	245	RecycleNode(pNewNode);\
	246	return 0;\
	247	}\
	248	\
	249	pParent = pCurrent;\
	250	\
	251	pCurrent = is_less( _X_KEY_NAME, value(pCurrent) ) \
	252	? pCurrent->mpLeft \
	253	: pCurrent->mpRight;\
	254	}\
	255	\
	256	pNewNode->mpParent = pParent;\
	257	\
	258	if(pParent)\
	259	\
	260	if( is_less(_X_KEY_NAME, value(pParent) ) )\
	261	\
	262	pParent->mpLeft = pNewNode;\
	263	else\
	264	pParent->mpRight = pNewNode;\
	265	else\
	266	mpRoot = pNewNode;\
	267	\
	268	new ( &pNewNode->_KEY_NAME ) key_type(_X_KEY_NAME);\
	269	new ( &pNewNode->_VALUE_NAME ) actual_value_type(_X_VALUE_NAME);\
	270	\
	271	if ( prev(pNewNode) == 0 ) mpLeftMost = pNewNode;\
	272	if ( next(pNewNode) == 0 ) mpRightMost = pNewNode;\
	273	\
	274	return pNewNode;\
	275	}\
	276	\
	277	friend class iterator;\
	278	\
	279	public:\
	280	\
	281	class iterator;\
	282	class const_iterator;\
	283	\
	284	class iterator \
	285	{\
	286	public:\
	287	node_ref_type mpNode;\
	288	friend class CONT_CLASS_NAME;\
	289	friend class const_iterator;\
	290	friend class const_reverse_iterator;\
	291	\
	292	inline iterator( node_ref_type pNode )\
	293	{\
	294	mpNode = pNode;\
	295	}\
	296	\
	297	public:\
	298	inline iterator() {}\
	299	inline int operator==( const iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
	300	inline int operator!=( const iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
	301	\
	302	inline iterator( const iterator& other )\
	303	{\
	304	mpNode = other.mpNode;\
	305	}\
	306	\
	307	inline const iterator& operator=( const iterator& other )\
	308	{\
	309	mpNode = other.mpNode;\
	310	return *this;\
	311	}\
	312	\
	313	inline const iterator& operator--() \
	314	{\
	315	mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
	316	return *this;\
	317	}\
	318	\
	319	inline iterator operator--(int)\
	320	{\
	321	iterator tmp = *this;\
	322	mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
	323	return tmp;\
	324	}\
	325	\
	326	inline const iterator& operator++() \
	327	{\
	328	mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
	329	return *this;\
	330	}\
	331	\
	332	inline iterator operator++(int)\
	333	{\
	334	iterator tmp = *this;\
	335	mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
	336	return tmp;\
	337	}\
	338	\
	339	inline reference operator*() const { return mpNode->mData; }\
	340	};\
	341	\
	342	\
	343	class const_iterator \
	344	{\
	345	public:\
	346	node_ref_type mpNode;\
	347	friend class CONT_CLASS_NAME;\
	348	friend class const_reverse_iterator;\
	349	\
	350	inline const_iterator( node_ref_type pNode )\
	351	{\
	352	mpNode = pNode;\
	353	}\
	354	\
	355	public:\
	356	inline const_iterator() {}\
	357	\
	358	inline int operator==( const const_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
	359	inline int operator!=( const const_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
	360	\
	361	inline const_iterator( const iterator& other )\
	362	{\
	363	mpNode = other.mpNode;\
	364	}\
	365	\
	366	inline const_iterator( const const_iterator& other )\
	367	{\
	368	mpNode = other.mpNode;\
	369	}\
	370	\
	371	inline const const_iterator& operator=( const const_iterator& other )\
	372	{\
	373	mpNode = other.mpNode;\
	374	return *this;\
	375	}\
	376	\
	377	inline const const_iterator& operator--() \
	378	{\
	379	mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
	380	return *this;\
	381	}\
	382	\
	383	inline const_iterator operator--(int)\
	384	{\
	385	const_iterator tmp = *this;\
	386	mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
	387	return tmp;\
	388	}\
	389	\
	390	inline const const_iterator& operator++() \
	391	{\
	392	mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
	393	return *this;\
	394	}\
	395	\
	396	inline const_iterator operator++(int)\
	397	{\
	398	const_iterator tmp = *this;\
	399	mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
	400	return tmp;\
	401	}\
	402	\
	403	inline const_reference operator*() const { return mpNode->mData; }\
	404	};\
	405	\
	406	public:\
	407	\
	408	inline ASSOC_CONT_CLASS_NAME( key_compare cmpFunctorObj = key_compare(),\
	409	int keyIsUnique = ARG_IS_UNIQUE )\
	410	: mpFreeListHead( 0 ),\
	411	mKeyIsUnique( keyIsUnique ),\
	412	mCmpFunctorObj( cmpFunctorObj )\
	413	{\
	414	mpLeftMost = 0;\
	415	mpRightMost = 0;\
	416	mpRoot = 0;\
	417	}\
	418	\
	419	inline ~ASSOC_CONT_CLASS_NAME() \
	420	{ \
	421	erase( begin(), end() ); \
	422	\
	423	DestroyFreeList();\
	424	}\
	425	\
	426	inline iterator begin() { return mpLeftMost; }\
	427	inline iterator end() { return 0; }\
	428	\
	429	inline const_iterator begin() const { return mpLeftMost; }\
	430	inline const_iterator end() const { return 0; }\
	431	\
	432	inline iterator lower_bound( const key_type& x )\
	433	{ \
	434	node_ref_type pCurrent = mpRoot;\
	435	\
	436	while( pCurrent )\
	437	{\
	438	node_ref_type pParent = pCurrent;\
	439	\
	440	if( are_equel( x, key(pCurrent) ) )\
	441	\
	442	return (pCurrent);\
	443	else\
	444	pCurrent = is_less( x, key(pCurrent) ) \
	445	? pCurrent->mpLeft \
	446	: pCurrent->mpRight;\
	447	\
	448	if ( !pCurrent ) return (pParent);\
	449	}\
	450	\
	451	return begin();\
	452	}\
	453	\
	454	inline const_iterator lower_bound( const key_type& x ) const\
	455	\
	456	{ return const_iterator( lower_bound(x).mpNode ); }\
	457	\
	458	inline iterator upper_bound( const key_type& x )\
	459	{\
	460	node_ref_type pCurrent = mpRoot;\
	461	\
	462	while( pCurrent )\
	463	{\
	464	node_ref_type pParent = pCurrent;\
	465	\
	466	if( are_equel( x, key(pCurrent) ) )\
	467	\
	468	return (pCurrent);\
	469	else\
	470	pCurrent = is_less( x, key(pCurrent) ) \
	471	? pCurrent->mpLeft \
	472	: pCurrent->mpRight;\
	473	\
	474	if ( !pCurrent ) return next(pParent);\
	475	}\
	476	\
	477	return end();\
	478	}\
	479	\
	480	inline const_iterator upper_bound( const key_type& x ) const\
	481	\
	482	{ return const_iterator( upper_bound(x).mpNode ); }\
	483	\
	484	inline iterator find( const key_type& x )\
	485	{\
	486	node_ref_type pCurrent = mpRoot;\
	487	\
	488	while( pCurrent )\
	489	{\
	490	if( are_equel( x, key(pCurrent) ) )\
	491	\
	492	return (pCurrent);\
	493	else\
	494	pCurrent = is_less( x, key(pCurrent) ) \
	495	? pCurrent->mpLeft \
	496	: pCurrent->mpRight;\
	497	}\
	498	\
	499	return end();\
	500	}\
	501	\
	502	inline const_iterator find( const key_type& x ) const\
	503	\
	504	{ return const_iterator( find(x).mpNode ); }\
	505	\
	506	inline void erase(iterator first, iterator last)\
	507	{\
	508	if ( first.mpNode == 0 ) return;\
	509	\
	510	while( first != last ) \
	511	{\
	512	iterator next = first;\
	513	++next;\
	514	erase( first );\
	515	first = next;\
	516	}\
	517	}\
	518	\
	519	inline void erase(iterator position)\
	520	{\
	521	if ( position.mpNode == 0 ) return;\
	522	\
	523	node_ref_type pZ = position.mpNode;\
	524	node_ref_type pX, pY;\
	525	\
	526	if ( pZ == mpLeftMost ) mpLeftMost = next(pZ);\
	527	if ( pZ == mpRightMost ) mpRightMost = prev( pZ );\
	528	\
	529	if ( !pZ->mpLeft \|\| !pZ->mpRight )\
	530	\
	531	pY = pZ;\
	532	else \
	533	{\
	534	pY = pZ->mpRight;\
	535	\
	536	while (pY->mpLeft) \
	537	\
	538	pY = pY->mpLeft;\
	539	}\
	540	\
	541	if ( pY->mpLeft)\
	542	\
	543	pX = pY->mpLeft;\
	544	else\
	545	pX = pY->mpRight;\
	546	\
	547	if ( pX ) pX->mpParent = pY->mpParent;\
	548	\
	549	if (pY->mpParent)\
	550	\
	551	if (pY == pY->mpParent->mpLeft )\
	552	\
	553	pY->mpParent->mpLeft = pX;\
	554	else\
	555	pY->mpParent->mpRight = pX;\
	556	else\
	557	mpRoot = pX;\
	558	\
	559	node_ref_type toRemove = 0;\
	560	\
	561	if (pY != pZ) {\
	562	\
	563	pY->mpLeft = pZ->mpLeft;\
	564	\
	565	if (pY->mpLeft) pY->mpLeft->mpParent = pY;\
	566	\
	567	pY->mpRight = pZ->mpRight;\
	568	\
	569	if ( pY->mpRight ) \
	570	\
	571	pY->mpRight->mpParent = pY;\
	572	\
	573	pY->mpParent = pZ->mpParent;\
	574	\
	575	if (pZ->mpParent)\
	576	\
	577	if (pZ == pZ->mpParent->mpLeft)\
	578	\
	579	pZ->mpParent->mpLeft = pY;\
	580	else\
	581	pZ->mpParent->mpRight = pY;\
	582	else\
	583	mpRoot = pY;\
	584	\
	585	toRemove = pZ;\
	586	} \
	587	else \
	588	toRemove = pY;\
	589	\
	590	value(toRemove).~actual_value_type();\
	591	key(toRemove).~actual_value_type();\
	592	\
	593	RecycleNode( toRemove );\
	594	}\
	595	\
	596	_INSERT_METHOD_DEFINITION\
	597	}
	598
	599	// do not undefine ___WXSTL_COMMA, where associated containers are defined!
	600	// (it is used as workaround for constraints of C-Preprocessor's nested macros)
	601
	602	#define ___WXSTL_COMMA ,
	603
	604	#define __DEFINE_MAP(ARG_IS_UNIQUE, KEY_TYPE, VAL_TYPE, FUNCTOR ) \
	605	__DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
	606	FUNCTOR,\
	607	__WXSTLMAP_##KEY_TYPE##VAL_TYPE##ARG_IS_UNIQUE, \
	608	struct key_value_pair { KEY_TYPE first ; \
	609	VAL_TYPE second;\
	610	key_value_pair() {}\
	611	key_value_pair( const KEY_TYPE& key ___WXSTL_COMMA const VAL_TYPE& value ) \
	612	: first(key) ___WXSTL_COMMA second( value ) {} \
	613	} , \
	614	KEY_TYPE,\
	615	VAL_TYPE,\
	616	mData.first, mData.second, x.first, x.second, \
	617	struct insert_result_iterator\
	618	{\
	619	iterator first;\
	620	int second;\
	621	};\
	622	inline insert_result_iterator insert( const value_type& x )\
	623	{\
	624	insert_result_iterator result;\
	625	\
	626	result.first = do_insert(x);\
	627	result.second = ( result.first == end() ) ? 0 : 1;\
	628	\
	629	return result;\
	630	} )
	631
	632	#define __DEFINE_SET(ARG_IS_UNIQUE, KEY_TYPE, FUNCTOR ) \
	633	__DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
	634	FUNCTOR,\
	635	__WXSTLSET_##TYPE##ARG_IS_UNIQUE, \
	636	KEY_TYPE,\
	637	KEY_TYPE,\
	638	KEY_TYPE,\
	639	mData, mData, x, x, \
	640	struct insert_result_iterator\
	641	{\
	642	iterator first;\
	643	int second;\
	644	};\
	645	inline insert_result_iterator insert( const value_type& x )\
	646	{\
	647	insert_result_iterator result;\
	648	\
	649	result.first = do_insert(x);\
	650	result.second = ( result.first == end() ) ? 0 : 1;\
	651	\
	652	return result;\
	653	} )
	654
	655	// helper macros to create functor objects for associative containers of the given type
	656
	657	#define LESS_THEN_FUNCTOR(TYPE) struct \
	658	{ inline int operator()(const TYPE& x, const TYPE& y ) const { return x < y; } }
	659
	660	#define GREATER_THEN_FUNCTOR(TYPE) struct \
	661	{ inline int operator()(const TYPE& x, const TYPE& y ) const { return x > y; } }
	662
	663	// functor argument should be created using the two above macros
	664	// or passing own class with method "operator()(const TYPE&,cosnt TYPE&)" defined in it
	665
	666	#define WXSTL_MAP( KEY_TYPE, VALUE_TYPE, FUNCTOR ) __DEFINE_MAP( 1 ,KEY_TYPE, VALUE_TYPE, FUNCTOR)
	667	#define WXSTL_MULTIMAP( KEY_TYPE, VALUE_TYPE, FUNCTOR ) __DEFINE_MAP( 0 ,KEY_TYPE, VALUE_TYPE, FUNCTOR)
	668	#define WXSTL_SET( KEY_TYPE, FUNCTOR ) __DEFINE_SET( 1 ,KEY_TYPE, FUNCTOR )
	669	#define WXSTL_MULTISET( KEY_TYPE, FUNCTOR ) __DEFINE_SET( 0 ,KEY_TYPE, FUNCTOR )
	670
	671	#endif