]> git.saurik.com Git - wxWidgets.git/blob - utils/HelpGen/src/wxstlac.h
Deprecated lib tweaks
[wxWidgets.git] / utils / HelpGen / src / wxstlac.h
1 /////////////////////////////////////////////////////////////////////////////
2 // Name: No names yet.
3 // Purpose: Contrib. demo
4 // Author: Aleksandras Gluchovas
5 // Modified by:
6 // Created: 27/09/98
7 // RCS-ID: $Id$
8 // Copyright: (c) Aleskandars Gluchovas
9 // Licence: wxWindows licence
10 /////////////////////////////////////////////////////////////////////////////
11
12 #ifndef __WXSTLAC_G__
13 #define __WXSTLAC_G__
14
15 #ifdef new
16 #undef new
17 #endif
18
19 #include <stddef.h>
20 #if !defined(__WXMAC__) || defined(__DARWIN__)
21 # include <sys/types.h>
22 #endif
23 #include <memory.h>
24 #include <limits.h>
25 #include <new.h>
26
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, \
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:\
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 \
75 protected:\
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 \
97 public:\
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 \
174 protected:\
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 \
279 public:\
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 \
406 public:\
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
604 #define __DEFINE_MAP(ARG_IS_UNIQUE, KEY_TYPE, VAL_TYPE, FUNCTOR ) \
605 __DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
606 FUNCTOR,\
607 __WXSTLMAP_##KEY_TYPE##VAL_TYPE##ARG_IS_UNIQUE, \
608 struct key_value_pair { KEY_TYPE first ; \
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 } , \
614 KEY_TYPE,\
615 VAL_TYPE,\
616 mData.first, mData.second, x.first, x.second, \
617 struct insert_result_iterator\
618 {\
619 iterator first;\
620 int second;\
621 };\
622 inline 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
632 #define __DEFINE_SET(ARG_IS_UNIQUE, KEY_TYPE, FUNCTOR ) \
633 __DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
634 FUNCTOR,\
635 __WXSTLSET_##TYPE##ARG_IS_UNIQUE, \
636 KEY_TYPE,\
637 KEY_TYPE,\
638 KEY_TYPE,\
639 mData, mData, x, x, \
640 struct insert_result_iterator\
641 {\
642 iterator first;\
643 int second;\
644 };\
645 inline 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