home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / qt3_emx.zip / include / qmap.h < prev    next >
C/C++ Source or Header  |  2001-10-11  |  18KB  |  795 lines

  1. /****************************************************************************
  2. ** $Id:  qt/qmap.h   3.0.0   edited Oct 2 17:15 $
  3. **
  4. ** Definition of QMap class
  5. **
  6. ** Created : 990406
  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 QMAP_H
  39. #define QMAP_H
  40.  
  41. #ifndef QT_H
  42. #include "qshared.h"
  43. #include "qdatastream.h"
  44. #include "qpair.h"
  45. #include "qtl.h"
  46. #endif // QT_H
  47.  
  48. #ifndef QT_NO_STL
  49. #include <iterator>
  50. #include <map>
  51. #endif
  52.  
  53. //#define QT_CHECK_MAP_RANGE
  54.  
  55. struct QMapNodeBase
  56. {
  57.     enum Color { Red, Black };
  58.  
  59.     QMapNodeBase* left;
  60.     QMapNodeBase* right;
  61.     QMapNodeBase* parent;
  62.  
  63.     Color color;
  64.  
  65.     QMapNodeBase* minimum() {
  66.     QMapNodeBase* x = this;
  67.     while ( x->left )
  68.         x = x->left;
  69.     return x;
  70.     }
  71.  
  72.     QMapNodeBase* maximum() {
  73.     QMapNodeBase* x = this;
  74.     while ( x->right )
  75.         x = x->right;
  76.     return x;
  77.     }
  78. };
  79.  
  80.  
  81. template <class K, class T>
  82. struct QMapNode : public QMapNodeBase
  83. {
  84.     QMapNode( const K& _key, const T& _data ) { data = _data; key = _key; }
  85.     QMapNode( const K& _key )       { key = _key; }
  86.     QMapNode( const QMapNode<K,T>& _n ) { key = _n.key; data = _n.data; }
  87.     QMapNode() { }
  88.     T data;
  89.     K key;
  90. };
  91.  
  92.  
  93. template<class K, class T>
  94. class Q_EXPORT QMapIterator
  95. {
  96.  public:
  97.     /**
  98.      * Typedefs
  99.      */
  100.     typedef QMapNode< K, T >* NodePtr;
  101. #ifndef QT_NO_STL
  102.     typedef std::bidirectional_iterator_tag  iterator_category;
  103. #endif
  104.     typedef T          value_type;
  105. #ifndef QT_NO_STL
  106.     typedef ptrdiff_t  difference_type;
  107. #else
  108.     typedef int difference_type;
  109. #endif
  110.     typedef T*         pointer;
  111.     typedef T&         reference;
  112.  
  113.     /**
  114.      * Variables
  115.      */
  116.     QMapNode<K,T>* node;
  117.  
  118.     /**
  119.      * Functions
  120.      */
  121.     QMapIterator() : node( 0 ) {}
  122.     QMapIterator( QMapNode<K,T>* p ) : node( p ) {}
  123.     QMapIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}
  124.  
  125.     bool operator==( const QMapIterator<K,T>& it ) const { return node == it.node; }
  126.     bool operator!=( const QMapIterator<K,T>& it ) const { return node != it.node; }
  127.     T& operator*() { return node->data; }
  128.     const T& operator*() const { return node->data; }
  129.     // UDT for T = x*
  130.     // T* operator->() const { return &node->data; }
  131.  
  132.     const K& key() const { return node->key; }
  133.     T& data() { return node->data; }
  134.     const T& data() const { return node->data; }
  135.  
  136. private:
  137.     int inc() {
  138.     QMapNodeBase* tmp = node;
  139.     if ( tmp->right ) {
  140.         tmp = tmp->right;
  141.         while ( tmp->left )
  142.         tmp = tmp->left;
  143.     } else {
  144.         QMapNodeBase* y = tmp->parent;
  145.         while (tmp == y->right) {
  146.         tmp = y;
  147.         y = y->parent;
  148.         }
  149.         if (tmp->right != y)
  150.         tmp = y;
  151.     }
  152.     node = (NodePtr)tmp;
  153.     return 0;
  154.     }
  155.  
  156.     int dec() {
  157.     QMapNodeBase* tmp = node;
  158.     if (tmp->color == QMapNodeBase::Red &&
  159.         tmp->parent->parent == tmp ) {
  160.         tmp = tmp->right;
  161.     } else if (tmp->left != 0) {
  162.         QMapNodeBase* y = tmp->left;
  163.         while ( y->right )
  164.         y = y->right;
  165.         tmp = y;
  166.     } else {
  167.         QMapNodeBase* y = tmp->parent;
  168.         while (tmp == y->left) {
  169.         tmp = y;
  170.         y = y->parent;
  171.         }
  172.         tmp = y;
  173.     }
  174.     node = (NodePtr)tmp;
  175.     return 0;
  176.     }
  177.  
  178. public:
  179.     QMapIterator<K,T>& operator++() {
  180.     inc();
  181.     return *this;
  182.     }
  183.  
  184.     QMapIterator<K,T> operator++(int) {
  185.     QMapIterator<K,T> tmp = *this;
  186.     inc();
  187.     return tmp;
  188.     }
  189.  
  190.     QMapIterator<K,T>& operator--() {
  191.     dec();
  192.     return *this;
  193.     }
  194.  
  195.     QMapIterator<K,T> operator--(int) {
  196.     QMapIterator<K,T> tmp = *this;
  197.     dec();
  198.     return tmp;
  199.     }
  200. };
  201.  
  202. template<class K, class T>
  203. class Q_EXPORT QMapConstIterator
  204. {
  205.  public:
  206.     /**
  207.      * Typedefs
  208.      */
  209.     typedef QMapNode< K, T >* NodePtr;
  210. #ifndef QT_NO_STL
  211.     typedef std::bidirectional_iterator_tag  iterator_category;
  212. #endif
  213.     typedef T          value_type;
  214. #ifndef QT_NO_STL
  215.     typedef ptrdiff_t  difference_type;
  216. #else
  217.     typedef int difference_type;
  218. #endif
  219.     typedef const T*   pointer;
  220.     typedef const T&   reference;
  221.  
  222.  
  223.     /**
  224.      * Variables
  225.      */
  226.     QMapNode<K,T>* node;
  227.  
  228.     /**
  229.      * Functions
  230.      */
  231.     QMapConstIterator() : node( 0 ) {}
  232.     QMapConstIterator( QMapNode<K,T>* p ) : node( p ) {}
  233.     QMapConstIterator( const QMapConstIterator<K,T>& it ) : node( it.node ) {}
  234.     QMapConstIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}
  235.  
  236.     bool operator==( const QMapConstIterator<K,T>& it ) const { return node == it.node; }
  237.     bool operator!=( const QMapConstIterator<K,T>& it ) const { return node != it.node; }
  238.     const T& operator*()  const { return node->data; }
  239.     // UDT for T = x*
  240.     // const T* operator->() const { return &node->data; }
  241.  
  242.     const K& key() const { return node->key; }
  243.     const T& data() const { return node->data; }
  244.  
  245. private:
  246.     int inc() {
  247.     QMapNodeBase* tmp = node;
  248.     if ( tmp->right ) {
  249.         tmp = tmp->right;
  250.         while ( tmp->left )
  251.         tmp = tmp->left;
  252.     } else {
  253.         QMapNodeBase* y = tmp->parent;
  254.         while (tmp == y->right) {
  255.         tmp = y;
  256.         y = y->parent;
  257.         }
  258.         if (tmp->right != y)
  259.         tmp = y;
  260.     }
  261.     node = (NodePtr)tmp;
  262.     return 0;
  263.     }
  264.  
  265.     int dec() {
  266.     QMapNodeBase* tmp = node;
  267.     if (tmp->color == QMapNodeBase::Red &&
  268.         tmp->parent->parent == tmp ) {
  269.         tmp = tmp->right;
  270.     } else if (tmp->left != 0) {
  271.         QMapNodeBase* y = tmp->left;
  272.         while ( y->right )
  273.         y = y->right;
  274.         tmp = y;
  275.     } else {
  276.         QMapNodeBase* y = tmp->parent;
  277.         while (tmp == y->left) {
  278.         tmp = y;
  279.         y = y->parent;
  280.         }
  281.         tmp = y;
  282.     }
  283.     node = (NodePtr)tmp;
  284.     return 0;
  285.     }
  286.  
  287. public:
  288.     QMapConstIterator<K,T>& operator++() {
  289.     inc();
  290.     return *this;
  291.     }
  292.  
  293.     QMapConstIterator<K,T> operator++(int) {
  294.     QMapConstIterator<K,T> tmp = *this;
  295.     inc();
  296.     return tmp;
  297.     }
  298.  
  299.     QMapConstIterator<K,T>& operator--() {
  300.     dec();
  301.     return *this;
  302.     }
  303.  
  304.     QMapConstIterator<K,T> operator--(int) {
  305.     QMapConstIterator<K,T> tmp = *this;
  306.     dec();
  307.     return tmp;
  308.     }
  309. };
  310.  
  311.  
  312. class Q_EXPORT QMapPrivateBase : public QShared
  313. {
  314. public:
  315.     QMapPrivateBase() {
  316.     node_count = 0;
  317.     }
  318.     QMapPrivateBase( const QMapPrivateBase* _map) {
  319.     node_count = _map->node_count;
  320.     }
  321.  
  322.     /**
  323.      * Implementations of basic tree algorithms
  324.      */
  325.     void rotateLeft( QMapNodeBase* x, QMapNodeBase*& root);
  326.     void rotateRight( QMapNodeBase* x, QMapNodeBase*& root );
  327.     void rebalance( QMapNodeBase* x, QMapNodeBase*& root );
  328.     QMapNodeBase* removeAndRebalance( QMapNodeBase* z, QMapNodeBase*& root,
  329.                       QMapNodeBase*& leftmost,
  330.                       QMapNodeBase*& rightmost );
  331.  
  332.     /**
  333.      * Variables
  334.      */
  335.     int node_count;
  336. };
  337.  
  338.  
  339. template <class Key, class T>
  340. class QMapPrivate : public QMapPrivateBase
  341. {
  342. public:
  343.     /**
  344.      * Typedefs
  345.      */
  346.     typedef QMapIterator< Key, T > Iterator;
  347.     typedef QMapConstIterator< Key, T > ConstIterator;
  348.     typedef QMapNode< Key, T > Node;
  349.     typedef QMapNode< Key, T >* NodePtr;
  350.  
  351.     /**
  352.      * Functions
  353.      */
  354.     QMapPrivate() {
  355.     header = new Node;
  356.     header->color = QMapNodeBase::Red; // Mark the header
  357.     header->parent = 0;
  358.     header->left = header->right = header;
  359.     }
  360.     QMapPrivate( const QMapPrivate< Key, T >* _map ) : QMapPrivateBase( _map ) {
  361.     header = new Node;
  362.     header->color = QMapNodeBase::Red; // Mark the header
  363.     if ( _map->header->parent == 0 ) {
  364.         header->parent = 0;
  365.         header->left = header->right = header;
  366.     } else {
  367.         header->parent = copy( (NodePtr)(_map->header->parent) );
  368.         header->parent->parent = header;
  369.         header->left = header->parent->minimum();
  370.         header->right = header->parent->maximum();
  371.     }
  372.     }
  373.     ~QMapPrivate() { clear(); delete header; }
  374.  
  375.     NodePtr copy( NodePtr p ) {
  376.     if ( !p )
  377.         return 0;
  378.     NodePtr n = new Node( *p );
  379.     n->color = p->color;
  380.     if ( p->left ) {
  381.         n->left = copy( (NodePtr)(p->left) );
  382.         n->left->parent = n;
  383.     } else {
  384.         n->left = 0;
  385.     }
  386.     if ( p->right ) {
  387.         n->right = copy( (NodePtr)(p->right) );
  388.         n->right->parent = n;
  389.     } else {
  390.         n->right = 0;
  391.     }
  392.     return n;
  393.     }
  394.  
  395.     void clear() {
  396.     clear( (NodePtr)(header->parent) );
  397.     header->color = QMapNodeBase::Red;
  398.     header->parent = 0;
  399.     header->left = header->right = header;
  400.     node_count = 0;
  401.     }
  402.  
  403.     void clear( NodePtr p ) {
  404.     while ( p != 0 ) {
  405.         clear( (NodePtr)p->right );
  406.         NodePtr y = (NodePtr)p->left;
  407.         delete p;
  408.         p = y;
  409.     }
  410.     }
  411.  
  412.     Iterator begin()    { return Iterator( (NodePtr)(header->left ) ); }
  413.     Iterator end()    { return Iterator( header ); }
  414.     ConstIterator begin() const { return ConstIterator( (NodePtr)(header->left ) ); }
  415.     ConstIterator end() const { return ConstIterator( header ); }
  416.  
  417.     ConstIterator find(const Key& k) const {
  418.     QMapNodeBase* y = header;        // Last node
  419.     QMapNodeBase* x = header->parent; // Root node.
  420.  
  421.     while ( x != 0 ) {
  422.         // If as k <= key(x) go left
  423.         if ( !( key(x) < k ) ) {
  424.         y = x;
  425.         x = x->left;
  426.         } else {
  427.         x = x->right;
  428.         }
  429.     }
  430.  
  431.     // Was k bigger/smaller then the biggest/smallest
  432.     // element of the tree ? Return end()
  433.     if ( y == header || k < key(y) )
  434.         return ConstIterator( header );
  435.     return ConstIterator( (NodePtr)y );
  436.     }
  437.  
  438.     void remove( Iterator it ) {
  439.     NodePtr del = (NodePtr) removeAndRebalance( it.node, header->parent, header->left, header->right );
  440.     delete del;
  441.     --node_count;
  442.     }
  443.  
  444. #ifdef QT_QMAP_DEBUG
  445.     void inorder( QMapNodeBase* x = 0, int level = 0 ){
  446.     if ( !x )
  447.         x = header->parent;
  448.     if ( x->left )
  449.         inorder( x->left, level + 1 );
  450.     //cout << level << " Key=" << key(x) << " Value=" << ((NodePtr)x)->data << endl;
  451.     if ( x->right )
  452.         inorder( x->right, level + 1 );
  453.     }
  454. #endif
  455.  
  456. #if 0
  457.     Iterator insertMulti(const Key& v){
  458.     QMapNodeBase* y = header;
  459.     QMapNodeBase* x = header->parent;
  460.     while (x != 0){
  461.         y = x;
  462.         x = ( v < key(x) ) ? x->left : x->right;
  463.     }
  464.     return insert(x, y, v);
  465.     }
  466. #endif
  467.  
  468.     Iterator insertSingle( const Key& k ) {
  469.     // Search correct position in the tree
  470.     QMapNodeBase* y = header;
  471.     QMapNodeBase* x = header->parent;
  472.     bool result = TRUE;
  473.     while ( x != 0 ) {
  474.         result = ( k < key(x) );
  475.         y = x;
  476.         x = result ? x->left : x->right;
  477.     }
  478.     // Get iterator on the last not empty one
  479.     Iterator j( (NodePtr)y );
  480.     if ( result ) {
  481.         // Smaller then the leftmost one ?
  482.         if ( j == begin() ) {
  483.         return insert(x, y, k );
  484.         } else {
  485.         // Perhaps daddy is the right one ?
  486.         --j;
  487.         }
  488.     }
  489.     // Really bigger ?
  490.     if ( (j.node->key) < k )
  491.         return insert(x, y, k );
  492.     // We are going to replace a node
  493.     return j;
  494.     }
  495.  
  496.     Iterator insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k ) {
  497.     NodePtr z = new Node( k );
  498.     if (y == header || x != 0 || k < key(y) ) {
  499.         y->left = z;                // also makes leftmost = z when y == header
  500.         if ( y == header ) {
  501.         header->parent = z;
  502.         header->right = z;
  503.         } else if ( y == header->left )
  504.         header->left = z;           // maintain leftmost pointing to min node
  505.     } else {
  506.         y->right = z;
  507.         if ( y == header->right )
  508.         header->right = z;          // maintain rightmost pointing to max node
  509.     }
  510.     z->parent = y;
  511.     z->left = 0;
  512.     z->right = 0;
  513.     rebalance( z, header->parent );
  514.     ++node_count;
  515.     return Iterator(z);
  516.     }
  517.  
  518. protected:
  519.     /**
  520.      * Helpers
  521.      */
  522.     const Key& key( QMapNodeBase* b ) const { return ((NodePtr)b)->key; }
  523.  
  524.     /**
  525.      * Variables
  526.      */
  527.     NodePtr header;
  528. };
  529.  
  530. #ifdef QT_CHECK_RANGE
  531. # if !defined( QT_NO_DEBUG ) && defined( QT_CHECK_MAP_RANGE )
  532. #  define QT_CHECK_INVALID_MAP_ELEMENT if ( empty() ) qWarning( "QMap: Warning invalid element" )
  533. #  define QT_CHECK_INVALID_MAP_ELEMENT_FATAL Q_ASSERT( !empty() );
  534. # else
  535. #  define QT_CHECK_INVALID_MAP_ELEMENT
  536. #  define QT_CHECK_INVALID_MAP_ELEMENT_FATAL
  537. # endif
  538. #else
  539. # define QT_CHECK_INVALID_MAP_ELEMENT
  540. # define QT_CHECK_INVALID_MAP_ELEMENT_FATAL
  541. #endif
  542.  
  543. template<class Key, class T>
  544. class Q_EXPORT QMap
  545. {
  546. public:
  547.     /**
  548.      * Typedefs
  549.      */
  550.     typedef Key key_type;
  551.     typedef T mapped_type;
  552.     typedef QPair<const key_type, mapped_type> value_type;
  553.     typedef value_type* pointer;
  554.     typedef const value_type* const_pointer;
  555.     typedef value_type& reference;
  556.     typedef const value_type& const_reference;
  557. #ifndef QT_NO_STL
  558.     typedef ptrdiff_t  difference_type;
  559. #else
  560.     typedef int difference_type;
  561. #endif
  562.     typedef size_t      size_type;
  563.     typedef QMapIterator<Key,T> iterator;
  564.     typedef QMapConstIterator<Key,T> const_iterator;
  565.  
  566.     /**
  567.      * API
  568.      */
  569.     QMap()
  570.     {
  571.     sh = new QMapPrivate< Key, T >;
  572.     }
  573.     QMap( const QMap<Key,T>& m )
  574.     {
  575.     sh = m.sh; sh->ref();
  576.     }
  577.  
  578. #ifndef QT_NO_STL
  579.     QMap( const Q_TYPENAME std::map<Key,T>& m )
  580.     {
  581.     sh = new QMapPrivate<Key,T>;
  582. #if defined(Q_OS_WIN32)
  583.     std::map<Key,T>::const_iterator it = m.begin();
  584. #else
  585.     QMapConstIterator<Key,T> it = m.begin();
  586. #endif
  587.     for ( ; it != m.end(); ++it ) {
  588.         value_type p( (*it).first, (*it).second );
  589.         insert( p );
  590.     }
  591.     }
  592. #endif
  593.     ~QMap()
  594.     {
  595.     if ( sh->deref() )
  596.         delete sh;
  597.     }
  598.     QMap<Key,T>& operator= ( const QMap<Key,T>& m )
  599.     {
  600.     m.sh->ref();
  601.     if ( sh->deref() )
  602.         delete sh;
  603.     sh = m.sh;
  604.     return *this;
  605.     }
  606. #ifndef QT_NO_STL
  607.     QMap<Key,T>& operator= ( const Q_TYPENAME std::map<Key,T>& m )
  608.     {
  609.     clear();
  610. #if defined(Q_OS_WIN32)
  611.     std::map<Key,T>::const_iterator it = m.begin();
  612. #else
  613.     QMapConstIterator<Key,T> it = m.begin();
  614. #endif
  615.     for ( ; it != m.end(); ++it ) {
  616.         value_type p( (*it).first, (*it).second );
  617.         insert( p );
  618.     }
  619.     return *this;
  620.     }
  621. #endif
  622.  
  623.     iterator begin()
  624.     {
  625.     detach();
  626.     return sh->begin();
  627.     }
  628.     iterator end()
  629.     {
  630.     detach();
  631.     return sh->end();
  632.     }
  633.     const_iterator begin() const
  634.     {
  635.     return ((const Priv*)sh)->begin();
  636.     }
  637.     const_iterator end() const
  638.     {
  639.     return ((const Priv*)sh)->end();
  640.     }
  641.     iterator replace( const Key& k, const T& v )
  642.     {
  643.     remove( k );
  644.     return insert( k, v );
  645.     }
  646.  
  647.     size_type size() const
  648.     {
  649.     return sh->node_count;
  650.     }
  651.     bool empty() const
  652.     {
  653.     return sh->node_count == 0;
  654.     }
  655.     QPair<iterator,bool> insert( const value_type& x )
  656.     {
  657.     detach();
  658.     size_type n = size();
  659.     iterator it = sh->insertSingle( x.first );
  660.     bool inserted = FALSE;
  661.     if ( n < size() ) {
  662.         inserted = TRUE;
  663.         it.data() = x.second;
  664.     }
  665.     return QPair<iterator,bool>( it, inserted );
  666.     }
  667.     void erase( iterator it )
  668.     {
  669.     detach();
  670.     sh->remove( it );
  671.     }
  672.     void erase( const key_type& k )
  673.     {
  674.     detach();
  675.     iterator it( sh->find( k ).node );
  676.     if ( it != end() )
  677.         sh->remove( it );
  678.     }
  679.     size_type count( const key_type& k ) const
  680.     {
  681.     const_iterator it( sh->find( k ).node );
  682.     if ( it != end() ) {
  683.         size_type c = 0;
  684.         while ( it != end() ) {
  685.         ++it;
  686.         ++c;
  687.         }
  688.         return c;
  689.     }
  690.     return 0;
  691.     }
  692.  
  693.     T& operator[] ( const Key& k )
  694.     {
  695.     detach();
  696.     QMapNode<Key,T>* p = sh->find( k ).node;
  697.     if ( p != sh->end().node )
  698.         return p->data;
  699.     return insert( k, T() ).data();
  700.     }
  701.  
  702.     void clear()
  703.     {
  704.     if ( sh->count == 1 )
  705.         sh->clear();
  706.     else {
  707.         sh->deref();
  708.         sh = new QMapPrivate<Key,T>;
  709.     }
  710.     }
  711.  
  712.     typedef QMapIterator< Key, T > Iterator;
  713.     typedef QMapConstIterator< Key, T > ConstIterator;
  714.     typedef T ValueType;
  715.     typedef QMapPrivate< Key, T > Priv;
  716.  
  717.     iterator find ( const Key& k )
  718.     {
  719.     detach();
  720.     return iterator( sh->find( k ).node );
  721.     }
  722.     const_iterator find ( const Key& k ) const {    return sh->find( k ); }
  723.  
  724.     const T& operator[] ( const Key& k ) const
  725.     { QT_CHECK_INVALID_MAP_ELEMENT; return sh->find( k ).data(); }
  726.     bool contains ( const Key& k ) const
  727.     { return find( k ) != end(); }
  728.     //{ return sh->find( k ) != ((const Priv*)sh)->end(); }
  729.  
  730.     size_type count() const { return sh->node_count; }
  731.  
  732.     bool isEmpty() const { return sh->node_count == 0; }
  733.  
  734.  
  735.     iterator insert( const Key& key, const T& value, bool overwrite = TRUE ) {
  736.     detach();
  737.     size_type n = size();
  738.     iterator it = sh->insertSingle( key );
  739.     if ( overwrite || n < size() )
  740.         it.data() = value;
  741.     return it;
  742.     }
  743.  
  744.     void remove( iterator it ) { detach(); sh->remove( it ); }
  745.     void remove( const Key& k ) {
  746.     detach();
  747.     iterator it( sh->find( k ).node );
  748.     if ( it != end() )
  749.         sh->remove( it );
  750.     }
  751.  
  752. #if defined(Q_FULL_TEMPLATE_INSTANTIATION)
  753.     bool operator==( const QMap<Key,T>& ) const { return FALSE; }
  754. #ifndef QT_NO_STL
  755.     bool operator==( const Q_TYPENAME std::map<Key,T>& ) const { return FALSE; }
  756. #endif
  757. #endif
  758.  
  759. protected:
  760.     /**
  761.      * Helpers
  762.      */
  763.     void detach() { if ( sh->count > 1 ) { sh->deref(); sh = new QMapPrivate<Key,T>( sh ); } }
  764.  
  765.     Priv* sh;
  766. };
  767.  
  768.  
  769. #ifndef QT_NO_DATASTREAM
  770. template<class Key, class T>
  771. inline QDataStream& operator>>( QDataStream& s, QMap<Key,T>& m ) {
  772.     m.clear();
  773.     Q_UINT32 c;
  774.     s >> c;
  775.     for( Q_UINT32 i = 0; i < c; ++i ) {
  776.     Key k; T t;
  777.     s >> k >> t;
  778.     m.insert( k, t );
  779.     }
  780.     return s;
  781. }
  782.  
  783.  
  784. template<class Key, class T>
  785. inline QDataStream& operator<<( QDataStream& s, const QMap<Key,T>& m ) {
  786.     s << (Q_UINT32)m.size();
  787.     QMapConstIterator<Key,T> it = m.begin();
  788.     for( ; it != m.end(); ++it )
  789.     s << it.key() << it.data();
  790.     return s;
  791. }
  792. #endif
  793.  
  794. #endif // QMAP_H
  795.