/****************************************************************************

** 

**

** 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