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