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: wxstllst.h 34519 2005-06-02 09:44:45Z ABX $
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/assign-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
33typedef 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{\
41public:\
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\
51protected:\
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     m_Size;\
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\
99public:\
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\
317public:\
318\
319    inline listClass()\
320			: mpFreeListHead( 0 ),\
321			  m_Size(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			  m_Size(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 (m_Size == 0); }\
388\
389	inline size_type size() const { return m_Size; }\
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		++m_Size;\
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		m_Size += other.m_Size;\
445		other.m_Size = 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		m_Size += sz;\
461		other.m_Size -= 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			--m_Size;\
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 ( m_Size < 2 ) return;\
522\
523		iterator from = begin();\
524		iterator other_end = end();\
525		--other_end;\
526\
527		for( size_type i = 0; i != m_Size; ++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
562