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