Eneboo - Documentación para desarrolladores
src/qt/include/qmap.h
Ir a la documentación de este archivo.
00001 /****************************************************************************
00002 ** $Id: qt/qmap.h   3.3.8   edited Jan 11 14:38 $
00003 **
00004 ** Definition of QMap class
00005 **
00006 ** Created : 990406
00007 **
00008 ** Copyright (C) 1992-2007 Trolltech ASA.  All rights reserved.
00009 **
00010 ** This file is part of the tools module of the Qt GUI Toolkit.
00011 **
00012 ** This file may be distributed under the terms of the Q Public License
00013 ** as defined by Trolltech ASA of Norway and appearing in the file
00014 ** LICENSE.QPL included in the packaging of this file.
00015 **
00016 ** This file may be distributed and/or modified under the terms of the
00017 ** GNU General Public License version 2 as published by the Free Software
00018 ** Foundation and appearing in the file LICENSE.GPL included in the
00019 ** packaging of this file.
00020 **
00021 ** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
00022 ** licenses may use this file in accordance with the Qt Commercial License
00023 ** Agreement provided with the Software.
00024 **
00025 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
00026 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
00027 **
00028 ** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
00029 **   information about Qt Commercial License Agreements.
00030 ** See http://www.trolltech.com/qpl/ for QPL licensing information.
00031 ** See http://www.trolltech.com/gpl/ for GPL licensing information.
00032 **
00033 ** Contact info@trolltech.com if any conditions of this licensing are
00034 ** not clear to you.
00035 **
00036 **********************************************************************/
00037 
00038 #ifndef QMAP_H
00039 #define QMAP_H
00040 
00041 #ifndef QT_H
00042 #include "qglobal.h"
00043 #include "qshared.h"
00044 #include "qdatastream.h"
00045 #include "qpair.h"
00046 #include "qvaluelist.h"
00047 #endif // QT_H
00048 
00049 #ifndef QT_NO_STL
00050 #include <iterator>
00051 #include <map>
00052 #endif
00053 
00054 //#define QT_CHECK_MAP_RANGE
00055 
00056 struct Q_EXPORT QMapNodeBase
00057 {
00058     enum Color { Red, Black };
00059 
00060     QMapNodeBase* left;
00061     QMapNodeBase* right;
00062     QMapNodeBase* parent;
00063 
00064     Color color;
00065 
00066     QMapNodeBase* minimum() {
00067         QMapNodeBase* x = this;
00068         while ( x->left )
00069             x = x->left;
00070         return x;
00071     }
00072 
00073     QMapNodeBase* maximum() {
00074         QMapNodeBase* x = this;
00075         while ( x->right )
00076             x = x->right;
00077         return x;
00078     }
00079 };
00080 
00081 
00082 template <class K, class T>
00083 struct QMapNode : public QMapNodeBase
00084 {
00085     QMapNode( const K& _key, const T& _data ) { data = _data; key = _key; }
00086     QMapNode( const K& _key )      { key = _key; }
00087     QMapNode( const QMapNode<K,T>& _n ) { key = _n.key; data = _n.data; }
00088     QMapNode() { }
00089     T data;
00090     K key;
00091 };
00092 
00093 
00094 template<class K, class T>
00095 class QMapIterator
00096 {
00097  public:
00101     typedef QMapNode< K, T >* NodePtr;
00102 #ifndef QT_NO_STL
00103     typedef std::bidirectional_iterator_tag  iterator_category;
00104 #endif
00105     typedef T          value_type;
00106 #ifndef QT_NO_STL
00107     typedef ptrdiff_t  difference_type;
00108 #else
00109     typedef int difference_type;
00110 #endif
00111     typedef T*         pointer;
00112     typedef T&         reference;
00113 
00117     QMapNode<K,T>* node;
00118 
00122     QMapIterator() : node( 0 ) {}
00123     QMapIterator( QMapNode<K,T>* p ) : node( p ) {}
00124     QMapIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}
00125 
00126     bool operator==( const QMapIterator<K,T>& it ) const { return node == it.node; }
00127     bool operator!=( const QMapIterator<K,T>& it ) const { return node != it.node; }
00128     T& operator*() { return node->data; }
00129     const T& operator*() const { return node->data; }
00130     // UDT for T = x*
00131     // T* operator->() const { return &node->data; }
00132 
00133     const K& key() const { return node->key; }
00134     T& data() { return node->data; }
00135     const T& data() const { return node->data; }
00136 
00137 private:
00138     int inc();
00139     int dec();
00140 
00141 public:
00142     QMapIterator<K,T>& operator++() {
00143         inc();
00144         return *this;
00145     }
00146 
00147     QMapIterator<K,T> operator++(int) {
00148         QMapIterator<K,T> tmp = *this;
00149         inc();
00150         return tmp;
00151     }
00152 
00153     QMapIterator<K,T>& operator--() {
00154         dec();
00155         return *this;
00156     }
00157 
00158     QMapIterator<K,T> operator--(int) {
00159         QMapIterator<K,T> tmp = *this;
00160         dec();
00161         return tmp;
00162     }
00163 };
00164 
00165 template <class K, class T>
00166 Q_INLINE_TEMPLATES int QMapIterator<K,T>::inc()
00167 {
00168     QMapNodeBase* tmp = node;
00169     if ( tmp->right ) {
00170         tmp = tmp->right;
00171         while ( tmp->left )
00172             tmp = tmp->left;
00173     } else {
00174         QMapNodeBase* y = tmp->parent;
00175         while (tmp == y->right) {
00176             tmp = y;
00177             y = y->parent;
00178         }
00179         if (tmp->right != y)
00180             tmp = y;
00181     }
00182     node = (NodePtr)tmp;
00183     return 0;
00184 }
00185 
00186 template <class K, class T>
00187 Q_INLINE_TEMPLATES int QMapIterator<K,T>::dec()
00188 {
00189     QMapNodeBase* tmp = node;
00190     if (tmp->color == QMapNodeBase::Red &&
00191         tmp->parent->parent == tmp ) {
00192         tmp = tmp->right;
00193     } else if (tmp->left != 0) {
00194         QMapNodeBase* y = tmp->left;
00195         while ( y->right )
00196             y = y->right;
00197         tmp = y;
00198     } else {
00199         QMapNodeBase* y = tmp->parent;
00200         while (tmp == y->left) {
00201             tmp = y;
00202             y = y->parent;
00203         }
00204         tmp = y;
00205     }
00206     node = (NodePtr)tmp;
00207     return 0;
00208 }
00209 
00210 template<class K, class T>
00211 class QMapConstIterator
00212 {
00213  public:
00217     typedef QMapNode< K, T >* NodePtr;
00218 #ifndef QT_NO_STL
00219     typedef std::bidirectional_iterator_tag  iterator_category;
00220 #endif
00221     typedef T          value_type;
00222 #ifndef QT_NO_STL
00223     typedef ptrdiff_t  difference_type;
00224 #else
00225     typedef int difference_type;
00226 #endif
00227     typedef const T*   pointer;
00228     typedef const T&   reference;
00229 
00230 
00234     QMapNode<K,T>* node;
00235 
00239     QMapConstIterator() : node( 0 ) {}
00240     QMapConstIterator( QMapNode<K,T>* p ) : node( p ) {}
00241     QMapConstIterator( const QMapConstIterator<K,T>& it ) : node( it.node ) {}
00242     QMapConstIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}
00243 
00244     bool operator==( const QMapConstIterator<K,T>& it ) const { return node == it.node; }
00245     bool operator!=( const QMapConstIterator<K,T>& it ) const { return node != it.node; }
00246     const T& operator*()  const { return node->data; }
00247     // UDT for T = x*
00248     // const T* operator->() const { return &node->data; }
00249 
00250     const K& key() const { return node->key; }
00251     const T& data() const { return node->data; }
00252 
00253 private:
00254     int inc();
00255     int dec();
00256 
00257 public:
00258     QMapConstIterator<K,T>& operator++() {
00259         inc();
00260         return *this;
00261     }
00262 
00263     QMapConstIterator<K,T> operator++(int) {
00264         QMapConstIterator<K,T> tmp = *this;
00265         inc();
00266         return tmp;
00267     }
00268 
00269     QMapConstIterator<K,T>& operator--() {
00270         dec();
00271         return *this;
00272     }
00273 
00274     QMapConstIterator<K,T> operator--(int) {
00275         QMapConstIterator<K,T> tmp = *this;
00276         dec();
00277         return tmp;
00278     }
00279 };
00280 
00281 template <class K, class T>
00282 Q_INLINE_TEMPLATES int QMapConstIterator<K,T>::inc()
00283 {
00284     QMapNodeBase* tmp = node;
00285     if ( tmp->right ) {
00286         tmp = tmp->right;
00287         while ( tmp->left )
00288             tmp = tmp->left;
00289     } else {
00290         QMapNodeBase* y = tmp->parent;
00291         while (tmp == y->right) {
00292             tmp = y;
00293             y = y->parent;
00294         }
00295         if (tmp->right != y)
00296             tmp = y;
00297     }
00298     node = (NodePtr)tmp;
00299     return 0;
00300 }
00301 
00302 template <class K, class T>
00303 Q_INLINE_TEMPLATES int QMapConstIterator<K,T>::dec()
00304 {
00305     QMapNodeBase* tmp = node;
00306     if (tmp->color == QMapNodeBase::Red &&
00307         tmp->parent->parent == tmp ) {
00308         tmp = tmp->right;
00309     } else if (tmp->left != 0) {
00310         QMapNodeBase* y = tmp->left;
00311         while ( y->right )
00312             y = y->right;
00313         tmp = y;
00314     } else {
00315         QMapNodeBase* y = tmp->parent;
00316         while (tmp == y->left) {
00317             tmp = y;
00318             y = y->parent;
00319         }
00320         tmp = y;
00321     }
00322     node = (NodePtr)tmp;
00323     return 0;
00324 }
00325 
00326 // ### 4.0: rename to something without Private in it. Not really internal.
00327 class Q_EXPORT QMapPrivateBase : public QShared
00328 {
00329 public:
00330     QMapPrivateBase() {
00331         node_count = 0;
00332     }
00333     QMapPrivateBase( const QMapPrivateBase* _map) {
00334         node_count = _map->node_count;
00335     }
00336 
00340     void rotateLeft( QMapNodeBase* x, QMapNodeBase*& root);
00341     void rotateRight( QMapNodeBase* x, QMapNodeBase*& root );
00342     void rebalance( QMapNodeBase* x, QMapNodeBase*& root );
00343     QMapNodeBase* removeAndRebalance( QMapNodeBase* z, QMapNodeBase*& root,
00344                                       QMapNodeBase*& leftmost,
00345                                       QMapNodeBase*& rightmost );
00346 
00350     int node_count;
00351 };
00352 
00353 
00354 template <class Key, class T>
00355 class QMapPrivate : public QMapPrivateBase
00356 {
00357 public:
00361     typedef QMapIterator< Key, T > Iterator;
00362     typedef QMapConstIterator< Key, T > ConstIterator;
00363     typedef QMapNode< Key, T > Node;
00364     typedef QMapNode< Key, T >* NodePtr;
00365 
00369     QMapPrivate();
00370     QMapPrivate( const QMapPrivate< Key, T >* _map );
00371     ~QMapPrivate() { clear(); delete header; }
00372 
00373     NodePtr copy( NodePtr p );
00374     void clear();
00375     void clear( NodePtr p );
00376 
00377     Iterator begin()    { return Iterator( (NodePtr)(header->left ) ); }
00378     Iterator end()      { return Iterator( header ); }
00379     ConstIterator begin() const { return ConstIterator( (NodePtr)(header->left ) ); }
00380     ConstIterator end() const { return ConstIterator( header ); }
00381 
00382     ConstIterator find(const Key& k) const;
00383 
00384     void remove( Iterator it ) {
00385         NodePtr del = (NodePtr) removeAndRebalance( it.node, header->parent, header->left, header->right );
00386         delete del;
00387         --node_count;
00388     }
00389 
00390 #ifdef QT_QMAP_DEBUG
00391     void inorder( QMapNodeBase* x = 0, int level = 0 ){
00392         if ( !x )
00393             x = header->parent;
00394         if ( x->left )
00395             inorder( x->left, level + 1 );
00396     //cout << level << " Key=" << key(x) << " Value=" << ((NodePtr)x)->data << endl;
00397         if ( x->right )
00398             inorder( x->right, level + 1 );
00399     }
00400 #endif
00401 
00402 #if 0
00403     Iterator insertMulti(const Key& v){
00404         QMapNodeBase* y = header;
00405         QMapNodeBase* x = header->parent;
00406         while (x != 0){
00407             y = x;
00408             x = ( v < key(x) ) ? x->left : x->right;
00409         }
00410         return insert(x, y, v);
00411     }
00412 #endif
00413 
00414     Iterator insertSingle( const Key& k );
00415     Iterator insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k );
00416 
00417 protected:
00421     const Key& key( QMapNodeBase* b ) const { return ((NodePtr)b)->key; }
00422 
00426     NodePtr header;
00427 };
00428 
00429 
00430 template <class Key, class T>
00431 Q_INLINE_TEMPLATES QMapPrivate<Key,T>::QMapPrivate() {
00432     header = new Node;
00433     header->color = QMapNodeBase::Red; // Mark the header
00434     header->parent = 0;
00435     header->left = header->right = header;
00436 }
00437 template <class Key, class T>
00438 Q_INLINE_TEMPLATES QMapPrivate<Key,T>::QMapPrivate( const QMapPrivate< Key, T >* _map ) : QMapPrivateBase( _map ) {
00439     header = new Node;
00440     header->color = QMapNodeBase::Red; // Mark the header
00441     if ( _map->header->parent == 0 ) {
00442         header->parent = 0;
00443         header->left = header->right = header;
00444     } else {
00445         header->parent = copy( (NodePtr)(_map->header->parent) );
00446         header->parent->parent = header;
00447         header->left = header->parent->minimum();
00448         header->right = header->parent->maximum();
00449     }
00450 }
00451 
00452 template <class Key, class T>
00453 Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::NodePtr QMapPrivate<Key,T>::copy( Q_TYPENAME QMapPrivate<Key,T>::NodePtr p )
00454 {
00455     if ( !p )
00456         return 0;
00457     NodePtr n = new Node( *p );
00458     n->color = p->color;
00459     if ( p->left ) {
00460         n->left = copy( (NodePtr)(p->left) );
00461         n->left->parent = n;
00462     } else {
00463         n->left = 0;
00464     }
00465     if ( p->right ) {
00466         n->right = copy( (NodePtr)(p->right) );
00467         n->right->parent = n;
00468     } else {
00469         n->right = 0;
00470     }
00471     return n;
00472 }
00473 
00474 template <class Key, class T>
00475 Q_INLINE_TEMPLATES void QMapPrivate<Key,T>::clear()
00476 {
00477     clear( (NodePtr)(header->parent) );
00478     header->color = QMapNodeBase::Red;
00479     header->parent = 0;
00480     header->left = header->right = header;
00481     node_count = 0;
00482 }
00483 
00484 template <class Key, class T>
00485 Q_INLINE_TEMPLATES void QMapPrivate<Key,T>::clear( Q_TYPENAME QMapPrivate<Key,T>::NodePtr p )
00486 {
00487     while ( p != 0 ) {
00488         clear( (NodePtr)p->right );
00489         NodePtr y = (NodePtr)p->left;
00490         delete p;
00491         p = y;
00492     }
00493 }
00494 
00495 template <class Key, class T>
00496 Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::ConstIterator QMapPrivate<Key,T>::find(const Key& k) const
00497 {
00498     QMapNodeBase* y = header;        // Last node
00499     QMapNodeBase* x = header->parent; // Root node.
00500 
00501     while ( x != 0 ) {
00502         // If as k <= key(x) go left
00503         if ( !( key(x) < k ) ) {
00504             y = x;
00505             x = x->left;
00506         } else {
00507             x = x->right;
00508         }
00509     }
00510 
00511     // Was k bigger/smaller then the biggest/smallest
00512     // element of the tree ? Return end()
00513     if ( y == header || k < key(y) )
00514         return ConstIterator( header );
00515     return ConstIterator( (NodePtr)y );
00516 }
00517 
00518 template <class Key, class T>
00519 Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::Iterator QMapPrivate<Key,T>::insertSingle( const Key& k )
00520 {
00521     // Search correct position in the tree
00522     QMapNodeBase* y = header;
00523     QMapNodeBase* x = header->parent;
00524     bool result = TRUE;
00525     while ( x != 0 ) {
00526         result = ( k < key(x) );
00527         y = x;
00528         x = result ? x->left : x->right;
00529     }
00530     // Get iterator on the last not empty one
00531     Iterator j( (NodePtr)y );
00532     if ( result ) {
00533         // Smaller then the leftmost one ?
00534         if ( j == begin() ) {
00535             return insert(x, y, k );
00536         } else {
00537             // Perhaps daddy is the right one ?
00538             --j;
00539         }
00540     }
00541     // Really bigger ?
00542     if ( (j.node->key) < k )
00543         return insert(x, y, k );
00544     // We are going to replace a node
00545     return j;
00546 }
00547 
00548 
00549 template <class Key, class T>
00550 Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::Iterator QMapPrivate<Key,T>::insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k )
00551 {
00552     NodePtr z = new Node( k );
00553     if (y == header || x != 0 || k < key(y) ) {
00554         y->left = z;                // also makes leftmost = z when y == header
00555         if ( y == header ) {
00556             header->parent = z;
00557             header->right = z;
00558         } else if ( y == header->left )
00559             header->left = z;           // maintain leftmost pointing to min node
00560     } else {
00561         y->right = z;
00562         if ( y == header->right )
00563             header->right = z;          // maintain rightmost pointing to max node
00564     }
00565     z->parent = y;
00566     z->left = 0;
00567     z->right = 0;
00568     rebalance( z, header->parent );
00569     ++node_count;
00570     return Iterator(z);
00571 }
00572 
00573 
00574 #ifdef QT_CHECK_RANGE
00575 # if !defined( QT_NO_DEBUG ) && defined( QT_CHECK_MAP_RANGE )
00576 #  define QT_CHECK_INVALID_MAP_ELEMENT if ( empty() ) qWarning( "QMap: Warning invalid element" )
00577 #  define QT_CHECK_INVALID_MAP_ELEMENT_FATAL Q_ASSERT( !empty() );
00578 # else
00579 #  define QT_CHECK_INVALID_MAP_ELEMENT
00580 #  define QT_CHECK_INVALID_MAP_ELEMENT_FATAL
00581 # endif
00582 #else
00583 # define QT_CHECK_INVALID_MAP_ELEMENT
00584 # define QT_CHECK_INVALID_MAP_ELEMENT_FATAL
00585 #endif
00586 
00587 template <class T> class QDeepCopy;
00588 
00589 template<class Key, class T>
00590 class QMap
00591 {
00592 public:
00596     typedef Key key_type;
00597     typedef T mapped_type;
00598     typedef QPair<const key_type, mapped_type> value_type;
00599     typedef value_type* pointer;
00600     typedef const value_type* const_pointer;
00601     typedef value_type& reference;
00602     typedef const value_type& const_reference;
00603 #ifndef QT_NO_STL
00604     typedef ptrdiff_t  difference_type;
00605 #else
00606     typedef int difference_type;
00607 #endif
00608     typedef size_t      size_type;
00609     typedef QMapIterator<Key,T> iterator;
00610     typedef QMapConstIterator<Key,T> const_iterator;
00611     typedef QPair<iterator,bool> insert_pair;
00612 
00613     typedef QMapIterator< Key, T > Iterator;
00614     typedef QMapConstIterator< Key, T > ConstIterator;
00615     typedef T ValueType;
00616     typedef QMapPrivate< Key, T > Priv;
00617 
00621     QMap()
00622     {
00623         sh = new QMapPrivate< Key, T >;
00624     }
00625     QMap( const QMap<Key,T>& m )
00626     {
00627         sh = m.sh; sh->ref();
00628     }
00629 
00630 #ifndef QT_NO_STL
00631     QMap( const std::map<Key,T>& m )
00632     {
00633         sh = new QMapPrivate<Key,T>;
00634         Q_TYPENAME std::map<Key,T>::const_iterator it = m.begin();
00635         for ( ; it != m.end(); ++it ) {
00636             value_type p( (*it).first, (*it).second );
00637             insert( p );
00638         }
00639     }
00640 #endif
00641     ~QMap()
00642     {
00643         if ( sh->deref() )
00644             delete sh;
00645     }
00646     QMap<Key,T>& operator= ( const QMap<Key,T>& m );
00647 #ifndef QT_NO_STL
00648     QMap<Key,T>& operator= ( const std::map<Key,T>& m )
00649     {
00650         clear();
00651         Q_TYPENAME std::map<Key,T>::const_iterator it = m.begin();
00652         for ( ; it != m.end(); ++it ) {
00653             value_type p( (*it).first, (*it).second );
00654             insert( p );
00655         }
00656         return *this;
00657     }
00658 #endif
00659 
00660     iterator begin() { detach(); return sh->begin(); }
00661     iterator end() { detach(); return sh->end(); }
00662     const_iterator begin() const { return ((const Priv*)sh)->begin(); }
00663     const_iterator end() const { return ((const Priv*)sh)->end(); }
00664     const_iterator constBegin() const { return begin(); }
00665     const_iterator constEnd() const { return end(); }
00666 
00667     iterator replace( const Key& k, const T& v )
00668     {
00669         remove( k );
00670         return insert( k, v );
00671     }
00672 
00673     size_type size() const
00674     {
00675         return sh->node_count;
00676     }
00677     bool empty() const
00678     {
00679         return sh->node_count == 0;
00680     }
00681     QPair<iterator,bool> insert( const value_type& x );
00682 
00683     void erase( iterator it )
00684     {
00685         detach();
00686         sh->remove( it );
00687     }
00688     void erase( const key_type& k );
00689     size_type count( const key_type& k ) const;
00690     T& operator[] ( const Key& k );
00691     void clear();
00692 
00693     iterator find ( const Key& k )
00694     {
00695         detach();
00696         return iterator( sh->find( k ).node );
00697     }
00698     const_iterator find ( const Key& k ) const {        return sh->find( k ); }
00699 
00700     const T& operator[] ( const Key& k ) const
00701         { QT_CHECK_INVALID_MAP_ELEMENT; return sh->find( k ).data(); }
00702     bool contains ( const Key& k ) const
00703         { return find( k ) != end(); }
00704         //{ return sh->find( k ) != ((const Priv*)sh)->end(); }
00705 
00706     size_type count() const { return sh->node_count; }
00707 
00708     QValueList<Key> keys() const {
00709         QValueList<Key> r;
00710         for (const_iterator i=begin(); i!=end(); ++i)
00711             r.append(i.key());
00712         return r;
00713     }
00714 
00715     QValueList<T> values() const {
00716         QValueList<T> r;
00717         for (const_iterator i=begin(); i!=end(); ++i)
00718             r.append(*i);
00719         return r;
00720     }
00721 
00722     bool isEmpty() const { return sh->node_count == 0; }
00723 
00724     iterator insert( const Key& key, const T& value, bool overwrite = TRUE );
00725     void remove( iterator it ) { detach(); sh->remove( it ); }
00726     void remove( const Key& k );
00727 
00728 #if defined(Q_FULL_TEMPLATE_INSTANTIATION)
00729     bool operator==( const QMap<Key,T>& ) const { return FALSE; }
00730 #ifndef QT_NO_STL
00731     bool operator==( const std::map<Key,T>& ) const { return FALSE; }
00732 #endif
00733 #endif
00734 
00735 protected:
00739     void detach() {  if ( sh->count > 1 ) detachInternal(); }
00740 
00741     Priv* sh;
00742 private:
00743     void detachInternal();
00744 
00745     friend class QDeepCopy< QMap<Key,T> >;
00746 };
00747 
00748 template<class Key, class T>
00749 Q_INLINE_TEMPLATES QMap<Key,T>& QMap<Key,T>::operator= ( const QMap<Key,T>& m )
00750 {
00751     m.sh->ref();
00752     if ( sh->deref() )
00753         delete sh;
00754     sh = m.sh;
00755     return *this;
00756 }
00757 
00758 template<class Key, class T>
00759 Q_INLINE_TEMPLATES Q_TYPENAME QMap<Key,T>::insert_pair QMap<Key,T>::insert( const Q_TYPENAME QMap<Key,T>::value_type& x )
00760 {
00761     detach();
00762     size_type n = size();
00763     iterator it = sh->insertSingle( x.first );
00764     bool inserted = FALSE;
00765     if ( n < size() ) {
00766         inserted = TRUE;
00767         it.data() = x.second;
00768     }
00769     return QPair<iterator,bool>( it, inserted );
00770 }
00771 
00772 template<class Key, class T>
00773 Q_INLINE_TEMPLATES void QMap<Key,T>::erase( const Key& k )
00774 {
00775     detach();
00776     iterator it( sh->find( k ).node );
00777     if ( it != end() )
00778         sh->remove( it );
00779 }
00780 
00781 template<class Key, class T>
00782 Q_INLINE_TEMPLATES Q_TYPENAME QMap<Key,T>::size_type QMap<Key,T>::count( const Key& k ) const
00783 {
00784     const_iterator it( sh->find( k ).node );
00785     if ( it != end() ) {
00786         size_type c = 0;
00787         while ( it != end() ) {
00788             ++it;
00789             ++c;
00790         }
00791         return c;
00792     }
00793     return 0;
00794 }
00795 
00796 template<class Key, class T>
00797 Q_INLINE_TEMPLATES T& QMap<Key,T>::operator[] ( const Key& k )
00798 {
00799     detach();
00800     QMapNode<Key,T>* p = sh->find( k ).node;
00801     if ( p != sh->end().node )
00802         return p->data;
00803     return insert( k, T() ).data();
00804 }
00805 
00806 template<class Key, class T>
00807 Q_INLINE_TEMPLATES void QMap<Key,T>::clear()
00808 {
00809     if ( sh->count == 1 )
00810         sh->clear();
00811     else {
00812         sh->deref();
00813         sh = new QMapPrivate<Key,T>;
00814     }
00815 }
00816 
00817 template<class Key, class T>
00818 Q_INLINE_TEMPLATES Q_TYPENAME QMap<Key,T>::iterator QMap<Key,T>::insert( const Key& key, const T& value, bool overwrite )
00819 {
00820     detach();
00821     size_type n = size();
00822     iterator it = sh->insertSingle( key );
00823     if ( overwrite || n < size() )
00824         it.data() = value;
00825     return it;
00826 }
00827 
00828 template<class Key, class T>
00829 Q_INLINE_TEMPLATES void QMap<Key,T>::remove( const Key& k )
00830 {
00831     detach();
00832     iterator it( sh->find( k ).node );
00833     if ( it != end() )
00834         sh->remove( it );
00835 }
00836 
00837 template<class Key, class T>
00838 Q_INLINE_TEMPLATES void QMap<Key,T>::detachInternal()
00839 {
00840     sh->deref(); sh = new QMapPrivate<Key,T>( sh );
00841 }
00842 
00843 
00844 #ifndef QT_NO_DATASTREAM
00845 template<class Key, class T>
00846 Q_INLINE_TEMPLATES QDataStream& operator>>( QDataStream& s, QMap<Key,T>& m ) {
00847     m.clear();
00848     Q_UINT32 c;
00849     s >> c;
00850     for( Q_UINT32 i = 0; i < c; ++i ) {
00851         Key k; T t;
00852         s >> k >> t;
00853         m.insert( k, t );
00854         if ( s.atEnd() )
00855             break;
00856     }
00857     return s;
00858 }
00859 
00860 
00861 template<class Key, class T>
00862 Q_INLINE_TEMPLATES QDataStream& operator<<( QDataStream& s, const QMap<Key,T>& m ) {
00863     s << (Q_UINT32)m.size();
00864     QMapConstIterator<Key,T> it = m.begin();
00865     for( ; it != m.end(); ++it )
00866         s << it.key() << it.data();
00867     return s;
00868 }
00869 #endif
00870 
00871 #define Q_DEFINED_QMAP
00872 #include "qwinexport.h"
00873 #endif // QMAP_H
 Todo Clases Namespaces Archivos Funciones Variables 'typedefs' Enumeraciones Valores de enumeraciones Propiedades Amigas 'defines'