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: wxstlvec.h 28244 2004-07-15 06:27:13Z ABX $
8// Copyright:   (c) Aleskandars Gluchovas
9// Licence:   	wxWindows licence
10/////////////////////////////////////////////////////////////////////////////
11
12#ifndef __WXSTLVEC_G__
13#define __WXSTLVEC_G__
14
15#ifdef new
16#undef new
17#endif
18
19#include <memory.h>
20#include <string.h>  // imports memmove()
21#include <stddef.h>
22#if !defined(__WXMAC__) || defined(__DARWIN__)
23#  include <sys/types.h>
24#endif
25#include <limits.h>
26#include <new>
27
28// the below macro used internally (see actual interface after this macro)
29
30#define __DEFINE_STL_VECTOR_DEEP( vectorClass, Type ) class vectorClass {\
31\
32public:\
33	typedef Type              value_type;\
34	typedef value_type*	      iterator;\
35	typedef const value_type* const_iterator;\
36	typedef iterator		  pointer;\
37	typedef const iterator    const_pointer;\
38	typedef value_type&       reference;\
39	typedef const value_type& const_reference;\
40	typedef size_t            size_type;\
41	typedef ptrdiff_t         difference_type;\
42\
43	typedef iterator       OutputIterator;\
44	typedef const_iterator InputIterator;\
45\
46protected:\
47\
48	inline void PlacementCopy( const_iterator first, const_iterator last, iterator result )\
49	{\
50		while ( first != last ) \
51			new (result++) value_type(*first++);\
52	}\
53\
54	inline void ConstructObjects( iterator first, iterator last, const value_type& pattern )\
55	{\
56		while( first != last ) \
57			new (first++) value_type(pattern);\
58	}\
59\
60	inline void CopyObjects( iterator first, iterator last, iterator result )\
61	{\
62		while( first != last ) \
63			*result++ = *first++;\
64	}\
65\
66	inline void CopyObjectsBack( iterator first, iterator last, iterator result )\
67	{\
68		result += difference_type(last,first);\
69\
70		while( first != last ) \
71			*(--result) = *(--last);\
72	}\
73\
74public:\
75\
76	class reverse_iterator \
77	{\
78		friend class vectorClass;\
79		friend class const_reverse_iterator;\
80\
81	public:\
82		iterator mpPos;\
83\
84	public:\
85\
86		reverse_iterator() {}\
87\
88		reverse_iterator ( iterator pPos )\
89		{\
90			mpPos = pPos;\
91		}\
92	\
93		int operator==( const reverse_iterator& rhs ) const { return (mpPos == rhs.mpPos); }\
94		int operator!=( const reverse_iterator& rhs ) const { return (mpPos != rhs.mpPos); }\
95\
96		inline reverse_iterator( const reverse_iterator& other )\
97		{\
98			mpPos = other.mpPos;\
99		}\
100\
101		inline const reverse_iterator& operator--() \
102		{\
103			--mpPos;\
104			return *this;\
105		}\
106\
107		inline reverse_iterator operator--(int)\
108		{\
109			reverse_iterator tmp = *this;\
110			--mpPos;\
111			return tmp;\
112		}\
113\
114		inline const reverse_iterator & operator++() \
115		{\
116			++mpPos;\
117			return *this;\
118		}\
119\
120		inline reverse_iterator  operator++(int)\
121		{\
122			reverse_iterator tmp = *this;\
123			++mpPos;\
124			return tmp;\
125		}\
126\
127		inline const_reference operator*() const { return *mpPos; }\
128	};\
129\
130\
131	class const_reverse_iterator \
132	{\
133	protected:\
134		iterator mpPos;\
135	public:\
136\
137		const_reverse_iterator() {}\
138\
139		const_reverse_iterator( const iterator pPos )\
140		{\
141			mpPos = pPos;\
142		}\
143	\
144		int operator==( const const_reverse_iterator& rhs ) const { return (mpPos == rhs.mpPos); }\
145		int operator!=( const const_reverse_iterator& rhs ) const { return (mpPos != rhs.mpPos); }\
146\
147		inline const_reverse_iterator( const reverse_iterator& other )\
148		{\
149			mpPos = other.mpPos;\
150		}\
151\
152		inline const const_reverse_iterator& operator--() \
153		{\
154			--mpPos;\
155			return *this;\
156		}\
157\
158		inline const_reverse_iterator operator--(int)\
159		{\
160			const_reverse_iterator tmp = *this;\
161			--mpPos;\
162			return tmp;\
163		}\
164\
165		inline const const_reverse_iterator & operator++() \
166		{\
167			++mpPos;\
168			return *this;\
169		}\
170\
171		inline const_reverse_iterator operator++(int)\
172		{\
173			const_reverse_iterator tmp = *this;\
174			++mpPos;\
175			return tmp;\
176		}\
177\
178		inline const_reference operator*() const { return *mpPos; }\
179	};\
180\
181protected:\
182	\
183	pointer mpStart;\
184	pointer mpEnd;\
185	pointer mpEndOfBuf;\
186\
187protected:\
188\
189	inline void quick_sort(int WXUNUSED(low), int WXUNUSED(hi)) \
190	{\
191	}\
192\
193	inline void DestructRange( iterator first, iterator last )\
194	{\
195		typedef value_type value_type_local;\
196\
197		while ( first != last ) \
198		{\
199			first->value_type_local::~value_type_local();\
200			++first;\
201		}\
202	}\
203\
204	inline iterator DoInsert(iterator position, const value_type& x)\
205	{\
206		if ( mpEnd < mpEndOfBuf )\
207		{\
208			new (mpEnd) value_type(*(mpEnd-1) );\
209	    \
210			CopyObjectsBack( position, mpEnd, position + 1 );\
211	    \
212			*position = x;\
213	    \
214			++mpEnd;\
215	    \
216			return position;\
217		}\
218	    \
219		size_type minBufLen = WXSTL_VECTOR_MIN_BUF_SIZE/sizeof(value_type);\
220	    \
221		size_type doubledSize = size()*2;\
222	    \
223		size_type newLen = ( doubledSize < minBufLen ) ? minBufLen : doubledSize;\
224	    \
225		iterator pNewStart = (iterator)( new char[newLen*sizeof(value_type)] );\
226	    \
227		PlacementCopy( mpStart, position, pNewStart );\
228	    \
229		iterator atPosition = pNewStart + difference_type( position - mpStart );\
230	    \
231		new (atPosition) value_type(x);\
232	    \
233		iterator newPos = atPosition;\
234	    \
235		++atPosition;\
236	    \
237		if ( mpStart ) \
238		{\
239			PlacementCopy( position, mpEnd, atPosition );\
240			DestructRange( mpStart, mpEnd );\
241			delete [](char*)mpStart;\
242		}\
243	    \
244		mpEnd = atPosition + difference_type( mpEnd - position );\
245	    \
246		mpStart    = pNewStart;\
247		mpEndOfBuf = pNewStart + newLen;\
248	    \
249		return newPos;\
250	}\
251\
252public:\
253\
254	inline vectorClass() : mpStart(0), \
255						   mpEnd(0),\
256						   mpEndOfBuf(0)\
257	{}\
258\
259	inline vectorClass( const_iterator first, const_iterator last )\
260		: mpStart(0),\
261		  mpEnd(0),\
262		  mpEndOfBuf(0)\
263		\
264		{ while( first != last ) push_back( *first++ ); }\
265\
266	inline vectorClass( size_type n, const value_type& value = value_type() )\
267		: mpStart(0),\
268		  mpEnd(0),\
269		  mpEndOfBuf(0)\
270		\
271		{ for( size_type i = 0; i != n; ++i ) push_back( value ); }\
272\
273	inline const vectorClass& operator=( const vectorClass& other )\
274	{\
275		if (mpStart) \
276		{\
277			DestructRange( begin(), end() );\
278			delete [](char*)mpStart; \
279		}\
280\
281		size_t newLen = difference_type( other.mpEndOfBuf - other.mpStart );\
282\
283		mpStart = (iterator)( new char[newLen*sizeof(value_type)] );\
284\
285		PlacementCopy( other.begin(), other.end(), mpStart );\
286\
287		mpEnd = mpStart + other.size();\
288\
289		mpEndOfBuf = mpStart + newLen;\
290\
291		return *this;\
292	}\
293\
294	inline vectorClass( const vectorClass& other )\
295		: mpStart(0),\
296		  mpEnd(0),\
297		  mpEndOfBuf(0)\
298	{\
299		this->operator=( other );\
300	}\
301\
302	inline ~vectorClass() \
303	{ \
304		if (mpStart) \
305		{\
306			DestructRange( begin(), end() );\
307			delete [](char*)mpStart; \
308		}\
309	}\
310\
311	inline iterator begin() { return mpStart; }\
312\
313	inline const_iterator begin() const { return mpStart; }\
314\
315	inline iterator end() { return mpEnd; }\
316\
317	inline const_iterator end() const { return mpEnd; }\
318\
319	inline size_type size() const { return (size_type)difference_type(mpEnd-mpStart); }\
320\
321	inline size_type max_size() const { return UINT_MAX/sizeof(value_type); }\
322\
323	inline size_type capacity() const \
324			{ return difference_type(mpEndOfBuf-mpStart)/sizeof(value_type); }\
325\
326	inline int empty() const { return mpStart == mpEnd; }\
327\
328	inline reference operator[](size_type n) { return *(mpStart+n); }\
329\
330	inline const_reference operator[](size_type n) const { return *(mpStart+n); }\
331\
332	inline reference front() { return (*mpStart); }\
333	\
334	inline const_reference front() const { return (*mpStart); }\
335\
336	inline reference back() { return (*(mpEnd-1)); }\
337\
338	inline const_reference back() const { return (*(mpEnd-1)); }\
339\
340	inline void reserve(size_type WXUNUSED(n)) {}\
341\
342	inline void push_back(const value_type& x)\
343	{\
344		if ( mpEnd != mpEndOfBuf ) \
345		{\
346			new (mpEnd) value_type(x);\
347			++mpEnd;\
348		}\
349		else\
350			DoInsert( mpEnd, x );\
351	}\
352\
353	inline iterator insert(iterator position, const value_type& x = value_type())\
354	{\
355		if ( position == mpEnd && mpEnd != mpEndOfBuf )\
356		{\
357			new (mpEnd) value_type(x);\
358			++mpEnd;\
359			return (mpEnd-1);\
360		}\
361		else return DoInsert( position, x );\
362	}\
363\
364	inline void pop_back()\
365	{\
366		DestructRange( mpEnd-1, mpEnd );\
367\
368		--mpEnd;\
369	}\
370\
371	inline void erase(iterator first, iterator last)\
372	{\
373		if ( last == mpEnd )\
374		{\
375			DestructRange( first, last );\
376			mpEnd = first;\
377			return;\
378		}\
379	    \
380		CopyObjects( last, last + difference_type( mpEnd - last ), first );\
381	    \
382		iterator newEnd = mpEnd - difference_type( last - first );\
383		DestructRange( newEnd, mpEnd );\
384	    \
385		mpEnd = newEnd;\
386	}\
387\
388	inline void erase( iterator position )\
389	{\
390		erase( position, position + 1 );\
391	}\
392\
393	inline void sort()\
394	{\
395		if ( size() < 2 ) return;\
396		quick_sort( 0, size()-1 );\
397	}\
398}
399
400/////////////////////////////// shallow-copy container ///////////////////////
401
402#define __DEFINE_STL_VECTOR_SHALLOW( vectorClass, Type ) class vectorClass {\
403\
404public:\
405	typedef Type              value_type;\
406	typedef value_type*	      iterator;\
407	typedef const value_type* const_iterator;\
408	typedef iterator		  pointer;\
409	typedef const iterator    const_pointer;\
410	typedef value_type&       reference;\
411	typedef const value_type& const_reference;\
412	typedef size_t            size_type;\
413	typedef ptrdiff_t         difference_type;\
414\
415	typedef iterator       OutputIterator;\
416	typedef const_iterator InputIterator;\
417\
418protected:\
419\
420	inline void PlacementCopy( const_iterator first, const_iterator last, iterator result )\
421	{\
422		memcpy(result, first, int(difference_type(last-first)*sizeof(value_type)) );\
423	}\
424\
425	inline void ConstructObjects( iterator first, iterator last, const value_type& pattern )\
426	{\
427			if ( sizeof(pattern) == 1 )\
428			\
429				memset( first, int(difference_type(last-first)/sizeof(value_type)), \
430				        int(*((char*)&pattern)) );\
431			else\
432				while( first != last ) \
433					*first++ = pattern;\
434	}\
435\
436	inline void CopyObjects( iterator first, iterator last, iterator result )\
437	{\
438		memcpy(result, first, int(difference_type(last-first)*sizeof(value_type)) );\
439	}\
440\
441	inline void CopyObjectsBack( iterator first, iterator last, iterator result )\
442	{\
443		memmove(result, first, int(difference_type(last-first)*sizeof(value_type)) );\
444	}\
445\
446public:\
447\
448	class reverse_iterator \
449	{\
450		friend class vectorClass;\
451		friend class const_reverse_iterator;\
452\
453	public:\
454		iterator mpPos;\
455\
456	public:\
457\
458		reverse_iterator() {}\
459\
460		reverse_iterator ( iterator pPos )\
461		{\
462			mpPos = pPos;\
463		}\
464	\
465		int operator==( const reverse_iterator& rhs ) const { return (mpPos == rhs.mpPos); }\
466		int operator!=( const reverse_iterator& rhs ) const { return (mpPos != rhs.mpPos); }\
467\
468		inline reverse_iterator( const reverse_iterator& other )\
469		{\
470			mpPos = other.mpPos;\
471		}\
472\
473		inline const reverse_iterator& operator--() \
474		{\
475			--mpPos;\
476			return *this;\
477		}\
478\
479		inline reverse_iterator operator--(int)\
480		{\
481			reverse_iterator tmp = *this;\
482			--mpPos;\
483			return tmp;\
484		}\
485\
486		inline const reverse_iterator & operator++() \
487		{\
488			++mpPos;\
489			return *this;\
490		}\
491\
492		inline reverse_iterator  operator++(int)\
493		{\
494			reverse_iterator tmp = *this;\
495			++mpPos;\
496			return tmp;\
497		}\
498\
499		inline const_reference operator*() const { return *mpPos; }\
500	};\
501\
502\
503	class const_reverse_iterator \
504	{\
505	protected:\
506		iterator mpPos;\
507	public:\
508\
509		const_reverse_iterator() {}\
510\
511		const_reverse_iterator( const iterator pPos )\
512		{\
513			mpPos = pPos;\
514		}\
515	\
516		int operator==( const const_reverse_iterator& rhs ) const { return (mpPos == rhs.mpPos); }\
517		int operator!=( const const_reverse_iterator& rhs ) const { return (mpPos != rhs.mpPos); }\
518\
519		inline const_reverse_iterator( const reverse_iterator& other )\
520		{\
521			mpPos = other.mpPos;\
522		}\
523\
524		inline const const_reverse_iterator& operator--() \
525		{\
526			--mpPos;\
527			return *this;\
528		}\
529\
530		inline const_reverse_iterator operator--(int)\
531		{\
532			const_reverse_iterator tmp = *this;\
533			--mpPos;\
534			return tmp;\
535		}\
536\
537		inline const const_reverse_iterator & operator++() \
538		{\
539			++mpPos;\
540			return *this;\
541		}\
542\
543		inline const_reverse_iterator operator++(int)\
544		{\
545			const_reverse_iterator tmp = *this;\
546			++mpPos;\
547			return tmp;\
548		}\
549\
550		inline const_reference operator*() const { return *mpPos; }\
551	};\
552\
553protected:\
554	\
555	pointer mpStart;\
556	pointer mpEnd;\
557	pointer mpEndOfBuf;\
558\
559protected:\
560\
561	inline void quick_sort(int WXUNUSED(low), int WXUNUSED(hi)) \
562	{\
563	}\
564\
565	inline void DestructRange( iterator WXUNUSED(first), iterator WXUNUSED(last))\
566	{\
567	}\
568\
569	inline iterator DoInsert(iterator position, const value_type& x)\
570	{\
571		if ( mpEnd < mpEndOfBuf )\
572		{\
573			new (mpEnd) value_type(*(mpEnd-1) );\
574	    \
575			CopyObjectsBack( position, mpEnd, position + 1 );\
576	    \
577			*position = x;\
578	    \
579			++mpEnd;\
580	    \
581			return position;\
582		}\
583	    \
584		size_type minBufLen = WXSTL_VECTOR_MIN_BUF_SIZE/sizeof(value_type);\
585	    \
586		size_type doubledSize = size()*2;\
587	    \
588		size_type newLen = ( doubledSize < minBufLen ) ? minBufLen : doubledSize;\
589	    \
590		iterator pNewStart = (iterator)( new char[newLen*sizeof(value_type)] );\
591	    \
592		PlacementCopy( mpStart, position, pNewStart );\
593	    \
594		iterator atPosition = pNewStart + difference_type( position - mpStart );\
595	    \
596		new (atPosition) value_type(x);\
597	    \
598		iterator newPos = atPosition;\
599	    \
600		++atPosition;\
601	    \
602		if ( mpStart ) \
603		{\
604			PlacementCopy( position, mpEnd, atPosition );\
605			DestructRange( mpStart, mpEnd );\
606			delete [](char*)mpStart;\
607		}\
608	    \
609		mpEnd = atPosition + difference_type( mpEnd - position );\
610	    \
611		mpStart    = pNewStart;\
612		mpEndOfBuf = pNewStart + newLen;\
613	    \
614		return newPos;\
615	}\
616\
617public:\
618\
619	inline vectorClass() : mpStart(0), \
620						   mpEnd(0),\
621						   mpEndOfBuf(0)\
622	{}\
623\
624	inline vectorClass( const_iterator first, const_iterator last )\
625		: mpStart(0),\
626		  mpEnd(0),\
627		  mpEndOfBuf(0)\
628		\
629		{ while( first != last ) push_back( *first++ ); }\
630\
631	inline vectorClass( size_type n, const value_type& value = value_type() )\
632		: mpStart(0),\
633		  mpEnd(0),\
634		  mpEndOfBuf(0)\
635		\
636		{ for( size_type i = 0; i != n; ++i ) push_back( value ); }\
637\
638	inline const vectorClass& operator=( const vectorClass& other )\
639	{\
640		if (mpStart) \
641		{\
642			DestructRange( begin(), end() );\
643			delete [](char*)mpStart; \
644		}\
645\
646		size_t newLen = difference_type( other.mpEndOfBuf - other.mpStart );\
647\
648		mpStart = (iterator)( new char[newLen*sizeof(value_type)] );\
649\
650		PlacementCopy( other.begin(), other.end(), mpStart );\
651\
652		mpEnd = mpStart + other.size();\
653\
654		mpEndOfBuf = mpStart + newLen;\
655\
656		return *this;\
657	}\
658\
659	inline vectorClass( const vectorClass& other )\
660		: mpStart(0),\
661		  mpEnd(0),\
662		  mpEndOfBuf(0)\
663	{\
664		this->operator=( other );\
665	}\
666\
667	inline ~vectorClass() \
668	{ \
669		if (mpStart) \
670		{\
671			DestructRange( begin(), end() );\
672			delete [](char*)mpStart; \
673		}\
674	}\
675\
676	inline iterator begin() { return mpStart; }\
677\
678	inline const_iterator begin() const { return mpStart; }\
679\
680	inline iterator end() { return mpEnd; }\
681\
682	inline const_iterator end() const { return mpEnd; }\
683\
684	inline size_type size() const { return (size_type)difference_type(mpEnd-mpStart); }\
685\
686	inline size_type max_size() const { return UINT_MAX/sizeof(value_type); }\
687\
688	inline size_type capacity() const \
689			{ return difference_type(mpEndOfBuf-mpStart)/sizeof(value_type); }\
690\
691	inline int empty() const { return mpStart == mpEnd; }\
692\
693	inline reference operator[](size_type n) { return *(mpStart+n); }\
694\
695	inline const_reference operator[](size_type n) const { return *(mpStart+n); }\
696\
697	inline reference front() { return (*mpStart); }\
698	\
699	inline const_reference front() const { return (*mpStart); }\
700\
701	inline reference back() { return (*(mpEnd-1)); }\
702\
703	inline const_reference back() const { return (*(mpEnd-1)); }\
704\
705	inline void reserve(size_type WXUNUSED(n)) {}\
706\
707	inline void push_back(const value_type& x)\
708	{\
709		if ( mpEnd != mpEndOfBuf ) \
710		{\
711			new (mpEnd) value_type(x);\
712			++mpEnd;\
713		}\
714		else\
715			DoInsert( mpEnd, x );\
716	}\
717\
718	inline iterator insert(iterator position, const value_type& x = value_type())\
719	{\
720		if ( position == mpEnd && mpEnd != mpEndOfBuf )\
721		{\
722			new (mpEnd) value_type(x);\
723			++mpEnd;\
724			return (mpEnd-1);\
725		}\
726		else return DoInsert( position, x );\
727	}\
728\
729	inline void pop_back()\
730	{\
731		DestructRange( mpEnd-1, mpEnd );\
732\
733		--mpEnd;\
734	}\
735\
736	inline void erase(iterator first, iterator last)\
737	{\
738		if ( last == mpEnd )\
739		{\
740			DestructRange( first, last );\
741			mpEnd = first;\
742			return;\
743		}\
744	    \
745		CopyObjects( last, last + difference_type( mpEnd - last ), first );\
746	    \
747		iterator newEnd = mpEnd - difference_type( last - first );\
748		DestructRange( newEnd, mpEnd );\
749	    \
750		mpEnd = newEnd;\
751	}\
752\
753	inline void erase( iterator position )\
754	{\
755		erase( position, position + 1 );\
756	}\
757\
758	inline void sort()\
759	{\
760		if ( size() < 2 ) return;\
761		quick_sort( 0, size()-1 );\
762	}\
763}
764
765
766
767// redefine below symbol to change the default allocation unit of vector content buffer
768#define WXSTL_VECTOR_MIN_BUF_SIZE 64
769
770// defines vector class, where objects are copied
771// using "deep-copy" sematics (i.e. by calling their copy constructors)
772
773#define WXSTL_VECTOR(ELEMENT_CLASS) \
774__DEFINE_STL_VECTOR_DEEP(_WXSTL_VECTOR_##ELEMENT_CLASS, ELEMENT_CLASS)
775
776// defines vector class, where objects are copied
777// using "shallow-copy" sematics (i.e. instead of calling
778// their constructors, memcpy() and memmove() are used to copy their raw data)
779
780
781#define WXSTL_VECTOR_SHALLOW_COPY(ELEMENT_CLASS) __DEFINE_STL_VECTOR_SHALLOW(_WXSTL_VECTORSC_##ELEMENT_CLASS, ELEMENT_CLASS)
782
783#endif
784