-rw-r--r-- | qmake/include/qtl.h | 321 |
1 files changed, 321 insertions, 0 deletions
diff --git a/qmake/include/qtl.h b/qmake/include/qtl.h new file mode 100644 index 0000000..346cecc --- a/dev/null +++ b/qmake/include/qtl.h | |||
@@ -0,0 +1,321 @@ | |||
1 | /**************************************************************************** | ||
2 | ** $Id$ | ||
3 | ** | ||
4 | ** Definition of Qt template library classes | ||
5 | ** | ||
6 | ** Created : 990128 | ||
7 | ** | ||
8 | ** Copyright (C) 1992-2000 Trolltech AS. All rights reserved. | ||
9 | ** | ||
10 | ** This file is part of the tools module of the Qt GUI Toolkit. | ||
11 | ** | ||
12 | ** This file may be distributed under the terms of the Q Public License | ||
13 | ** as defined by Trolltech AS of Norway and appearing in the file | ||
14 | ** LICENSE.QPL included in the packaging of this file. | ||
15 | ** | ||
16 | ** This file may be distributed and/or modified under the terms of the | ||
17 | ** GNU General Public License version 2 as published by the Free Software | ||
18 | ** Foundation and appearing in the file LICENSE.GPL included in the | ||
19 | ** packaging of this file. | ||
20 | ** | ||
21 | ** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition | ||
22 | ** licenses may use this file in accordance with the Qt Commercial License | ||
23 | ** Agreement provided with the Software. | ||
24 | ** | ||
25 | ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE | ||
26 | ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. | ||
27 | ** | ||
28 | ** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for | ||
29 | ** information about Qt Commercial License Agreements. | ||
30 | ** See http://www.trolltech.com/qpl/ for QPL licensing information. | ||
31 | ** See http://www.trolltech.com/gpl/ for GPL licensing information. | ||
32 | ** | ||
33 | ** Contact info@trolltech.com if any conditions of this licensing are | ||
34 | ** not clear to you. | ||
35 | ** | ||
36 | **********************************************************************/ | ||
37 | |||
38 | #ifndef QTL_H | ||
39 | #define QTL_H | ||
40 | |||
41 | #ifndef QT_H | ||
42 | #include "qglobal.h" | ||
43 | #include "qtextstream.h" | ||
44 | #include "qstring.h" | ||
45 | #endif // QT_H | ||
46 | |||
47 | #ifndef QT_NO_TEXTSTREAM | ||
48 | template <class T> | ||
49 | class QTextOStreamIterator | ||
50 | { | ||
51 | protected: | ||
52 | QTextOStream& stream; | ||
53 | QString separator; | ||
54 | |||
55 | public: | ||
56 | QTextOStreamIterator( QTextOStream& s) : stream( s ) {} | ||
57 | QTextOStreamIterator( QTextOStream& s, const QString& sep ) | ||
58 | : stream( s ), separator( sep ) {} | ||
59 | QTextOStreamIterator<T>& operator= ( const T& x ) { | ||
60 | stream << x; | ||
61 | if ( !separator.isEmpty() ) | ||
62 | stream << separator; | ||
63 | return *this; | ||
64 | } | ||
65 | QTextOStreamIterator<T>& operator*() { return *this; } | ||
66 | QTextOStreamIterator<T>& operator++() { return *this; } | ||
67 | QTextOStreamIterator<T>& operator++(int) { return *this; } | ||
68 | }; | ||
69 | #endif //QT_NO_TEXTSTREAM | ||
70 | |||
71 | template <class InputIterator, class OutputIterator> | ||
72 | inline OutputIterator qCopy( InputIterator _begin, InputIterator _end, | ||
73 | OutputIterator _dest ) | ||
74 | { | ||
75 | while( _begin != _end ) | ||
76 | *_dest++ = *_begin++; | ||
77 | return _dest; | ||
78 | } | ||
79 | |||
80 | template <class BiIterator, class BiOutputIterator> | ||
81 | inline BiOutputIterator qCopyBackward( BiIterator _begin, BiIterator _end, | ||
82 | BiOutputIterator _dest ) | ||
83 | { | ||
84 | while ( _begin != _end ) | ||
85 | *--_dest = *--_end; | ||
86 | return _dest; | ||
87 | } | ||
88 | |||
89 | template <class InputIterator1, class InputIterator2> | ||
90 | inline bool qEqual( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 ) | ||
91 | { | ||
92 | for ( ; first1 != last1; ++first1, ++first2 ) | ||
93 | if ( *first1 != *first2 ) | ||
94 | return FALSE; | ||
95 | return TRUE; | ||
96 | } | ||
97 | |||
98 | template <class ForwardIterator, class T> | ||
99 | inline void qFill( ForwardIterator first, ForwardIterator last, const T& val ) | ||
100 | { | ||
101 | for ( ; first != last; ++first ) | ||
102 | *first = val; | ||
103 | } | ||
104 | |||
105 | #if 0 | ||
106 | template <class BiIterator, class OutputIterator> | ||
107 | inline OutputIterator qReverseCopy( BiIterator _begin, BiIterator _end, | ||
108 | OutputIterator _dest ) | ||
109 | { | ||
110 | while ( _begin != _end ) { | ||
111 | --_end; | ||
112 | *_dest = *_end; | ||
113 | ++_dest; | ||
114 | } | ||
115 | return _dest; | ||
116 | } | ||
117 | #endif | ||
118 | |||
119 | |||
120 | template <class InputIterator, class T> | ||
121 | inline InputIterator qFind( InputIterator first, InputIterator last, | ||
122 | const T& val ) | ||
123 | { | ||
124 | while ( first != last && *first != val ) | ||
125 | ++first; | ||
126 | return first; | ||
127 | } | ||
128 | |||
129 | template <class InputIterator, class T, class Size> | ||
130 | inline void qCount( InputIterator first, InputIterator last, const T& value, | ||
131 | Size& n ) | ||
132 | { | ||
133 | for ( ; first != last; ++first ) | ||
134 | if ( *first == value ) | ||
135 | ++n; | ||
136 | } | ||
137 | |||
138 | template <class T> | ||
139 | inline void qSwap( T& _value1, T& _value2 ) | ||
140 | { | ||
141 | T tmp = _value1; | ||
142 | _value1 = _value2; | ||
143 | _value2 = tmp; | ||
144 | } | ||
145 | |||
146 | |||
147 | template <class InputIterator> | ||
148 | Q_INLINE_TEMPLATES void qBubbleSort( InputIterator b, InputIterator e ) | ||
149 | { | ||
150 | // Goto last element; | ||
151 | InputIterator last = e; | ||
152 | --last; | ||
153 | // only one element or no elements ? | ||
154 | if ( last == b ) | ||
155 | return; | ||
156 | |||
157 | // So we have at least two elements in here | ||
158 | while( b != last ) { | ||
159 | bool swapped = FALSE; | ||
160 | InputIterator swap_pos = b; | ||
161 | InputIterator x = e; | ||
162 | InputIterator y = x; | ||
163 | y--; | ||
164 | do { | ||
165 | --x; | ||
166 | --y; | ||
167 | if ( *x < *y ) { | ||
168 | swapped = TRUE; | ||
169 | qSwap( *x, *y ); | ||
170 | swap_pos = y; | ||
171 | } | ||
172 | } while( y != b ); | ||
173 | if ( !swapped ) | ||
174 | return; | ||
175 | b = swap_pos; | ||
176 | b++; | ||
177 | } | ||
178 | } | ||
179 | |||
180 | |||
181 | template <class Container> | ||
182 | inline void qBubbleSort( Container &c ) | ||
183 | { | ||
184 | qBubbleSort( c.begin(), c.end() ); | ||
185 | } | ||
186 | |||
187 | |||
188 | template <class Value> | ||
189 | Q_INLINE_TEMPLATES void qHeapSortPushDown( Value* heap, int first, int last ) | ||
190 | { | ||
191 | int r = first; | ||
192 | while ( r <= last / 2 ) { | ||
193 | if ( last == 2 * r ) { | ||
194 | // node r has only one child | ||
195 | if ( heap[2 * r] < heap[r] ) | ||
196 | qSwap( heap[r], heap[2 * r] ); | ||
197 | r = last; | ||
198 | } else { | ||
199 | // node r has two children | ||
200 | if ( heap[2 * r] < heap[r] && !(heap[2 * r + 1] < heap[2 * r]) ) { | ||
201 | // swap with left child | ||
202 | qSwap( heap[r], heap[2 * r] ); | ||
203 | r *= 2; | ||
204 | } else if ( heap[2 * r + 1] < heap[r] | ||
205 | && heap[2 * r + 1] < heap[2 * r] ) { | ||
206 | // swap with right child | ||
207 | qSwap( heap[r], heap[2 * r + 1] ); | ||
208 | r = 2 * r + 1; | ||
209 | } else { | ||
210 | r = last; | ||
211 | } | ||
212 | } | ||
213 | } | ||
214 | } | ||
215 | |||
216 | |||
217 | template <class InputIterator, class Value> | ||
218 | Q_INLINE_TEMPLATES void qHeapSortHelper( InputIterator b, InputIterator e, Value, uint n ) | ||
219 | { | ||
220 | // Create the heap | ||
221 | InputIterator insert = b; | ||
222 | Value* realheap = new Value[n]; | ||
223 | // Wow, what a fake. But I want the heap to be indexed as 1...n | ||
224 | Value* heap = realheap - 1; | ||
225 | int size = 0; | ||
226 | for( ; insert != e; ++insert ) { | ||
227 | heap[++size] = *insert; | ||
228 | int i = size; | ||
229 | while( i > 1 && heap[i] < heap[i / 2] ) { | ||
230 | qSwap( heap[i], heap[i / 2] ); | ||
231 | i /= 2; | ||
232 | } | ||
233 | } | ||
234 | |||
235 | // Now do the sorting | ||
236 | for( uint i = n; i > 0; i-- ) { | ||
237 | *b++ = heap[1]; | ||
238 | if ( i > 1 ) { | ||
239 | heap[1] = heap[i]; | ||
240 | qHeapSortPushDown( heap, 1, (int)i - 1 ); | ||
241 | } | ||
242 | } | ||
243 | |||
244 | delete[] realheap; | ||
245 | } | ||
246 | |||
247 | |||
248 | template <class InputIterator> | ||
249 | Q_INLINE_TEMPLATES void qHeapSort( InputIterator b, InputIterator e ) | ||
250 | { | ||
251 | // Empty ? | ||
252 | if ( b == e ) | ||
253 | return; | ||
254 | |||
255 | // How many entries have to be sorted ? | ||
256 | InputIterator it = b; | ||
257 | uint n = 0; | ||
258 | while ( it != e ) { | ||
259 | ++n; | ||
260 | ++it; | ||
261 | } | ||
262 | |||
263 | // The second last parameter is a hack to retrieve the value type | ||
264 | // Do the real sorting here | ||
265 | qHeapSortHelper( b, e, *b, n ); | ||
266 | } | ||
267 | |||
268 | |||
269 | template <class Container> | ||
270 | Q_INLINE_TEMPLATES void qHeapSort( Container &c ) | ||
271 | { | ||
272 | if ( c.begin() == c.end() ) | ||
273 | return; | ||
274 | |||
275 | // The second last parameter is a hack to retrieve the value type | ||
276 | // Do the real sorting here | ||
277 | qHeapSortHelper( c.begin(), c.end(), *(c.begin()), (uint)c.count() ); | ||
278 | } | ||
279 | |||
280 | template <class Container> | ||
281 | class QBackInsertIterator | ||
282 | { | ||
283 | public: | ||
284 | Q_EXPLICIT QBackInsertIterator( Container &c ) | ||
285 | : container( &c ) | ||
286 | { | ||
287 | } | ||
288 | |||
289 | QBackInsertIterator<Container>& | ||
290 | operator=( const Q_TYPENAME Container::value_type &value ) | ||
291 | { | ||
292 | container->push_back( value ); | ||
293 | return *this; | ||
294 | } | ||
295 | |||
296 | QBackInsertIterator<Container>& operator*() | ||
297 | { | ||
298 | return *this; | ||
299 | } | ||
300 | |||
301 | QBackInsertIterator<Container>& operator++() | ||
302 | { | ||
303 | return *this; | ||
304 | } | ||
305 | |||
306 | QBackInsertIterator<Container>& operator++(int) | ||
307 | { | ||
308 | return *this; | ||
309 | } | ||
310 | |||
311 | protected: | ||
312 | Container *container; | ||
313 | }; | ||
314 | |||
315 | template <class Container> | ||
316 | inline QBackInsertIterator<Container> qBackInserter( Container &c ) | ||
317 | { | ||
318 | return QBackInsertIterator<Container>( c ); | ||
319 | } | ||
320 | |||
321 | #endif | ||