1 /****************************************************************************

     2 ** 

     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 #endif // QT_H

    45 

    46 

    47 struct QMapNodeBase

    48 {

    49     enum Color { Red, Black };

    50 

    51     QMapNodeBase* left;

    52     QMapNodeBase* right;

    53     QMapNodeBase* parent;

    54 

    55     Color color;

    56 

    57     QMapNodeBase* minimum() {

    58 	QMapNodeBase* x = this;

    59 	while ( x->left )

    60 	    x = x->left;

    61 	return x;

    62     }

    63 

    64     QMapNodeBase* maximum() {

    65 	QMapNodeBase* x = this;

    66 	while ( x->right )

    67 	    x = x->right;

    68 	return x;

    69     }

    70 };

    71 

    72 

    73 template <class K, class T>

    74 struct QMapNode : public QMapNodeBase

    75 {

    76     QMapNode( const K& _key, const T& _data ) { data = _data; key = _key; }

    77     QMapNode( const K& _key )	   { key = _key; }

    78     QMapNode( const QMapNode<K,T>& _n ) { key = _n.key; data = _n.data; }

    79     QMapNode() { }

    80     T data;

    81     K key;

    82 };

    83 

    84 

    85 template<class K, class T>

    86 class Q_EXPORT QMapIterator

    87 {

    88  public:

    89     /**

    90      * Typedefs

    91      */

    92     typedef QMapNode< K, T >* NodePtr;

    93 

    94     /**

    95      * Variables

    96      */

    97     QMapNode<K,T>* node;

    98 

    99     /**

   100      * Functions

   101      */

   102     QMapIterator() : node( 0 ) {}

   103     QMapIterator( QMapNode<K,T>* p ) : node( p ) {}

   104     QMapIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}

   105 

   106     bool operator==( const QMapIterator<K,T>& it ) const { return node == it.node; }

   107     bool operator!=( const QMapIterator<K,T>& it ) const { return node != it.node; }

   108     T& operator*() { return node->data; }

   109     const T& operator*() const { return node->data; }

   110 

   111     // Cannot have this - some compilers are too stupid

   112     //T* operator->() const { return &(node->data); }

   113 

   114     const K& key() const { return node->key; }

   115     T& data() { return node->data; }

   116     const T& data() const { return node->data; }

   117 

   118 private:

   119     int inc() {

   120 	QMapNodeBase* tmp = node;

   121 	if ( tmp->right ) {

   122 	    tmp = tmp->right;

   123 	    while ( tmp->left )

   124 		tmp = tmp->left;

   125 	} else {

   126 	    QMapNodeBase* y = tmp->parent;

   127 	    while (tmp == y->right) {

   128 		tmp = y;

   129 		y = y->parent;

   130 	    }

   131 	    if (tmp->right != y)

   132 		tmp = y;

   133 	}

   134 	node = (NodePtr)tmp;

   135 	return 0;

   136     }

   137 

   138     int dec() {

   139 	QMapNodeBase* tmp = node;

   140 	if (tmp->color == QMapNodeBase::Red &&

   141 	    tmp->parent->parent == tmp ) {

   142 	    tmp = tmp->right;

   143 	} else if (tmp->left != 0) {

   144 	    QMapNodeBase* y = tmp->left;

   145 	    while ( y->right )

   146 		y = y->right;

   147 	    tmp = y;

   148 	} else {

   149 	    QMapNodeBase* y = tmp->parent;

   150 	    while (tmp == y->left) {

   151 		tmp = y;

   152 		y = y->parent;

   153 	    }

   154 	    tmp = y;

   155 	}

   156 	node = (NodePtr)tmp;

   157 	return 0;

   158     }

   159 

   160 public:

   161     QMapIterator<K,T>& operator++() {

   162 	inc();

   163 	return *this;

   164     }

   165 

   166     QMapIterator<K,T> operator++(int) {

   167 	QMapIterator<K,T> tmp = *this;

   168 	inc();

   169 	return tmp;

   170     }

   171 

   172     QMapIterator<K,T>& operator--() {

   173 	dec();

   174 	return *this;

   175     }

   176 

   177     QMapIterator<K,T> operator--(int) {

   178 	QMapIterator<K,T> tmp = *this;

   179 	dec();

   180 	return tmp;

   181     }

   182 };

   183 

   184 template<class K, class T>

   185 class Q_EXPORT QMapConstIterator

   186 {

   187  public:

   188     /**

   189      * Typedefs

   190      */

   191     typedef QMapNode< K, T >* NodePtr;

   192 

   193     /**

   194      * Variables

   195      */

   196     QMapNode<K,T>* node;

   197 

   198     /**

   199      * Functions

   200      */

   201     QMapConstIterator() : node( 0 ) {}

   202     QMapConstIterator( QMapNode<K,T>* p ) : node( p ) {}

   203     QMapConstIterator( const QMapConstIterator<K,T>& it ) : node( it.node ) {}

   204     QMapConstIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}

   205 

   206     bool operator==( const QMapConstIterator<K,T>& it ) const { return node == it.node; }

   207     bool operator!=( const QMapConstIterator<K,T>& it ) const { return node != it.node; }

   208     const T& operator*()  const { return node->data; }

   209 

   210     // Cannot have this - some compilers are too stupid

   211     //const T* operator->() const { return &(node->data); }

   212 

   213     const K& key() const { return node->key; }

   214     const T& data() const { return node->data; }

   215 

   216 private:

   217     int inc() {

   218         QMapNodeBase* tmp = node;

   219 	if ( tmp->right ) {

   220 	    tmp = tmp->right;

   221 	    while ( tmp->left )

   222 		tmp = tmp->left;

   223 	} else {

   224 	    QMapNodeBase* y = tmp->parent;

   225 	    while (tmp == y->right) {

   226 		tmp = y;

   227 		y = y->parent;

   228 	    }

   229 	    if (tmp->right != y)

   230 		tmp = y;

   231 	}

   232 	node = (NodePtr)tmp;

   233 	return 0;

   234     }

   235 

   236     int dec() {

   237 	QMapNodeBase* tmp = node;

   238 	if (tmp->color == QMapNodeBase::Red &&

   239 	    tmp->parent->parent == tmp ) {

   240 	    tmp = tmp->right;

   241 	} else if (tmp->left != 0) {

   242 	    QMapNodeBase* y = tmp->left;

   243 	    while ( y->right )

   244 		y = y->right;

   245 	    tmp = y;

   246 	} else {

   247 	    QMapNodeBase* y = tmp->parent;

   248 	    while (tmp == y->left) {

   249 		tmp = y;

   250 		y = y->parent;

   251 	    }

   252 	    tmp = y;

   253 	}

   254 	node = (NodePtr)tmp;

   255 	return 0;

   256     }

   257 

   258 public:

   259     QMapConstIterator<K,T>& operator++() {

   260 	inc();

   261 	return *this;

   262     }

   263 

   264     QMapConstIterator<K,T> operator++(int) {

   265 	QMapConstIterator<K,T> tmp = *this;

   266 	inc();

   267 	return tmp;

   268     }

   269 

   270     QMapConstIterator<K,T>& operator--() {

   271 	dec();

   272 	return *this;

   273     }

   274 

   275     QMapConstIterator<K,T> operator--(int) {

   276 	QMapConstIterator<K,T> tmp = *this;

   277 	dec();

   278 	return tmp;

   279     }

   280 };

   281 

   282 

   283 class Q_EXPORT QMapPrivateBase : public QShared

   284 {

   285 public:

   286     QMapPrivateBase() {

   287 	node_count = 0;

   288     }

   289     QMapPrivateBase( const QMapPrivateBase* _map) {

   290 	node_count = _map->node_count;

   291     }

   292 

   293     /**

   294      * Implementations of basic tree algorithms

   295      */

   296     void rotateLeft( QMapNodeBase* x, QMapNodeBase*& root);

   297     void rotateRight( QMapNodeBase* x, QMapNodeBase*& root );

   298     void rebalance( QMapNodeBase* x, QMapNodeBase*& root );

   299     QMapNodeBase* removeAndRebalance( QMapNodeBase* z, QMapNodeBase*& root,

   300 				      QMapNodeBase*& leftmost,

   301 				      QMapNodeBase*& rightmost );

   302 

   303     /**

   304      * Variables

   305      */

   306     int node_count;

   307 };

   308 

   309 

   310 template <class Key, class T>

   311 class QMapPrivate : public QMapPrivateBase

   312 {

   313 public:

   314     /**

   315      * Typedefs

   316      */

   317     typedef QMapIterator< Key, T > Iterator;

   318     typedef QMapConstIterator< Key, T > ConstIterator;

   319     typedef QMapNode< Key, T > Node;

   320     typedef QMapNode< Key, T >* NodePtr;

   321 

   322     /**

   323      * Functions

   324      */

   325     QMapPrivate() {

   326 	header = new Node;

   327 	header->color = QMapNodeBase::Red; // Mark the header

   328 	header->parent = 0;

   329 	header->left = header->right = header;

   330     }

   331     QMapPrivate( const QMapPrivate< Key, T >* _map ) : QMapPrivateBase( _map ) {

   332 	header = new Node;

   333 	header->color = QMapNodeBase::Red; // Mark the header

   334 	if ( _map->header->parent == 0 ) {

   335 	    header->parent = 0;

   336 	    header->left = header->right = header;

   337 	} else {

   338 	    header->parent = copy( (NodePtr)(_map->header->parent) );

   339 	    header->parent->parent = header;

   340 	    header->left = header->parent->minimum();

   341 	    header->right = header->parent->maximum();

   342 	}

   343     }

   344     ~QMapPrivate() { clear(); delete header; }

   345 

   346     NodePtr copy( NodePtr p ) {

   347 	if ( !p )

   348 	    return 0;

   349 	NodePtr n = new Node( *p );

   350 	n->color = p->color;

   351 	if ( p->left ) {

   352 	    n->left = copy( (NodePtr)(p->left) );

   353 	    n->left->parent = n;

   354 	} else {

   355 	    n->left = 0;

   356 	}

   357 	if ( p->right ) {

   358 	    n->right = copy( (NodePtr)(p->right) );

   359 	    n->right->parent = n;

   360 	} else {

   361 	    n->right = 0;

   362 	}

   363 	return n;

   364     }

   365 

   366     void clear() {

   367 	clear( (NodePtr)(header->parent) );

   368 	header->color = QMapNodeBase::Red;

   369 	header->parent = 0;

   370 	header->left = header->right = header;

   371 	node_count = 0;

   372     }

   373 

   374     void clear( NodePtr p ) {

   375 	while ( p != 0 ) {

   376 	    clear( (NodePtr)p->right );

   377 	    NodePtr y = (NodePtr)p->left;

   378 	    delete p;

   379 	    p = y;

   380 	}

   381     }

   382 

   383     Iterator begin()	{ return Iterator( (NodePtr)(header->left ) ); }

   384     Iterator end()	{ return Iterator( header ); }

   385     ConstIterator begin() const { return ConstIterator( (NodePtr)(header->left ) ); }

   386     ConstIterator end() const { return ConstIterator( header ); }

   387 

   388     ConstIterator find(const Key& k) const {

   389 	QMapNodeBase* y = header;        // Last node

   390 	QMapNodeBase* x = header->parent; // Root node.

   391 

   392 	while ( x != 0 ) {

   393 	    // If as k <= key(x) go left

   394 	    if ( !( key(x) < k ) ) {

   395 		y = x;

   396 		x = x->left;

   397 	    } else {

   398 		x = x->right;

   399 	    }

   400 	}

   401 

   402 	// Was k bigger/smaller then the biggest/smallest

   403 	// element of the tree ? Return end()

   404 	if ( y == header || k < key(y) )

   405 	    return ConstIterator( header );

   406 	return ConstIterator( (NodePtr)y );

   407     }

   408 

   409     void remove( Iterator it ) {

   410 	NodePtr del = (NodePtr) removeAndRebalance( it.node, header->parent, header->left, header->right );

   411 	delete del;

   412 	--node_count;

   413     }

   414 

   415 #ifdef QT_QMAP_DEBUG

   416     void inorder( QMapNodeBase* x = 0, int level = 0 ){

   417 	if ( !x )

   418 	    x = header->parent;

   419 	if ( x->left )

   420 	    inorder( x->left, level + 1 );

   421     //cout << level << " Key=" << key(x) << " Value=" << ((NodePtr)x)->data << endl;

   422 	if ( x->right )

   423 	    inorder( x->right, level + 1 );

   424     }

   425 #endif

   426 

   427     Iterator insertMulti(const Key& v){

   428 	QMapNodeBase* y = header;

   429 	QMapNodeBase* x = header->parent;

   430 	while (x != 0){

   431 	    y = x;

   432 	    x = ( v < key(x) ) ? x->left : x->right;

   433 	}

   434 	return insert(x, y, v);

   435     }

   436 

   437     Iterator insertSingle( const Key& k ) {

   438 	// Search correct position in the tree

   439 	QMapNodeBase* y = header;

   440 	QMapNodeBase* x = header->parent;

   441 	bool result = TRUE;

   442 	while ( x != 0 ) {

   443 	    result = ( k < key(x) );

   444 	    y = x;

   445 	    x = result ? x->left : x->right;

   446 	}

   447 	// Get iterator on the last not empty one

   448 	Iterator j( (NodePtr)y );

   449 	if ( result ) {

   450 	    // Smaller then the leftmost one ?

   451 	    if ( j == begin() ) {

   452 		return insert(x, y, k );

   453 	    } else {

   454 		// Perhaps daddy is the right one ?

   455 		--j;

   456 	    }

   457 	}

   458 	// Really bigger ?

   459 	if ( (j.node->key) < k )

   460 	    return insert(x, y, k );

   461 	// We are going to replace a node

   462 	return j;

   463     }

   464 

   465     Iterator insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k ) {

   466 	NodePtr z = new Node( k );

   467 	if (y == header || x != 0 || k < key(y) ) {

   468 	    y->left = z;                // also makes leftmost = z when y == header

   469 	    if ( y == header ) {

   470 		header->parent = z;

   471 		header->right = z;

   472 	    } else if ( y == header->left )

   473 		header->left = z;           // maintain leftmost pointing to min node

   474 	} else {

   475 	    y->right = z;

   476 	    if ( y == header->right )

   477 		header->right = z;          // maintain rightmost pointing to max node

   478 	}

   479 	z->parent = y;

   480 	z->left = 0;

   481 	z->right = 0;

   482 	rebalance( z, header->parent );

   483 	++node_count;

   484 	return Iterator(z);

   485     }

   486 

   487 protected:

   488     /**

   489      * Helpers

   490      */

   491     const Key& key( QMapNodeBase* b ) const { return ((NodePtr)b)->key; }

   492 

   493     /**

   494      * Variables

   495      */

   496     NodePtr header;

   497 };

   498 

   499 

   500 template<class Key, class T>

   501 class Q_EXPORT QMap

   502 {

   503 public:

   504     /**

   505      * Typedefs

   506      */

   507     typedef QMapIterator< Key, T > Iterator;

   508     typedef QMapConstIterator< Key, T > ConstIterator;

   509     typedef T ValueType;

   510     typedef QMapPrivate< Key, T > Priv;

   511 

   512     /**

   513      * API

   514      */

   515     QMap() { sh = new QMapPrivate< Key, T >; }

   516     QMap( const QMap<Key,T>& m ) { sh = m.sh; sh->ref(); }

   517     ~QMap() { if ( sh->deref() ) delete sh; }

   518 

   519     QMap<Key,T>& operator= ( const QMap<Key,T>& m )

   520       { m.sh->ref(); if ( sh->deref() ) delete sh; sh = m.sh; return *this; }

   521 

   522     Iterator begin() { detach(); return sh->begin(); }

   523     Iterator end() { detach(); return sh->end(); }

   524     ConstIterator begin() const { return ((const Priv*)sh)->begin(); }

   525     ConstIterator end() const { return ((const Priv*)sh)->end(); }

   526 

   527     Iterator find ( const Key& k )

   528 	{ detach(); return Iterator( sh->find( k ).node ); }

   529     ConstIterator find ( const Key& k ) const

   530 	{ return sh->find( k ); }

   531     T& operator[] ( const Key& k ) {

   532 	detach(); QMapNode<Key,T>* p = sh->find( k ).node;

   533 	if ( p != sh->end().node ) return p->data;

   534 	return insert( k, T() ).data(); }

   535     const T& operator[] ( const Key& k ) const

   536 	{ return sh->find( k ).data(); }

   537     bool contains ( const Key& k ) const

   538 	{ return find( k ) != end(); }

   539 	//{ return sh->find( k ) != ((const Priv*)sh)->end(); }

   540 

   541     uint count() const { return sh->node_count; }

   542 

   543     bool isEmpty() const { return sh->node_count == 0; }

   544 

   545     Iterator insert( const Key& key, const T& value ) {

   546         detach();

   547         Iterator it = sh->insertSingle( key );

   548         it.data() = value;

   549         return it;

   550     }

   551 

   552     void remove( Iterator it ) { detach(); sh->remove( it ); }

   553     void remove( const Key& k ) {

   554         detach();

   555         Iterator it( sh->find( k ).node );

   556         if ( it != end() )

   557             sh->remove( it );

   558     }

   559 

   560     Iterator replace( const Key& k, const T& v ) {

   561 	remove( k );

   562 	return insert( k, v );

   563     }

   564 

   565     void clear() { if ( sh->count == 1 ) sh->clear(); else { sh->deref(); sh = new QMapPrivate<Key,T>; } }

   566 

   567 #if defined(Q_FULL_TEMPLATE_INSTANTIATION)

   568     bool operator==( const QMap<Key,T>& ) const { return FALSE; }

   569 #endif

   570 

   571 protected:

   572     /**

   573      * Helpers

   574      */

   575     void detach() { if ( sh->count > 1 ) { sh->deref(); sh = new QMapPrivate<Key,T>( sh ); } }

   576 

   577     Priv* sh;

   578 };

   579 

   580 

   581 #ifndef QT_NO_DATASTREAM

   582 template<class Key, class T>

   583 inline QDataStream& operator>>( QDataStream& s, QMap<Key,T>& m ) {

   584     m.clear();

   585     Q_UINT32 c;

   586     s >> c;

   587     for( Q_UINT32 i = 0; i < c; ++i ) {

   588 	Key k; T t;

   589 	s >> k >> t;

   590 	m.insert( k, t );

   591     }

   592     return s;

   593 }

   594 

   595 

   596 template<class Key, class T>

   597 inline QDataStream& operator<<( QDataStream& s, const QMap<Key,T>& m ) {

   598     s << (Q_UINT32)m.count();

   599     QMapConstIterator<Key,T> it = m.begin();

   600     for( ; it != m.end(); ++it )

   601 	s << it.key() << it.data();

   602     return s;

   603 }

   604 #endif

   605 

   606 #endif // QMAP_H