]> git.saurik.com Git - wxWidgets.git/blame - utils/HelpGen/src/wxstlac.h
projects / wxWidgets.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
added url of Fink Unix to Mac OS X porting instructions
[wxWidgets.git] / utils / HelpGen / src / wxstlac.h
CommitLineData
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
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>
24#include <limits.h>
25#include <new.h>
26
cecfc5e7
VZ		 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, \
47FUNCTOR,\
48ASSOC_CONT_CLASS_NAME, \
49ARG_VALUE_TYPE, \
50ARG_KEY_TYPE, \
51ARG_ACTUAL_VALUE_TYPE, \
52_KEY_NAME, \
53_VALUE_NAME, \
54_X_KEY_NAME, \
55_X_VALUE_NAME, \
56_INSERT_METHOD_DEFINITION \
57) class \
58ASSOC_CONT_CLASS_NAME\
59{\
60protected:\
61\
62public:\
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\
75protected:\
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\
97public:\
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\
174protected:\
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\
279public:\
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\
406public:\
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
ad053960
GD		 604#define __DEFINE_MAP(ARG_IS_UNIQUE, KEY_TYPE, VAL_TYPE, FUNCTOR ) \
605__DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
cecfc5e7
VZ		 606FUNCTOR,\
607__WXSTLMAP_##KEY_TYPE##VAL_TYPE##ARG_IS_UNIQUE, \
608struct key_value_pair { KEY_TYPE first ; \
ad053960
GD		 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 } , \
cecfc5e7
VZ		 614KEY_TYPE,\
615VAL_TYPE,\
616mData.first, mData.second, x.first, x.second, \
617struct insert_result_iterator\
618{\
619 iterator first;\
620 int second;\
621};\
622inline 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
ad053960
GD		 632#define __DEFINE_SET(ARG_IS_UNIQUE, KEY_TYPE, FUNCTOR ) \
633__DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
cecfc5e7
VZ		 634FUNCTOR,\
635__WXSTLSET_##TYPE##ARG_IS_UNIQUE, \
636KEY_TYPE,\
637KEY_TYPE,\
638KEY_TYPE,\
639mData, mData, x, x, \
640struct insert_result_iterator\
641{\
642 iterator first;\
643 int second;\
644};\
645inline 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
wxWidgets (Impactor)