]> 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
wxCocoa build fix. Use XPM everywhere.
[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>
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//
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\
3f378995 86public:\
cecfc5e7 87 typedef tree_node* node_ref_type;\
3f378995 88protected:\
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\
99public:\
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\
112 if ( pNode->mpParent )\
113 {\
114 if ( pNode == pNode->mpParent->mpLeft )\
115\
116 return pNode->mpParent;\
117\
118 pNode = pNode->mpParent;\
119\
120 node_ref_type prevNode = pNode;\
121 pNode = pNode->mpParent;\
122\
123 while(pNode)\
124 {\
125 if ( pNode->mpRight &&\
126 pNode->mpRight != prevNode\
127 ) return pNode;\
128\
129 prevNode = pNode;\
130 pNode= pNode->mpParent;\
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\
150 if ( pNode->mpParent )\
151 {\
152 if ( pNode == pNode->mpParent->mpRight )\
153 return pNode->mpParent;\
154\
155 pNode = pNode->mpParent;\
156\
157 node_ref_type prevNode = pNode;\
158 pNode = pNode->mpParent;\
159\
160 while(pNode)\
161 {\
162 if ( pNode->mpLeft &&\
163 pNode->mpLeft != prevNode\
164 ) return pNode;\
165\
166 prevNode = pNode;\
167 pNode= pNode->mpParent;\
168 }\
169\
170 return 0;\
171 }\
172 else \
173 return 0;\
174 }\
175\
176protected:\
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\
236 pNewNode->mpParent = \
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 \
258 pNewNode->mpParent = pParent;\
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\
281public:\
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\
408public:\
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 \
549 if ( pX ) pX->mpParent = pY->mpParent;\
550 \
551 if (pY->mpParent)\
552 \
553 if (pY == pY->mpParent->mpLeft )\
554 \
555 pY->mpParent->mpLeft = pX;\
556 else\
557 pY->mpParent->mpRight = pX;\
558 else\
559 mpRoot = pX;\
560 \
561 node_ref_type toRemove = 0;\
562 \
563 if (pY != pZ) {\
564 \
565 pY->mpLeft = pZ->mpLeft;\
566 \
567 if (pY->mpLeft) pY->mpLeft->mpParent = pY;\
568 \
569 pY->mpRight = pZ->mpRight;\
570 \
571 if ( pY->mpRight ) \
572 \
573 pY->mpRight->mpParent = pY;\
574 \
575 pY->mpParent = pZ->mpParent;\
576 \
577 if (pZ->mpParent)\
578 \
579 if (pZ == pZ->mpParent->mpLeft)\
580 \
581 pZ->mpParent->mpLeft = pY;\
582 else\
583 pZ->mpParent->mpRight = pY;\
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 ) \
607__DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
cecfc5e7
VZ		 608FUNCTOR,\
609__WXSTLMAP_##KEY_TYPE##VAL_TYPE##ARG_IS_UNIQUE, \
610struct 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		 616KEY_TYPE,\
617VAL_TYPE,\
618mData.first, mData.second, x.first, x.second, \
619struct insert_result_iterator\
620{\
621 iterator first;\
622 int second;\
623};\
624inline 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 ) \
635__DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
cecfc5e7
VZ		 636FUNCTOR,\
637__WXSTLSET_##TYPE##ARG_IS_UNIQUE, \
638KEY_TYPE,\
639KEY_TYPE,\
640KEY_TYPE,\
641mData, mData, x, x, \
642struct insert_result_iterator\
643{\
644 iterator first;\
645 int second;\
646};\
647inline 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
665// functor argument should be created using the two above macros
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
wxWidgets (Impactor)