Root/
| Source at commit 1406 created 12 years 10 months ago. By meklort, Revert drivers.c so that kexts are only loaded when OSBundleRequired is set and that value is not safe mode. Added some comments about it too. | |
|---|---|
| 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 | |
