home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / qt3_emx.zip / include / qtl.h < prev    next >
C/C++ Source or Header  |  2001-10-11  |  7KB  |  289 lines
  1. /****************************************************************************
  2. ** $Id$
  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.  
  38. #ifndef QTL_H
  39. #define QTL_H
  40.  
  41. #ifndef QT_H
  42. #include "qtextstream.h"
  43. #include "qstring.h"
  44. #endif // QT_H
  45.  
  46. // Visual Age C++ 5.0[0-2] has Defect 121 of the C++ Standard
  47. #if defined(Q_CC_XLC)
  48. #define Q_TYPENAME typename
  49. #else
  50. #define Q_TYPENAME
  51. #endif
  52.  
  53. #ifndef QT_NO_TEXTSTREAM
  54. template <class T>
  55. class QTextOStreamIterator
  56. {
  57. protected:
  58.     QTextOStream& stream;
  59.     QString separator;
  60.  
  61. public:
  62.     QTextOStreamIterator( QTextOStream& s) : stream( s ) {}
  63.     QTextOStreamIterator( QTextOStream& s, const QString& sep )
  64.     : stream( s ), separator( sep )  {}
  65.     QTextOStreamIterator<T>& operator= ( const T& x ) {
  66.     stream << x;
  67.     if ( !separator.isEmpty() )
  68.         stream << separator;
  69.     return *this;
  70.     }
  71.     QTextOStreamIterator<T>& operator*() { return *this; }
  72.     QTextOStreamIterator<T>& operator++() { return *this; }
  73.     QTextOStreamIterator<T>& operator++(int) { return *this; }
  74. };
  75. #endif //QT_NO_TEXTSTREAM
  76.  
  77. template <class InputIterator, class OutputIterator>
  78. inline OutputIterator qCopy( InputIterator _begin, InputIterator _end,
  79.                  OutputIterator _dest )
  80. {
  81.     while( _begin != _end )
  82.     *_dest++ = *_begin++;
  83.     return _dest;
  84. }
  85.  
  86. template <class BiIterator, class BiOutputIterator>
  87. inline BiOutputIterator qCopyBackward( BiIterator _begin, BiIterator _end,
  88.                        BiOutputIterator _dest )
  89. {
  90.     while ( _begin != _end )
  91.     *--_dest = *--_end;
  92.     return _dest;
  93. }
  94.  
  95. template <class InputIterator1, class InputIterator2>
  96. inline bool qEqual( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
  97. {
  98.     for ( ; first1 != last1; ++first1, ++first2 )
  99.     if ( *first1 != *first2 )
  100.         return FALSE;
  101.     return TRUE;
  102. }
  103.  
  104. template <class ForwardIterator, class T>
  105. inline void qFill( ForwardIterator first, ForwardIterator last, const T& val )
  106. {
  107.     for ( ; first != last; ++first )
  108.     *first = val;
  109. }
  110.  
  111. #if 0
  112. template <class BiIterator, class OutputIterator>
  113. inline OutputIterator qReverseCopy( BiIterator _begin, BiIterator _end,
  114.                     OutputIterator _dest )
  115. {
  116.     while ( _begin != _end ) {
  117.     --_end;
  118.     *_dest = *_end;
  119.     ++_dest;
  120.     }
  121.     return _dest;
  122. }
  123. #endif
  124.  
  125.  
  126. template <class InputIterator, class T>
  127. inline InputIterator qFind( InputIterator first, InputIterator last,
  128.                 const T& val )
  129. {
  130.     while ( first != last && *first != val )
  131.     ++first;
  132.     return first;
  133. }
  134.  
  135. template <class InputIterator, class T, class Size>
  136. inline void qCount( InputIterator first, InputIterator last, const T& value,
  137.             Size& n )
  138. {
  139.     for ( ; first != last; ++first )
  140.     if ( *first == value )
  141.         ++n;
  142. }
  143.  
  144. template <class T>
  145. inline void qSwap( T& _value1, T& _value2 )
  146. {
  147.     T tmp = _value1;
  148.     _value1 = _value2;
  149.     _value2 = tmp;
  150. }
  151.  
  152.  
  153. template <class InputIterator>
  154. inline void qBubbleSort( InputIterator b, InputIterator e )
  155. {
  156.     // Goto last element;
  157.     InputIterator last = e;
  158.     --last;
  159.     // only one element or no elements ?
  160.     if ( last == b )
  161.     return;
  162.  
  163.     // So we have at least two elements in here
  164.     while( b != last ) {
  165.     bool swapped = FALSE;
  166.     InputIterator swap_pos = b;
  167.     InputIterator x = e;
  168.     InputIterator y = x;
  169.     y--;
  170.     do {
  171.         --x;
  172.         --y;
  173.         if ( *x < *y ) {
  174.         swapped = TRUE;
  175.         qSwap( *x, *y );
  176.         swap_pos = y;
  177.         }
  178.     } while( y != b );
  179.     if ( !swapped )
  180.         return;
  181.     b = swap_pos;
  182.     b++;
  183.     }
  184. }
  185.  
  186.  
  187. template <class Container>
  188. inline void qBubbleSort( Container &c )
  189. {
  190.   qBubbleSort( c.begin(), c.end() );
  191. }
  192.  
  193.  
  194. template <class Value>
  195. inline void qHeapSortPushDown( Value* heap, int first, int last )
  196. {
  197.     int r = first;
  198.     while( r <= last/2 ) {
  199.     // Node r has only one child ?
  200.     if ( last == 2*r ) {
  201.         // Need for swapping ?
  202.         if ( heap[r] > heap[ 2*r ] )
  203.         qSwap( heap[r], heap[ 2*r ] );
  204.         // That's it ...
  205.         r = last;
  206.     } else { // Node has two children
  207.         if ( heap[r] > heap[ 2*r ] && heap[ 2*r ] <= heap[ 2*r+1 ] ) {
  208.         // Swap with left child
  209.         qSwap( heap[r], heap[ 2*r ] );
  210.         r *= 2;
  211.         } else if ( heap[r] > heap[ 2*r+1 ] &&
  212.             heap[ 2*r+1 ] < heap[ 2*r ] ) {
  213.         // Swap with right child
  214.         qSwap( heap[r], heap[ 2*r+1 ] );
  215.         r = 2*r+1;
  216.         } else {
  217.         // We are done
  218.         r = last;
  219.         }
  220.     }
  221.     }
  222. }
  223.  
  224.  
  225. template <class InputIterator, class Value>
  226. inline void qHeapSortHelper( InputIterator b, InputIterator e, Value, uint n )
  227. {
  228.     // Create the heap
  229.     InputIterator insert = b;
  230.     Value* realheap = new Value[ n ];
  231.     // Wow, what a fake. But I want the heap to be indexed as 1...n
  232.     Value* heap = realheap - 1;
  233.     int size = 0;
  234.     for( ; insert != e; ++insert ) {
  235.     heap[++size] = *insert;
  236.     int i = size;
  237.     while( i > 1 && heap[i] < heap[ i / 2 ] ) {
  238.         qSwap( heap[i], heap[ i / 2 ] );
  239.         i /= 2;
  240.     }
  241.     }
  242.  
  243.     // Now do the sorting
  244.     for( uint i = n; i > 0; i-- ) {
  245.     *b++ = heap[1];
  246.     if ( i > 1 ) {
  247.         heap[1] = heap[i];
  248.         qHeapSortPushDown( heap, 1, (int)i - 1 );
  249.     }
  250.     }
  251.  
  252.     delete[] realheap;
  253. }
  254.  
  255.  
  256. template <class InputIterator>
  257. inline void qHeapSort( InputIterator b, InputIterator e )
  258. {
  259.     // Empty ?
  260.     if ( b == e )
  261.     return;
  262.  
  263.     // How many entries have to be sorted ?
  264.     InputIterator it = b;
  265.     uint n = 0;
  266.     while ( it != e ) {
  267.     ++n;
  268.     ++it;
  269.     }
  270.  
  271.     // The second last parameter is a hack to retrieve the value type
  272.     // Do the real sorting here
  273.     qHeapSortHelper( b, e, *b, n );
  274. }
  275.  
  276.  
  277. template <class Container>
  278. inline void qHeapSort( Container &c )
  279. {
  280.     if ( c.begin() == c.end() )
  281.     return;
  282.  
  283.     // The second last parameter is a hack to retrieve the value type
  284.     // Do the real sorting here
  285.     qHeapSortHelper( c.begin(), c.end(), *(c.begin()), (uint)c.count() );
  286. }
  287.  
  288. #endif
  289.