]> git.saurik.com Git - wxWidgets.git/blob - utils/HelpGen/src/wxstllst.h
Deprecated lib tweaks
[wxWidgets.git] / utils / HelpGen / src / wxstllst.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 __WXSTLLST_G__
13 #define __WXSTLLST_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 // VERSION:: 0.2 (copy-constructor/adign-op added)
28
29 // FOR NOW:: class-member operators "new" and "delete"
30 // are ignored by list class, memory allocated
31 // and freed using global operators
32
33 typedef int Type;
34
35
36 // the below macro used internally (see actual interface after this macro)
37
38 #define __DEFINE_STL_LIST(listClass,Type) class \
39 listClass \
40 {\
41 public:\
42 \
43 typedef Type value_type;\
44 typedef value_type* pointer;\
45 typedef const value_type* const_pointer;\
46 typedef value_type& reference;\
47 typedef const value_type& const_reference;\
48 typedef size_t size_type;\
49 typedef ptrdiff_t difference_type;\
50 \
51 protected:\
52 struct list_node\
53 {\
54 list_node* mpNext;\
55 list_node* mpPrev;\
56 value_type mData;\
57 };\
58 \
59 typedef list_node* node_ref_type;\
60 \
61 node_ref_type mpFreeListHead;\
62 node_ref_type mpTerminator;\
63 size_type mSize;\
64 \
65 inline node_ref_type AllocNode() \
66 { \
67 if ( mpFreeListHead ) \
68 {\
69 node_ref_type pFreeNode = mpFreeListHead;\
70 mpFreeListHead = mpFreeListHead->mpPrev;\
71 \
72 return pFreeNode;\
73 }\
74 else\
75 {\
76 char* pHeapBlock = new char[sizeof(list_node)];\
77 \
78 return (node_ref_type)pHeapBlock;\
79 }\
80 }\
81 \
82 inline void DestroyFreeList()\
83 {\
84 while ( mpFreeListHead )\
85 {\
86 node_ref_type tmp = mpFreeListHead;\
87 mpFreeListHead = mpFreeListHead->mpPrev;\
88 \
89 delete [](char*)tmp;\
90 }\
91 }\
92 \
93 inline void RecycleNode( node_ref_type pNode ) \
94 {\
95 pNode->mpPrev = mpFreeListHead;\
96 mpFreeListHead = pNode;\
97 }\
98 \
99 public:\
100 \
101 class iterator \
102 {\
103 public:\
104 node_ref_type mpNode;\
105 friend class listClass;\
106 friend class const_iterator;\
107 friend class const_reverse_iterator;\
108 \
109 protected:\
110 iterator( node_ref_type pNode )\
111 {\
112 mpNode = pNode;\
113 }\
114 \
115 public:\
116 iterator() {}\
117 int operator==( const iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
118 int operator!=( const iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
119 \
120 inline iterator( const iterator& other )\
121 {\
122 mpNode = other.mpNode;\
123 }\
124 \
125 inline const iterator& operator--() \
126 {\
127 mpNode = mpNode->mpPrev;\
128 return *this;\
129 }\
130 \
131 inline iterator operator--(int)\
132 {\
133 iterator tmp = *this;\
134 mpNode = mpNode->mpPrev;\
135 return tmp;\
136 }\
137 \
138 inline const iterator& operator++() \
139 {\
140 mpNode = mpNode->mpNext;\
141 return *this;\
142 }\
143 \
144 inline iterator operator++(int)\
145 {\
146 iterator tmp = *this;\
147 mpNode = mpNode->mpNext;\
148 return tmp;\
149 }\
150 \
151 inline reference operator*() const { return mpNode->mData; }\
152 };\
153 \
154 \
155 class const_iterator \
156 {\
157 protected:\
158 node_ref_type mpNode;\
159 friend class listClass;\
160 \
161 protected:\
162 const_iterator( node_ref_type pNode )\
163 {\
164 mpNode = pNode;\
165 }\
166 \
167 public:\
168 \
169 const_iterator() {}\
170 int operator==( const const_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
171 int operator!=( const const_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
172 \
173 \
174 inline const_iterator( const iterator& other )\
175 {\
176 mpNode = other.mpNode;\
177 }\
178 \
179 inline const const_iterator& operator--() \
180 {\
181 mpNode = mpNode->mpPrev;\
182 return *this;\
183 }\
184 \
185 inline const_iterator operator--(int)\
186 {\
187 const_iterator tmp = *this;\
188 mpNode = mpNode->mpPrev;\
189 return tmp;\
190 }\
191 \
192 inline const const_iterator& operator++() \
193 {\
194 mpNode = mpNode->mpNext;\
195 return *this;\
196 }\
197 \
198 inline const_iterator operator++(int)\
199 {\
200 const_iterator tmp = *this;\
201 mpNode = mpNode->mpNext;\
202 return tmp;\
203 }\
204 \
205 inline const_reference operator*() const { return mpNode->mData; }\
206 };\
207 \
208 typedef iterator OutputIterator;\
209 typedef const_iterator InputIterator;\
210 \
211 class reverse_iterator \
212 {\
213 public:\
214 node_ref_type mpNode;\
215 friend class listClass;\
216 friend class const_reverse_iterator;\
217 \
218 protected:\
219 reverse_iterator ( node_ref_type pNode )\
220 {\
221 mpNode = pNode;\
222 }\
223 \
224 public:\
225 \
226 reverse_iterator() {}\
227 int operator==( const reverse_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
228 int operator!=( const reverse_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
229 \
230 inline reverse_iterator( const reverse_iterator& other )\
231 {\
232 mpNode = other.mpNode;\
233 }\
234 \
235 inline const reverse_iterator& operator--() \
236 {\
237 mpNode = mpNode->mpNext;\
238 return *this;\
239 }\
240 \
241 inline reverse_iterator operator--(int)\
242 {\
243 reverse_iterator tmp = *this;\
244 mpNode = mpNode->mpPrev;\
245 return tmp;\
246 }\
247 \
248 inline const reverse_iterator & operator++() \
249 {\
250 mpNode = mpNode->mpNext;\
251 return *this;\
252 }\
253 \
254 inline reverse_iterator operator++(int)\
255 {\
256 reverse_iterator tmp = *this;\
257 mpNode = mpNode->mpPrev;\
258 return tmp;\
259 }\
260 \
261 inline const_reference operator*() const { return mpNode->mData; }\
262 };\
263 \
264 \
265 class const_reverse_iterator \
266 {\
267 protected:\
268 node_ref_type mpNode;\
269 friend class listClass;\
270 \
271 protected:\
272 const_reverse_iterator( node_ref_type pNode )\
273 {\
274 mpNode = pNode;\
275 }\
276 \
277 public:\
278 \
279 const_reverse_iterator() {}\
280 int operator==( const const_reverse_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
281 int operator!=( const const_reverse_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
282 \
283 inline const_reverse_iterator( const reverse_iterator& other )\
284 {\
285 mpNode = other.mpNode;\
286 }\
287 \
288 inline const const_reverse_iterator& operator--() \
289 {\
290 mpNode = mpNode->mpNext;\
291 return *this;\
292 }\
293 \
294 inline const_reverse_iterator operator--(int)\
295 {\
296 const_reverse_iterator tmp = *this;\
297 mpNode = mpNode->mpNext;\
298 return tmp;\
299 }\
300 \
301 inline const const_reverse_iterator& operator++() \
302 {\
303 mpNode = mpNode->mpPrev;\
304 return *this;\
305 }\
306 \
307 inline const_reverse_iterator operator++(int)\
308 {\
309 const_reverse_iterator tmp = *this;\
310 mpNode = mpNode->mpPrev;\
311 return tmp;\
312 }\
313 \
314 inline const_reference operator*() const { return mpNode->mData; }\
315 };\
316 \
317 public:\
318 \
319 inline listClass()\
320 : mpFreeListHead( 0 ),\
321 mSize(0)\
322 {\
323 mpTerminator = AllocNode();\
324 mpTerminator->mpPrev = mpTerminator->mpNext = mpTerminator;\
325 }\
326 \
327 listClass( const listClass& other )\
328 {\
329 mpTerminator = AllocNode();\
330 mpTerminator->mpPrev = mpTerminator->mpNext = mpTerminator;\
331 \
332 for( listClass::const_iterator i = other.begin(); i != other.end(); ++i )\
333 \
334 push_back( (*i) );\
335 }\
336 \
337 inline const listClass& operator=( const listClass& rhs ) \
338 {\
339 erase( begin(), end() );\
340 \
341 for( listClass::const_iterator i = rhs.begin(); i != rhs.end(); ++i )\
342 \
343 push_back( (*i) );\
344 \
345 return *this;\
346 }\
347 \
348 inline listClass(const_iterator first, const_iterator last)\
349 : mpFreeListHead( 0 ),\
350 mSize(0)\
351 \
352 { while( first != last ) push_back( *first++ ); }\
353 \
354 inline listClass( size_type n, const value_type& value = value_type() )\
355 \
356 { for( size_t i = 0; i != n; ++n ) push_back( value ); }\
357 \
358 inline ~listClass() \
359 { \
360 erase( begin(), end() ); \
361 \
362 RecycleNode( mpTerminator );\
363 DestroyFreeList();\
364 }\
365 \
366 inline iterator begin() { return iterator(mpTerminator->mpNext); }\
367 \
368 inline const_iterator begin() const \
369 { return const_iterator(mpTerminator->mpNext); }\
370 \
371 inline iterator end() { return iterator(mpTerminator); }\
372 \
373 inline const_iterator end() const { return const_iterator(mpTerminator); }\
374 \
375 inline reverse_iterator rbegin() \
376 { return reverse_iterator(mpTerminator->mpPrev); }\
377 \
378 inline reverse_iterator rend() \
379 { return reverse_iterator(mpTerminator); }\
380 \
381 inline const_reverse_iterator rbegin() const\
382 { return const_reverse_iterator(mpTerminator->mpPrev); }\
383 \
384 inline const_reverse_iterator rend() const\
385 { return const_reverse_iterator(mpTerminator); }\
386 \
387 inline int empty() const { return (mSize == 0); }\
388 \
389 inline size_type size() const { return mSize; }\
390 \
391 inline size_type max_size() const { return UINT_MAX/sizeof(list_node); }\
392 \
393 inline reference front() { return mpTerminator->mData; }\
394 \
395 inline const_reference front() const { return mpTerminator->mData; }\
396 \
397 inline reference back() { return mpTerminator->mpPrev->mData; }\
398 \
399 inline const_reference back() const { return mpTerminator->mpPrev->mData; }\
400 \
401 inline void push_front(const value_type& x) { insert( begin(), x ); }\
402 \
403 inline void push_back(const value_type& x) { insert( end(), x ); }\
404 \
405 iterator insert(iterator position, const value_type& x = value_type())\
406 {\
407 node_ref_type pNew = AllocNode();\
408 \
409 node_ref_type pos = *((node_ref_type*)&position);\
410 \
411 pNew->mpNext = pos;\
412 pNew->mpPrev = pos->mpPrev;\
413 pos->mpPrev->mpNext = pNew;\
414 pos->mpPrev = pNew;\
415 \
416 new (&pNew->mData) value_type(x);\
417 \
418 ++mSize;\
419 \
420 return iterator(pNew);\
421 }\
422 \
423 inline void insert(iterator position, const_iterator first, const_iterator last )\
424 {\
425 while( first != last ) insert( position, *first++ );\
426 }\
427 \
428 inline void splice( iterator position, listClass& other )\
429 {\
430 if ( other.begin() == other.end() ) return;\
431 \
432 node_ref_type pTill = other.mpTerminator->mpPrev;\
433 node_ref_type pFrom = other.begin().mpNode;\
434 \
435 mpTerminator->mpPrev->mpNext = pFrom;\
436 pFrom->mpPrev = mpTerminator->mpPrev->mpNext;\
437 \
438 pTill->mpNext = mpTerminator;\
439 mpTerminator->mpPrev = pTill;\
440 \
441 other.mpTerminator->mpNext = \
442 other.mpTerminator->mpPrev = other.mpTerminator;\
443 \
444 mSize += other.mSize;\
445 other.mSize = 0;\
446 }\
447 \
448 inline void splice( iterator position, listClass& other, iterator first, iterator last )\
449 {\
450 if ( first == last ) return;\
451 \
452 size_type sz = 0;\
453 iterator tmp = first;\
454 while( tmp != last ) \
455 {\
456 ++tmp;\
457 ++sz;\
458 }\
459 \
460 mSize += sz;\
461 other.mSize -= sz;\
462 \
463 node_ref_type pPos = position.mpNode;\
464 node_ref_type pFirst = first.mpNode;\
465 node_ref_type pLast = last.mpNode;\
466 node_ref_type pTill = last.mpNode->mpPrev;\
467 \
468 pPos->mpPrev->mpNext = pFirst;\
469 pPos->mpPrev = pTill;\
470 \
471 pFirst->mpPrev->mpNext = last.mpNode;\
472 pLast->mpPrev = pTill;\
473 \
474 pFirst->mpPrev = pPos->mpPrev;\
475 pTill->mpNext = pPos;\
476 }\
477 \
478 inline void pop_front() { erase( begin() ); }\
479 inline void pop_back() { erase( --end() ); }\
480 \
481 inline void erase(iterator position)\
482 {\
483 erase( position, ++position );\
484 }\
485 \
486 inline void erase(iterator first, iterator last)\
487 {\
488 node_ref_type firstNode = *((node_ref_type*)&first);\
489 node_ref_type lastNode = *((node_ref_type*)&last);\
490 \
491 firstNode->mpPrev->mpNext = lastNode;\
492 lastNode->mpPrev = firstNode->mpPrev;\
493 \
494 while( firstNode != lastNode )\
495 {\
496 node_ref_type next = firstNode->mpNext;\
497 \
498 typedef value_type value_type_local;\
499 firstNode->mData.value_type_local::~value_type_local();\
500 \
501 RecycleNode( firstNode );\
502 \
503 firstNode = next;\
504 \
505 --mSize;\
506 }\
507 }\
508 \
509 inline void remove(const value_type& value)\
510 {\
511 for( iterator i = begin(); i != end(); ++i )\
512 \
513 if ( (*i) == value ) \
514 {\
515 erase( i ); break;\
516 }\
517 }\
518 \
519 void sort()\
520 {\
521 if ( mSize < 2 ) return;\
522 \
523 iterator from = begin();\
524 iterator other_end = end();\
525 --other_end;\
526 \
527 for( size_type i = 0; i != mSize; ++i )\
528 {\
529 size_type nSwaps = 0;\
530 \
531 iterator next = begin();\
532 ++next;\
533 \
534 for( iterator j = begin(); j != other_end; ++j )\
535 {\
536 \
537 if ( (*next) < (*j) )\
538 {\
539 value_type tmp = (*j);\
540 (*j) = (*next);\
541 (*next) = tmp;\
542 \
543 ++nSwaps;\
544 }\
545 \
546 ++next;\
547 }\
548 \
549 if ( !nSwaps) break;\
550 \
551 --other_end;\
552 }\
553 }\
554 }
555
556 // defines list class with the given element type
557 #define WXSTL_LIST(ELEMENT_CLASS) __DEFINE_STL_LIST(\
558 \
559 _WXSTL_LIST_##ELEMENT_CLASS, ELEMENT_CLASS )
560
561 #endif