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