|
1 /**************************************************************************** |
|
2 ** |
|
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 #ifndef QTL_H |
|
38 #define QTL_H |
|
39 |
|
40 #ifndef QT_H |
|
41 #include "qtextstream.h" |
|
42 #include "qstring.h" |
|
43 #endif // QT_H |
|
44 |
|
45 #ifndef QT_NO_TEXTSTREAM |
|
46 template <class T> |
|
47 class QTextOStreamIterator |
|
48 { |
|
49 protected: |
|
50 QTextOStream& stream; |
|
51 QString separator; |
|
52 |
|
53 public: |
|
54 QTextOStreamIterator( QTextOStream& s) : stream( s ) {} |
|
55 QTextOStreamIterator( QTextOStream& s, const QString& sep ) |
|
56 : stream( s ), separator( sep ) {} |
|
57 QTextOStreamIterator<T>& operator= ( const T& x ) { |
|
58 stream << x; |
|
59 if ( !separator.isEmpty() ) |
|
60 stream << separator; |
|
61 return *this; |
|
62 } |
|
63 QTextOStreamIterator<T>& operator*() { return *this; } |
|
64 QTextOStreamIterator<T>& operator++() { return *this; } |
|
65 QTextOStreamIterator<T>& operator++(int) { return *this; } |
|
66 }; |
|
67 #endif //QT_NO_TEXTSTREAM |
|
68 |
|
69 template <class InputIterator, class OutputIterator> |
|
70 inline OutputIterator qCopy( InputIterator _begin, InputIterator _end, |
|
71 OutputIterator _dest ) |
|
72 { |
|
73 while( _begin != _end ) |
|
74 *_dest++ = *_begin++; |
|
75 return _dest; |
|
76 } |
|
77 |
|
78 |
|
79 template <class T> |
|
80 inline void qSwap( T& _value1, T& _value2 ) |
|
81 { |
|
82 T tmp = _value1; |
|
83 _value1 = _value2; |
|
84 _value2 = tmp; |
|
85 } |
|
86 |
|
87 |
|
88 template <class InputIterator> |
|
89 inline void qBubbleSort( InputIterator b, InputIterator e ) |
|
90 { |
|
91 // Goto last element; |
|
92 InputIterator last = e; |
|
93 --last; |
|
94 // only one element or no elements ? |
|
95 if ( last == b ) |
|
96 return; |
|
97 |
|
98 // So we have at least two elements in here |
|
99 while( b != last ) { |
|
100 bool swapped = FALSE; |
|
101 InputIterator swap_pos = b; |
|
102 InputIterator x = e; |
|
103 InputIterator y = x; |
|
104 y--; |
|
105 do { |
|
106 --x; |
|
107 --y; |
|
108 if ( *x < *y ) { |
|
109 swapped = TRUE; |
|
110 qSwap( *x, *y ); |
|
111 swap_pos = y; |
|
112 } |
|
113 } while( y != b ); |
|
114 if ( !swapped ) |
|
115 return; |
|
116 b = swap_pos; |
|
117 b++; |
|
118 } |
|
119 } |
|
120 |
|
121 |
|
122 template <class Container> |
|
123 inline void qBubbleSort( Container &c ) |
|
124 { |
|
125 qBubbleSort( c.begin(), c.end() ); |
|
126 } |
|
127 |
|
128 |
|
129 template <class Value> |
|
130 inline void qHeapSortPushDown( Value* heap, int first, int last ) |
|
131 { |
|
132 int r = first; |
|
133 while( r <= last/2 ) { |
|
134 // Node r has only one child ? |
|
135 if ( last == 2*r ) { |
|
136 // Need for swapping ? |
|
137 if ( heap[r] > heap[ 2*r ] ) |
|
138 qSwap( heap[r], heap[ 2*r ] ); |
|
139 // That's it ... |
|
140 r = last; |
|
141 } else { // Node has two children |
|
142 if ( heap[r] > heap[ 2*r ] && heap[ 2*r ] <= heap[ 2*r+1 ] ) { |
|
143 // Swap with left child |
|
144 qSwap( heap[r], heap[ 2*r ] ); |
|
145 r *= 2; |
|
146 } else if ( heap[r] > heap[ 2*r+1 ] && |
|
147 heap[ 2*r+1 ] < heap[ 2*r ] ) { |
|
148 // Swap with right child |
|
149 qSwap( heap[r], heap[ 2*r+1 ] ); |
|
150 r = 2*r+1; |
|
151 } else { |
|
152 // We are done |
|
153 r = last; |
|
154 } |
|
155 } |
|
156 } |
|
157 } |
|
158 |
|
159 |
|
160 template <class InputIterator, class Value> |
|
161 inline void qHeapSortHelper( InputIterator b, InputIterator e, Value, uint n ) |
|
162 { |
|
163 // Create the heap |
|
164 InputIterator insert = b; |
|
165 Value* realheap = new Value[ n ]; |
|
166 // Wow, what a fake. But I want the heap to be indexed as 1...n |
|
167 Value* heap = realheap - 1; |
|
168 int size = 0; |
|
169 for( ; insert != e; ++insert ) { |
|
170 heap[++size] = *insert; |
|
171 int i = size; |
|
172 while( i > 1 && heap[i] < heap[ i / 2 ] ) { |
|
173 qSwap( heap[i], heap[ i / 2 ] ); |
|
174 i /= 2; |
|
175 } |
|
176 } |
|
177 |
|
178 // Now do the sorting |
|
179 for( uint i = n; i > 0; i-- ) { |
|
180 *b++ = heap[1]; |
|
181 if ( i > 1 ) { |
|
182 heap[1] = heap[i]; |
|
183 qHeapSortPushDown( heap, 1, (int)i - 1 ); |
|
184 } |
|
185 } |
|
186 |
|
187 delete[] realheap; |
|
188 } |
|
189 |
|
190 |
|
191 template <class InputIterator> |
|
192 inline void qHeapSort( InputIterator b, InputIterator e ) |
|
193 { |
|
194 // Empty ? |
|
195 if ( b == e ) |
|
196 return; |
|
197 |
|
198 // How many entries have to be sorted ? |
|
199 InputIterator it = b; |
|
200 uint n = 0; |
|
201 while ( it != e ) { |
|
202 ++n; |
|
203 ++it; |
|
204 } |
|
205 |
|
206 // The second last parameter is a hack to retrieve the value type |
|
207 // Do the real sorting here |
|
208 qHeapSortHelper( b, e, *b, n ); |
|
209 } |
|
210 |
|
211 |
|
212 template <class Container> |
|
213 inline void qHeapSort( Container &c ) |
|
214 { |
|
215 if ( c.isEmpty() ) |
|
216 return; |
|
217 |
|
218 // The second last parameter is a hack to retrieve the value type |
|
219 // Do the real sorting here |
|
220 qHeapSortHelper( c.begin(), c.end(), *(c.begin()), c.count() ); |
|
221 } |
|
222 |
|
223 #endif |