qtools/qmap.h

   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