Imported Upstream version 1.8.2upstream/1.8.2

1 files changed, 223 insertions, 0 deletions

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