[wxWidgets.git] / utils / HelpGen / include / 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__

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