Root/
| Source at commit 1322 created 12 years 8 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␊ |
| 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␊ |
| 224 | |
