qtl.h File Reference

#include "qtextstream.h"
#include "qstring.h"

Go to the source code of this file.

Classes
class	QTextOStreamIterator< T >

Functions
template<class InputIterator , class OutputIterator >
OutputIterator	qCopy (InputIterator _begin, InputIterator _end, OutputIterator _dest)
template<class T >
void	qSwap (T &_value1, T &_value2)
template<class InputIterator >
void	qBubbleSort (InputIterator b, InputIterator e)
template<class Container >
void	qBubbleSort (Container &c)
template<class Value >
void	qHeapSortPushDown (Value *heap, int first, int last)
template<class InputIterator , class Value >
void	qHeapSortHelper (InputIterator b, InputIterator e, Value, uint n)
template<class InputIterator >
void	qHeapSort (InputIterator b, InputIterator e)
template<class Container >
void	qHeapSort (Container &c)

Function Documentation

template<class InputIterator >

void qBubbleSort ( InputIterator  b, InputIterator  e  )

inline

Definition at line 89 of file qtl.h.

{
    // 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 >

void qBubbleSort ( Container &  c )

inline

Definition at line 123 of file qtl.h.

{
  qBubbleSort( c.begin(), c.end() );
}

template<class InputIterator , class OutputIterator >

OutputIterator qCopy ( InputIterator  _begin, InputIterator  _end, OutputIterator  _dest  )

inline

Definition at line 70 of file qtl.h.

{
    while( _begin != _end )
        *_dest++ = *_begin++;
    return _dest;
}

template<class InputIterator >

void qHeapSort ( InputIterator  b, InputIterator  e  )

inline

Definition at line 192 of file qtl.h.

{
    // 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 >

void qHeapSort ( Container &  c )

inline

Definition at line 213 of file qtl.h.

{
    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() );
}

template<class InputIterator , class Value >

void qHeapSortHelper ( InputIterator  b, InputIterator  e, Value  , uint  n  )

inline

Definition at line 161 of file qtl.h.

{
    // 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 Value >

void qHeapSortPushDown ( Value *  heap, int  first, int  last  )

inline

Definition at line 130 of file qtl.h.

{
    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 T >

void qSwap ( T &  _value1, T &  _value2  )

inline

Definition at line 80 of file qtl.h.

{
    T tmp = _value1;
    _value1 = _value2;
    _value2 = tmp;
}