Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/util/doxygen/qtools/qtl.h

Source at commit 1322 created 9 years 5 months ago.
By meklort, Add doxygen to utils folder
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
46template <class T>
47class QTextOStreamIterator
48{
49protected:
50 QTextOStream& stream;
51 QString separator;
52
53public:
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 ) {
58stream << x;
59if ( !separator.isEmpty() )
60 stream << separator;
61return *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
69template <class InputIterator, class OutputIterator>
70inline OutputIterator qCopy( InputIterator _begin, InputIterator _end,
71 OutputIterator _dest )
72{
73 while( _begin != _end )
74*_dest++ = *_begin++;
75 return _dest;
76}
77
78
79template <class T>
80inline void qSwap( T& _value1, T& _value2 )
81{
82 T tmp = _value1;
83 _value1 = _value2;
84 _value2 = tmp;
85}
86
87
88template <class InputIterator>
89inline 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 )
96return;
97
98 // So we have at least two elements in here
99 while( b != last ) {
100bool swapped = FALSE;
101InputIterator swap_pos = b;
102InputIterator x = e;
103InputIterator y = x;
104y--;
105do {
106 --x;
107 --y;
108 if ( *x < *y ) {
109swapped = TRUE;
110qSwap( *x, *y );
111swap_pos = y;
112 }
113} while( y != b );
114if ( !swapped )
115 return;
116b = swap_pos;
117b++;
118 }
119}
120
121
122template <class Container>
123inline void qBubbleSort( Container &c )
124{
125 qBubbleSort( c.begin(), c.end() );
126}
127
128
129template <class Value>
130inline 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 ?
135if ( last == 2*r ) {
136 // Need for swapping ?
137 if ( heap[r] > heap[ 2*r ] )
138qSwap( 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
144qSwap( heap[r], heap[ 2*r ] );
145r *= 2;
146 } else if ( heap[r] > heap[ 2*r+1 ] &&
147heap[ 2*r+1 ] < heap[ 2*r ] ) {
148// Swap with right child
149qSwap( heap[r], heap[ 2*r+1 ] );
150r = 2*r+1;
151 } else {
152// We are done
153r = last;
154 }
155}
156 }
157}
158
159
160template <class InputIterator, class Value>
161inline 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 ) {
170heap[++size] = *insert;
171int i = size;
172while( 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];
181if ( i > 1 ) {
182 heap[1] = heap[i];
183 qHeapSortPushDown( heap, 1, (int)i - 1 );
184}
185 }
186
187 delete[] realheap;
188}
189
190
191template <class InputIterator>
192inline void qHeapSort( InputIterator b, InputIterator e )
193{
194 // Empty ?
195 if ( b == e )
196return;
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
212template <class Container>
213inline void qHeapSort( Container &c )
214{
215 if ( c.isEmpty() )
216return;
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
224

Archive Download this file

Revision: 1322