|
Packit Service |
50c9f2 |
/****************************************************************************
|
|
Packit Service |
50c9f2 |
**
|
|
Packit Service |
50c9f2 |
**
|
|
Packit Service |
50c9f2 |
** Definition of Qt template library classes
|
|
Packit Service |
50c9f2 |
**
|
|
Packit Service |
50c9f2 |
** Created : 990128
|
|
Packit Service |
50c9f2 |
**
|
|
Packit Service |
50c9f2 |
** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.
|
|
Packit Service |
50c9f2 |
**
|
|
Packit Service |
50c9f2 |
** This file is part of the tools module of the Qt GUI Toolkit.
|
|
Packit Service |
50c9f2 |
**
|
|
Packit Service |
50c9f2 |
** This file may be distributed under the terms of the Q Public License
|
|
Packit Service |
50c9f2 |
** as defined by Trolltech AS of Norway and appearing in the file
|
|
Packit Service |
50c9f2 |
** LICENSE.QPL included in the packaging of this file.
|
|
Packit Service |
50c9f2 |
**
|
|
Packit Service |
50c9f2 |
** This file may be distributed and/or modified under the terms of the
|
|
Packit Service |
50c9f2 |
** GNU General Public License version 2 as published by the Free Software
|
|
Packit Service |
50c9f2 |
** Foundation and appearing in the file LICENSE.GPL included in the
|
|
Packit Service |
50c9f2 |
** packaging of this file.
|
|
Packit Service |
50c9f2 |
**
|
|
Packit Service |
50c9f2 |
** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
|
|
Packit Service |
50c9f2 |
** licenses may use this file in accordance with the Qt Commercial License
|
|
Packit Service |
50c9f2 |
** Agreement provided with the Software.
|
|
Packit Service |
50c9f2 |
**
|
|
Packit Service |
50c9f2 |
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
|
|
Packit Service |
50c9f2 |
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
|
|
Packit Service |
50c9f2 |
**
|
|
Packit Service |
50c9f2 |
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
|
|
Packit Service |
50c9f2 |
** information about Qt Commercial License Agreements.
|
|
Packit Service |
50c9f2 |
** See http://www.trolltech.com/qpl/ for QPL licensing information.
|
|
Packit Service |
50c9f2 |
** See http://www.trolltech.com/gpl/ for GPL licensing information.
|
|
Packit Service |
50c9f2 |
**
|
|
Packit Service |
50c9f2 |
** Contact info@trolltech.com if any conditions of this licensing are
|
|
Packit Service |
50c9f2 |
** not clear to you.
|
|
Packit Service |
50c9f2 |
**
|
|
Packit Service |
50c9f2 |
**********************************************************************/
|
|
Packit Service |
50c9f2 |
#ifndef QTL_H
|
|
Packit Service |
50c9f2 |
#define QTL_H
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
#ifndef QT_H
|
|
Packit Service |
50c9f2 |
#include "qtextstream.h"
|
|
Packit Service |
50c9f2 |
#include "qstring.h"
|
|
Packit Service |
50c9f2 |
#endif // QT_H
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
#ifndef QT_NO_TEXTSTREAM
|
|
Packit Service |
50c9f2 |
template <class T>
|
|
Packit Service |
50c9f2 |
class QTextOStreamIterator
|
|
Packit Service |
50c9f2 |
{
|
|
Packit Service |
50c9f2 |
protected:
|
|
Packit Service |
50c9f2 |
QTextOStream& stream;
|
|
Packit Service |
50c9f2 |
QString separator;
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
public:
|
|
Packit Service |
50c9f2 |
QTextOStreamIterator( QTextOStream& s) : stream( s ) {}
|
|
Packit Service |
50c9f2 |
QTextOStreamIterator( QTextOStream& s, const QString& sep )
|
|
Packit Service |
50c9f2 |
: stream( s ), separator( sep ) {}
|
|
Packit Service |
50c9f2 |
QTextOStreamIterator<T>& operator= ( const T& x ) {
|
|
Packit Service |
50c9f2 |
stream << x;
|
|
Packit Service |
50c9f2 |
if ( !separator.isEmpty() )
|
|
Packit Service |
50c9f2 |
stream << separator;
|
|
Packit Service |
50c9f2 |
return *this;
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
QTextOStreamIterator<T>& operator*() { return *this; }
|
|
Packit Service |
50c9f2 |
QTextOStreamIterator<T>& operator++() { return *this; }
|
|
Packit Service |
50c9f2 |
QTextOStreamIterator<T>& operator++(int) { return *this; }
|
|
Packit Service |
50c9f2 |
};
|
|
Packit Service |
50c9f2 |
#endif //QT_NO_TEXTSTREAM
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
template <class InputIterator, class OutputIterator>
|
|
Packit Service |
50c9f2 |
inline OutputIterator qCopy( InputIterator _begin, InputIterator _end,
|
|
Packit Service |
50c9f2 |
OutputIterator _dest )
|
|
Packit Service |
50c9f2 |
{
|
|
Packit Service |
50c9f2 |
while( _begin != _end )
|
|
Packit Service |
50c9f2 |
*_dest++ = *_begin++;
|
|
Packit Service |
50c9f2 |
return _dest;
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
template <class T>
|
|
Packit Service |
50c9f2 |
inline void qSwap( T& _value1, T& _value2 )
|
|
Packit Service |
50c9f2 |
{
|
|
Packit Service |
50c9f2 |
T tmp = _value1;
|
|
Packit Service |
50c9f2 |
_value1 = _value2;
|
|
Packit Service |
50c9f2 |
_value2 = tmp;
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
template <class InputIterator>
|
|
Packit Service |
50c9f2 |
inline void qBubbleSort( InputIterator b, InputIterator e )
|
|
Packit Service |
50c9f2 |
{
|
|
Packit Service |
50c9f2 |
// Goto last element;
|
|
Packit Service |
50c9f2 |
InputIterator last = e;
|
|
Packit Service |
50c9f2 |
--last;
|
|
Packit Service |
50c9f2 |
// only one element or no elements ?
|
|
Packit Service |
50c9f2 |
if ( last == b )
|
|
Packit Service |
50c9f2 |
return;
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
// So we have at least two elements in here
|
|
Packit Service |
50c9f2 |
while( b != last ) {
|
|
Packit Service |
50c9f2 |
bool swapped = FALSE;
|
|
Packit Service |
50c9f2 |
InputIterator swap_pos = b;
|
|
Packit Service |
50c9f2 |
InputIterator x = e;
|
|
Packit Service |
50c9f2 |
InputIterator y = x;
|
|
Packit Service |
50c9f2 |
y--;
|
|
Packit Service |
50c9f2 |
do {
|
|
Packit Service |
50c9f2 |
--x;
|
|
Packit Service |
50c9f2 |
--y;
|
|
Packit Service |
50c9f2 |
if ( *x < *y ) {
|
|
Packit Service |
50c9f2 |
swapped = TRUE;
|
|
Packit Service |
50c9f2 |
qSwap( *x, *y );
|
|
Packit Service |
50c9f2 |
swap_pos = y;
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
} while( y != b );
|
|
Packit Service |
50c9f2 |
if ( !swapped )
|
|
Packit Service |
50c9f2 |
return;
|
|
Packit Service |
50c9f2 |
b = swap_pos;
|
|
Packit Service |
50c9f2 |
b++;
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
template <class Container>
|
|
Packit Service |
50c9f2 |
inline void qBubbleSort( Container &c )
|
|
Packit Service |
50c9f2 |
{
|
|
Packit Service |
50c9f2 |
qBubbleSort( c.begin(), c.end() );
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
template <class Value>
|
|
Packit Service |
50c9f2 |
inline void qHeapSortPushDown( Value* heap, int first, int last )
|
|
Packit Service |
50c9f2 |
{
|
|
Packit Service |
50c9f2 |
int r = first;
|
|
Packit Service |
50c9f2 |
while( r <= last/2 ) {
|
|
Packit Service |
50c9f2 |
// Node r has only one child ?
|
|
Packit Service |
50c9f2 |
if ( last == 2*r ) {
|
|
Packit Service |
50c9f2 |
// Need for swapping ?
|
|
Packit Service |
50c9f2 |
if ( heap[r] > heap[ 2*r ] )
|
|
Packit Service |
50c9f2 |
qSwap( heap[r], heap[ 2*r ] );
|
|
Packit Service |
50c9f2 |
// That's it ...
|
|
Packit Service |
50c9f2 |
r = last;
|
|
Packit Service |
50c9f2 |
} else { // Node has two children
|
|
Packit Service |
50c9f2 |
if ( heap[r] > heap[ 2*r ] && heap[ 2*r ] <= heap[ 2*r+1 ] ) {
|
|
Packit Service |
50c9f2 |
// Swap with left child
|
|
Packit Service |
50c9f2 |
qSwap( heap[r], heap[ 2*r ] );
|
|
Packit Service |
50c9f2 |
r *= 2;
|
|
Packit Service |
50c9f2 |
} else if ( heap[r] > heap[ 2*r+1 ] &&
|
|
Packit Service |
50c9f2 |
heap[ 2*r+1 ] < heap[ 2*r ] ) {
|
|
Packit Service |
50c9f2 |
// Swap with right child
|
|
Packit Service |
50c9f2 |
qSwap( heap[r], heap[ 2*r+1 ] );
|
|
Packit Service |
50c9f2 |
r = 2*r+1;
|
|
Packit Service |
50c9f2 |
} else {
|
|
Packit Service |
50c9f2 |
// We are done
|
|
Packit Service |
50c9f2 |
r = last;
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
template <class InputIterator, class Value>
|
|
Packit Service |
50c9f2 |
inline void qHeapSortHelper( InputIterator b, InputIterator e, Value, uint n )
|
|
Packit Service |
50c9f2 |
{
|
|
Packit Service |
50c9f2 |
// Create the heap
|
|
Packit Service |
50c9f2 |
InputIterator insert = b;
|
|
Packit Service |
50c9f2 |
Value* realheap = new Value[ n ];
|
|
Packit Service |
50c9f2 |
// Wow, what a fake. But I want the heap to be indexed as 1...n
|
|
Packit Service |
50c9f2 |
Value* heap = realheap - 1;
|
|
Packit Service |
50c9f2 |
int size = 0;
|
|
Packit Service |
50c9f2 |
for( ; insert != e; ++insert ) {
|
|
Packit Service |
50c9f2 |
heap[++size] = *insert;
|
|
Packit Service |
50c9f2 |
int i = size;
|
|
Packit Service |
50c9f2 |
while( i > 1 && heap[i] < heap[ i / 2 ] ) {
|
|
Packit Service |
50c9f2 |
qSwap( heap[i], heap[ i / 2 ] );
|
|
Packit Service |
50c9f2 |
i /= 2;
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
// Now do the sorting
|
|
Packit Service |
50c9f2 |
for( uint i = n; i > 0; i-- ) {
|
|
Packit Service |
50c9f2 |
*b++ = heap[1];
|
|
Packit Service |
50c9f2 |
if ( i > 1 ) {
|
|
Packit Service |
50c9f2 |
heap[1] = heap[i];
|
|
Packit Service |
50c9f2 |
qHeapSortPushDown( heap, 1, (int)i - 1 );
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
delete[] realheap;
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
template <class InputIterator>
|
|
Packit Service |
50c9f2 |
inline void qHeapSort( InputIterator b, InputIterator e )
|
|
Packit Service |
50c9f2 |
{
|
|
Packit Service |
50c9f2 |
// Empty ?
|
|
Packit Service |
50c9f2 |
if ( b == e )
|
|
Packit Service |
50c9f2 |
return;
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
// How many entries have to be sorted ?
|
|
Packit Service |
50c9f2 |
InputIterator it = b;
|
|
Packit Service |
50c9f2 |
uint n = 0;
|
|
Packit Service |
50c9f2 |
while ( it != e ) {
|
|
Packit Service |
50c9f2 |
++n;
|
|
Packit Service |
50c9f2 |
++it;
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
// The second last parameter is a hack to retrieve the value type
|
|
Packit Service |
50c9f2 |
// Do the real sorting here
|
|
Packit Service |
50c9f2 |
qHeapSortHelper( b, e, *b, n );
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
template <class Container>
|
|
Packit Service |
50c9f2 |
inline void qHeapSort( Container &c )
|
|
Packit Service |
50c9f2 |
{
|
|
Packit Service |
50c9f2 |
if ( c.isEmpty() )
|
|
Packit Service |
50c9f2 |
return;
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
// The second last parameter is a hack to retrieve the value type
|
|
Packit Service |
50c9f2 |
// Do the real sorting here
|
|
Packit Service |
50c9f2 |
qHeapSortHelper( c.begin(), c.end(), *(c.begin()), c.count() );
|
|
Packit Service |
50c9f2 |
}
|
|
Packit Service |
50c9f2 |
|
|
Packit Service |
50c9f2 |
#endif
|